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.
Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on May 6, 2009 at 06:54 from IEEE Xplore. Restrictions apply.
剩余19页未读，继续阅读
weixin_41534690
- 粉丝: 0
- 资源: 1
我的内容管理
展开
最新资源
- 计算机人脸表情动画技术发展综述
- 关系数据库的关键字搜索技术综述：模型、架构与未来趋势
- 迭代自适应逆滤波在语音情感识别中的应用
- 概念知识树在旅游领域智能分析中的应用
- 构建is-a层次与OWL本体集成：理论与算法
- 基于语义元的相似度计算方法研究：改进与有效性验证
- 网格梯度多密度聚类算法：去噪与高效聚类
- 网格服务工作流动态调度算法PGSWA研究
- 突发事件连锁反应网络模型与应急预警分析
- BA网络上的病毒营销与网站推广仿真研究
- 离散HSMM故障预测模型：有效提升系统状态预测
- 煤矿安全评价：信息融合与可拓理论的应用
- 多维度Petri网工作流模型MD_WFN：统一建模与应用研究
- 面向过程追踪的知识安全描述方法
- 基于收益的软件过程资源调度优化策略
- 多核环境下基于数据流Java的Web服务器优化实现提升性能
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
