Multiobjective Heuristic Search: An Introduction to intelligent Search Methods for Multicriteria Optimization
Pallab Dasgupta, P. P. Chakrabarti, S.C. DeSarkar · 1999
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*.