MOO-EALib Documentation

Reference for the Multi ObjectiveOptimization Evolutionary Algorithms library.

Introduction

Many real-world optimization problems have more than one objective and require multi objective optimization (MOO), also known as vector optimization. In "real" MOO one tries to approximate the set of Pareto-optimal trade-offs, that is, those solutions that cannot be improved in any objective without getting worse in at least one other objective. That is, we are interested in the set of non-dominated solutions. Considering an MOO with m objectives, a solution x dominates a solution y, if x is at least as good as y in any objective and is strictly better than y in at least one objective (refer to the figure on the right). The following figure illustrates the situation in objective space for a minimization problem. The green points correspond to non-dominated solutions and make up the so-called Pareto front. The red point corresponds to a solution that is dominated by at least one of the solutions corresponding to the Pareto-front. Now, a major difference between single- and multi-objective optimization becomes obvious: the set of solutions consists of more than one point in the latter case.

As an example, we consider the development of an industrial product. We want to decrease the cost and the size of the product. Often these objectives are conflicting, thus it is reasonable to ask for the set of trade-offs we can get. This set of trade-offs, which correspond to the Pareto-front (refer to the figure above), can be regarded as the solution of an MOO problem.

MOO-EALib is a library providing basic components to easily build evolutionary algorithms for multi objective optimization. It extends the EALib which focuses on the evolutionary optimization of single-objective optimization problems (SOO). The library was originally developed by the Honda Research Institute Europe.

Structure

In SOO, each individual is evaluated with respect to only one objective, i.e. it is assigned a single scalar fitness value. In MOO, two or more objective function values have to be considered for eachindividual and thus the selection of individuals needs to be adapted.

However, there is no need for changes at the chromosome level. That is, the search space or genotype space remains the same. Thus, the MOO-EALib imports all chromosome types used from the EALib.

Technically, individuals have to handle multiple fitness values and populations have to cope with more complicated sorting and selection procedures. In order to take advantage of the structure of EALib, the new classes IndividualMOO and PopulationMOO are derived from the EALib classes Individual and Population, respectively. The following figure gives an overview of the data structure upon which the library is based and its relation to the EALib.

Algorithms

Multiple multi-objective evolutionary algorithms have been implemented in Shark, most of them relying on the concept of indicator-based selection operators. First of all, they provide users and developers with a simple and quick entry to MOO. Secondly, they serve as an example on how to assemble quite complex optimization procedures from the basic building blocks provided by the MOO-EALib and Shark in general.

The following performance indicators needed to evaluate candidate solutions in the objective space have been implemented in Shark:

• Crowding Distance: originally suggested as second level sorting criterion in the NSGA-II
• Epsilon Measure: performs quite good and is not that complex computationally-wise.
• Hypervolume Measure: perhaps the best indicator from a theoretical point of view, although it takes exponential time for the computation

Finally, we list the algorithms that are available in Shark:

• MO-CMA-ES - Multi-Objective Covariance Matrix Adaption Evolution Strategy (see examples/fonSteadyStateMO-CMA.cpp)
• NSGAII - Non-Dominated Sorting Genetic Algorithm II (see examples/NSGA2.cpp)
• PAES - Pareto Archived Evolution Strategy (see examples/PAES.cpp)
• SPEA2 - Strength Pareto Evolutionary Algorithm 2 (see examples/SPEA2.cpp)
• MOGA - Multi-Objective Optimization GA (see examples/MOGA.cpp)
• DWA - Dynamic Weighted Aggregation (see examples/DWA.cpp)

To get a quick overview refer to the class or file list or have a look at the examples.