nach oben

2007 | Buch

Kapitel lesen Erstes Kapitel lesen

Evolutionary Algorithms for Solving Multi-Objective Problems

Second Edition

verfasst von: Carlos A. Coello Coello, Gary B. Lamont, David A. Van Veldhuizen

Verlag: Springer US

Buchreihe : Genetic and Evolutionary Computation

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Solving multi-objective problems is an evolving effort, and computer science and other related disciplines have given rise to many powerful deterministic and stochastic techniques for addressing these large-dimensional optimization problems. Evolutionary algorithms are one such generic stochastic approach that has proven to be successful and widely applicable in solving both single-objective and multi-objective problems.

This textbook is a second edition of Evolutionary Algorithms for Solving Multi-Objective Problems, significantly expanded and adapted for the classroom. The various features of multi-objective evolutionary algorithms are presented here in an innovative and student-friendly fashion, incorporating state-of-the-art research. The book disseminates the application of evolutionary algorithm techniques to a variety of practical problems, including test suites with associated performance based on a variety of appropriate metrics, as well as serial and parallel algorithm implementations.

Inhaltsverzeichnis

Frontmatter

1. Basic Concepts

Problems with multiple objectives arise in a natural fashion in most disciplines and their solution has been a challenge to researchers for a long time. Despite the considerable variety of techniques developed in Operations Research (OR) and other disciplines to tackle these problems, the complexities of their solution calls for alternative approaches.

The use of evolutionary algorithms (EAs) to solve problems of this nature has been motivated mainly because of the population-based nature of EAs which allows the generation of several elements of the Pareto optimal set in a single run. Additionally, the complexity of some multiobjective optimization problems (MOPs) (e.g., very large search spaces, uncertainty, noise, disjoint Pareto curves, etc.) may prevent use (or application) of traditional OR MOPsolution techniques.

2. MOP Evolutionary Algorithm Approaches

Both researchers and practitioners in science, engineering, government, and industry certainly have a strong interest in knowing state-of-the-art multi-objective optimization techniques. For researchers, this is the normal procedure to trigger new and original algorithmic contributions. For practitioners, this knowledge allows them to choose the most appropriate algorithm(s) for their specific multi-objective problem (MOP) domain application. From the decision maker’s (DM) perspective, it is desired that only a “few” solutions are available for ease of decision. Thus, as presented in Chapter 1, one is attempting to optimize a vector objective function possibly with constraints resulting in trade-offs between the multiple objectives. This chapter employs the various generic mathematical definitions defined in Chapter 1 for discussing multi-objective evolutionary algorithm (MOEA) design. It is desired that an MOEA generates MOP solutions in P_true which provide a trade-off of performance (efficiency, effectiveness) for specific system model objectives (cost/profit, constraints, etc.) that may mutually conflict. For example, the classical multiobjective knapsack problem (profit and weight) and drug development (cost vs. effectiveness) represent vectors of two objectives. Maximizing one objective such as profit usually does not optimize another such as reliability.

3. MOEA Local Search and Coevolution

beneficial to real-world applications, local search structures have been proposed to drive the search towards the Pareto front more effectively and efficiently. A number of generic local search techniques have been proposed along with problem domain specific methods. These approaches are discussed in this chapter with thoughts on integrating new innovative local search with MOEAs. Another emerging area of MOEA research is applying coevolutionary techniques. Relatively few researchers have explored the idea of combining coevolution with MOEAs. This chapter presents various researchers’ algorithmic processes for Coevolutionary MOEAs (CMOEA) with each researcher’s efforts summarized, categorized, and analyzed. Some potential concept and future applications of MOEA coevolution are also suggested. Exercises, discussion questions, and possible research directions for MOEA local search and coevolution are presented at the end of the chapter.

4. MOEA Test Suites

Why test multi-objective evolutionary algorithms (MOEAs)? To evaluate, compare, classify, and improve algorithm performance (effectiveness and effi- ciency). What is a MOEA test? Should we use a multi-objective optimization problem (MOP) test function, a MOP test suite, pedagogical functions, or a real-world problem? How to find an appropriate MOEA test?

Should we rely on the MOEA literature, on historical use, on test generators, or on well known real-world applications? When to test? Should we adopt and incremental algorithm and test development methodology or should we wait until the final stage of algorithm development to test it?

How should we design a MOEA test? Evidently, several important issues must be taken into consideration. For example: basic assumptions, computational platform selection, statistical tools, performance measures selection, experimental plan, among others. Thus, considerable effort must be spent not only in defining proper MOP tests and in generating the proper design of MOEA experiments, but also in employing the appropriate performance measures and experiment conditions, as well as the proper statistical tools that allow a fair algorithmic comparison. In this chapter, the development of various MOP test suites is discussed in detail.

5. MOEA Testing and Analysis

