英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料
外文翻译
题 目 一种用于多目标优化的自适应进化算法
作 者 Ruifen Cao bull; Guoli Li bull;Yican Wu
发表时间_____2007年_______
二ＯＯ七 年 五 月 二十八 日
摘要：进化算法在多目标优化问题中得到了广泛的应用。提出了一种用于多目标优化的自适应进化算法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 |
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
