Metaheuristic Techniques

Authors:
  • SBSunith Bandaru
    Sunith Bandaru
  • KDKalyanmoy Deb
    Kalyanmoy Deb
Publisher website
Google Scholar
Abstract
CONTENTS 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 3.2 MO Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 3.2.1 Principles of MO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 3.2.2 Special Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 3.2.2.1 Ideal Objective Vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 3.2.2.2 Utopian Objective Vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 3.2.2.3 Nadir Objective Vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 3.2.3 Concept of Domination in MO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 3.2.4 Properties of Dominance Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 3.2.5 Pareto-Optimality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 3.2.6 Strong Dominance and Weak Pareto-Optimality . . . . . . . . . . . . . . . . . . . . . . . 154 3.3 Optimality Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 3.4 Classification Based on the Role of the Decision Maker . . . . . . . . . . . . . . . . . . . . . . . 157 3.5 No-Preference Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 3.5.1 Method of Global Criterion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 3.6 A Posteriori Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 3.6.1 Weighting Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 3.6.2 -Constraint Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 3.6.3 Method of Weighted Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 3.6.4 Achievement Scalarizing Function Approach . . . . . . . . . . . . . . . . . . . . . . . . . 162 3.6.5 Normal Boundary Intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 3.6.6 Normalized Normal Constraint Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 3.6.7 Evolutionary Multi-Objective Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . 165 3.6.7.1 A Brief History of EMO Methodologies . . . . . . . . . . . . . . . . . . . . . . 165 3.6.7.2 Elitist EMO: NSGA-II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 3.6.7.3 Constraint Handling in EMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 3.6.7.4 Many-Objective EMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 3.7 A Priori Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 3.7.1 Lexicographic Ordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 3.7.2 Goal Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 3.8 Interactive Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 3.8.1 Reference Point Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 3.8.2 GUESS Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 3.8.3 STOM Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 3.8.4 Reference Direction Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 3.8.5 Synchronous NIMBUS Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 3.8.6 Interactive EMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 3.9 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 ABSTRACT Basic concepts and principles of multi-objective optimization (MO) methods and multiple criteria decision making (MCDM) approaches will be the focus area of this chapter. Algorithms are classified based on the role of decision makers, and four different classifications have been made. Algorithms such as the weighting method, epsilon-constraint method, achievement scalarizing function method, and normal boundary intersection method are discussed in detail. Moreover, evolutionary multi-objective optimization (EMO) methods are discussed highlighting certain recent advanced topics. Methods for handling constraints and many objectives (as many as 15 objectives) are also discussed. Under a priori methods, lexicographic and goal programming methods are presented as well. Finally, a number of existing and recent interactive methods such as the reference point method, GUESS method, STOM method, and the NIMBUS method are discussed.

This publication has 144 references indexed in Scilit: