This book is the second part of a presentation on “multi-objective optimization in theory and practice.” This book treats static multi-objective optimization programming (MOOP) problems in which an objective or constraint does not vary over time. The first part focused on classical methods of problem-solving. These methods concerned extensive areas of real-life decision problems including hierarchical programming problems, fuzzy programming problems, and game theory applications.
This second part concerns the use of metaheuristic methods of resolution in more challenging practical cases. These difficulties include the size of the real-world application, the nonlinearities, and discontinuities of the Pareto-optimal front we may have.
The development of multi-objective approaches accelerated in the mid-1980s with the help of evolutionary algorithms for solving real-world multi-objective problems. A recent review by I. Fister et al. (2013) collected 74 nature-inspired algorithms. These algorithms refer mainly to swarm intelligence, physics and chemistry, and biological systems.
Thus, Particle Swarm Optimization (PSO) algorithm is inspired by the social behavior of birds in flocks in search of food. A recent survey study by Lalwani et al. (2013) showed that PSO can be applied to various real-world problems. The first three domains electrical engineering, industrial engineering, and flow shop scheduling problems represent the half of the collected studies within 16 different areas and challenges. A significant contribution is due to K. Deb et al. (2002, 2005) for generating tunable test problems.
Different toolkits and suites were designed to evaluate the process of optimization algorithms. Evolutionary computation includes standard evolution strategy, evolution programming, genetic algorithm, and genetic programming.
Their extension to MOOP problems required new concepts, such as Pareto domination ranking and fitness sharing. The goal is to maintain the diversity in the population of solutions through successive generations. Evolution strategies algorithms are nature-inspired approaches. These algorithms are stochastic population-based. Collective strategies are possible within a population. Such situations occur in nature with birds or fish in flocks. Other co-evolutionary models implicate two different populations or species which compete. Solving MOOP problems may use two different ways. One way is to decompose the initial problem into a sequence of subproblems. The hybrid evolutionary algorithm is another efficient method in which different metaheuristics or heuristics combine.
This book is an attempt to handle most significant aspects of the real-life complexities in decision-making. Various difficulties arise from non-convexities, nonlinearities, and non-differentiability of objective functions and side-constraints, multiple conflicting goals, a multiplicity of global and local solutions, uncertainties due to inaccurate data, etc.
This book originated in lectures by the author on operations research and optimization techniques with applications at the University of Paris. More recently, the author was participating as an invited speaker at several international conferences, notably on game theory, evolutionary optimization, and metaheuristic algorithm in general.
This book reviews and evaluates multi-objective programming models using several software packages. The book includes ten Chapters. Chapter 1 focuses on techniques that determine Pareto-optimal sets of solutions. This Chapter shows the vast variety of algorithms currently available to solve multi-objective optimization problems. We attempt one classification of these methods by considering standard categories (e.g., swarm intelligence, genetic algorithm, physics and chemistry-based algorithms). In Chapter 1 dominance concepts are defined, and we propose an original Pareto ranking method based on the Hasse diagrams. Chapter 2 and Chapter 3 introduce the interest of metaheuristic algorithms for solving optimization problems. A metaheuristic algorithm refers to a higher level ‘master’ strategy which guides and controls the operations of other lower-level ‘worker’ heuristics. The simulated annealing algorithm illustrates this approach by the physical annealing principle (Chapter 2). Free software packages SciLab and GENOCOP solve constrained and unconstrained multi-objective optimization problems (Chapter 3). Chapter 4 to Chapter 6 discuss genetic search algorithms and evolution strategies. The population-based genetic algorithms (Chapter 4) adopt new concepts such as Pareto ranking and fitness sharing. In fact, one goal is to maintain the diversity in the population of solutions. Evolution strategy algorithms are nature-inspired techniques (Chapter 5 and Chapter 6). Collective behaviors are those prevailing in birds or fish in flocks. Co-evolutionary models involve different populations or species. In Chapter 7, we examine two ways of solving MOOP problems. One way consists of a decomposition of the initial problem into a sequence of subproblems. Another performant way is a hybridization of different metaheuristics or heuristics. Chapter 8 is on many-objective (more than three objectives) optimization and parallel computation. These approaches are suitable for the complex and time-consuming real-world applications. Chapter 9 and Chapter 10 treat the design and types of test problems. Test functions help to evaluate MOOP algorithms. Toolkits and suites allow constructing tunable tests problems (Chapter 9). Chapter 10 includes a collection of a variety of fifty test functions. For each of them, the package NSGA-II is used to approximate the Pareto-optimal front.
This book is typically user-oriented with theoretical and practical aspects. This book includes detailed examples, figures, test functions, and small-size applications from the literature. This book uses the commercial package Mathematica 7®, and free software packages, including notably SciLab 5.5.2 (an alternative to MatLab), GENOCOP III, NSGA-II and a pseudo NSGA-III.
Prof. André A. Keller
Center for Research in Computer Science
Signal and Automatic Control of Lille
University of Lille – CNRS