基于参考点的多目标进化优化算法NSGA-III

需积分: 25 64 浏览量更新于2024-07-21 收藏 41.53MB PDF 举报

"这篇论文是多目标进化算法领域的权威之作，由知名专家Deb撰写，主要探讨了如何使用基于参考点的非支配排序方法解决具有箱约束的多目标优化问题。" 多目标进化算法（Multi-Objective Evolutionary Algorithms，MOEA）是一种用于处理多个相互冲突目标的优化问题的方法，它在实际工程和科学问题中有着广泛的应用。随着优化问题复杂性的增加，涉及四个或更多目标的多目标优化问题（也称为多目标问题）逐渐引起关注。传统的二元或三元目标优化算法已经无法满足需求，因此开发适用于解决多目标问题的进化算法变得至关重要。论文中，作者Deb和Jain首先回顾了近期在多目标优化算法领域的进展，并讨论了几种可能的发展方向。他们提出了一种新的潜在的多目标进化算法，名为NSGA-III，它是基于NSGA-II框架的扩展。NSGA-II（Non-dominated Sorting Genetic Algorithm Ⅱ）是非支配排序遗传算法的第二代，是一种经典的多目标优化算法，以其高效的性能和稳定性而闻名。 NSGA-III引入了参考点的概念，这是一种创新的策略，旨在更有效地处理多目标优化问题中的多样性和分布。通过考虑种群成员与一组预设的参考点之间的距离，该算法可以更好地保持解的非支配性，并且更均匀地覆盖了目标空间。这种方法有助于生成更接近理想解的解决方案集合，同时保持种群的多样性，这对于理解和探索多目标问题的帕累托前沿至关重要。此外，论文还详细阐述了如何在具有箱约束的环境中应用这种算法，箱约束是指变量的取值范围受到限制，这在实际问题中非常常见。通过对这些约束的处理，NSGA-III能够生成满足所有约束条件的可行解，从而增加了算法在实际应用中的实用性。这篇论文为多目标优化领域提供了新的理论基础和技术方法，对于理解、设计和实现多目标进化算法有极大的参考价值，特别是在处理具有复杂约束条件的多目标优化问题时。通过引入参考点的非支配排序策略，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页未读，继续阅读

newpine

粉丝: 0
资源: 4

基于参考点的多目标进化优化算法NSGA-III

多目标进化算法资料汇总

多目标进化算法：原理、改进与控制领域应用综述

高维多目标进化算法及软件平台开发研究

多目标进化算法

多目标问题及多目标进化算法

ev-MOGA 多目标进化算法：这个工具箱实现了 ev-MOGA 多目标进化算法。-matlab开发

多目标进化算法合集

多目标进化算法评价

MATLAB多目标进化算法

多目标进化算法源码

最新资源