Evolutionary Algorithms for Solving Multi-Objective Problems

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche


Reference

Coello, C.C., Veldhuizen, D.V., Lamont, G. (2007). Evolutionary Algorithms for Solving Multi-Objective Problems. 2nd ed. 2007 Springer. ISBN 978-0-387-36797-2

DOI

http://www.springer.com/computer/swe/book/978-0-387-33254-3

Abstract

Designed for courses on Evolutionary Multi-objective Optimization and Evolutionary Algorithms

2nd Edition is completely updated and presents the latest research

Provides a complete set of teaching tutorials, exercises and solutions

Contains exhaustive appendices, index and bibliography

This textbook is the second edition of Evolutionary Algorithms for Solving Multi-Objective Problems, significantly augmented with contemporary knowledge and adapted for the classroom. All the various features of multi-objective evolutionary algorithms (MOEAs) are presented in an innovative and student-friendly fashion, incorporating state-of-the-art research results. The diversity of serial and parallel MOEA structures are given, evaluated and compared. The book provides detailed insight into the application of MOEA techniques to an array of practical problems. The assortment of test suites are discussed along with the variety of appropriate metrics and relevant statistical performance techniques.

Distinctive features of the new edition include:

Designed for graduate courses on Evolutionary Multi-Objective Optimization, with exercises and links to a complete set of teaching material including tutorials

Updated and expanded MOEA exercises, discussion questions and research ideas at the end of each chapter

New chapter devoted to coevolutionary and memetic MOEAs with added material on solving constrained multi-objective problems

Additional material on the most recent MOEA test functions and performance measures, as well as on the latest developments on the theoretical foundations of MOEAs

An exhaustive index and bibliography

This self-contained reference is invaluable to students, researchers and in particular to computer scientists, operational research scientists and engineers working in evolutionary computation, genetic algorithms and artificial intelligence.

Extended Abstract

Bibtex

Table of contents

Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.1 Single-Objective Optimization . . . . . . . . . . . . . . . . . . . . . .

1.2.2 The Multiobjective Optimization Problem . . . . . . . . . . . .

1.2.3 Multiobjective Optimization Problem . . . . . . . . . . . . . . . .

1.2.4 Definition of MOEA Progress . . . . . . . . . . . . . . . . . . . . . . .

1.2.5 Computational Domain Impact . . . . . . . . . . . . . . . . . . . . .

1.2.6 Pareto Epsilon Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.7 Decision Maker Impact . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4 General Optimization Algorithm Overview . . . . . . . . . . . . . . . . . .

1.5 EA Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.6 Origins of Multiobjective Optimization . . . . . . . . . . . . . . . . . . . . .

1.6.1 Mathematical Foundations . . . . . . . . . . . . . . . . . . . . . . . . .

1.6.2 Early Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.7 Classifying Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.7.1 A priori Preference Articulation . . . . . . . . . . . . . . . . . . . . .

1.7.2 A Posteriori Preference Articulation . . . . . . . . . . . . . . . . .

1.7.3 Progressive Preference Articulation . . . . . . . . . . . . . . . . . .

1.8 Using Evolutionary Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.8.1 Pareto Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.8.2 MOEA Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Further Explorations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57


2 MOP Evolutionary Algorithm Approaches . . . . . . . . . . . . . . . . .

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 MOEA Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.1 A Priori Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.2 Progressive Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

2.2.3 A Posteriori Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

2.2.4 Generic MOEA Goals and Operator Design . . . . . . . . . . . 77

2.3 Structures of Various MOEAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

2.3.1 Multi-Objective Genetic Algorithm (MOGA) . . . . . . . . . 88

2.3.2 Nondominated Sorting Genetic Algorithm (NSGA) . . . . 91

2.3.3 Niched-Pareto Genetic Algorithm (NPGA) . . . . . . . . . . . 94

2.3.4 Pareto Archived Evolution Strategy (PAES) . . . . . . . . . . 95

2.3.5 Strength Pareto Evolutionary Algorithm (SPEA) . . . . . . 97

2.3.6 Multiobjective Messy Genetic Algorithm (MOMGA) . . . 99

2.3.7 Pareto Envelope-based Selection Algorithm (PESA) . . . 101

2.3.8 The Micro-Genetic Algorithm for Multiobjective Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

2.3.9 Multiobjective Struggle GA (MOSGA) . . . . . . . . . . . . . . . 105

