Pareto Optimality

Solving the multi-objective optimization problem requires a criterion which regards the distinct objectives. One possible criterion is the Pareto dominance which is formulated for two decision vectors a and b in the design space X as follows:

Using the dominance criterion allows for creating a partial order between different decision vectors as illustrated in Figure 3.17: Pareto. A solution is Pareto optimal if there is no decision vector that would improve one objective without causing a deterioration in at least one other objective. In other words a solution is Pareto optimal if it is not dominated by any other solution. The term Pareto is named after Vilfredo Pareto, an Italian economist who used the concept in his studies of economic efficiency and income distribution.

If all objectives are equally important and no preferences are made a priori, the dominance of a solution is the only way to determine if it is better than others. As a result the non-dominated subset out of the feasible set of solutions constitutes the Pareto set. The corresponding points in the objective space are called Pareto frontier.

Figure 3.17: Pareto

Pareto dominating (filled circles) and dominated designs (unfilled circles) including the resulting Pareto frontier of two conflicting objectives. (a and b dominate c but are indifferent to each other)

The following requirements concerning the multi-objective optimization can be formulated:

Although the optimization produces a set of Pareto optimal solutions, the user is interested in getting only one solution. Additional preferences have to be introduced, which needs comprehensive knowledge about the problem, to select a solution that meets the requirements.

Analysis of Conflicting Objectives

In order to obtain different trade-off solutions there must be conflicting objectives. The results of a preceding sensitivity analysis should be used to check the objective functions concerning possible conflicts.

In case of the oscillator example the damped eigen-frequency is used as second objective function which should be minimized. The anthill plots of the samples used for the sensitivity analysis and design exploration are shown in Figure 3.18: Conflicting Objectives. The figure indicates that the minimization of the maximum amplitude is in conflict with the minimization of the damped eigen-frequency. In the anthill plot all Pareto dominant designs can be identified. Further information can be gained by subdividing the Pareto optimal designs in the objective space in clusters which are investigated with respect to their region in the design space. The figure indicates e.g. that the designs of cluster 2 are highly concentrated in the objective space but widely distributed in the design space. Furthermore, all Pareto optimal designs are close to the design space boundaries.

Figure 3.18: Conflicting Objectives

Conflicting objectives of the damped oscillator (maximum amplitude vs. eigen-frequency) including cluster analysis of the Pareto optimal designs in the objective space (left) and in the design space (right).

Multi-Objective Population-Based Methods

The application of evolutionary algorithms for solving multi-objective optimization problems has been established over the past two decades. The parallel search for a set of Pareto optimal solutions is the major advantage of this method. The optiSLang implementation is based on the Strength Pareto Evolutionary Algorithm 2 (SPEA2) (Zitzler et al. 2001) and is characterized by the following principles:

The algorithm starts with the random or manual initialization of the first population of size µ followed by the evaluation of all individuals. For the first generation λ (number of parents) individuals are selected out of the population for reproduction. After the evaluation of all newborns both archive individuals and offspring are assigned new fitness values. The α best solutions form the archive of the next generation. The optimization stops if the maximum number of generations has been reached or the archive stagnated.

The Particle Swarm Optimization algorithm can also be applied to multi-objective optimization problems. As mentioned for single-objective PSO optiSLang selects the fittest design as global leader. For the next iteration step the swarm will move in this direction. In multi-objective optimization the fitness evaluation is different from the single-objective approach.

In contrast to the single-objective nature inspired optimization methods, fitness assignment of the multi-objective EA and PSO always regards the whole population, because the criterion is based on the comparison of individuals. The fitness assignment method is a dominance-based ranking which takes into account by how many individuals a solution is dominated and how many individuals a solution dominates. To preserve the diversity of the Pareto frontier an additional criterion is introduced to the fitness assignment procedure. The distance of an individual to its k-th nearest neighbor serves as an estimator of density. The intention is to prefer solutions in less crowded regions of the objective space such as boundary solutions.

Figure 3.19: Pareto Frontier

Pareto frontier for the damped oscillator (left) and Pareto optimal designs plotted in the design space (right) obtained by evolutionary algorithms.

In Figure 3.19: Pareto Frontier, the resulting Pareto frontier of the multi-objective evolutionary algorithm is shown for the damped oscillator example. The Pareto frontier shows a good agreement with the Pareto optimal designs from Figure 3.18: Conflicting Objectives. The Pareto frontier can now be used to judge about the importance of the different optimization goals and to choose a suitable optimal design. The efficiency of the multi-objective optimization methods can be dramatically improved especially for high-dimensional optimization problems by choosing a suitable start population instead of a pure random generation. Selected designs of a sensitivity analysis or previous optimization runs shall be used for this purpose.