《支配的多目标进化算法及自适应调整策划方案》由会员分享，可在线阅读，更多相关《支配的多目标进化算法及自适应调整策划方案（45页珍藏版）》请在金锄头文库上搜索。
1、n 当前文档修改密码：8362839 基于-支配的多目标进化算法及自适应调整策略本文研究工作受国家自然科学基金（No.70571057，No.70171002）和“新世纪优秀人才支持打算” (NCET-05-0253) 资助。刘鎏，男，1982年生，博士研究生，研究方向为多目标进化算法理论及其应用。Email: 。 李敏强，男，1965年生，教授，博士生导师，要紧研究领域为进化计算理论，数据挖掘和机器学习。 林丹，男，1968年生， 副教授，硕士生导师，要紧研究方向为遗传算法理论及其应用。刘鎏1，李敏强1，林丹21（天津大学 系统工程研究所 天津 300072）2（天津大学 理学院应用数学系
2、天津 300072）摘要: 本文提出了一类新的基于-支配关系的多目标进化算法。该算法采纳配对比较选择和稳态替换策略，提高了算法的收敛速度，降低了计算时刻。首先，在保持种群分布性上，采纳了一种新的基于-支配关系的精英保留策略，幸免了传统修剪策略所引起的Pareto前沿面的退化。其次，依照不同取值分析了算法收敛性，提出了一种自适应调整策略。最后，通过5个常用的双目标测试函数的计算，验证了包括该自适应调整策略的多目标进化算法在求解质量上要显着强于 NSGAII，SPEA2和-MOEA等主流多目标进化算法。关键词： 多目标优化;-支配;进化算法; 自适应调整;精英保留策略;稳态策略1. 前言 求解最优
3、化问题（也称数学规划问题）是指从所有可能的方案中选择最合理的一种以达到目标优化的过程。当优化问题的目标个数多于一个时，称之为多目标优化。在通常情况下，同一问题中的多个目标函数是彼此矛盾的，因此最终结果是获得一系列折衷解。多目标进化算法是指利用进化搜索的技术去解决多目标优化问题。David Schaffer1提出了第一个多目标进化算法即向量进化遗传算法，而后该领域专家又提出了多种多目标进化算法并应用于求解实际问题。Coello2总结了目前的多目标进化算法，并将它们分为两代：第一代强调简洁，第二代强调效率，它们之间的要紧区不在于精英个体是否被引入种群的进化过程之中。Laumanns3归纳了采纳精英
4、策略的多目标进化统一模型（A unified model for MOEAs，UMMEA），通过将存储当前所有非被支配个体的种群同一般的进化种群相结合，实现精英参与种群的进化。大部分第二代的多目标进化算法，如强度Pareto进化算法(SPEA)4，强度Pareto进化算法2（SPEA2）5，Pareto包络选择算法（PAES）6，都符合如此的模型结构。另一个常用的非劣排序遗传算法2（NSGAII）没有直接利用外部种群。它将子代种群和父代种群相结合，优先选择其中的精英个体去构成下一代的进化种群。这种策略也实现了精英个体加入种群进化，并取得了专门好的计算结果。另一个分类标准即是否采纳了Pareto
5、支配排序。Goldberg7领先将Pareto优化的概念引入多目标进化算法。当前的多目标进化算法大多通过Pareto支配关系的排序来计算种群中个体的适应值，从而引导种群朝向Pareto前沿面进化。尽管这种方法能够较好地改善算法的收敛性，然而排序过程要耗费大量的计算。为了提高进化算法效率，一些研究者采纳了稳态的进化策略。所谓稳态是当新个体产生后立即加入种群的下一代进化过程之中，如简单进化算法（SEAMO）8，Pareto收敛遗传算法（PCGA）9，-多目标进化算法（-MOEA）10。在选择个体进入交配池的操作中，它们均采纳配对比较的方法，而没有进行个体适应值的计算。实验结果表明这些基于稳态的进化
6、算法在处理某些问题上要优于基于Pareto排序的算法8, 11。另外，由于非支配解的数量巨大，而外部种群存储容量有限，专门多修剪策略，如PAES中的自适应网格，NSGAII中的Crowding-Distance，SPEA中的聚类和SPEA2中的最近距离方法等，都在各自算法中发挥了专门好的作用。然而，正如12所述，这些修剪策略专门可能造成Pareto 前沿的退化，进而阻碍到最终种群的收敛。Laummans13依照-支配关系，提出一种基于网格向量的种群修剪策略，能够专门好地防止进化过程中种群的退化。这种策略在计算网格向量时，除了参数，还需要获得各个目标上的最小值，同时相同网格中的个体比较需要计算各
7、自的欧式距离，相对来讲计算量比较大。本文提出了一种新的基于-支配关系的多目标进化算法，即-支配多目标进化算法（-dominance MOEA，EDMOEA）。该算法采纳一种新的基于-支配关系的修剪策略，不仅能够防止退化现象，还能够有效的保存极端值个体以保证Pareto前沿面的广度。该算法基于稳态替换策略，利用的选择方法，能够更加快速有效地到达Pareto前沿面。同时，在新算法中采纳了新的自适应调整策略，实验结果验证了这种新策略的优越性。本文的结构如下：第2节介绍了Pareto优化和-Pareto优化的概念；第3节简要引入了协同UMMEA模型，并对其进行了修正；第4节详细讨论了新的EDMOEA算
8、法和自适应调整策略；第5节针对在一系列测试函数上的计算实验，将包含自适应调整策略的自适应多目标进化算法（AEDMOEA）同固定策略的EDMOEA及NSGAII，SPEA2，-MOEA等其它算法进行对比,分析了新算法的性能优势。第6节总结本文研究结论。2差不多概念 2.1 Pareto 支配关系在多目标优化问题中，Pareto优化解是最常用的优化概念。它最早由Francis Ysidro Edgeworth 在1881年提出而后经Vilfredo Pareto推广14（为方便讨论起见，本文的优化问题皆为最小化问题），其定义如下： 定义 1（Pareto 支配）：设，。称解支配解当且仅当部分地优于
9、，即 ,，记做。 定义2（Pareto 最优解）：解称之为解集合的Pareto优化解当且仅当集合。 定义 3（Pareto 最优解集）：关于给定的多目标优化问题，设其定义域为，则其Pareto最优集，定义为：。将Pareto最优解集在函数空间上对应的集合称之为Pareto前沿，记为。22 -支配关系-支配关系是传统的Pareto支配关系的弱化15，其具有多种概念形式。那个地点我们采纳加的形式,且关于给定的，。其定义如下： 定义4（-支配）：设,，对，称-支配当且仅当，且,。记为：。 定义 5（-Pareto最优解集近似）13：集合称为的-Pareto最优解集近似，当且仅当对任意都存在，使得。
10、定义 6（-Pareto解集）13：集合称为集合的-Pareto解集,当且仅当为集合的-Pareto最优解集近似,且。依照以上定义，能够得到如下两个定理。定理 1 , 。证明：因为，故对有，且, 使得。又由，则对, 。因此可知。定理得证。 定理 2 设，则有 。 证明：由题设可知，则有, ， 且，使得 。又由，故可知, 。另一方面，由，据定义可知, , , 。显然可知，对，有，即。定理得证。值得注意的是，和分不作为集合的-Pareto解集和-Pareto最优解集近似，都不是唯一的。一些个体靠近Pareto前沿，但不是Pareto最优解，若满足-支配关系，都有可能包含在中。定义6能够保证中的个体
11、皆为Pareto最优解。3. 多目标进化算法的进化模型Laumanns 3给出了采纳精英策略的多目标进化算法的一般模型结构UMMEA，协同进化个体种群和精英种群。精英策略是指优良的个体可不能因为劣个体的阻碍而被排除出种群的基因池。其算法流程如下：首先, 采纳初始化算子生成进化种群和精英种群，并选择参数精英强度。然后,由当前的进化种群和精英种群生成子代种群。其中, 精英强度操纵精英个体的参与程度，即从精英种群中选择个体作为交配个体的概率。取样过程由取样算子(sample)操纵，变化算子（vary）则通过交叉和变异操作而产生子代个体。尽管PAES，SPEA，SPEA2皆可抽象为如此的构架，然而关于
12、NSGAII和-MOEA来讲，却需要做一些必要的修正，如算法1所示。 算法1 修正的具有精英策略的多目标进化算法。表示精英种群，表示进化种群，表示精英强度，表示子代种群。1. 2. 3. while terminatefalse do 4. 5. vary6.7.8. 9. end while 算法1在进化过程中强调了子代种群同父代种群之间的竞争作用。这种竞争不仅在评估过程中而且也分不在两个种群的更新算子（和）中。显然，-MOEA能够看作算法1的一个实例，NSGAII即是精英种群设置为零的专门情形。当直接把子代种群看作下一代进化种群时，算法1同Laumanns所提的UMMEA是等价的3。由于进
13、化种群的更新过程同精英种群是相对独立的，在进化过程中或许有部分的精英个体进入进化种群。因此,精英强度重新定义为从两个协同种群中选择的交配个体都为精英的概率。4EDMOEA 算法在本节中，我们提出了一类新的基于-支配关系的多目标进化算法。同-MOEA一样，它也能够分解为算法1的实例。这两个算法的要紧区不即在于精英种群的更新策略上。新算法的更新策略结构简单，且具有较少的参数设置。4.1 精英种群的更新策略首先，我们给出关于给定的集合逼近其Pareto最优解集的迭代搜索算法的差不多框架13，如算法2所示。算法2 迭代的搜索算法1: 2:3: while terminate false do4:5:
14、generate() 6: update 7: end while8: Output: 其中,表示迭代次数，表示在第次循环时所产生的新的个体，而集合表示时的精英种群。算子generate()是指在第次迭代时产生新的子代个体；update()表示结合新的子代个体对原有的精英种群做更新操作，其流程如算法3所示。算法3 生成Pareto最优解集的更新算法1: Input: , 2: if such that then3: 4: else5: 6: 7: end if8: Output: . 显然，假如我们采纳算法3的更新策略，通过算法2所得到的最终种群将是Pareto最优解集的子集合。然而若仅仅将算
15、法3第2行的Pareto支配关系改为-Pareto支配关系，最后所输出的解集仅仅是-Pareto最优解集近似13。故一类新的用以生成-Pareto解集的算法构成如下：算法4 生成-Pareto解集的更新算法1: Input: , 2: if such that then3:4: Output: ;/ 算法终止5: else6: 7: 8: end if9: if such that then10:11: else12: 13: end if14: Output: . / 算法终止 定理3 设是第代生成的个体，为到第代为止所生成的个体的集合。而指依照算法4的更新策略在第代时所输出的最终种群，则是的一个-Pareto 解集。 证明：首先，可证。令任意,。假设存在,。假如，则在时可不能被接收（算法4，第3行）；假如存在,，使得，则依照Pareto支配关系的传递性可知，故依旧被排除在最终种群之外。假如，则将会
