Evolutionary Algorithms for Solving Multi-Objective Problems

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

Volume 5 of the Book Series on

Genetic Algorithms and Evolutionary Computation

Kluwer Academic Publishers; ISBN: 0306467623, May 2002







From the Preface


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 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 (EAs). Such algorithms have been demonstrated to be very powerful and generally applicable for solving difficult 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.

Based upon the original contributions of Darwin and Mendel, evolution occurs through natural selection and adaptation. Using this basic biological model, various evolutionary algorithm structures have been developed. Single objective EAs and in particular genetic algorithms (GAs), evolutionary programming (EP) and evolution strategies (ES) have been shown to find if not the optimal solution something that is satisfactory; i.e. "satisfices'' the user. The goal of course is to search the associated objective/fitness function landscape (phenotype space) through exploration and exploitation for the "optimal'' solution. Such activity is controlled through the use of biologically inspired "mating'', "mutation'' and "selection'' operators. Specific evolutionary algorithm development involves the encoding of the independent variables (genotype) and the structuring of specific parametric mating, mutation, and selection operators. These operators manipulate each genotype individual appropriately as the search proceeds through the phenotype landscape.

The design of innovative evolutionary algorithmic approaches for multi-objective problems is built upon the research and development for single objective functions. Understanding this body of knowledge lends insight to the design and implementation of MOEAs. The use of MOEAs requires insight not only of the algorithmic domain, but also knowledge of the application problem domain. This monograph addresses such variations in the development of multi-objective evolutionary algorithms (MOEA), associated theory, appropriate multi-objective problems (MOPs) for MOEA testing, and experience with real-world applications. Many references are included and suggested for further reading.

Applying the fundamental concepts of MOEAs to real-world problems was initially a curiosity, but today is a common trend. By using the concepts and techniques presented in this book one can obtain insight into the selection of an MOEA software platform and associated tuning of the various operator parameters for complex applications. Moreover, most complex real-world applications have side constraints which requires MOEA tailoring in searching the fitness landscape. This book attempts to address all these issues through the following features:

  • It has been conceived to be a self-contained reference. This book provides all the necessary elements to guide a newcomer in the design, implementation, validation and application of MOEAs.

  • Researchers in the field will benefit from the book's comprehensive review of state-of-the-art concepts and discussions of open research topics.

  • The book is also written for graduate students in computer science, computer engineering, operations research, management science, and other scientific and engineering disciplines, who are interested in multi-objective optimization using evolutionary algorithms.

  • The book has also been conceived for professionals interested in developing practical applications of evolutionary algorithms to real-world multi-objective optimization problems.

  • Each chapter is complemented by discussion questions and several ideas that attempt to trigger novel research paths. Supplementary reading is strongly suggested for deepen the understanding of MOEAs.

  • Key features include MOEA classifications and explanations, MOEA applications and techniques, MOEA test function suites, and MOEA performance measurements.

The flow of material in each chapter is intended to present a natural and comprehensive development of MOEAs from basic concepts to complex applications. As previously stated, at the end of each chapter a list of possible research topics is given along with a number of pertinent discussion questions.

 

Ordering Information

 


You can order this book from Kluwer or Amazon, or you can download the order form from here.

 

Book Presentation in Mexico City

 

  You can find here a couple of pictures of the presentation of this book that Dr. Coello organized in Mexico City.

 

Teaching Material

 


 

Additional Exercises

 


This book contains several discussion questions and research ideas. The first are meant to be used as exercises either in class or for assignments. The second are meant to trigger everything from a small class project all the way up to a PhD thesis project.

Despite the information previously indicated, the evolutionary multiobjective optimization is constantly growing and therefore, we will be adding additional exercises inspired on current research.

The following are additional exercises for each of the chapters of this book:


Table of Contents

(pdf format)


