Multiobjective Heuristic Search: An Introduction to intelligent Search Methods for Multicriteria Optimization(Computational Intelligence)

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.

Table of Contents:
1 Introduction.- 1.1 Multiobjective Search.- 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.3 An induced total ordering: K-ordering.- 3.4 The algorithm MOA**.- 3.5 Memory bounded multiobjective search.- 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.2 The Channel Routing Problem.- 4.3 The Log Cutting problem.- 4.4 Evaluation of the Multiobjective Strategies.- 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.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.5 Conclusion.- 7 Conclusion.- A.- A.1 The outline of algorithm MOMA*.

About the Author :
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