搜索
多目标优化算法——11级计算一班20113745陆慧玲近年来,多目标优化问题求解已成为演化计算的一个重要研究方向,而基于Pareto最优概念的多目标演化算法则是当前演化计算的研究热点。多目标演化算法的研究目标是使算法种群快速收敛并均匀分布于问题的非劣最优域。最优化问题是工程实践和科学研究中主要的问题形式之一，其中，仅有一个目标函数的最优化问题称为单目标优化问题，目标函数超过一个并且需要同时处理的最优化问题称为多目标优化问题(multiobjectiveoptimizationprob-lems，简称MOPs)。对于多目标优化问题，一个解对于某个目标来说可能是较好的，而对于其他目标来讲可能是较差的，因此，存在一个折衷解的集合，称为Pareto最优解集(Paretooptimalset)或非支配解集(nondominatedset)。起初，多目标优化问题往往通过加权等方式转化为单目标问题，然后用数学规划的方法来求解，每次只能得到一种权值情况下的最优解。同时，由于多目标优化问题的目标函数和约束函数可能是非线性、不可微或不连续的，传统的数学规划方法往往效率较低，且它们对于权重值或目标给定的次序较敏感。进化算法通过在代与代之间维持由潜在解组成的种群来实现全局搜索，这种从种群到种群的方法对于搜索多目标优化问题的Pareto最优解集是很有用的。第一代进化多目标优化算法以Goldberg的建议为萌芽。1989年，Goldberg建议用非支配排序和小生境技术来解决多目标优化问题。非支配排序的过程为：对当前种群中的非支配个体分配等级1，并将其从竞争中移去；然后从当前种群中选出非支配个体，并对其分配等级2，该过程持续到种群中所有个体都分配到次序后结束。小生境技术用来保持种群多样性，防止早熟。Goldberg虽然没有把他的思想具体实施到进化多目标优化中，但是其思想对以后的学者来说，具有启发意义。随后，一些学者基于这种思想提出了MOGA，NSGA和NPGA。从20世纪末期开始，进化多目标优化领域的研究趋势发生了巨大的变化，l999年，Zitzler等人提出了SPEA。该方法使精英保留机制在进化多目标优化领域流行起来。第二代进化多目标优化算法的诞生就是以精英保留策略的引入为标志。在进化多目标优化领域，精英保留策略指的是采用一个外部种群(相对于原来个体种群而言)来保留非支配个体。(1)SPEA和SPEA2SPEA是Zitzler和Thiele在1999年提出来的算法。在该算法中，个体的适应度又称为Pareto强度，非支配集中个体的适应度定义为其所支配的个体总数在群体中所占的比重，其他个体的适应度定义为支配它的个体总数加1，约定适应度低的个体对应着较高的选择概率。除了进化种群以外，还设置了一个保存当前非支配个体的外部种群，当外部种群的个体数目超过约定值时，则用聚类技术来删减个体。采用锦标赛选择从进化群体和外部种群中选择个体进入交配池，进行交叉、变异操作。该算法的计算复杂度高达种群大小的立方。SEPA2是Zitzler和Thiele在2001年提出的对SPEA的改进版本。他们在适应度分配策略、个体分布性的评估方法以及非支配解集的更新三个方面进行了改进。在SPEA2中，个体的适应度函数为f)=R(f)+D(f)，其中，R(i)同时考虑到个体i在外部种群和进化种群中的个体支配信息09(0是由个体i到它的第k个邻近个体的距离决定的拥挤度度量。在构造新群体时，首先进行环境选择，然后进行交配选择。在进行环境选择时，首先选择适应度小于1的个体进入外部种群，当这些个体数目小于外部种群的大小时，选择进化种群中适应度较低的个体；当这些个体数目大于外部种群的大小时，则运用环境选择进行删减。在交配选择中，运用锦标赛机制选择个体进入交配池。SPEA2引入了基于近邻规则的环境选择，简化了SPEA中基于聚类的外部种群更新方法。虽然其计算复杂度仍为种群规模的立方，但是，基于近邻规则的环境选择得出的解分布的均匀性是很多其他方法无法超越的。(2)PAES,PESA和PESA—IIPAES采用(1+1)进化策略对当前一个解进行变异操作，然后对变异后的个体进行评价，比较它与变异前个体的支配关系，采用精英保留策略保留其中较好的。该算法的经典之处在于引进了空间超格的机制来保持种群的多样性，每一个个体分配进一个格子。该算法的时问复杂度为O(Nx)，其中，Ⅳ为进化种群的大小，为外部种群的大小。该算法的空间超格的策略被以后许多进化多目标算法所采。随后，Come等人基于这种空间超格的思想提出了PESA。PESA设置了一个内部种群和一个外部种群，进化时将内部种群的非支配个体并入到外部种群中，当一个新个体进入外部种群时，同时要在外部种群中淘汰一个个体，具体的方法是在外部种群中寻找拥挤系数最大的个体并将其删除，如果同时存在多个个体具有相同的拥挤系数，则随机地删除一个。一个个体的拥挤系数是指该个体所对应的超格中所聚集个体的数目。Come等人在2001年对PESA作了进一步改进。称为PESA-II，提出了基于区域选择的概念，与基于个体选择的PESA相比，PESA。II用网格选择代替个体选择，在一定程度上提高了算法的效率。