Efficient and Scalable Evolutionary Multi-Objective Evolutionary Algorithms
Regularity and Connectedness of Pareto-Optimal Solutions
Regularity and connectedness are general properties of multi-objective optimization problems
that is not problem-specific. These properties include
- Pareto-optimal solutions are often connected, or piecewisely connected.
- The distribution of Pareto-optimal solutions, i.e., the Pareto-front or Pareto surface, are often of low order
- According to the Karush-Kuhn-Tucker conditions, for continuous multi-objective problems with m objectives, the Pareto-front is a (m-1)-dimensional piecewise continuous manifold
Researchers in the evolutionary optimization community have not paid sufficient attention
to take advantage of resularity and connectedness of Pareto-optimal solutions to improve
the performance of multi-objective evolutionary algorithms, although the success
of combining local search in evolutionary algorithms can mainly attributed
to these properties [1]. In the recent years, we have performed research on developing
evolutionary algorithm that are able to take advantage of connectedness and regularity properties.
These algorithms include the dynamic weighted aggregation method [2-4], and the modeling regularity
in evolutionary multi-objective optimization using edtimation of distribution algorithms [5-7].
The main differences between single-objective optimization
and multi-objective optimization, which are most essential in developing
efficient and scalable evolutionary multi-objective optimization algorithms, have been elaborated
in [8].
Dynamic Weighted Aggregation for Evolutionary Multiobjective
Optimization
Conventional weighted aggregation (CWA) is an intuitive way for multiobjective
optimization. In this approach, different objectives are weighted and
summed up to one single objective. Take a bi-objective problem as an example:
F = w_{1}f_{1} +w_{2}f_{2},
where w_{1} and w_{2} are non-negative weights with
w_{1} + w_{2} = 1, f_{1} and f_{2} are
two conflicting objectives. Conventionally, the weights are fixed during
optimization. The following conclusions can be drawn for the conventional
weighted aggregation (CWA):
- It is computationally very efficient
- It is conceptually very easy to understand
- Only one solution can be obtained in one run, assuming that
the Pareto front is convex
- The solutions located in the concave region of the Pareto front cannot
be obtained.
An evolutionary dynamic weighted aggregation has been proposed in [2,3,4]. This
method proposes a brand-new concept on multiobjective optimization
using weighted aggregation. The key aspects of the concept are:
- For a convex Pareto front, each weight combination corresponds to
a stable minimum on the Pareto front.
- For a concave Pareto front, all solutions with exception to
the two points on the two ends are unstable minima. Therefore, an
optimization algorithm will converge to either of the two points whatever
weight combination is used.
- When the Pareto front is rotated slowly, meaning the weight combination is
changed gradually during optimization, the optimizer will move from one stable
minimum to another, once it has reached any point of the Pareto front. If
the pareto front is convex, the moving speed is determined by the change of
the weights. If the Pareto front is concave, the optimizer will stay on
one stable minimum until the minimum becomes unstable. In this case, the
optimizer will be able to move along the Pareto front to the next stable
minimum.
Refere to Figures 1 and 2 for an illustration.
Fig. 1. A convex Pareto front. Each point on the Perato front
is a stable minimum corresponding to a given weight combination (a rotation angle).
Fig. 2. A concave Pareto front. Only the two points at the two ends
of the Pareto front are stable minima.
According to this theory, the whole Pareto set can be obtained by
- changing the weight (say w1) gradually from 0 to 1 (or 1 to 0) generation
by generation during optimization.
- switching the weight (say w1) between 0 and 1. Notice that the switching
should be done after the optimizer has conveged to one stable minimum
on the Pareto front and the switching period should be larger that one
generation.
Preliminary result from an example with 3 objectives is shown in Fig. 3. The
weights are changed as following:
w_{1} = sin(2 &trade t/F);
w_{2} = (1-w_{1})*sin(2&Pi t/F);
w_{3} = (1-w_{1} -w_{2}).
The projections onto three two-dimensional spaces, i.e.,
(f_{1}, f_{2}), (f_{2}, f_{3}),
(f_{3}, f_{1}) are in Fig. 4. A 3D picture of the analytical Pareto-optimal
surface is shown in Fig.5. (Thanks to Oliver Schütze, Dept. of Mathematics and Computer Science,
University of Paderborn for proving me this picture.)
Fig. 3. Pareto-optimal solutions for a 3-objective test function.
Fig. 4. The projections of the obtained Pareto-optimal surface.
Fig. 5. The analytical Pareto-optimal surface.
It has been shown on several test functions that the evolutionary dynamic
weighted aggregation methods work very efficiently, no matter whether
the Pareto front is convex or concave. In general, the following conclusions
can be reached for the EDWA:
- It is computationally very efficient and conceptually very easy.
- It is able to obtain the whole Pareto set in one run.
- It is able to handle both convex and concave Pareto fronts.
From the above conclusions, it can be seen that the EDWA has overcome
the two main weaknesses of the weighted aggregation based approach to
multiobjective optimization.
Readers are referred to the references [2-4] for more details.
Modeling Regularity explicitly in Multi-Objective Optimization (Mr-MOO)
Refer to [5-7] for details.
References
[1] Y. Jin and B. Sendhoff. Connectedness, regularity and the success
of local search in evolutionary multi-objective optimization.
In: Proceedings of the IEEE Congress on Evolutionary Computation, Vol.3, pp.1910-1917, 2003
[2] Y. Jin, T. Okabe and B. Sendhoff.
Adapting weighted aggregation for
multiobjective evolution strategies. First International Conference on
Evolutionary Multi-criteria Optimization, LNCS 1993, pp.96-110, Springer,
2001
[3] Y. Jin, M. Olhofer and B. Sendhoff.
Dynamic weighted aggregation for
evolutionary multiobjective optimization: Why does it work and how? In
Genetic and Evolutionary Computation Conference, San Francisco,
July 2001
[4] Y. Jin.
Effectiveness of weighted sum of the objectives for
evolutionary multi-objective optimization: Methods, analysis and applications.
Unpublished manuscript. 2002
[5] Y. Jin, A. Zhou, Q. Zhang, B. Sendhoff, and E. Tsang. Modeling regularity to improve scalability of model-based multi-objective optimization algorithms. In: J. Knowles, D. Corne, K. Deb (eds.), Multi-Objective Problem Solving from Nature, pp. 331-356, Springer, 2008
[6] Q. Zhang, A. Zhou, Y. Jin. RM-MEDA: A regularity model based multi-objective estimation of distribution algorithm. IEEE Transactions on Evolutionary Computation, 12(1):41--63, 2008
[7] A. Zhou, Q. Zhang, Y. Jin. Approximating the set of Pareto-optimal solutions in both decision and objective spaces by an estimation of distribution algorithm. IEEE Transactions on Evolutionary Computation, 13(5):1167-1189, 2009
[8] Y. Jin and B. Sendhoff. A systems approach to evolutionary multi-objective structural optimization and beyond. IEEE Computational Intelligence Magazine, 4(3):62-76, 2009
For discussions, please contact Yaochu Jin.