题 目 一种用于多目标优化的自适应进化算法外文翻译资料

 2022-12-19 05:12

英语原文共 14 页,剩余内容已隐藏,支付完成后下载完整资料


外文翻译

题 目 一种用于多目标优化的自适应进化算法

作 者 Ruifen Cao bull; Guoli Li bull;Yican Wu

发表时间_____2007年_______

二OO七 年 五 月 二十八 日

摘要:进化算法在多目标优化问题中得到了广泛的应用。提出了一种用于多目标优化的自适应进化算法SEA。在SEA中,交叉概率和变异概率会随着适应度值而变化。SEA的适应度分配实现了保持种群多样性和引导种群走向真正的Pareto前沿的双重目标;个体的适应度值不仅依赖于改进的密度估计,而且依赖于非支配等级。密度估计可以在所有情况下保持多样性,包括当所有目标的标量彼此相差很大时。在MOEA中引入的一组测试问题上,将SEA与非优势排序遗传算法(NSGA-II)进行了比较。仿真结果表明,SEA在大多数测试函数中与NSGA-II一样有效,但当目标数量相差较大时,SEA具有更好的非优势解分布。

关键词:多目标优化,进化算法,SEA,非支配

1.介绍

一些现实世界的问题通常由许多相互冲突的目标组成。由于存在多个可能相互矛盾的目标需要同时优化,因此不存在单一的最优解,而是存在一组等价质量的可能解。为了获得最优解,目标之间需要进行一组最优权衡。

近年来,进化算法由于具有候选解的总体特征,能够在模拟运行中得到一组近似解,在多目标优化中得到广泛应用。近十年来,各种多目标进化算法(MOEAs)被提出并应用于多目标优化问题(MOP)。代表算法包括Schaffer[2]的向量评估遗传算法(Vector Evaluated Genetic Algorithm, VEGA),Horn等人[3]的小生境遗传算法,Srinivas和Deb[4]的非支配排序遗传算法(NSGA),Deb等人的非支配排序遗传算法算法II(NSGA-II),Zitzler和Thiele[5]提出的强度帕累托进化算法(SPEA),Zitzler等人的强度帕累托进化算法II (SPEA-II),Knowles and Corne[7] 提出的帕累托存档进化算法(PAES),还有Knowles和Corne[8]等人的模因PAES (M-PAES)。虽然这些MOEAs在开发和探索上各不相同,但它们的共同目的是为给定的MOP寻找一个近似最优、扩展良好且一致多样化的Pareto最优前沿。

在本文的第三部分中,我们提出了一种新的自适应进化算法(SEA)。第二部分介绍了多目标优化的一些概念和定义。第四节中SEA针对NSGA-II选择的一组适当的测试问题进行了测试。最后,第五节是结束语。

2.多目标优化

一般的多目标优化问题用:

s.t.

(1)

是个目标函数,为个优化参数,是解或参数的可行空间。

定义1(主导):,,支配(),满足(=1,2,hellip;,)或对于至少一个函数满足。

定义2(Pareto解):如果没有其他可行解优于,则称为MOP的Pareto最优解。所有的Pareto解都形成Pareto最优前沿。

MOP的目标是寻找一个近似最优的、延伸良好的、均匀多样化的帕累托最优锋。

3.SEA算法

单目标优化与多目标优化的区别在于求解的难易程度,这正是多目标进化算法的难点所在。为了缓解上述困难,SEA开发了一个计算适应度值的公式,包括基于快速非支配排序[1]的虚拟适应度和基于改进的密度估计的密度适应度。虚拟适应度可以指导搜索过程到达真实的Pareto前沿,密度适应度可以在所有情况下保持多样性。在上述适应度分配的基础上,SEA根据解的适应度值将自适应交叉和变异引入进化过程。在下面的文章中,我们将介绍一些组成SEA的不同模块。

3.1 快速非支配排序

