基于-支配的多目标进化算法及自适应调整策略.docx

基于-支配的多目标进化算法及自适应调整策略本文研究工作受国家自然科学基金（No.70571057No.70171002）和“新世纪优秀人才支持计划”(NCET-05-0253)资助。刘鎏男1982年生博士研究生研究方向为多目标进化算法理论及其应用。Email:[e-mail]。李敏强男1965年生教授博士生导师主要研究领域为进化计算理论数据挖掘和机器学习。林丹男1968年生副教授硕士生导师主要研究方向为遗传算法理论及其应用。刘鎏1李敏强1林丹21（天津大学系统工程研究所天津300072）2（天津大学理学院应用数学系天津300072）摘要:本文提出了一类新的基于-支配关系的多目标进化算法。该算法采用配对比较选择和稳态替换策略提高了算法的收敛速度降低了计算时间。首先在保持种群分布性上采用了一种新的基于-支配关系的精英保留策略避免了传统修剪策略所引起的Pareto前沿面的退化。其次根据不同取值分析了算法收敛性提出了一种自适应调整策略。最后通过5个常用的双目标测试函数的计算验证了包括该自适应调整策略的多目标进化算法在求解质量上要显著强于NSGAIISPEA2和-MOEA等主流多目标进化算法。关键词：多目标优化;-支配;进化算法;自适应调整;精英保留策略;稳态策略1.前言求解最优化问题（也称数学规划问题）是指从所有可能的方案中选择最合理的一种以达到目标优化的过程。当优化问题的目标个数多于一个时称之为多目标优化。在通常情况下同一问题中的多个目标函数是彼此矛盾的因此最终结果是获得一系列折衷解。多目标进化算法是指利用进化搜索的技术去解决多目标优化问题。DavidSchaffer[1]提出了第一个多目标进化算法即向量进化遗传算法而后该领域专家又提出了多种多目标进化算法并应用于求解实际问题。Coello[2]总结了目前的多目标进化算法并将它们分为两代：第一代强调简洁第二代强调效率它们之间的主要区别在于精英个体是否被引入种群的进化过程之中。Laumanns[3]归纳了采用精英策略的多目标进化统一模型（AunifiedmodelforMOEAsUMMEA）通过将存储当前所有非被支配个体的种群同一般的进化种群相结合实现精英参与种群的进化。大部分第二代的多目标进化算法如强度Pareto进化算法(SPEA)[4]强度Pareto进化算法2（SPEA2）[5]Pareto包络选择算法（PAES）[6]都符合这样的模型结构。另一个常用的非劣排序遗传算法2（NSGAII）没有直接利用外部种群。它将子代种群和父代种群相结合优先选择其中的精英个体去构成下一代的进化种群。这种策略也实现了精英个体加入种群进化并取得了很好的计算结果。另一个分类标准即是否采用了Pareto支配排序。Goldberg[7]率先将Pareto优化的概念引入多目标进化算法。当前的多目标进化算法大多通过Pareto支配关系的排序来计算种群中个体的适应值从而引导种群朝向Pareto前沿面进化。虽然这种方法可以较好地改善算法的收敛性但是排序过程要耗费大量的计算。为了提高进化算法效率一些研究者采用了稳态的进化策略。所谓稳态是当新个体产生后立即加入种群的下一代进化过程之中如简单进化算法（SEAMO）[8]Pareto收敛遗传算法（PCGA）[9]-多目标进化算法（-MOEA）[10]。在选择个体进入交配池的操作中它们均采用配对比较的方法而没有进行个体适应值的计算。实验结果表明这些基于稳态的进化算法在处理某些问题上要优于基于Pareto排序的算法[811]。另外由于非支配解的数量巨大而外部种群存储容量有限很多修剪策略如PAES中的自适应网格NSGAII中的Crowding-DistanceSPEA中的聚类和SPEA2中的最近距离方法等都在各自算法中发挥了很好的作用。然而正如[12]所述这些修剪策略很可能造成Pareto前沿的退化进而影响到最终种群的收敛。Laummans[13]根据-支配关系提出一种基于网格向量的种群修剪策略可以很好地防止进化过程中种群的退化。这种策略在计算网格向量时除了参数还需要获得各个目标上的最小值并且相同网格中的个体比较需要计算各自的欧式距离相对来说计算量比较大。本文提出了一种新的基于-支配关系的多目标进化算法即-支配多目标进化算法（-dominanceMOEAEDMOEA）。该算法采用一种新的基于-支配关系的修剪策略不仅可以防止退化现象还可以有效的保存极端值个体以保证Pareto前沿面的广度。该算法基于稳态替换策略利用的选择方法可以更加快速有效地到达Pareto前沿面。同时在新算法中采用了新的自适应调整策略实验结果验证了这种新策略的优越性。本文的结构如下：第2节介绍了Pareto优化和-Pareto优