NSGA-III：多目标优化算法的参考点非支配排序方法

需积分: 35 93 浏览量更新于2024-07-20 1 收藏 41.51MB PDF 举报

"NSGA-III算法是一种多目标优化算法，基于参考点的非支配排序方法，用于解决具有四个或更多目标的复杂优化问题。它扩展了经典的NSGA-II框架，旨在平衡解决方案的多样性和均匀性。" NSGA-III算法是进化多目标优化（EMO）领域的一个重要进展，由Kalyanmoy Deb和Himanshu Jain提出，发表在2014年的《IEEE Transactions on Evolutionary Computation》期刊上。在多目标优化问题中，尤其是涉及两个或三个目标的问题，传统的优化算法已经取得了显著成就。然而，随着工程和科学问题的复杂性增加，需要处理四个或更多目标的优化问题变得越来越普遍，这促使研究人员开发出更适应这种需求的算法。 NSGA-III的核心是参考点（reference point）的概念，它引入了一个新的非支配排序策略。传统的NSGA-II算法依赖于帕累托前沿的构建，而NSGA-III则利用一组预定义的参考点来指导搜索过程。这些参考点定义了期望解的空间分布，使得算法可以同时追求解决方案的多样性（非支配解的广泛覆盖）和均匀性（在参考点附近的解决方案分布）。在NSGA-III中，种群中的个体不仅根据它们是否被其他个体支配进行排序，还根据它们与参考点的距离进行评价。这种评价机制使得算法能够优先考虑那些接近参考点且未被支配的个体，从而有效地探索多目标空间的不同区域。此外，为了保持种群的多样性，NSGA-III采用了基于分层结构的拥挤距离概念，确保了在不同参考点之间的解决方案都有所代表。 NSGA-III算法通过以下几个步骤工作： 1. 初始化种群：随机生成一组初始解。 2. 非支配排序：根据帕累托支配关系对所有个体进行排序。 3. 分类：根据与参考点的接近程度将非支配解分为不同的簇。 4. 基于参考点的拥挤距离计算：计算每个个体到最近参考点的距离，并结合拥挤距离进行第二次排序。 5. 选择操作：使用精英保留策略，结合拥挤距离选择下一代个体，以保持种群的多样性和均匀性。 6. 变异和交叉操作：应用遗传操作，如变异和交叉，生成新的解决方案。 7. 重复步骤2-6，直至达到预设的迭代次数或满足停止条件。 NSGA-III算法的成功在于其对多目标优化问题的高效处理，尤其是在解决具有多个相互冲突目标的复杂问题时。它在工程设计、资源配置、系统优化等多个领域有广泛的应用，帮助决策者找到一组可接受的折衷解，以平衡各种目标和约束。

DEB AND JAIN: EMO ALGORITHM USING REFERENCE-POINT-BASED NONDOMINATED SORTING APPROACH, PART I 581

NSGA-II, this is achieved through a computationally efﬁcient,

yet approximate, niche-preservation operator that computes

the crowding distance for every last level member as the

summation of objective-wise normalized distance between two

neighboring solutions. Thereafter, the solutions that have larger

crowding distance values are chosen. In NSGA-III, we replace

the crowding distance operator with the following approaches

(Sections IV-A–IV-E).

A. Classiﬁcation of Population Into Nondominated Levels

The above procedure of identifying nondominated fronts

using the usual domination principle [17] is also used in

NSGA-III. All population members from the nondominated

front level 1 to level l are ﬁrst included in S

.If|S

| = N;

no further operations are needed and the next generation is

started with P

t+1

= S

.For|S

| >N, members from one to

(l − 1) fronts are already selected, i.e., P

t+1

= ∪

l−1

i=1

, and the

remaining (K = N −|P

t+1

|) population members are chosen

from the last front F

. We describe the remaining selection

process in the following subsections.

B. Determination of Reference Points on a Hyper-Plane

As indicated before, NSGA-III uses a predeﬁned set of

reference points to ensure diversity in obtained solutions.

The chosen reference points can either be predeﬁned in a

structured manner or supplied preferentially by the user. We

will present results of both methods in the results section later.

In the absence of any preference information, any predeﬁned