首先,对于每个解,我们计算两个实体:(1),支配解的解的个数;(2),一组被支配的解。然后,我们找出的所有解,并将它们放入列表中,我们称为当前前沿面。对于当前前沿面的每个解,访问其集合中的每个成员,并将成员的计数减少1。对于任何成员,如果,它将被放入另一个列表中。我们重复的过程,直到遍历当前前沿面的所有个体。是当前的前沿面,对于当前列表(=2,hellip;)我们像一样继续这个过程,直到所有的解都被分配出来,的下标是中每个个体的非支配等级。

3.2 密度估计

为了保持种群的多样性,我们对种群中某一点周围的密度进行了估计。SEA与NSGA-II不同的是,它取该点两侧两点(相对于两个边界点的距离)沿每个目标的平均相对距离(图1.(b))。的数量作为包围点的最大长方体的相对平均边长,不包含种群中的任何其它点(我们称之为拥挤距离)。下面的算法用于计算拥挤度。

拥挤度距离分配:

l=|L| //number of solutions in L

for each i, set L[i]distance=0 //initialize distance

for each objective m

L=sort(L,m) //sort using each objective

//according ascending

if L[0]==L[l-1]

For i=0 to i=l-1

L[i]distance=L[i]distance 0

else

L[0]distance=L[l-1]distance=1 //boundary points

//are always selected

For i=1 to i=l-2

L[i]distance=L[i]distance (L[i 1].m-L[i-1].m)/(L[l-1].m-L[0].m) L[i]distance=L[i]distance/m

图1 拥挤度距离的比较

SEA使用相对值而不是文献[1]中使用的绝对值作为密度估计值,这样即使所有目标的标量相差很大,也能在所有情况下保持多样性。图1显示和具有相同的非优势秩数,但的密度估计值实际上大于。由于的标量远大于,如果使用绝对值(图1.(a)),将占主导地位,的密度值将大于。如果和锦标赛,将被选中,在进化结束时,大多数非主导的解决方案将倾向于。为了避免这种情况,SEA将图1中的密度估计由(a)转换为(b)。选择进入下一代。因此,与NSGA-II相比,它能获得更好的(均匀的)Pareto前沿分布。经过测试的示例6证明了这一点。

3.3 适应度分配

SEA的适应度分配方案遵循两个准则,这两个准则是每个进化算法的设计目标:引导进化方向到真正的Pareto前沿,保持种群的多样性。首先,SEA根据种群中个体的非优势秩数为其分配一个虚拟适应度(dumfit) 1-,是所有个体等级的最大值。等级越小,越大,相同非支配等级的个体具有相同的。其次,SEA根据每个个体的密度估计值给出一个密度适应度(denfit) (1)。最后,计算每个个体的适应度为:

(2)

因为个体的距离不大于1,所以等级大的个体与等级小的个体的适应度是不可能相同的,即使它们的非常大。具有相同非支配等级的个体,由于其密度的不同而具有不同的适应度。由此,适应度分配同时考虑了解的多样性和非支配等级,SEA不仅保证了向真Pareto前沿演化的过程,而且得到的解均匀分布。

3.4 自适应交叉和变异

SEA将自适应交叉和变异引入进化过程,根据解的适应度值自适应调整交叉概率和变异概率(式3-4)。和是保持种群多样性和进化算法收敛能力的重要因素。对于给定的问题,为了得到一组好的(,),如果使用当前通用的多目标进化算法,用户需要反复调整(, ),这是非常麻烦的。SEA为特定的解决方案自适应地提供了一组最佳的和。高适应度的解决方案受到保护,而低于平均适应度的解决方案则完全被破坏;当群体中所有个体的适应度值趋于或接近局部最优值时,解的和值将较大;当所有个体的适应度值都分散时,解决方案的和值都很小。

(4)

(3)

=

=

,,,,和分别是种群的平均适应度和最大适应度,是两个个体之间的更大的适合度,是个体发生变异的适合度。

