分解策略下的多目标组合优化：MOEA/D算法解析

1星需积分: 11 24 浏览量更新于2024-07-22 收藏 1.51MB PDF 举报

"基于分解的多目标组合优化进化算法" 在多目标优化问题中，往往存在多个相互冲突的目标函数需要同时优化。传统的单目标优化方法无法有效地处理这些目标间的权衡，因此多目标进化算法（Multiobjective Evolutionary Algorithm, MOEA）应运而生。本文介绍的是一种基于分解的多目标进化算法（MOEA/D），它旨在解决工程领域中多目标函数下的最优解求解问题。分解是传统多目标优化中的一种基础策略，但在此之前并未在多目标进化优化中得到广泛应用。MOEA/D的核心思想是将多目标优化问题分解成多个单目标子问题，然后并行地对这些子问题进行优化。每个子问题仅利用其相邻子问题的信息进行优化，这种设计使得MOEA/D在每代的计算复杂度上低于基于分级的多目标遗传算法（MOGLS）和非支配排序遗传算法第二代（NSGA-II）。 MOEA/D的工作流程主要包括以下几个步骤： 1. **问题分解**：首先，多目标优化问题被分解为一系列与目标函数相关的子问题。这些子问题通常通过一定的坐标系统或者权重分配来表示。 2. **邻域定义**：每个子问题都与一个邻域内的其他子问题相关联，邻域大小和结构可以根据问题特性调整。 3. **解的生成与更新**：在进化过程中，每个个体（解）只与邻域内的个体进行交互，通过交叉、变异等操作生成新的解，并根据子问题的目标函数进行评估。 4. **种群管理**：种群中的个体通过非支配排序和拥挤距离等指标进行选择，确保种群的多样性和分布质量。实验结果显示，即使采用简单的分解方法，MOEA/D在0-1背包问题和连续多目标优化问题上的性能也优于或与MOGLS和NSGA-II相当。进一步的研究表明，通过使用目标规范化的分解方法，可以增强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.

剩余19页未读，继续阅读

guihaiyunou

粉丝: 0
资源: 3

分解策略下的多目标组合优化：MOEA/D算法解析

NSGA2优化算法Matlab求解多目标优化问题

基于分解的多目标优化算法_MOEAD.rar

基于指标的多目标优化算法和基于分解的多目标优化算法

基于帕累托的多目标优化算法、基于分解的多目标优化算法、基于指标的多目标优化算法对比优缺点

基于分解的多目标粒子群算法

多目标微分进化算法有哪些

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

基于遗传算法的多目标优化算法

多目标差分进化算法是哪一年提出的

有没有多目标差分进化算法

最新资源