Evolutionary Algorithms for Solving Multi-Objective Problems

by Coello Coello, Carlos A.; Van Veldhuizen, David A.; Lamont, Gary B.

• ISBN13: 9780306467622
• ISBN10: 0306467623
• Format: Hardcover
• Copyright: 2002-06-01
• Publisher: Kluwer Academic Pub

Summary

The solving of multi-objective problems (MOPs) has been a continuing effort by humans in many diverse areas, including computer science, engineering, economics, finance, industry, physics, chemistry, and ecology, among others. Many powerful and deterministic and stochastic techniques for solving these large dimensional optimization problems have risen out of operations research, decision science, engineering, computer science and other related disciplines. The explosion in computing power continues to arouse extraordinary interest in stochastic search algorithms that require high computational speed and very large memories. A generic stochastic approach is that of evolutionary algorithms (EA). Such algorithms have been demonstrated to be very powerful and generally applicable for solving different single objective problems. Their fundamental algorithmic structures can also be applied to solving many multi-objective problems. In this book, the various features of multi-objective evolutionary algorithms (MOEAs) are presented in an innovative and unique fashion, with detailed customized forms suggested for a variety of applications. Also, extensive MOEA discussion questions and possible research directions are presented at the end of each chapter. For additional information and supplementary teaching materials, please visit the authors' website at http://www.cs.cinvestav.mx/~EVOCINV/bookinfo.html.

Table of Contents

