![](https://csdnimg.cn/release/download_crawler_static/8460741/bg4.jpg)
ZHANG AND LI: MOEA/D: A MULTIOBJECTIVE EVOLUTIONARY ALGORITHM BASED ON DECOMPOSITION 715
our major purpose is to study the feasibility and efficiency of the
algorithm framework. We only use the above three decomposi-
tion approaches in the experimental studies in this paper.
III. T
HE FRAMEWORK OF
MULTIOBJECTIVE EVOLUTIONARY
ALGORITHM
BASED ON
DECOMPOSITION (MOEA/D)
A. General Framework
Multiobjective evolutionary algorithm based on decomposi-
tion (MOEA/D), the algorithm proposed in this paper, needs to
decompose the MOP under consideration. Any decomposition
approaches can serve this purpose. In the following description,
we suppose that the Tchebycheff approach is employed. It is
very trivial to modify the following MOEA/D when other de-
composition methods are used.
Let
be a set of even spread weight vectors and
be the reference point. As shown in Section II, the problem of
approximation of the PF of (1) can be decomposed into
scalar
optimization subproblems by using the Tchebycheff approach
and the objective function of the
th subproblem is
(6)
where
. MOEA/D minimizes all these
objective functions simultaneously in a single run.
Note that
is continuous of , the optimal solution of
should be close to that of if and
are close to each other. Therefore, any information about
these
’s with weight vectors close to should be helpful
for optimizing
. This is a major motivation behind
MOEA/D.
In MOEA/D, a neighborhood of weight vector
is defined
as a set of its several closest weight vectors in
.
The neighborhood of the
th subproblem consists of all the sub-
problems with the weight vectors from the neighborhood of
.
The population is composed of the best solution found so far
for each subproblem. Only the current solutions to its neigh-
boring subproblems are exploited for optimizing a subproblem
in MOEA/D.
At each generation
, MOEA/D with the Tchebycheff ap-
proach maintains:
• a population of
points , where is the
current solution to the
th subproblem;
•
, where is the -value of , i.e.,
for each ;
•
, where is the best value found so far
for objective
;
• an external population (EP), which is used to store non-
dominated solutions found during the search.
The algorithm works as follows:
Input:
• MOP (1);
• a stopping criterion;
•
: the number of the subproblems considered in
MOEA/D;
• a uniform spread of
weight vectors: ;
•
: the number of the weight vectors in the neighborhood
of each weight vector.
Output:
.
Step 1) Initialization:
Step 1.1) Set
.
Step 1.2) Compute the Euclidean distances between any
two weight vectors and then work out the
closest weight
vectors to each weight vector. For each
, set
, where are the closest
weight vectors to
.
Step 1.3) Generate an initial population
randomly or by a problem-specific method. Set
.
Step 1.4) Initialize by a problem-specific
method.
Step 2) Update:
For
,do
Step 2.1) Reproduction: Randomly select two indexes
from , and then generate a new solution from and
by using genetic operators.
Step 2.2) Improvement: Apply a problem-specific repair/
improvement heuristic on
to produce .
Step 2.3) Update of
: For each ,if
, then set .
Step 2.4) Update of Neighboring Solutions: For each index
,if , then set
and .
Step 2.5) Update of :
Remove from
all the vectors dominated by .
Add
to if no vectors in dominate .
Step 3) Stopping Criteria: If stopping criteria is satisfied,
then stop and output
. Otherwise, go to Step 2.
In initialization,
contains the indexes of the closest
vectors of
. We use the Euclidean distance to measure the
closeness between any two weight vectors. Therefore,
’s
closest vector is itself, and then
.If , the
th subproblem can be regarded as a neighbor of the th sub-
problem.
In the
th pass of the loop in Step 2, the neighboring sub-
problems of the
th subproblem are considered. Since and
in Step 2.1 are the current best solutions to neighbors of the
th subproblem, their offspring should hopefully be a good
solution to the
th subproblem. In Step 2.2, a problem-specific
heuristic
7
is used to repair
in the case when invalidates any
constraints, and/or optimize the
th . Therefore, the resultant
solution
is feasible and very likely to have a lower function
value for the neighbors of
th subproblem. Step 2.4 considers all
the neighbors of the
th subproblem, it replaces with if
performs better than with regard to the th subproblem.
is needed in computing the value of in Step 2.4.
Since it is often very time-consuming to find the exact ref-
erence point
, we use , which is initialized in Step 1.4 by a
7
An exemplary heuristic can be found in the implementation of MOEA/D for
the MOKP in Section IV.