2.3.10 Orthogonal Multi-Objective Evolutionary Algorithm (OMOEA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

2.3.11 General Multiobjective Evolutionary Algorithm (GENMOP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

2.3.12 Criticism to Pareto sampling techniques . . . . . . . . . . . . . . 111

2.4 Constraint-Handling Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

2.5 Critical MOEA Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

2.5.1 MOEA Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

2.5.2 MOEA Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

2.5.3 MOEA Fitness Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

2.5.4 MOEA Chromosomal Representations . . . . . . . . . . . . . . . 117

2.5.5 MOEA Problem Domains . . . . . . . . . . . . . . . . . . . . . . . . . . 119

MOEA Design Recapitulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

Further Explorations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123


3 MOEA Local Search and Coevolution . . . . . . . . . . . . . . . . . . . . . 131

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

3.2 MOEA Local Search Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

3.2.1 Hybrid MOEA Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . 134

3.2.2 Comments on Hybrid MOEA Techniques . . . . . . . . . . . . . 143

3.3 MOEA Coevolutionary Techniques . . . . . . . . . . . . . . . . . . . . . . . . 144

3.4 Coevolution and Symbiosis in EAs . . . . . . . . . . . . . . . . . . . . . . . . . 147

3.4.1 Coevolutionary Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 147

3.4.2 Cooperative Coevolutionary Genetic Algorithms . . . . . . . 149

3.4.3 Symbiogenetic Coevolution . . . . . . . . . . . . . . . . . . . . . . . . . 150

3.5 Coevolution and Symbiosis in MOEAs . . . . . . . . . . . . . . . . . . . . . 152

3.5.1 Elitist Recombinative MOGA with Coevolutionary Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

3.5.2 Parmee’s Co-Evolutionary MOEA . . . . . . . . . . . . . . . . . . . 154

3.5.3 Genetic Symbiosis Algorithm . . . . . . . . . . . . . . . . . . . . . . . 155

3.5.4 Interactive GA with Co-evolving Weighting Factors . . . . 157

3.5.5 Multiobjective Co-operative Co-evolutionary GA . . . . . . 158

3.5.6 Lohn’s Coevolutionary Genetic Algorithm . . . . . . . . . . . . 159

.5.7 Distributed Cooperative Coevolutionary Algorithm . . . . 161

3.5.8 Coello’s Coevolutionary MOEA . . . . . . . . . . . . . . . . . . . . . 163

3.5.9 Nondominated Sorting Cooperative Coevolutionary GA 165

3.6 Applying Coevolutionary MOEAs . . . . . . . . . . . . . . . . . . . . . . . . . 165

3.6.1 Coevolving Multiple MOEAs . . . . . . . . . . . . . . . . . . . . . . . 166

3.6.2 Coevolving MOEAs with other Search Algorithms . . . . . 167

3.6.3 Coevolving Density Estimators . . . . . . . . . . . . . . . . . . . . . . 167

3.6.4 Coevolving Target Solutions . . . . . . . . . . . . . . . . . . . . . . . . 167

3.6.5 Coevolving Competing Populations . . . . . . . . . . . . . . . . . . 168

3.7 Final Comments on Coevolutionary MOEAs . . . . . . . . . . . . . . . . 168

Further Explorations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

4 MOEA Test Suites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

4.2 MOEA Test Function Suite Issues . . . . . . . . . . . . . . . . . . . . . . . . . 176

4.3 MOP Domain Feature Classification . . . . . . . . . . . . . . . . . . . . . . . 179

4.3.1 Unconstrained Numeric MOEA Test Functions . . . . . . . . 182

4.3.2 Side-Constrained Numeric MOEA Test Functions . . . . . 187

4.3.3 MOP Test Function Generators . . . . . . . . . . . . . . . . . . . . . 193

4.4 Generic Scalable MOP Test Problems . . . . . . . . . . . . . . . . . . . . . . 199

4.4.1 Okabe’s Test Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

4.4.2 Huband’s Test Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

4.5 Combinatorial MOEA Test Functions . . . . . . . . . . . . . . . . . . . . . . 220

4.6 Real-World MOEA Test Functions . . . . . . . . . . . . . . . . . . . . . . . . . 222

4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228

Further Explorations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

5 MOEA Testing and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233

5.2 MOEA Experiments: Motivation and Objectives . . . . . . . . . . . . . 235

5.3 Experimental Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236

5.3.1 MOP Pareto Front Determination . . . . . . . . . . . . . . . . . . . 236

5.3.2 MOEA Algorithms Testing . . . . . . . . . . . . . . . . . . . . . . . . . 238

5.3.3 Key MOEA Algorithmic Parameters . . . . . . . . . . . . . . . . . 239

5.4 MOEA Experimental Measurements . . . . . . . . . . . . . . . . . . . . . . . 243

5.4.1 Selection of MOEA Comparison Measures . . . . . . . . . . . . 245

5.4.2 Generic Attainment Function . . . . . . . . . . . . . . . . . . . . . . . 245

5.4.3 Dominance Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250

5.4.4 Primary Quality Indicators . . . . . . . . . . . . . . . . . . . . . . . . . 254XVIII Contents

5.4.5 Other MOEA Quality Indicators . . . . . . . . . . . . . . . . . . . . 263

5.4.6 MOEA Experimental Metrics Summary . . . . . . . . . . . . . . 267

5.5 MOEA Statistical Testing Approaches . . . . . . . . . . . . . . . . . . . . . 268

5.5.1 Statistical Testing Techniques . . . . . . . . . . . . . . . . . . . . . . . 268

5.5.2 Non-Parametric Statistics (Analysis of Variance) . . . . . . 270

5.5.3 Methods for Presentation of MOEA Results . . . . . . . . . . 272

5.5.4 Visualization of Test Results . . . . . . . . . . . . . . . . . . . . . . . . 272

5.6 Software Support of MOEA Testing . . . . . . . . . . . . . . . . . . . . . . . . 273

5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276

Further Explorations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277


6 MOEA Theory and Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283

6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283

6.2 Pareto-Related Theoretical Contributions . . . . . . . . . . . . . . . . . . . 284

6.2.1 Partially Ordered Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284

6.2.2 MOEA Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288

6.3 MOEA Theoretical Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300

6.3.1 Fitness Landscapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300

6.3.2 Fitness Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305

6.3.3 Pareto Ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307

6.3.4 Pareto Niching and Fitness Sharing . . . . . . . . . . . . . . . . . . 310

6.3.5 Recombination Operators . . . . . . . . . . . . . . . . . . . . . . . . . . 314

6.3.6 Mating Restrictions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315

6.3.7 Solution Stability and Robustness . . . . . . . . . . . . . . . . . . . 317

6.3.8 MOEA Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317

6.3.9 MOEA Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

6.3.10 Running Time Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320

6.3.11 MOEA Computational “Cost” . . . . . . . . . . . . . . . . . . . . . . 326

6.3.12 NFL-Theorem for Multiobjective Optimization Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326

6.3.13 Alternative Definitions of Optimality . . . . . . . . . . . . . . . . 327

6.3.14 Local Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329

6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333

Further Explorations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335

7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339

7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339

7.2 Engineering Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340

.2.1 Environmental, Naval and Hydraulic Engineering . . . . . . 340

7.2.2 Electrical and Electronics Engineering . . . . . . . . . . . . . . . 347

7.2.3 Telecommunications and Network Optimization . . . . . . . 356

7.2.4 Robotics and Control Engineering . . . . . . . . . . . . . . . . . . . 360

7.2.5 Structural and Mechanical Engineering . . . . . . . . . . . . . . . 369Contents

7.2.6 Civil and Construction Engineering . . . . . . . . . . . . . . . . . . 376

7.2.7 Transport Engineering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377

7.2.8 Aeronautical Engineering . . . . . . . . . . . . . . . . . . . . . . . . . . . 381

Scientific Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388

7.3.1 Geography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388

7.3.2 Chemistry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389

7.3.3 Physics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391

7.3.4 Medicine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393

7.3.5 Ecology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396

7.3.6 Computer Science and Computer Engineering . . . . . . . . . 397

7.4 Industrial Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407

7.4.1 Design and Manufacture . . . . . . . . . . . . . . . . . . . . . . . . . . . 408

7.4.2 Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416

7.4.3 Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424

7.4.4 Grouping and Packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426

7.5 Miscellaneous Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428

7.5.1 Finance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428

7.5.2 Classification and Prediction . . . . . . . . . . . . . . . . . . . . . . . . 430

Future Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435

Further Explorations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437


8 MOEA Parallelization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443

8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443

8.2 pMOEA Fundamental Background . . . . . . . . . . . . . . . . . . . . . . . . 445

8.2.1 pMOEA Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445

8.2.2 pMOEA Motivation and Issues . . . . . . . . . . . . . . . . . . . . . . 446

8.3 pMOEA Paradigms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450

8.3.1 Master-Slave pMOEA Model . . . . . . . . . . . . . . . . . . . . . . . . 452

8.3.2 Island pMOEA Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455

8.3.3 Diffusion pMOEA Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 458

8.3.4 Hierarchical Hybrid pMOEA Models . . . . . . . . . . . . . . . . . 459

8.4 pMOEAs From the Literature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460

8.4.1 Master-Slave pMOEAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460

8.4.2 Island pMOEAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465

8.4.3 Diffusion pMOEAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473

8.5 pMOEA Analyses and Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475

8.5.1 pMOEA Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476

8.5.2 pMOEA Suitability Issues . . . . . . . . . . . . . . . . . . . . . . . . . . 476

8.5.3 pMOEA Hardware and Software Architecture Issues . . . 477

8.5.4 pMOEA Test Function Issues . . . . . . . . . . . . . . . . . . . . . . . 480

8.5.5 pMOEA Metric/Parameter Issues . . . . . . . . . . . . . . . . . . . 484

8.6 pMOEA Development Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488

8.6.1 pMOEA Creation Options . . . . . . . . . . . . . . . . . . . . . . . . . . 490

8.6.2 Master-Slave Implementation Issues . . . . . . . . . . . . . . . . . 491

8.6.3 Island Implementation Issues . . . . . . . . . . . . . . . . . . . . . . . 493

8.6.4 Diffusion Implementation Issues . . . . . . . . . . . . . . . . . . . . . 499

8.6.5 Parallel Niching Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500

8.6.6 Parallel Archiving Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . 502

8.6.7 pMOEA Theory Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503

8.7 A “Generic” pMOEA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503

8.7.1 Engineering a pMOEA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504

8.7.2 “Genericizing” a pMOEA . . . . . . . . . . . . . . . . . . . . . . . . . . 507

8.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507

Further Explorations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509


9 Multi-Criteria Decision Making . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515

9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515

9.2 Multi-Criteria Decision Making . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516

9.2.1 Operational Attitude of the Decision Maker . . . . . . . . . . . 517

9.2.2 When to Get the Preference Information? . . . . . . . . . . . . 518

9.3 Incorporation of Preferences in MOEAs . . . . . . . . . . . . . . . . . . . . 520

9.3.1 Definition of Desired Goals . . . . . . . . . . . . . . . . . . . . . . . . . 522

9.3.2 Utility Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526

9.3.3 Preference Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528

9.3.4 Outranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531

9.3.5 Fuzzy Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533

9.3.6 Compromise Programming . . . . . . . . . . . . . . . . . . . . . . . . . 535

9.4 Issues Deserving Attention . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536

9.4.1 Preserving Dominance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537

9.4.2 Transitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537

9.4.3 Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537

9.4.4 Group Decision Making . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537

9.4.5 Other important issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539

9.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540

Further Explorations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541

10 Alternative Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547

10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547

10.2 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548

10.2.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548

10.2.2 Multiobjective Versions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550

10.2.3 Advantages and Disadvantages of Simulated Annealing . 556

10.3 Tabu Search and Scatter Search . . . . . . . . . . . . . . . . . . . . . . . . . . . 557

10.3.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558

10.3.2 Multiobjective Versions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559

10.3.3 Advantages and Disadvantages of Tabu Search and Scatter Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571

10.4 Ant System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 572

10.4.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 572

10.4.2 Multiobjective Versions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575

10.4.3 Advantages and Disadvantages of the Ant System . . . . . 581

10.5 Distributed Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . . 582

10.5.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 582

10.5.2 Advantages and Disadvantages of Distributed Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583

10.6 Particle Swarm Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584

10.6.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584

10.6.2 Multiobjective Versions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585

10.6.3 Advantages and Disadvantages of Particle Swarm Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593

10.7 Differential Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594

10.7.1 Multiobjective Versions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596

10.7.2 Advantages and Disadvantages of Differential Evolution 604

10.8 Artificial Immune Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604

10.8.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605

10.8.2 Multiobjective Versions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 606

10.8.3 Advantages and Disadvantages of Artificial Immune Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611

10.9 Other Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612

10.9.1 Cultural Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612

10.9.2 Cooperative Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614

10.10Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616

urther Explorations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 617

Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 761

Used References

ständig aktualisierte Gesamt-Publikationsliste: http://delta.cs.cinvestav.mx/~ccoello/EMOO/EMOObib.html


Links

Full Text

http://www.inf.ufpr.br/aurora/disciplinas/topicosia2/livros/Evolutionary%20Algorithms%20For%20Solving%20Multi-Objective%20Problems%202Nd%20Edition.pdf

intern file

Sonstige Links

http://delta.cs.cinvestav.mx/~ccoello/EMOO

http://www.cs.cinvestav.mx/~emoobook

Abgerufen von „http://de.evo-art.org/index.php?title=Evolutionary_Algorithms_for_Solving_Multi-Objective_Problems&oldid=1456“