Regarding the scientific method of experimentation, it is desirable to construct an accurate, reliable, consistent and non-arbitrary representation of multi-objective evolutionary algorithm (MOEA) architectures and performance over a variety of multi-objective optimization problems (MOPs). In particular, through the use of standard procedures and criteria, one should attempt to minimize the influence of bias or prejudice of the experimenter when testing a MOEA hypothesis. The design of each experiment must conform then to an accepted “standard” approach as reflected in any generic scientific method. When employing the scientific method, the detailed design of MOEA experiments can draw heavily from outlines presented by Barr et al. [93] and Jackson et al. [765]. These generic articles discuss computational experiment design for heuristic methods, providing guidelines for reporting results and ensuring their reproducibility. Specifically, they suggest that a well-designed experiment follows the following steps: 1. Define experimental goals; 2. Choose measures of performance - metrics; 3. Design and execute the experiment; 4. Analyze data and draw conclusions; 5. Report experimental results.

6. MOEA Theory and Issues

Many MOEA development efforts acknowledge various facets of underlying MOEA theory, but make limited contributions when simply citing relevant issues raised by others. Some authors, however, exhibit significant theoretical detail. Their work provides basic MOEA models and associated theories. Table 6.1 lists contemporary efforts reflecting MOEA theory development. In essence, a MOEA is searching for optimal elements in a partially ordered set or in the Pareto optimal set. Thus, the concept of convergence to P_true and PF_true is integral to the MOEA search process.

7. Applications

Although the application of classical multiobjective optimization techniques to solve problems in different areas (e.g., management, engineering and science) started as early as 1951 (see Section 1.6.2 from Chapter 1), Multi-Objective Evolutionary Algorithms (MOEAs) were applied for the first time until the mid-1980s. However, since the late 1990s, there has been a considerable increase in the number of applications of MOEAs. This has been mainly originated by the success of MOEAs in solving real-world problems. MOEAs have generated either competitive or better results than those produced using other search techniques. This has made the task of classifying MOEA applications difficult and subjective. Trying to deal with this problem, it was decided to use a rather simple and general classification in this chapter, trying to fit each paper reviewed within the closest category according to the focus of the work. For example, a paper that is related to scheduling and naval engineering but is more focused on the second subject, is classified under “environmental, naval and hydraulic engineering”. This avoids overlapping to a certain extent, but can be confusing for some people. Therefore, it was decided to add as many entries as possible to the analytical index provided at the end of this book to facilitate the search. Additionally, italics characters are used throughout this chapter to indicate the specific name of an application, in an attempt to facilitate the search of specific information.

8. MOEA Parallelization

Successfully engineering Multiobjective Evolutionary Algorithms (MOEAs) involves thoroughly addressing many different issues. However, the performance concepts of efficiency and effectiveness are paramount. MOEAs are stochastic, population-based computational procedures mimicking evolutionary concepts and operations in attempts to find satisfactory, if not optimal, solutions of problems with multiple objectives. Evolutionary Algorithms (EAs) and MOEAs are adaptive stochastic search techniques classified under the umbrella of soft computing; generic EAs such as Genetic Algorithms, Evolution Strategies, Evolutionary Programming, and Genetic Programming are all successfully used in MOEA implementations

9. Multi-Criteria Decision Making

One aspect that most of the current research on evolutionary multiobjective optimization (EMO) often disregards is the fact that the solution of a multiobjective optimization problem (MOP) really involves three stages: measurement, search, and decision making.

Being able to find P_true does not completely solve an MOP. The decision maker (DM) still has to choose a single solution out of this set. The process of selecting a single solution is not trivial. In fact, there is a set of methodologies regarding how and when to incorporate decisions from the DM into the search process.

10. Alternative Metaheuristics

Evolutionary Algorithms (EAs) are not the only search techniques that have been used to deal with multiobjective optimization problems. In fact, as other search techniques (e.g., Tabu search and simulated annealing) have proved to have very good performance in many combinatorial (as well as other types of) optimization problems, it is only natural to think of extensions of such approaches to deal with multiple objectives.

The Operations Research (OR) and EA communities have shown a clear interest in pursuing these extensions. Since the multiobjective formulation of combinatorial optimization problems (e.g., the quadratic assignment problem) are known to be NP-complete, they present real challenges to researchers. Additionally, many real-world problems (e.g., scheduling) require efficient approaches that can at least approximate P_true and PF_true in a reasonable amount of time.

Backmatter

Titel: Evolutionary Algorithms for Solving Multi-Objective Problems
verfasst von: Carlos A. Coello Coello
Gary B. Lamont
David A. Van Veldhuizen
Verlag: Springer US
Electronic ISBN: 978-0-387-36797-2
Print ISBN: 978-0-387-33254-3
DOI: https://doi.org/10.1007/978-0-387-36797-2

Springer Professional