多目标群体智能算法-多目标群体智能算法

2023-11-26 理论教育版权反馈

【摘要】：进化算法以其搜索的全局性逐渐成为解决MOP问题的有效工具。以下按照Coello Coello[14，15]的总结方式来简介多目标进化优化领域的一些代表性算法。第一代多目标进化算法1989年，Goldberg建议用非支配排序和小生境技术来解决MOP问题。第一代多目标进化算法以基于非支配排序的选择和基于共享函数的多样性保持为其主要特点，但这一代MOEA算法的缺点也十分明显。因此，第二代多目标进化算法普遍使用了精英策略。

人们在求解现实中的各类优化问题时发现，有些优化问题在现有的传统方法和计算机软硬件等条件下无法在合理的时间内获得满意的答案，因此，迫切需要发展新的方法来解决这些问题，而向自然界学习已成为探索复杂优化问题解决方案的一种途径。在人类向自然学习的过程中，以模拟自然进化过程、自然现象以及生物体行为特征为根本的一类计算方法也得以诞生和发展，这类算法通常统称为进化算法(Evolutionary Algorithm，EA)。

进化算法是一类基于种群的、模拟自然进化的随机搜索算法。进化算法在没有任何先验知识的情况下，通过迭代循环搜索黑盒问题的解或解集。进化算法一般范式如下:随机初始化种群，在每一次迭代过程中利用父代种群生成子代种群，再利用适应度函数筛选优秀个体作为下一代种群，直至终止条件满足为止。进化算法以其搜索的全局性逐渐成为解决MOP问题的有效工具。

早在1985年，Schaffer[13]就提出了矢量评价遗传算法(Vector-Evaluated Genetic Algorithm，VEGA)，其被视为利用进化算法求解MOP问题的开创性工作。20世纪90年代以后，各国研究者基于不同的研究背景和视角相继提出了许多种多目标进化算法(Multi-Objective Evolutionary Algorithm，MOEA)，这些MOEA算法以其单次运算可以获得整个解集的优良特性而获得了良好的发展。以下按照Coello Coello[14，15]的总结方式来简介多目标进化优化领域的一些代表性算法。

(1)第一代多目标进化算法

1989年，Goldberg建议用非支配排序和小生境技术来解决MOP问题。非支配排序的过程为:对当前种群中的非支配个体分配等级1，并将其从竞争中移去；然后从当前种群中选出非支配个体，并对其分配等级2，……，如此重复，直至种群中所有个体都分配到等级次序后结束。小生境技术则用来保持种群的多样性，防止群体早熟收敛。Goldberg虽然没有把他的思想具体实施到MOEA算法中，但其思想对以后的研究具有重要的启发意义。随后，一些学者基于这种思想提出了MOGA[16]、NSGA[17]和NPGA[18]算法等。

Fonseca和Fleming在1993年提出MOGA(Multi-objective Genetic Algorithm，MOGA)算法，该方法对每个个体划分等级(rank)，所有非支配个体的等级定义为1，其他个体的等级定义为支配它的个体数目加1，具有相同等级的个体用适应度共享机制进行选择。其适应度赋值方式如下:首先，种群按照等级排序；然后，对所有个体分配适应度，方法是采用Goldberg提出的线性或非线性插值的方法来分配，具有相同等级的个体适应度值是一样的。通过适应度共享机制采用随机采样进行选择。MOGA由于过于依赖共享函数的选择，而且可能产生较大的选择压力，容易导致早熟收敛。

NSGA算法也是基于Goldberg的非支配排序的思想设计的。首先确定种群中的非支配解，然后赋予它们一个很大的虚拟适应度值。为了保持种群的多样性，这些非支配解利用它们虚拟的适应度值进行共享。随后，这些非支配个体暂时不予考虑，接下来从余下的种群中确定第2批非支配个体，然后赋予它们一个比先前非支配个体共享后的最小适应度值还要小的虚拟适应度值。重复该过程，直至整个种群都被划分为若干等级为止。

NPGA算法构造了基于Pareto支配关系的锦标赛选择机制，其具体思想如下:随机地从进化种群中选择两个个体，再随机地从进化群体中选取一个比较集合，如果只有其中一个个体不受比较集的支配，则这个个体被选中进入下一代；当它们全部支配或全部被支配于该比较集合时，则采用小生境技术实现共享来选取其中一个个体进入下一代。算法选取共享适应值大的个体进入下一代。在该算法中，确定合适的小生境半径和比较集合的规模具有一定的难度。