1.- BASIC CONCEPTS

    1. Introduction

    2. Definitions

    3. An Example

    4. General Optimization Algorithm Overview

    5. EA Basics

    6. Origins of Multiobjective Optimization

    7. Classifying Techniques

    8. Using Evolutionary Algorithms

    9. Summary

    10. Discussion Questions

2.- EVOLUTIONARY ALGORITHM MOP APPROACHES

    1. Introduction

    2. MOEA Research Quantitative Analysis

    3. MOEA Research Qualitative Analysis

    4. Constraint-Handling

    5. MOEA Overview Discussion

    6. Summary

    7. Possible Research Ideas

    8. Discussion Questions

3.- MOEA TEST SUITES

    1. Introduction

    2. MOEA Test Function Suite Issues

    3. MOP Domain Feature Classification

    4. Summary

    5. Possible Research Ideas

    6. Discussion Questions

4.- MOEA TESTING AND ANALYSIS

    1. Introduction

    2. MOEA Experiments: Motivation and Objectives

    3. Experimental Methodology

    4. MOEA Statistical Testing Approaches

    5. MOEA Test Results and Analysis

    6. Summary

    7. Possible Research Ideas

    8. Discussion Questions

5.- MOEA THEORY AND ISSUES

    1. Introduction

    2. Pareto-Related Theoretical Contributions

    3. MOEA Theoretical Issues

    4. Summary

    5. Possible Research Ideas

    6. Discussion Questions

6.- APPLICATIONS

    1. Introduction

    2. Engineering Applications

    3. Scientific Applications

    4. Industrial Applications

    5. Miscellaneous Applications

    6. Future Applications

    7. Summary

    8. Possible Research Ideas

    9. Discussion Questions

7.- MOEA PARALLELIZATION

    1. Introduction

    2. Parallel MOEA Philosophy

    3. Parallel MOEA Paradigms

    4. Parallel MOEA Examples

    5. Parallel MOEA Analyses and Issues

    6. Parallel MOEA Development & Testing

    7. Summary

    8. Possible Research Ideas

    9. Discussion Questions

8.- MULTI-CRITERIA DECISION MAKING

    1. Introduction

    2. Multi-Criteria Decision Making

    3. Incorporation of Preferences in MOEAs

    4. Issues Deserving Attention

    5. Summary

    6. Possible Research Ideas

    7. Discussion Questions

9.- SPECIAL TOPICS

    1. Introduction

    2. Simulated Annealing

    3. Tabu Search and Scatter Search

    4. Ant System

    5. Distributed Reinforcement Learning

    6. Memetic Algorithms

    7. Other Heuristics

    8. Summary

    9. Possible Research Ideas

    10. Discussion Questions

10.- EPILOG


Appendix A: MOEACLASSIFICATIONANDTECHNIQUEANALYSIS

Appendix B: MOPs IN THE LITERATURE

Appendix C: Ptrue & PFtrue FOR SELECTED NUMERIC MOPs

Appendix D: Ptrue & PFtrue FOR SIDE-CONSTRAINED MOPs

Appendix E: MOEA SOFTWARE AVAILABILITY

Appendix F: MOEA-RELATED INFORMATION


Other volumes in the series:

Volume 1: Efficient and Accurate Parallel Genetic Algorithms by Erick Cantú-Paz
Volume 2: Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation by Pedro Larrañaga, José A. Lozano
Volume 3: Evolutionary Optimization in Dynamic Environmentsby Jürgen Branke
Volume 4: Anticipatory Learning Classifier Systems by Martin V. Butz
Volume 6: OmeGA by Dimitri Knjazew
Volume 7: The Design of Innovation by David E. Goldberg
Volume 8: Noisy Optimization with Evolution Strategies by Dirk V. Arnold
Volume 9: Classical and Evolutionary Algorithms in the Optimization of Optical Systems by Darko Vasiljevic
Volume 10: Evolutionary Algorithms for Embedded System Design by Rolf Drechsler and Nicole Drechsler


Further information about this book series is available here