《支配的多目标进化算法及自适应调整方案》由会员分享，可在线阅读，更多相关《支配的多目标进化算法及自适应调整方案（17页珍藏版）》请在金锄头文库上搜索。
1、n 当前文档档修改密密码：8836228399基于-支配的多目标标进化算算法及自自适应调调整策略略本文研究工作受国家自然科学基金（No.70571057，No.70171002）和“新世纪优秀人才支持计划” (NCET-05-0253) 资助。刘鎏，男，1982年生，博士研究生，研究方向为多目标进化算法理论及其应用。Email: 。 李敏强，男，1965年生，教授，博士生导师，主要研究领域为进化计算理论，数据挖掘和机器学习。 林丹，男，1968年生， 副教授，硕士生导师，主要研究方向为遗传算法理论及其应用。刘鎏1，李敏强强1，林丹丹21（天津津大学系系统工程程研究所所天津 33000072）2
2、（天津津大学理理学院应应用数学学系天津 30000772）摘要: 本文提提出了一一类新的的基于-支配关关系的多多目标进进化算法法。该算算法采用用配对比较较选择和和稳态替替换策略略，提高高了算法法的收敛敛速度，降低了了计算时间间。首先先，在保保持种群群分布性性上，采采用了一一种新的的基于-支配关关系的精英保保留策略略，避免免了传统统修剪策策略所引引起的PPareeto前前沿面的的退化。其次，根据不不同取值值分析了了算法收收敛性，提出了了一种自自适应调调整策略略。最后后，通过过5个常用用的双目目标测试试函数的的计算，验证了了包括该该自适应应调整策策略的多多目标进进化算法法在求解解质量上上要显着着强
3、于NNSGAAII，SPEEA2和和-MOOEA等等主流多多目标进进化算法法。关键词：多目标标优化;-支配;进化算算法;自适应应调整;精英保保留策略略;稳态策策略1. 前前言求解最优优化问题题（也称称数学规规划问题题）是指指从所有有可能的方方案中选选择最合合理的一一种以达达到目标标优化的的过程。当优化化问题的的目标个个数多于于一个时时，称之之为多目目标优化化。在通通常情况况下，同同一问题题中的多多个目标标函数是是彼此矛矛盾的，因此最最终结果果是获得得一系列列折衷解解。多目标进进化算法法是指利利用进化化搜索的的技术去去解决多多目标优优化问题题。Daavidd Scchaffferr1提出了了第一
4、个个多目标标进化算算法即向向量进化化遗传算算法，而而后该领领域专家家又提出出了多种种多目标标进化算算法并应应用于求求解实际际问题。Coeelloo2总结了了目前的的多目标标进化算算法，并并将它们们分为两两代：第第一代强强调简洁洁，第二代代强调效效率，它它们之间间的主要要区别在在于精英英个体是是否被引引入种群群的进化化过程之之中。LLaummannns33归纳纳了采用用精英策策略的多多目标进进化统一一模型（A uuniffiedd moodell foor MMOEAAs，UMMMEA），通过过将存储储当前所所有非被被支配个个体的种种群同一一般的进进化种群群相结合合，实现现精英参参与种群群的进化
5、化。大部部分第二二代的多多目标进进化算法法，如强强度Parretoo进化算算法(SSPEAA)44，强强度Paaretto进化算法法2（SPEEA2）5，Parretoo包络选选择算法法（PAESS）6，都符符合这样样的模型型结构。另一个个常用的的非劣排排序遗传传算法22（NSGGAIII）没有有直接利利用外部部种群。它将子子代种群群和父代代种群相相结合，优先选选择其中中的精英英个体去去构成下下一代的的进化种种群。这这种策略略也实现现了精英英个体加加入种群群进化，并取得得了很好好的计算算结果。另一个分分类标准准即是否否采用了了Parretoo支配排排序。GGolddberrg77率先先将Par
6、eeto优优化的概概念引入入多目标标进化算算法。当当前的多多目标进进化算法法大多通通过Paaretto支配配关系的的排序来来计算种种群中个个体的适适应值，从而引导导种群朝朝向Paaretto前沿沿面进化化。虽然然这种方方法可以以较好地地改善算算法的收收敛性，但是排排序过程程要耗费费大量的的计算。为了提高高进化算算法效率率，一些些研究者者采用了了稳态的的进化策策略。所所谓稳态态是当新新个体产产生后立立即加入入种群的的下一代代进化过过程之中中，如简简单进化化算法（SEAAMO）8，Parretoo收敛遗遗传算法法（PCCGA）9，-多目标标进化算算法（-MOEEA）100。在选择择个体进进入交配配
7、池的操操作中，它们均均采用配配对比较较的方法法，而没没有进行行个体适适应值的的计算。实验结结果表明明这些基基于稳态态的进化化算法在在处理某些些问题上上要优于于基于PPareeto排排序的算算法88, 111。另外，由由于非支支配解的的数量巨巨大，而而外部种种群存储储容量有有限，很很多修剪剪策略，如PAAES中中的自适适应网格格，NSSGAIII中的的Croowdiing-Disstannce，SPEEA中的的聚类和和SPEEA2中中的最近近距离方方法等，都在各各自算法法中发挥挥了很好好的作用用。然而，正如12所述，这些修修剪策略略很可能能造成PPareeto 前沿的的退化，进而影影响到最最终种
8、群群的收敛敛。Laaummmanss133根据据-支配关关系，提提出一种种基于网网格向量量的种群群修剪策策略，可可以很好好地防止止进化过过程中种种群的退退化。这这种策略略在计算算网格向向量时，除了参参数，还还需要获获得各个个目标上上的最小小值，并并且相同同网格中中的个体体比较需需要计算算各自的的欧式距距离，相相对来说说计算量量比较大大。本文提出出了一种种新的基基于-支配关关系的多多目标进进化算法法，即-支配多多目标进进化算法法（-ddomiinannce MOEEA，EDMMOEAA）。该算算法采用用一种新新的基于于-支配关关系的修修剪策略略，不仅可可以防止止退化现现象，还还可以有有效的保保存
9、极端端值个体体以保证证Parretoo前沿面面的广度度。该算法基于于稳态替替换策略略，利用用的选择择方法，可以更更加快速速有效地地到达Paaretto前沿沿面。同同时，在在新算法法中采用用了新的的自适应应调整策策略，实实验结果果验证了了这种新新策略的的优越性性。本文的结结构如下下：第22节介绍了了Parretoo优化和和-Paaretto优化化的概念念；第33节简要引引入了协协同UMMMEAA模型，并对其其进行了了修正；第4节详细讨讨论了新新的EDDMOEEA算法法和自适适应调整整策略；第5节针对在在一系列列测试函函数上的的计算实实验，将将包含自适适应调整整策略的的自适应应多目标标进化算算法（
10、AEDDMOEEA）同固定策略略的EDDMOEEA及NSGGAIII，SPEEA2，-MOOEA等等其它算算法进行行对比,分析了了新算法的的性能优优势。第第6节总结结本文研研究结论论。2基本本概念2.1 Parretoo 支配配关系在多目标标优化问问题中，Parretoo优化解解是最常常用的优优化概念念。它最最早由FFrannciss Yssidrro EEdgeeworrth 在18881年提提出而后后经Viilfrredoo Paaretto推广广144（为为方便讨讨论起见见，本文文的优化化问题皆皆为最小小化问题题），其其定义如如下：定义 11（Parretoo 支配配）：设设，。称解支配
11、解解当且仅仅当部分分地优于于，即,，记做做。定义2（Parretoo 最优优解）：解称之之为解集集合的Parretoo优化解解当且仅仅当集合合。定义 33（Parretoo 最优优解集）：对于于给定的的多目标标优化问问题，设设其定义义域为，则其Parretoo最优集集，定义为为：。将Parretoo最优解解集在函函数空间间上对应应的集合合称之为为Parretoo前沿，记为。22 -支配关关系-支配关关系是传传统的PPareeto支配关关系的弱弱化115，其具有有多种概概念形式式。这里里我们采采用加的的形式,且对于给给定的，。其定定义如下下：定义4（-支配）：设,，对，称称-支配当且且仅当，且,
12、。记为为：。定义 55（-Paaretto最优优解集近近似）13：集合合称为的-Paaretto最优优解集近近似，当当且仅当当对任意意都存在在，使得得。定义 66（-Paaretto解集集）113：集合称称为集合合的-Paaretto解集集,当且仅仅当为集集合的-Paaretto最优优解集近近似,且。根据以上上定义，可以得得到如下下两个定定理。定理 11 , 。证明：因因为，故故对有，且, 使得。又又由，则则对, 。因此此可知。定理得得证。定理 22 设，则有有。证明：由由题设可可知，则则有, ，且，使得得。又由由，故可可知, 。另一一方面，由，据据定义可可知, , , 。显然然可知，对，有有
13、，即。定定理得证证。值得注意意的是，和分别作作为集合合的-Paaretto解集集和-PPareeto最最优解集集近似，都不是是唯一的的。一些些个体靠靠近Paaretto前沿沿，但不不是Paaretto最优优解，若若满足-支配关关系，都有可可能包含含在中。定义66可以保保证中的的个体皆皆为Paaretto最优优解。3. 多目标进进化算法法的进化化模型Laummannns 3给给出了采采用精英英策略的的多目标标进化算算法的一一般模型型结构UUMMEEA，协同进进化个体体种群和和精英种种群。精英策策略是指指优良的的个体不不会因为为劣个体体的影响响而被排排除出种种群的基基因池。其算法法流程如如下：首首
14、先, 采用初初始化算算子生成成进化种种群和精精英种群群，并选选择参数数精英强强度。然然后,由当前前的进化化种群和和精英种种群生成成子代种种群。其其中,精英强强度控制制精英个个体的参参与程度度，即从精英英种群中中选择个个体作为为交配个个体的概概率。取取样过程程由取样样算子(sammplee)控制，变化算算子（vvaryy）则通过交交叉和变变异操作作而产生生子代个个体。虽虽然PAAES，SPEEA，SPEEA2皆皆可抽象象为这样样的构架架，然而而对于NNSGAAII和和-MOOEA来来说，却却需要做做一些必必要的修修正，如如算法11所示。算法1 修正的的具有精精英策略略的多目目标进化化算法。表示精
15、精英种群群，表示示进化种种群，表表示精英英强度，表示子子代种群群。1. 2. 3. wwhilleteermiinattefaalsee doo4. 5. varry6.7.8.9. eend whiile算法1在在进化过过程中强强调了子子代种群群同父代代种群之之间的竞竞争作用用。这种种竞争不不仅在评评估过程程中而且且也分别别在两个个种群的的更新算算子（和和）中。显显然，-MOOEA可可以看作作算法1的一个个实例，NSGGAIII即是精精英种群群设置为为零的特特殊情形形。当直直接把子子代种群群看作下下一代进进化种群群时，算算法1同Lauumannns所所提的UUMMEEA是等等价的3。由于进进化种群群的更新新过程同同精英种种群是相相对独立立的，在在进化过过程中或或许有部部分的精精英个体体进入进进化种群群。因此此,精英强强度重新新定义为为从两个个协同种种群中选选择的交交配个体体都为精精英的概概率。4EDDMOEEA 算算法在本节中中，我们们提出了了一类新新的基于于-支配关关系的多多目标进进化算法法。同-MOEEA一样样，它也也可以分分解为算算法1的实例例。