List of Figures	xxiii
List of Tables	xxxi
Basic Concepts	1	(58)
Introduction	1	(2)
Definitions	3	(13)
Global Optimization	3	(1)
The Multiobjective Optimization Problem	4	(1)
Decision Variables	4	(1)
Constraints	4	(1)
Commensurable vs Non-Commensurable	5	(1)
Attributes, Criteria, Goals and Objectives	5	(1)
General MOP	6	(1)
Types of MOPs	7	(2)
Ideal Vector	9	(1)
Convexity and Concavity	9	(1)
Pareto Optimum	9	(1)
Pareto Optimality	10	(1)
Pareto Dominance and Pareto Optimal Set	11	(1)
Pareto Front	11	(3)
Weak and Strong Nondominance	14	(1)
Kuhn-Tucker Conditions	15	(1)
MOP Global Minimum	15	(1)
An Example	16	(1)
General Optimization Algorithm Overview	17	(4)
EA Basics	21	(5)
Origins of Multiobjective Optimization	26	(3)
Mathematical Foundations	28	(1)
Early Applications	29	(1)
Classifying Techniques	29	(21)
A priori Preference Articulation	30	(1)
Global Criterion Method	30	(2)
Goal Programming	32	(2)
Goal-Attainment Method	34	(2)
Lexicographic Method	36	(1)
Min-Max Optimization	37	(1)
Multiattribute Utility Theory	38	(2)
Surrogate Worth Trade-Off	40	(1)
Electre	41	(2)
Promethee	43	(2)
A Posteriori Preference Articulation	45	(1)
Linear Combination of Weights	45	(1)
The ε-Constraint Method	45	(1)
Progressive Preference Articulation	46	(1)
Probabilistic Trade-Off Development Method	46	(1)
STEP Method	47	(1)
Sequential Multiobjective Problem Solving Method	48	(2)
Using Evolutionary Algorithms	50	(4)
Pareto Notation	52	(1)
MOEA Classification	53	(1)
Summary	54	(1)
Discussion Questions	55	(4)
Evolutionary Algorithm Mop Approaches	59	(42)
Introduction	59	(1)
MOEA Research Quantitative Analysis	60	(31)
MOEA Citations	60	(2)
A priori Techniques	62	(1)
Lexicographic Ordering	63	(1)
Criticism of Lexicographic Ordering	63	(1)
Linear Aggregating Functions	64	(1)
Criticism of Linear Aggregating Functions	65	(1)
Nonlinear Aggregating Functions	65	(1)
Criticism of Nonlinear Aggregating Functions	66	(1)
Criticism of A priori Techniques	66	(1)
Progressive Techniques	67	(1)
Criticism of Progressive Techniques	67	(1)
A posteriori Techniques	67	(1)
Independent Sampling Techniques	68	(1)
Criticism of Independent Sampling Techniques	68	(1)
Criterion Selection Techniques	68	(2)
Criticism of Criterion Selection Techniques	70	(1)
Aggregation Selection Techniques	70	(1)
Criticism of Aggregation Selection Techniques	70	(1)
Pareto Sampling	71	(14)
Criticism of Pareto Sampling Techniques	85	(2)
Criticism of A posteriori Techniques	87	(1)
Other MOEA-related Topics	87	(4)
MOEA Research Qualitative Analysis	91	(2)
Constraint-Handling	93	(1)
MOEA Overview Discussion	94	(1)
Summary	95	(1)
Possible Research Ideas	96	(1)
Discussion Questions	97	(4)
MOEA Test Suites	101	(40)
Introduction	101	(1)
MOEA Test Function Suite Issues	102	(3)
MOP Domain Feature Classification	105	(34)
Unconstrained Numeric MOEA Test Functions	109	(5)
Side-Constrained Numeric MOEA Test Functions	114	(6)
MOP Test Function Generators	120	(2)
Numerical Considerations---Generated MOPs	122	(2)
Two Objective Generated MOPs	124	(3)
Scalable Generated MOPs	127	(3)
Combinatorial MOEA Test Functions	130	(3)
Real-World MOEA Test Functions	133	(6)
Summary	139	(1)
Possible Research Ideas	139	(1)
Discussion Questions	140	(1)
MOEA Testing And Analysis	141	(38)
Introduction	141	(1)
MOEA Experiments: Motivation and Objectives	142	(1)
Experimental Methodology	143	(11)
MOP Pareto Front Determination	143	(2)
MOEA Test Algorithms	145	(5)
Key Algorithmic Parameters	150	(4)
MOEA Statistical Testing Approaches	154	(10)
MOEA Experimental Metrics	155	(7)
Statistical Testing Techniques	162	(2)
Methods for Presentation of MOEA Results	164	(1)
MOEA Test Results and Analysis	164	(12)
Unconstrained Numerical Test Functions	164	(3)
Side-Constrained Numerical Test Functions	167	(4)
MOEA Performance for 3 Objective Function MOPs	171	(2)
N P-Complete Test Problems	173	(1)
Application Test Problems	174	(2)
Summary	176	(1)
Possible Research Ideas	176	(1)
Discussion Questions	176	(3)
MOEA Theory and Issues	179	(28)
Introduction	179	(1)
Pareto-Related Theoretical Contributions	180	(10)
Partially Ordered Sets	180	(1)
Pareto Optimal Set Minimal Cardinality	181	(3)
MOEA Convergence	184	(6)
MOEA Theoretical Issues	190	(14)
Fitness Functions	191	(2)
Pareto Ranking	193	(3)
Pareto Niching and Fitness Sharing	196	(5)
Mating Restriction	201	(1)
Solution Stability and Robustness	202	(1)
MOEA Complexity	202	(2)
MOEA Computational ``Cost''	204	(1)
Summary	204	(1)
Possible Research Ideas	204	(1)
Discussion Questions	205	(2)
Applications	207	(86)
Introduction	207	(2)
Engineering Applications	209	(44)
Environmental, Naval and Hydraulic Engineering	210	(6)
Electrical and Electronics Engineering	216	(8)
Telecommunications and Network Optimization	224	(2)
Robotics and Control Engineering	226	(10)
Structural and Mechanical Engineering	236	(7)
Civil and Construction Engineering	243	(1)
Transport Engineering	244	(3)
Aeronautical Engineering	247	(6)
Scientific Applications	253	(14)
Geography	254	(1)
Chemistry	255	(1)
Physics	256	(1)
Medicine	257	(2)
Ecology	259	(1)
Computer Science and Computer Engineering	260	(7)
Industrial Applications	267	(17)
Design and Manufacture	268	(7)
Scheduling	275	(6)
Management	281	(2)
Grouping and Packing	283	(1)
Miscellaneous Applications	284	(5)
Finance	285	(1)
Classification and Prediction	286	(3)
Future Applications	289	(1)
Summary	290	(1)
Possible Research Ideas	290	(1)
Discussion Questions	291	(2)
MOEA Parallelization	293	(28)
Introduction	293	(1)
Parallel MOEA Philosophy	294	(3)
Parallel MOEA Task Decomposition	294	(2)
Parallel MOEA Objective Function Decomposition	296	(1)
Parallel MOEA Data Decomposition	297	(1)
Parallel MOEA Paradigms	297	(3)
Master-Slave Model	297	(2)
Island Model	299	(1)
Diffusion Model	300	(1)
Parallel MOEA Examples	300	(11)
Master-Slave MOEAs	301	(3)
Island MOEAs	304	(6)
Diffusion MOEAs	310	(1)
Parallel MOEA Analyses and Issues	311	(4)
Parallel MOEA Quantitative Analysis	312	(1)
Parallel MOEA Qualitative Analysis	313	(2)
Parallel MOEA Development & Testing	315	(3)
Specific Developmental Issues	317	(1)
Summary	318	(1)
Possible Research Ideas	318	(1)
Discussion Questions	319	(2)
Multi-Criteria Decision Making	321	(28)
Introduction	321	(1)
Multi-Criteria Decision Making	322	(4)
Operational Attitude of the Decision Maker	324	(1)
When to Get the Preference Information?	324	(2)
Incorporation of Preferences in MOEAs	326	(14)
Definition of Desired Goals	329	(3)
Criticism of Definition of Desired Goals	332	(1)
Utility Functions	332	(1)
Criticism of Utility Functions	333	(1)
Preference Relations	334	(2)
Criticism of Preference Relations	336	(1)
Outranking	336	(2)
Criticism of Outranking	338	(1)
Fuzzy Logic	338	(1)
Criticism of Fuzzy Logic	339	(1)
Compromise Programming	339	(1)
Criticism of Compromise Programming	339	(1)
Issues Deserving Attention	340	(4)
Preserving Dominance	340	(1)
Transitivity	340	(1)
Scalability	341	(1)
Group Decision Making	341	(2)
Other important issues	343	(1)
Summary	344	(1)
Possible Research Ideas	344	(2)
Discussion Questions	346	(3)
Special Topics	349	(40)
Introduction	349	(1)
Simulated Annealing	350	(7)
Basic Concepts	350	(6)
Advantages and Disadvantages of Simulated Annealing	356	(1)
Tabu Search and Scatter Search	357	(6)
Basic Concepts	358	(4)
Advantages and Disadvantages of Tabu Search and Scatter Search	362	(1)
Ant System	363	(7)
Basic Concepts	363	(6)
Advantages and Disadvantages of the Ant System	369	(1)
Distributed Reinforcement Learning	370	(2)
Basic Concepts	370	(2)
Advantages and Disadvantages of Distributed Reinforcement Learning	372	(1)
Memetic Algorithms	372	(4)
Basic Concepts	373	(3)
Advantages and Disadvantages of Memetic Algorithms	376	(1)
Other Heuristics	376	(8)
Particle Swarm Optimization	376	(2)
Cultural Algorithms	378	(2)
Immune System	380	(3)
Cooperative Search	383	(1)
Summary	384	(1)
Possible Research Ideas	385	(1)
Discussion Questions	386	(3)
Epilog	389	(4)
Appendix A: MOEA CLASSIFICATION AND TECHNIQUE ANALYSIS	393	(62)
1 Introduction	393	(1)
1.1 Mathematical Notation	393	(1)
1.2 Presentation Layout	394	(1)
2 A priori MOEA Techniques	394	(12)
2.1 Lexicographic Techniques	394	(2)
2.2 Linear Fitness Combination Techniques	396	(6)
2.3 Nonlinear Fitness Combination Techniques	402	(1)
2.3.1 Multiplicative Fitness Combination Techniques	402	(1)
2.3.2 Target Vector Fitness Combination Techniques	403	(2)
2.3.3 Minimax Fitness Combination Techniques	405	(1)
3 Progressive MOEA Techniques	406	(2)
4 A posteriori MOEA Techniques	408	(33)
4.1 Independent Sampling Techniques	408	(2)
4.2 Criterion Selection Techniques	410	(2)
4.3 Aggregation Selection Techniques	412	(3)
4.4 Pareto SamplingTechniques	415	(1)
4.4.1 Pareto-Based Selection	416	(7)
4.4.2 Pareto Rank-and Niche-Based Selection	423	(12)
4.4.3 Pareto Deme-Based Selection	435	(2)
4.4.4 Pareto Elitist-Based Selection	437	(3)
4.5 Hybrid Selection Techniques	440	(1)
5 MOEA Comparisons and Theory	441	(10)
5.1 MOEA Technique Comparisons	441	(9)
5.2 MOEA Theory and Reviews	450	(1)
6 Alternative Multiobjective Techniques	451	(4)
Appendix B: MOPs IN THE LITERATURE	455	(6)
Appendix C: Ptrue & PFtrue FOR SELECTED NUMERIC MOPs	461	(10)
Appendix D: Ptrue & PFtrue FOR SIDE-CONSTRAINED MOPs	471	(6)
Appendix E: MOEA SOFTWARE AVAILABILITY	477	(4)
1 Introduction	477	(4)
Appendix F: MOEA-RELATED INFORMATION	481	(8)
1 Introduction	481	(1)
2 Websites of Interest	482	(1)
3 Conferences	482	(1)
4 Journals	482	(1)
5 Researchers	483	(3)
6 Distribution Lists	486	(3)
Index	489	(26)
References	515