Scalable Multi-Objective Optimization Test Problems
Kalyanmoy
Deb
Department
of
Mechanical
Engineering
Lothar
Thiele,
Marco
Laumanns
and
Eckart
Zitzler
Computer Engineering
and
Networks
Laboratory
Indian
Institute
of
Technology,
Kanp&
Kanpur,
PIN
208
016,
India
deb@iitk.ac.in
Abstract
-
After adequately demonstrating the
ability to solve different two-objective optimization
problems, multi-objective evolutionary algorithms
(MOEAs) must now show their efficacy in handling
problems having more than two objectives. In this
paper, we suggest three different approaches for sys-
tematically designing test problems for this purpose.
The simplicity of construction, scalability to any num-
ber of decision variables and objectives, knowledge
of exact shape and location of the resulting Pareto-
optimal front, and ability to control difficulties in
both converging to the true Pareto-optimal front and
maintaining a widely distributed set of solutions are
the main features of the suggested test problems.
Be-
cause of these features, they should be found useful in
various research activities on MOEAs, such as testing
the performance of a new MOEA, comparing differ-
ent MOEAs, and having a better understanding of
the working principles of MOEAs.
I. Introduction
Most earlier studies on multi-objective evolutionary algo-
rithms (MOEAs) introduced test problems which were either
simple
or
not scalable. Some test problems were too compli-
cated to visualize the exact shape and location of the result-
ing Pareteoptimal front. Schaffer’s
(1984)
study introduced
two single-variable test problems
(SCH1
and
SCHZ),
which
have been widely used
as
test problems. Kursawe’s
(1990)
test problem
KUR
was scalable to any number of decision
variables, but was not scalable in terms of the number of
ob-
jectives. The same is true with Fonseca and Fleming’s
(1995)
test problem FON. Poloni et al.’s
(2000)
test problem POL
used only two decision variables. Viennet’s
(1996)
test prob-
lem VNT has
a
discrete set of Pareto-optimal fronts, but was
designed for three objectives only. Similar shortcomings pre-
vail in the existing constrained test problems (Veldhuizen,
1999;
Deb,
2001).
However, in
1999,
the first author introduced
a
system-
atic procedure of designing test problems which are simple
to construct and are scalable to the number of decision vari-
ables (Deb,
1999).
In these problems, the exact shape and
location of the Pareto-optimal solutions are also known. The
basic construction used two functionals
g
and
h
with non-
overlapping sets of decision variables to introduce difficulties
towards the convergence to the true Pareto-optimal front and
to introduce difficulties along the Pareto-optimal front for an
ETH Zurich
CH-8092,
Switzerland
{
thiele,laumanns,zitzler}@tik.ee.ethz.ch
MOEA
to
find
a
widely distributed set of solutions, respec-
tively. In the recent past, many MOEAs have adequately
demonstrated their ability to solve two-objective optimization
problems. With the suggestion of
a
number of such MOEAs,
it is time that they must be investigated for their ability to
solve problems with more than two objectives. In order to
help achieve such studies, it is therefore necessary
to
develop
scalable test problems with arbitrary number of objectives.
Besides testing an MOEA’s ability to solve problems with
many objectives, the proposed test problems can also be used
for systematically comparing two
or
more MOEAs.
In the remainder of the paper, we first describe the es-
sential features needed in
a
test problem and then suggest
three approaches for systematically designing test problems
for multi-objective optimization algorithms. Although most
problems are illustrated for three objectives (for an ease of
illustration), the test problems are generic and scalable to an
arbitrary number of objectives.
11.
Desired Features of Test Problems
Here, we suggest that the following features must be
present in
a
test problem suite for adequately testing an
MOEA: (i) test problems should be easy to construct, (ii) test
problems should be scalable to have any number of decision
variables, (iii) test problems should be scalable to have any
number of objectives, (iv) the resulting Pareto-optimal front
(continuous
or
discrete) must be easy
to
comprehend, and
its shape and location should be exactly known, and (v) test
problems should introduce controllable hindrance to converge
to the true Pareto-optimal front and also to find
a
widely dis-
tributed set of Pareto-optimal solutions.
111.
Different Methods of Test Problem Design
We discuss
a
number of different ways to systematically de-
sign test problems for multi-objective optimization: (i) mul-
tiple single-objective functions approach, (ii) bottom-up
ap
proach, and (iii) constraint surface approach.
The first approach
is
the most intuitive one and has been
implicitly used by early MOEA researchers to construct test
problems. In this approach,
M
different single-objective func-
tions are used to construct
a
multi-objective test problem. To
simplify the construction procedure, in many cases, different
objective functions are simply used
as
different translations
of
a
single objective function. For example, the problem
SCHl
uses the following two single-objective functions for minimiza-
tion (Schaffer,
1984):
(i)
fl(z)
=
z2
(ii)
fi(z)
=
(z
-
2)*.
0-7803-7282-4/02/$10.00 02002
IEEE
825
Authorized licensed use limited to: Guangdong Univ of Tech. Downloaded on December 06,2023 at 08:42:27 UTC from IEEE Xplore. Restrictions apply.