Generating Epsilon-Efficient Solutions in Multiobjective Optimization by Genetic Algorithm ()
1. Introduction
The goal of multiobjective optimization, also called vector optimization, is to find a certain set of optimal (efficient) elements of a nonempty subset of a partially ordered linear space. However, finding an exact description of this set often turns out to be practically impossible or computationally too expensive. Therefore, many researchers have focused their efforts on approximation pro- cedures and approximate solutions (see e.g. [1] [2] and references therein).
More than three decades ago, the notion of
-efficiency has been introduced by Loridan [3] for multi-objective optimization problems (MOPs). Afterwards, this concept has been used e.g. in [2] [4] [5] . To deal with a continuous multi- objective optimization problem, one has to consider a finite discretization of the set of feasible points (see Section 3 below). The discretization of the search space is one of the efficient techniques to obtain approximate solutions for MOPs, (e.g. [6] [7] ). The aim of the present paper is to develop a method of generating
- efficient solutions (as defined in [4] ) of a continuous MOP. This is achieved by discretizing the problem and then using a genetic algorithm according to the scheme described in [8] . In this way, some probabilistic stopping criteria are obtained for this procedure. They are given in the form of an upper bound for the number of iterations necessary to ensure finding all minimal elements of a finite partially ordered set with a prescribed probability. Supporting theoretical results are established and some computational examples are provided.
2. Stopping Criteria for Genetic Algorithms
In this section we review the results of [8] on probabilistic stopping criteria which will be applied later in Section 4 to some continuous multiobjective opti- mization problem.
2.1. Random Heuristic Search
The RHS (Random Heuristic Search) algorithm, described in [9] , is defined by a fixed initial population
and a transition rule
which, for a given popu- lation
, determines a new population
. Iterating
, we obtain a se- quence of populations:
(1)
Each population consists of a finite number of individuals which are elements of a given finite set
called the search space. Populations are multisets, which means that the same individual may appear more than once in a given popu- lation.
To simplify the notation, it is convenient to identify
with a subset of integers:
. The number
is called the size of search space. Then a population can be represented as an incidence vector (see [10] , p. 141):
(2)
where
is the number of copies of individual
in the population (
if the
-th individual does not appear in the population). The size of population
is the number
(3)
We assume that all the populations appearing in sequence (1) have the same size
. Dividing each component of incidence vector (2) by
, we obtain the population vector
(4)
where
is the proportion of individual
in the population. In this way, we obtain a more general representation of the population which is independent of population size. It follows that each vector
of this type be- longs to the set
(5)
which is a simplex in
. However, not all points of this simplex correspond to finite populations. For a fixed
, the following subset of
consists of all populations of size
(see [9] , p. 7):
(6)
We now define the mapping
called heuristic ( [9] , p. 9) or generational operator ( [10] , p. 144), in the following way: for a vector
representing the current population,
is the probability distribution that is sampled independently
times (with replace- ment) to produce the next population after
. For each of these
choices, the probability of selecting an individual
is equal to
, the
-th com- ponent of
.
A transition rule
is called admissible if it is a composition of a heuristic
with drawing a sample in the way described above. Symbolically,
(7)
Of course, a transition rule defined this way is nondeterministic, i.e., by applying it repeatedly to the same vector
, we can obtain different results. It should also be noted that, although
may not belong to
, the result of drawing an
-element sample is always a population of size
; therefore, it follows from (7) that
.
2.2. The Case of a Genetic Algorithm
In this subsection we consider a genetic algorithm as a particular case of the RHS. We assume that a single iteration of the genetic algorithm produces the next population from the current population as follows:
1) Choose two parents from the current population by using a selection method which can be described by some heuristic (see [9] , 4.2).
2) Crossover the two parents to obtain a child.
3) Mutate the child.
4) Put the mutated child into the next population.
5) If the next population contains less than
members, return to step 1.
The only difference between the iteration described above and the iteration of the Simple Genetic Algorithm defined in ( [9] , p. 44) is that in our version muta- tion is done after crossover.
To derive our stopping criteria, we will use some properties of mutation which is generally understood as changing one element of the search space to another, with a certain probability. The way of implementing selection and crossover is not important for our model, so we omit the discussion of them (we refer the reader to ( [10] , Chapter 5)). The only requirement is that the com- position of the three operations (selection, crossover, mutation) can be described in terms of some heuristic.
We assume that mutation consists in replacing a given individual from
by another individual, with a prescribed probability. Let us denote by
the probability that individual
mutates to
. In this way, we obtain a
matrix
. We denote by
the probability
of obtaining a population
in the current iteration of the RHS algorithm provided the previous population is
, and by
the pro- bability of selecting an individual
by a single sampling of the probability distribution
. In particular, the probability of generating individual
from population
by successive application of selection, crossover and muta- tion is equal to (see [8] , formula (7))
(8)
where the subscript sc means that we are dealing with the composition of selection and crossover, and the subscript scm indicates the composition of selection, crossover and mutation. To get a whole new population, one should draw an r-element sample from the probability distribution (8). The probability of generating a population
in this way is then equal to (see [8] , formula (8))
(9)
2.3. Stopping Criteria for Finding All Minimal Elements of
We now consider the following multiobjective optimization problem. Let
be a finite search space defined in Subsection 2.1, and let
be a function being minimized, where
and
is a partially ordered set. An element
is called a minimal element of
if there is no
such that
, where the relation
is defined by
(10)
The set of all minimal elements of
is denoted by Min
. We define the set of optimal solutions in our multiobjective problem as follows:
(11)
In particular, if
is a finite subset of the Euclidean space
, and
, where each component of
is being minimized indepen- dently, then the relation
in
can be defined by
In this case,
is the set of all Pareto optimal solutions of the respective multiobjective optimization problem.
In this section, we assume that the goal of RHS is to find all elements of
. Suppose that the set
of minimal solutions has the following form:
(12)
where the (possibly unknown) number
of these solutions is bounded from above by some known positive integer
. We say that all elements of
have been found in the first
iterations if, for each
, there exists
such that
. This means that each minimal solution is a member of some population generated in the first
iterations.
Theorem 1 ( [8] , Thm. 6.1) We consider the general model of genetic algori- thm, described in Subsection 2.2, being a special case of the RHS algorithm with the heuristic
given by (8). Suppose that there exists a number
sa- tisfying
(13)
Let
and
be two positive integers satisfying the inequality
(14)
Let
be of the form (12) with
. Then the probability of finding all elements of
in the first
iterations is at least
(15)
Corollary 2 ( [8] , Cor. 2) We consider the same model of algorithm as in Theorem 1. Suppose that condition (13) holds for some
. Let
be a given upper bound for the cardinality of
. For any
, we denote by
the smallest number of iterations required to guarantee that all elements of
have been found with probability
. Then
(16)
where
is the smallest integer greater than or equal to
.
2.4. Construction of the Set of Minimal Elements
The results of Section 2.3 give no practical way of constructing the set
. Different elements of this set are members of different populations generated by the genetic algorithm, and cannot be easily identified. To give an effective way of constructing
, some modification of the RHS is necessary.
The algorithm presented below is a combination of the RHS and the base VV (van Veldhuizen) algorithm described in ( [11] , 3.1). Suppose we have some RHS satisfying the assumptions of Theorem 1. It generates a sequence (1) of popu- lations, all of them being members of
. For each
, we define the set of individuals represented in population
:
(17)
Then we construct a sequence
of subsets of
as follows:
(18)
where
is the identity mapping. Finally, we define another sequence
of sets recursively by
(19)
(20)
where we have used the notation
as in (11). Formulas (19) and (20) define the VV algorithm.
It is shown in ( [11] , Prop. 1) that the sets
converge with probability 1 to
in the sense of some metric. However, as the authors comment, “The size of the sets
will finally grow to the size of the set of minimal elements. Since this size may be huge, this base algorithm offers only limited usefulness in practice”. In fact, our considerations can have practical value only if the cardinality of
is relatively small. For continuous multiobjective opti- mization problems, such situation can be achieved by choosing a suitable dis- cretization.
Our final result is the following theorem which shows that, with a prescribed probability, the sets
constructed by the VV algorithm are equal to
for
sufficiently large.
Theorem 3 ( [8] , Thm. 7.1) Let the assumptions of Corollary 2 be satisfied. Then, with probability
, we have
(21)
3. Generation of
-Efficient Solutions for a Continuous Problem
Let
be a given mapping, where
is a closed and bounded subset of
. We consider the following multiobjective optimization problem:
(22)
To solve this problem means to find all Pareto optimal (efficient) points of
with respect to the partial order relation in
defined by
(23)
However, in practical situations this can be very difficult or even impossible. Therefore, we shall consider a discretized version of problem (22).
For any given
, we say that a subset
of
is a
-discretization of
if
(24)
where
. Since
is compact, we can always find a finite
-discretization of
. The discretized multiobjective optimi- zation problem can now be formulated as follows:
(25)
where the same relation (23) is considered, but now in the finite set
.
It is natural to ask whether an exact solution of problem (25) yields some sort of approximate solution of problem (22). One of the cases where a positive answer can be given is described in the proposition below. Before formulating it, we must define
-efficient solutions, following ( [4] , Definition 2.3 (ii)).
Let
be such that
. We say that a point
is an
-efficient solution of problem (22) if there is no
such that
(26)
where the relation “
” is defined by formula (10).
Proposition 4 Let
where
is compact and each function
is Lipschitz continuous with constant
. Let
be such that
. Define
(27)
and let
be a
-discretization of
. Denote by
the set of all Pareto optimal solutions of problem (25) (i.e.,
as in formula (11)). Then every point
is an
-efficient solution of problem (22).
Proof. Let
. Suppose to the contrary that
is not an
-efficient solution of (22). Then there exists
such that (26) holds. In particular, we have
(28)
By the second inclusion in (24), there exists
such that
. Therefore, using (27) and (28), we obtain, for all
,
which contradicts the assumption that
.
4. The Main Algorithm
Consider the multiobjective optimization problem (22), where the constraint set
is a box defined by
(29)
where
. Suppose that the assumptions of Proposition 4 are satisfied. We want to specify a
-discretization of
. We construct the set
as follows:
(30)
where
are given positive integers.
Proposition 5 For every given
, it is possible to find the numbers
so large that the set
defined by (30) is a
-discretization of
.
Proof. The inclusion
is obvious. We now prove the second inclusion in (24). For simplicity, we consider the
norm in
:
(31)
Let us choose
so that
(32)
Take any
. Then, for each
, there exists
such that the number
defined by
(33)
satisfies
Then the vector
is such that
which completes the proof.
In the sequel we consider the following simple evolutionary algorithm which is a special case of the algorithm described in Subsection 2.4. It does not contain selection and crossover. The mutation process is very simple and consists in replacing the current population by another randomly chosen population of the same size. However, the stopping criteria described above still hold for this algorithm because their proofs make use of the properties of the mutation alone.
Algorithm 1 Parameters:
(for the stopping criterion),
(for defining
-discretization).
1) Set
.
2) Choose randomly a population
consisting of
elements of
.
3) Construct the set
by formula (19).
4) Mutate the population
by replacing it by another randomly chosen population
consisting of
elements of
.
5) Construct the set
by formula (20).
6) If
, then stop and define
.
7) Increase
by 1 and go to Step 4.
Proposition 6 After stopping Algorithm 1, the equality
holds with probability
, and consequently,
consists entirely of
-efficient solutions of problem (22) with probability
.
Proof. Apply Theorem 3 and Corollary 2 with
and
(we assume the equal probability
of mutating
to
for every
).
5. Computational Examples
Below we report on testing the algorithm described above on some examples taken from literature. To find the set of minimal elements (i.e., nondominated elements) of finite sets in Steps 3 and 5, we have used the simple algorithm for classifying a population according to non-domination, see Section 4.3.1 of [12] .
Example 7 (Problem SCH in Table I of [13] )
where
As stated in Table I of [13] , any point
is a Pareto optimal solution of this problem. Let
Since each of the functions
is continuously differentiable on
which is closed and bounded, then each of
is locally Lipschitz continuous on
Here
and
Hence,
and
Therefore, we can take the Lipschitz constants
such that
Let
Then, from (27), we have
In formula
(30), let
Hence the cardinality of
is
and
and therefore inequality (32) is satisfied. Suppose that
the population size is
For the stopping criterion, we take
and compute
. After 5016 iterations of Algorithm 1, the resulting set
is the following:
(34)
Remarks:
1) One should remember that the number
depends on the pre- scribed probability
. We have run Algorithm 1 many times up to 10,000 iterations and have observed the following changes in the set
: it has always become the set (34) somewhere between iterations 1155 and 1330, and has not changed in the later iterations. This means that the theoretically computed number of 5016 iterations gives the correct set
(in the sense that it cannot be further improved), but in fact much less iterations are sufficient to obtain the same result.
2) The cardinality of
is
. Each element of
belongs to the interval
, and hence is a Pareto efficient solution.
3) According to the performance measure Diversity Metric
see section B page 188 in [13] , the mean and variance of
for Algorithm 1 is
and
respectively, where
Hence our algorithm finds better spread of solutions than any other algorithm included in Table III of [13] , see Figure 1, this is because the mean is the smallest one.
Example 8 (Problem FON in Table I of [13] ). Consider the following opti- mization problem:
where
with variable bounds
Table I of [13] states that every point
satisfying the condition
(35)
is a Pareto optimal solution of this problem. Let
. Since each of the functions
is continuously differentiable on
, which is closed and bounded, then each of
is locally Lipschitz continuous on
We denote by
the gradient vector of
at
:
Then
![]()
Figure 1. True PF and nondominated solutions by New Algorithm on SCH.
Note that
for
. For any
, there exists
such that
(36)
Therefore, we can take the Lipschitz constants
such that
(37)
Let
Then, from (27), we have
In formula (30),
let
Hence the cardinality of
is
and
and therefore inequality (32) is satisfied. Suppose that
the population size is
. For the stopping criterion, we take
and compute
. After
iterations of Algorithm 1, the re- sulting set
is the following:
(38)
Remarks:
1) In practical tests, the set
has always become the set (38) somewhere between iterations 3475 and 3500, and has not changed in the later iterations.
2) The cardinality of
is card
The points in
which satisfy condition (35) are Pareto optimal but the other elements of
are not optimal. However, it follows from Proposition 6 that all elements of
are
-efficient solutions with probability
.
3) According to the performance measure Diversity Metric
see section B page 188 in [13] , the mean and variance of
for Algorithm 1 is
and
respectively, where
Hence our algorithm finds better spread of solutions than any other algorithm included in Table III of [13] , see Figure 2, this is because the mean is the smallest one.
Example 9 (Problem POL in Table I of [13] ).
where
with variable bounds
POL is a problem with two nonconvex Pareto fronts that are disconnected in both the objective and decision variable spaces, see [13] . The true set of Pareto- optimal solutions is difficult to know in this problem. Figure 3 illustrates that Algorithm 1 is able to discover the two disconnected Pareto fronts that lie on the boundaries of the search space.
Let
Since each of the functions
is con- tinuously differentiable on
which is closed and bounded, then each of
is locally Lipschitz continuous on
By using a computer program, it is possible to show that
and
. Using an estimate similar to (36), but with two variables, we find that, for the following Lipschitz constants:
and
, we have
![]()
Figure 2. True PF and nondominated solutions by New Algorithm on FON.
Let
Then, from (27), we have
In formula
(30), let
Hence the cardinality of
is
and
and therefore inequality (32) is
satisfied. Suppose that the population size is
. For the stopping criterion, we take
and compute
. After 706 iterations of Algorithm 1, the resulting set
is the following:
(39)
Remarks:
1) In practical tests, the set
has always become the set (39) somewhere
![]()
Figure 3. True PF and nondominated solutions by New Algorithm on POL.
between iterations 285 and 350, and has not changed in the later iterations.
2) The cardinality of
is
It follows from Proposition 6 that all elements of
are
-efficient solutions with probability
.
3) According to the performance measure Diversity Metric
see section B page 188 in [13] , the mean and variance of
for Algorithm 1 is
and
respectively, where
and
for the left Pareto front in Figure 3, and
and
for the right Pareto front in Fig- ure 3. Hence, in Table III of [13] , a better spread of solution is achieved by the algorithm NSGA-II (real-coded) in [13] . The spread of solution by our algori- thm is the next-best for this problem.
6. Conclusion
We have presented a new evolutionary method for generating
-efficient so- lutions of a continuous multiobjective programming problem. This was achieved by discretizing the problem and then using a genetic algorithm. Some proba- bilistic stopping criteria were used for this procedure to obtain, with a pre- scribed probability, all minimal solutions for the discretized problem, which are
-efficient solutions for the original problem. This article contains the main underlying theory and only some preliminary numerical computations pertaining to this method.
Acknowledgements
The authors are grateful to an anonymous referee for his/her comments which have improved the quality of the paper.