非支配排序遗传算法NSGA算子分析

管　　理　　工　　程　　学　　报

Vol118,No11

JournalofIndustrialEngineeringPEngineeringManagement

2004年第1期

非支配排序遗传算法(NSGA)算子分析

关志华

(天津工业大学管理学院,天津300160)

摘要:介绍了一种基于遗传算法的多目标进化算法-非支配排序遗传算法(NSGA)。并用NSGA对三个多目标优化问题进行了详尽的计算,对采用不同的算子和不同的算子取值进行了对照,初步得出了一组适用于不同类型问题的NSGA的遗传算子取值,对其他同类问题的计算提供了参考。

关键词:遗传算法;非支配排序遗传算法;遗传算子

中图分类号:TP18　　文献标识码:A　　文章编号:100426062(2004)0120056205

排成一类,这些被分级的个体共享它们的虚拟适应度值。然

0　概述

Schaffer于1984年将遗传算法引入多目标优化领域,自

[1]

后,忽略这组已分级的个体,对种群中的其它个体按照支配与非支配关系再进行分级,该过程继续直到群体中的所有个体被分级。在NSGA中对每个局部的Pareto曲面(线)上的所有个体分别采用适应度共享策略,有利于保持群体多样性,可以克服超级个体的过度繁殖,防止早熟收敛。算法流程如图1所示。算法根据适应度共享来对虚拟适应度值重新指定,比如,指定Front=1的个体虚拟适应度值为1,Front=2的个体虚拟适应度值相应减少,可以取为018,依此类推。这样,可使虚拟适应度值规范化,并且优良个体的适应度值保持优势,可以有更多的复制机会,同时也维持了种群的多样性。由于采用了适应度共享,对于在共享半径σshare内的个体其适应度相应减少为f(x)=

从1990年以来,这一领域逐渐成为多目标优化技术的研究热点。遗传算法是一种群体搜索方法,它可以在一个进化代中获得多个Pareto优化解。在1993年之后涌现了许多多目标遗传算法[2～4],在这些算法的基础上,有许多具体的工程领域应用成功的实例

[5,6]

和对原有算法的改进性工作

[10]

[7～9]

。

非支配排序遗传算法(NondominatedSortingGeneticAlgorithm)

-NSGA是由SrinivasandDeb

于1993年提出的,其基本思

路是对所有的个体按不同的层次分级,在执行选择算子之前,种群已经根据支配与非支配关系进行了分级排序,并且种群中的所有个体都被指定一个虚拟适应度值(一般情况下和种群规模成一定比例),同级个体的虚拟适应度值相同,这样就保证了同级个体有同样的复制概率。为了维持种群多样性,这些分级后的个体共享它们的虚拟适应度值。NSGA的特点在于将多个目标函数计算转化为虚拟适应度计算。

NSGA可以处理多个目标函数的优化问题

[11]

6

s(d(x,y))y∈P

其中,x,。

(x)—y—个体;f(x)—个体x共享后的适应度值;f′个体x

共享前的适应度值;s—共享函数;d—距离函数;p—种群;α为常数[16]。

,并且可以处理

最大化或最小化问题。有关NSGA的应用在很多文献中都可以见到[12～14]。在文献[12]中,讨论了NSGA对共享半径选择的敏感性,文献[13,14]都是应用NSGA进行实际问题优化的文章。本文首先给出多目标优化问题的一般描述和非支配排序遗传算法的算法流程,然后通过三个测试函数对

NSGA的不同算子和算子的不同取值进行了详尽的分析,得

2　NSGA实验测试问题

问题1minf1(x)=x

2

2

minf2(x)=(2-x)

　x∈[0,10]

x≤1

-x

出了一组具有指导意义的参数取值。

问题2minf1(x)=

x-21<x≤33<x≤4x>4

x∈[0,10]

-x+4x-4

1　非支配排序遗传算法

NSGA是基于对个体的几层分级实现的。在选择执行

2

minf2(x)=(x-5)

22

minf1(x1,x2)=(x1-2)+(x2-1)+22

minf2(x1,x2)=9x1-(x2-1)

前,群体根据支配与非支配关系来排序:所有非支配个体被

收稿日期:2001209217　修回日期:2002210228

),男,湖南湘乡人,博士研究生,主要研究方向为多目标进化算法及其应用。作者简介:关志华(1971—

—56—

Vol118,No11

22

g1=-(x1+x2-255)

管　理　工　程　学　报

x1∈[-15,15]x2∈[-15,15]

2004年第1期

问题3:s.t.

以得到比二进制编码好的结果。实数编码的最佳适应度值和平均适应度值都要好于二进制编码,它所得出的Pareto曲

g2=-(x1-3x2+10)

图1　NSGA算法流程图

问题1是同时优化两个简单的非线性、连续的函数,问题2中有一个目标函数是线性分段连续的,另一个目标函数是连续、非线性的,问题1和2都只有一个决策变量。问题3的两个目标函数都是二维、非线性的,并且有一个非线性约束和一个线性约束。

线也很好地反映了这一点:对三个问题实数编码的Pareto曲线均是凸的,而且分布很均匀。所以在NSGA中我们推荐采用实数编码方式。后续的实算问题均采用实数编码方式。

312　采用单点交叉和均匀交叉算子的比较分析

采用单点交叉的参数选择为:实数编码,种群规模为

100,最大进化代数为100,交叉概率为018,均匀变异,变异概

3　实验测试问题结果

311　采用实数编码和二进制编码方式的比较分析

率为0101,适应度空间共享,共享半径为0105(问题3共享半径为为01158)。

采用均匀交叉方法的参数选择为:实数编码,种群规模为100,最大进化代数为100,交叉概率为018,均匀变异,变异概率为0101,适应度空间共享,共享半径为0105(问题3为

01158)。结果如表2所示。

表2　采用单点交叉和均匀交叉的结果

问题1

单点交

问题3

12956711022114381293731531-2071241801566181650-801679-2011620

采用二进制编码的参数选择为:种群规模为100,染色体长度为40,最大进化代数为100,采用单点交叉,交叉概率为

018,均匀变异,变异概率为0101,适应度空间共享,共享半径

为0105(问题3为01158)。

采用实数编码的参数选择为:种群规模为100,最大进化代数为100,采用单点交叉,交叉概率为018,均匀变异,变异概率为0101,适应度空间共享,共享半径为0105(问题3为

01158)。结果如表1所示。

表1　采用二进制编码和实数编码的结果

问题1

二

进制编码实数编码

目标函数1目标函数2目标函数1目标函数2

平均适应度值最佳适应度值平均适应度值最佳适应度值平均适应度值最佳适应度值平均适应度值最佳适应度值

3168001000212490100011426010001134001001

问题2

-01140-019838119001000-01195-019718179401005

问题3

801566181650-801679-2011620961375201842-961046-2051364

目标函数1

平均适应度值最佳适应度值

1142601000113400100111566010011110501000

问题2

01158-019525102701000-01140-019838119001000

叉均匀交叉

目标函数2

平均适应度值最佳适应度值平均适应度值

目标函数1

最佳适应度值

目标函数2

平均适应度值最佳适应度值

　　从表2中可以看出,在三个问题的计算中单点交叉和均匀交叉都可以得到比较好的结果。对三个问题单点交叉和均匀交叉的Pareto曲线均是凸的,而且分布很均匀(只有问

—57

—

　　从上表中可以看出,实数编码在三个问题的计算中都可

关志华等:非支配排序遗传算法(NSGA)算子分析

题2 …… 此处隐藏：11354字，全部文档内容请下载后查看。喜欢就下载吧 ……