基于分解的多目标进化算法MOEA/D

需积分: 34 57 浏览量更新于2024-07-15 收藏 1.56MB PDF 举报

"MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition" 本文主要介绍了一种基于分解的多目标进化算法（MOEA/D），该算法是针对多目标优化问题设计的。多目标优化问题通常涉及寻找一组解决方案，这些解决方案在多个相互冲突的目标之间达到平衡，而传统的单目标优化方法无法有效地解决这类问题。MOEA/D借鉴了传统多目标优化中的分解策略，但将其应用于进化算法框架中，从而扩展了这一策略的应用。 MOEA/D的核心思想是将复杂的多目标优化问题分解成一系列的标量优化子问题。每个子问题代表了多目标问题的一个特定方向，它们共同构成了解空间的覆盖。在优化过程中，每个子问题仅使用其相邻子问题的信息来指导自身的进化，这种方法降低了算法在每一代的计算复杂度，相比其他如MOGLS（多目标遗传算法）和NSGA-II（非支配排序遗传算法第二代）更为高效。实验部分对比了MOEA/D与MOGLS和NSGA-II在简单多目标0-1背包问题以及连续多目标优化问题上的性能。结果显示，即使采用简单的分解方法，MOEA/D也能表现出优于或与这两者相当的性能。特别是在处理具有多个目标函数的优化任务时，MOEA/D能生成更均匀且质量高的解集，这是衡量多目标优化算法性能的关键指标。此外，文中还讨论了使用目标规范化的MOEA/D版本，这种变体进一步提高了算法的性能。通过使用目标规范化，可以更好地处理目标函数之间的尺度和单位差异，使得算法在不同规模和性质的多目标问题上都能展现出良好的适应性。 MOEA/D是一种有效的多目标优化工具，它利用分解策略降低了计算复杂度，提高了算法的效率。通过实验证明，MOEA/D在处理多目标优化问题时，无论是与经典算法的比较还是在实际问题的应用上，都显示出显著的优势。这一算法的提出为多目标优化领域提供了新的思路和解决方案。

ZHANG AND LI: MOEA/D: A MULTIOBJECTIVE EVOLUTIONARY ALGORITHM BASED ON DECOMPOSITION 715

our major purpose is to study the feasibility and efﬁciency 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 deﬁned

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-speciﬁc method. Set

Step 1.4) Initialize by a problem-speciﬁc

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-speciﬁc 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 satisﬁed,

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-speciﬁc

heuristic

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 ﬁnd the exact ref-

erence point

, we use , which is initialized in Step 1.4 by a

An exemplary heuristic can be found in the implementation of MOEA/D for

the MOKP in Section IV.

Authorized licensed use limited to: Northeastern University. Downloaded on November 02,2020 at 14:30:56 UTC from IEEE Xplore. Restrictions apply.

剩余19页未读，继续阅读

学游泳的笨猫

粉丝: 9
资源: 3

基于分解的多目标进化算法MOEA/D

MOEA/D、MOP多目标分解算法代码，MATLAB实现注释很详细

MOEA/D算法

MOEA/D原版英文论文

基于稳定匹配的选择和内存增强型MOEA / D用于进化动态多目标优化

Multiobjective_Evolutionary_Algorithms_and_Applications

2012-TEC-Ens-MOEAD_decomposition_EvolutionaryAlgo_multiobjective

MOED/D经典算法

MOEAD_2.zip

模型辅助的计算费时进化高维多目标优化.docx

最近写的MOEAD的matlab代码分享给大家供学习使用-MOEAD_陈旭编.rar

最新资源