Multiobjective Heuristic Search: An Introduction to Intelligent Search Methods for Multicriteria Optimization

ISBN-13: 9783528057084 / Angielski / Miękka / 1999 / 134 str.

Pallab Dasgupta; P. P. Chakrabarti; P. P. Chakrabarti

Opis

A large number of problems require the optimization of multiple criteria. These crite- ria are often non-commensurate and sometimes conflicting in nature making the task of optimization more difficult. In such problems, the task of creating a combined opti- mization function is often not easy. Moreover, the decision procedure can be affected by the sensitivity of the solution space, and the trade-off is often non-linear. In real life we traditionally handle such problems by suggesting not one, but several non-dominated solutions. Finding a set of non-dominated solutions is also useful in multistaged opti- mization problems, where the solution of one stage of optimization is passed on to the next stage. One classic example is that of circuit design, where high-level synthesis, logic synthesis and layout synthesis comprise important stages of optimization of the circuit. Passing a set of non-dominated partial solutions from one stage to the next typically ensures better global optimization. This book presents a new approach to multi-criteria optimization based on heuristic search techniques. Classical multicriteria optimization techniques rely on single criteria optimization algorithms, and hence we are either required to optimize one criterion at a time (under constraints on the others), or we are asked for a single scalar combined optimization function. On the other hand, the multiobjective search approach maps each optimization criterion onto a distinct dimension of a vector valued cost structure.

Spis treści

1 Introduction.- 1.1 Multiobjective Search.- 1.1.1 Contributions.- 1.2 Organization of the book.- 2 The Multiobjective Search Model.- 2.1 Popular Approaches.- 2.2 The multiobjective approach.- 2.3 The Multiobjective Search Problem.- 2.4 Previous Work: Multiobjective A*.- 2.5 Conclusion.- 3 Multiobjective State Space Search.- 3.1 Preliminary notations and definitions.- 3.2 Multidimensional Pathmax.- 3.2.1 The definition of pathmax.- 3.2.2 Two basic properties of pathmax.- 3.2.3 The significance of pathmax.- 3.3 An induced total ordering: K-ordering.- 3.4 The algorithm MOA**.- 3.4.1 The Algorithm Outline.- 3.4.2 Admissibility & Optimality.- 3.5 Memory bounded multiobjective search.- 3.5.1 Cost back-up and K-ordering.- 3.5.2 General philosophy of MOMA*0.- 3.5.3 Algorithm MOMA*0.- 3.5.4 Variants of MOMA*0.- 3.6 Searching with inadmissible heuristics.- 3.7 Extension to graphs.- 3.8 Conclusion.- 4 Applications of Multiobjective Search.- 4.1 The Operator Scheduling Problem.- 4.1.1 Notation & Terminology.- 4.1.2 Algorithm MObj_Schedule.- 4.2 The Channel Routing Problem.- 4.2.1 Notation & Terminology.- 4.2.2 Algorithm MObj_Route.- 4.2.3 Selection of wires for a track.- 4.3 The Log Cutting problem.- 4.4 Evaluation of the Multiobjective Strategies.- 4.4.1 Utility of Pathmax.- 4.4.2 Comparison of MOA** and ItrA*.- 4.4.3 Comparison of MOMA*0 and DFBB.- 4.4.4 Effect of multiple back-up costs in MOMA*0.- 5 Multiobjective Problem Reduction Search.- 5.1 The problem definition.- 5.2 The utility of K-ordering.- 5.3 Selection using pathmax is NP-hard.- 5.4 Selection for monotone heuristics.- 5.5 The Algorithm: MObj*.- 5.5.1 General philosophy of MObj*.- 5.5.2 Outline of MObj*.- 5.5.3 Admissibility of MObj*.- 5.5.4 Complexity of MObj*.- 5.5.5 MObj* for OR-graphs.- 5.6 Conclusion.- 6 Multiobjective Game Tree Search.- 6.1 The problem definition.- 6.2 Dominance Algebra.- 6.3 Finding the packets.- 6.4 Partial Order ?-? Pruning.- 6.4.1 Shallow ?-? pruning.- 6.4.2 Deep ?-? pruning.- 6.5 Conclusion.- 7 Conclusion.- A.- A.1 The outline of algorithm MOMA*.

O autorze

Assistant Professor Dr. Pallab Dasgupta, Associate Professor Dr. P.P. Chakrabarti and Professor Dr. S. C. DeSarkar are at the Department of Computer Science & Engineering at the Indian Institute of Technology Kharagpur, INDIA 721302

Blurb

Solutions to most real-world optimization problems involve a trade-off between multiple conflicting and non-commensurate objectives. Some of the most challenging ones are area-delay trade-off in VLSI synthesis and design space exploration, time-space trade-off in computation, and multi-strategy games. Conventional search techniques are not equipped to handle the partial order state spaces of multiobjective problems since they inherently assume a single scalar objective function. Multiobjective heuristic search techniques have been developed to specifically address multicriteria combinatorial optimization problems. This text describes the multiobjective search model and develops the theoretical foundations of the subject, including complexity results . The fundamental algorithms for three major problem formulation schemes, namely state-space formulations, problem-reduction formulations, and game-tree formulations are developed with the support of illustrative examples. Applications of multiobjective search techniques to synthesis problems in VLSI, and operations research are considered. This text provides a complete picture on contemporary research on multiobjective search, most of which is the contribution of the authors.