多目标群体智能算法的研究成果

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

【摘要】：例如，基于分布估计算法提出的RM-MEDA算法[20]、将传统的数学规划方法与进化算法相结合提出的MOEA/D[21]等。这些新型进化范例的引入提高了MOEA算法解题的效率与效果，它们为MOP问题的求解开辟了更广阔的空间。这一类MOEA算法避免了Pareto占优引起的大量比较问题，但由于超体积本身的计算量较大，需要引入蒙特卡罗估计等方法来提高计算速度。因此，单链模式便成为影响MOEAs收敛的重要潜在因素。

进化算法是根据生物学中遗传与进化的原理，仿效基因、染色体等物质表达方式，遵循达尔文“物竞天择、适者生存”的选择机理，使随机生成的初始解通过复制、交叉和变异等遗传操作不断迭代进化，并逐步逼近最优解。EA算法很好地吸收了生物界中“适者生存”和随机信息交互的思想，它既能消除解中不适应的因素，又能利用原有解的一些知识，最终获得全局的解个体。EA采用了随机化的定向搜索机制求解实际问题，它的迭代过程看似无序，实则有序，整个群体从总体上看是不断地适应环境的。

进化算法具有一些适于求解MOP问题的特征，这些特征集中表现在两方面:一是EA能够同时处理一组解个体(并行地处理种群中的若干个解个体)，算法每运行一次即能获得多个有效的解个体；二是EA对问题均衡面的形状和连续性不敏感，因此它能很好地逼近非凸性或不连续的均衡面或曲线。

自Schaffer[11]提出第一个真正意义上的多目标进化算法(Multi-objective Evolutionary Algorithm，MOEA)以来，各国研究者基于不同的应用背景和实际问题相继提出了各种不同的MOEA算法，使得MOEA已发展成为求解MOP问题的主流方法之一。

早期的MOEA算法以基于Pareto等级的个体选择和基于适应度共享的多样性保持为主要特征，代表性的算法有MOGA[12]、NSGA[13]和NPGA[14]等，这类算法一般采用小生境技术保持种群的多样性，需要用户预先给定共享半径参数，而且算法对共享半径参数较敏感。

之后，基于精英保留机制的多目标进化算法流行起来，其中代表性的算法包括SPEA2[15]、PAES[16]、PESA[17]、PESA-Ⅱ[18]和NSGA-Ⅱ[19]等，这类算法大多显式地采用一个外部档案保留非支配个体，并运用一些不同于小生境技术的多样性保持策略，例如基于聚类的方法、基于拥挤距离的方法和基于空间超格的方法等。精英保留策略不仅可用于算法求解结果的输出，而且可防止种群的退化，它是保证进化算法收敛的必要条件。

从2003年至今，多目标进化优化前沿领域的研究呈现出新的特点，一些新的进化机制被引入多目标优化领域。例如，基于分布估计算法提出的RM-MEDA算法[20]、将传统的数学规划方法与进化算法相结合提出的MOEA/D[21]等。这些新型进化范例的引入提高了MOEA算法解题的效率与效果，它们为MOP问题的求解开辟了更广阔的空间。(www.chuimin.cn)

此外，MOEA算法经常应用各种评估指标来度量算法解集的质量，因此在MOEA搜索过程中通过直接优化某个性能指标就是一个很好的策略。这类算法以IBEA[22]和HypE[23]等算法为代表，其基本原理是用直接优化Pareto近似集合的评估指标的方法来直接优化原MOP问题，这实际上是将多目标优化问题转化为一个单目标优化问题。在这类方法中，超体积指标最为常用。这一类MOEA算法避免了Pareto占优引起的大量比较问题，但由于超体积本身的计算量较大，需要引入蒙特卡罗估计等方法来提高计算速度。

近年来，将一些MOEA算法的算子(组件)和元启发式方法或概念有机结合起来设计混合型MOEA算法渐已成为MOEA研究的新的趋势之一。例如，Molina等[24]将分散搜索和禁忌搜索结合以解决非线性多目标优化问题；Soliman等[25]将协同进化与局部搜索的思想融入多目标差分进化算法中，以指导搜索朝Pareto最优解逼近。混合型MOEA算法可以利用每个MOEA或元启发式方法的长处，进行优势互补，从而可克服单个的MOEA或元启发式方法所固有的局限性，可进一步增强算法在解空间搜索的效果。

然而，已有的多目标进化算法基本上是采用单链结构实现的，即种群中的个体用一条单独的链表示其基因结构，这种表示方法简单，进化操作执行方便，但也存在明显不足，即个体携带的遗传信息量少，如不采用一定的机制，群体易出现退化。主流的多目标进化算法一般直接或间接地使用外部档案来保留精英个体，防止种群退化，促进算法收敛。因此，单链模式便成为影响MOEAs收敛的重要潜在因素。

Goldberg等[26]对单链模式进行过改进，提出一种变长染色体遗传算法(MGA)；Van等[27]提出将积木块假说和MGA的思想扩充到多目标进化领域，提出了多目标变长染色体遗传算法(MOMGA)；Zydallis等[28]针对MOMGA在PEI阶段耗时严重的缺陷做了改进，提出了MOMGA-2算法；Matayoshi[29]用一种带角连接的双染色体遗传算法解决二维条带包装的单目标优化问题，取得了较好的效果；Guo等[30]用一种改进的双倍体遗传算法解决单目标的车间作业调度问题，在全局搜索能力和收敛性方面均有较大的改善。

与已有的研究不同，我们提出一种双链结构的多目标进化算法DCMOEA[31]，它是一种双链模式的多目标进化算法，在多目标进化优化的研究中尚未发现类似的工作。DCMOEA的特点在于:它用两条相对独立的基因链表示种群个体，使个体能携带大量的遗传信息，有利于抑制种群退化，促进算法收敛；进化过程中搜索到的优良个体均保留在种群中，无须设置外部归档集；利用ε支配方法保持解群的多样性，比较实验表明了该策略具有明显的优势。

多目标群体智能算法的研究成果

相关推荐