3.5 主循环

首先,生成一个大小为N的随机父种群。种群按照非支配排序(根据3.1),计算每个解决方案的密度(根据3.2),每个解都被分配适应度值(根据3.3)。因此,采用了适应度最大化。使用二进制锦标赛选择、交叉和变异操作创建大小为N的子种群。然后将种群和结合起来形成种群。按3.1排序,密度估计(3.2),适应度分配(3.3),适应度排序,从中选取适应度最大的N个个体进入种群。将重复上述的过程,生成种群,与结合形成另一个种群,重复同样的循环,直到迭代次数等于给定值。迭代过程如图2所示:

图2 主循环

SEA实施两项精英战略:(1)通过组合用于选择的父种群和子种群来创建交配池;(2)选择N个适应度最大的个体进入下一代。所以最好的个体会被压制,不会失去。

4. 数值测试与分析

对SEA进行了测试,并与文献中最成功的MOEAs之一NSGA-II进行了比较。在其它实验对比研究[9]中,SPEA2被证明与NSGA-II一样有效。这里选择NSGA-II,因为它更高效、更容易实现。

对于所有的测试问题,每个算法都记录了10次运行的最佳结果。我们使用的种群规模是100个,最大迭代次数为250。将变量作为实数处理;采用了模拟二进制交叉(SBX)和实参变异算子。此外,NSGA-II使用的交叉概率为0.8,突变概率为1n (n是变量的个数)[1]。

为了测试SEA的性能,测试分为两个步骤。首先,我们使用了NSGA-II优于其他MOEAs的相同功能。然后,我们将NSGA-II的分布与SEA进行了比较,使用的问题中,每个目标的数量是不同的。结果表明,对于所有目标的标量都不同,而SEA可以得到均匀分布解的问题,NSGA-II缺乏均匀多样性。步骤和结果如下:

(1)NSGA-II优于其他MOEAs的测试性能

本部分使用的测试函数与Deb等人在2001年首次提出NSGA-II时使用的测试函数完全相同。事实上,该算法被证明在这些测试问题上的表现优于其他MOEAs之后,就开始流行起来。由于篇幅有限,读者可以参考[1]获得这些测试函数的详细列表。

为了比较SEA与NSGA-II的性能,我们对结果进行了定量分析。两种算法都滤除了一个公共的Pareto前沿(CPF):CPF = ND (SEAcup;NSGAminus;II).。然后计算了两个主要性能值,包括公共归档(PF)中Pareto前沿的百分比和相对覆盖指数(CS)[11]。同时得到CPF中每个MOEA的解的个数:MOEAPareto (MP) = MOEAcap;CPF。令MOEAisin;{SEA, NSGA - II}。上述指标计算如下:

(5)

(6)

(7)

表1给出了NSGA-II和SEA的Pareto解、CPF、MP、PF和CS的个数。NSGA-II的CS(NSGA-IIPareto, SEAPareto),SEA的CS(SEAPareto, NSGA-IIPareto)。很明显,具有较大MP、PF和CS的算法在接近真实Pareto前沿的能力方面更好。从表中我们可以看到SEA在MP、PF和CS上的表现似乎比MOP2、EC4和EC6上的NSGA-II要好一些。

表1 相对覆盖指数比较

<t

剩余内容已隐藏,支付完成后下载完整资料</t


资料编号:[19886],资料为PDF文档或Word文档,PDF文档可免费转换为Word

Problem

MOP2

MOP3

MOP4

EC4

EC6

MOEA

NSGA-II

SEA

NSGA-II

SEA

NSGA-II

SEA

NSGA-II

SEA

NSGA-II

SEA

Pareto

100

100

100

100

100

100

100

100

100

100

原文和译文剩余内容已隐藏,您需要先支付 30元 才能查看原文和译文全部内容!立即支付

以上是毕业论文外文翻译,课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。