structured placement of reference points can be adopted,

but, in this paper, we use Das and Dennis’s [48] systematic

approach

that places points on a normalized hyper-plane—an

(M − 1)-dimensional unit simplex—which is equally inclined

to all objective axes and has an intercept of one on each axis.

If p divisions are considered along each objective, the total

number of reference points (H )inanM-objective problem is

given by

H =



M + p − 1



. (3)

For example, in a three-objective problem (M = 3), the

reference points are created on a triangle with the apex at

(1, 0, 0), (0, 1, 0), and (0, 0, 1). If four divisions (p = 4 ) are

chosen for each objective axis H =



3+4−1



or 15 reference

points will be created. For clarity, these reference points are

shown in Fig. 1. In the proposed NSGA-III, in addition to

emphasizing nondominated solutions, we also emphasize pop-

ulation members that are in some sense associated with each

of these reference points. Since the above-created reference

points are widely distributed on the entire normalized hyper-

plane, the obtained solutions are also likely to be widely

distributed on or near the Pareto-optimal front. In the case of a

user-supplied set of preferred reference points, ideally the user

can mark H points on the normalized hyper-plane or indicate

any H, M-dimensional vectors for the purpose. The proposed

algorithm is likely to ﬁnd near Pareto-optimal solutions cor-

responding to the supplied reference points, thereby allowing

Any other structured distribution with or without a biasing on some part

of the Pareto-optimal front can be used as well.

Fig. 1. Fifteen structured reference points are shown on a normalized

reference plane for a three-objective problem with p =4.

Algorithm 1 Generation t of NSGA-III procedure

Input: H structured reference points Z

or supplied aspiration

points Z

, parent population P

Output: P

t+1

1: S

= ∅, i =1

2: Q

= Recombination+Mutation(P

)

3: R

= P

∪ Q

4: (F

,...) = Non-dominated-sort(R

)

5: repeat

6: S

= S

∪ F

and i = i +1

7: until |S

|≥N

8: Last front to be included: F

= F

9: if |S

| = N then

10: P

t+1

= S

, break

11: else

12:

t+1

= ∪

l−1

j=1

13: Points to be chosen from F

: K = N −|P

t+1

14:

Normalize objectives and create reference set Z

Normalize(f

)

15: Associate each member s of S

with a reference point:

[π(s),d(s)] =Associate(S

) % π(s): closest

reference point, d: distance between s and π(s)

16:

Compute niche count of reference point j ∈ Z

: ρ



∈S

(

(π(s)=j)?1:0

)

17: Choose K members one at a time from F

to construct

t+1

: Niching(K, ρ

,π,d,Z

t+1

)

18:

end if

this method to be used more from the point of view of a

combined application of decision-making and many-objective

optimization. The procedure is presented in Algorithm 1.

C. Adaptive Normalization of Population Members

First, the ideal point of the population S

is determined

by identifying the minimum value (z

min

) for each objective

function i =1, 2,... ,M in ∪

τ=0

and by constructing the

ideal point ¯z =(z

min

,... ,z

min

). Each objective value of

is then translated by subtracting objective f

by z

min

that the ideal point of translated S

becomes a zero vector.

We denote this translated objective as f



(x)=f

(x) − z

min

Thereafter, the extreme point (z

i,max

) in each (ith) objective

axis is identiﬁed by ﬁnding the solution (x ∈ S

) that makes the

corresponding achievement scalarizing function (formed with



(x) and a weight vector close to ith objective axis) minimum.

剩余24页未读，继续阅读

orasai

粉丝: 0
资源: 9

NSGA-III：多目标优化算法的参考点非支配排序方法

NSGA-III算法在Matlab中的实现与应用

MATLAB实现的3NSGA-III算法源码及解析视频

Matlab实现NSGA-III算法多目标电路优化器源码与视频

nsga-iii算法

NSGA-III算法实现文献参考

NSGA-III算法-matlab版本-写满了中文注释

nsga3:NSGA-III算法在C ++中的实现

NSGA-III算法C++源码解析与应用

MATLAB土地利用优化：nsga-iii算法应用

C++实现NSGA-III算法：源代码下载

最新资源