第一代多目标进化算法以基于非支配排序的选择和基于共享函数的多样性保持为其主要特点，但这一代MOEA算法的缺点也十分明显。首先，能否找到替代小生境(共享函数)的方法来保持种群的多样性。其次，适应度共享是由Goldberg和Richardson[19]针对多峰函数优化提出来的，它们需要关于有限峰数量的先验知识和解空间小生境均匀分布的假设，而对于MOP问题，同样需要确定共享半径的先验信息，且其计算复杂度为种群大小的平方。(www.chuimin.cn)

(2)第二代多目标进化算法

第二代多目标进化算法以NSGA-Ⅱ(Non-dominated Sorting Genetic AlgorithmⅡ，NSGA-Ⅱ)[20]、强度Pareto进化算法(Strength Pareto Evolutionary Algorithm，SPEA)[21]及其改进版本SPEA2[22]、Pareto存档的进化策略(Pareto Archived Evolutionary Strategy，PAES)[23]等为代表。由于当前种群中的非支配解不一定非支配于算法此前产生的解，保存算法此前得到的非支配解集显得尤为重要。精英策略不仅择优保留到当前为止所获得的非支配解，而且其中部分优秀个体也可通过某种选择策略被复制到下一代种群。精英策略能使算法的性能维持单调非减。理论上也已证明，精英策略是保证进化算法收敛的必要因素之一。因此，第二代多目标进化算法普遍使用了精英策略。在这一代算法中，除了部分算法如NSGA-Ⅱ等采用(μ＋λ)之选择来实现精英策略，其他算法的精英策略主要通过创建一个外部种群保存历代获得的非支配解，并利用当前代的非支配解对外部档案集合实施更新操作。

在NSGA-Ⅱ中，对父代种群Pt中的个体执行仿二进制交叉和多项式变异，产生后代种群Qt，然后对Pt和Qt合并后的群体Rt进行分级排序。新的父种群Pt＋1按级别高者优先的原则使用Rt中的个体进行填充，其中最后填入的一些同级个体按拥挤距离大者优先的原则进行选择。该算法产生新一代种群的过程即是利用父子竞争的(μ＋λ)之选择来实现精英策略的。

在SPEA中，采用外部种群保留迄今为止所获得的非支配解，而且外部种群中的非支配解也会执行进化操作。在每一代中，外部种群和当前的父种群进行合并。对于合并种群中的所有非支配解，按照它们支配其他解的计数进行适应度分配。为了兼顾解的收敛性和分布性，支配更多解的非支配解被赋予更高的适应度，另外被更多解所支配的解个体也被分配更高的适应度。在SPEA的改进版本SPEA2中，外部档案的规模保持不变，如果非支配解的数量少于档案集的容量，则使用被支配解填充档案集。另外，SPEA2还使用了与SPEA略有不同的适应度分配机制，且它利用了k-最近邻方法来区分适应度相同的解。

在PAES算法中也使用档案集来保存非支配个体。PAES使用了(1＋1)的进化策略，即在父个体与其产生的子个体之间竞争生存机会，若子个体支配父个体，则子个体被接受为下一代的父个体，反之，若父个体支配子个体，则抛弃子个体，继续产生新的个体。如果父个体与子个体彼此非支配，则执行多样性保持策略进行取舍。具体的做法是，子个体与档案集中的个体进行比较，移除档案集中被子个体所支配的解，并接受子个体为下一代的父个体；若档案集中没有解被子个体所支配，则检查父个体与子个体在档案集中的拥挤程度，若父个体处于更拥挤的区域，则接受子个体为新的父个体，并加入档案集中。

在PAES的改进版本PESA[24]中，该算法利用了SPEA和PAES的优点，PESA使用了两个种群，一个父种群和一个规模更大的档案集。基于非支配的概念和PAES中的拥挤度的概念，使用新产生的子个体来更新档案集。而在PESA的改进版本PESA-Ⅱ[25]中，首先以目标空间超盒中解的数量作为选择依据来选择超盒，然后从选择的超盒中随机选取一个要保留的解。实验结果表明，PESA-Ⅱ基于区域的选择过程要优于PESA中基于个体的选择过程。

除了上述提及的算法，还有一些其他的多目标进化算法，如Veldhuizen等[26]提出的多目标混乱遗传算法(Multi-objective Messy Genetic Algorithm，MOMGA)、Coello Coello等[27]提出的Micro-GA等。按照上述的分类依据，它们亦可归为第二代多目标进化算法，这些算法的独特之处在于它们采用了新的选择策略或变化算子。

多目标群体智能算法-多目标群体智能算法

相关推荐