多目标优化算法改进综述

谢秋红

(陆军特种作战学院，广东 广州 510000)

一、引言

在工程和科学上的许多问题都可以抽象为多目标优化问题，比如废水处理工艺、水的分配系统和空气动力学设计问题等，这些问题需要同时满足多个目标。为了解决多目标优化问题，多目标进化算法(Multi-objective Evolutionary Algorithms，MOEAs)应运而生。1975年，Holland教授提出了遗传算法。Schaffer于1985年首次将多目标优化算法与遗传算法结合，提出向量评估遗传算法。1989年，Goldberg使用Pareto理论解决多目标优化问题，从此，多目标优化算法研究成为热门研究方向。常见的算法包括：非支配排序遗传算法(NSGA和NSGA-II) 、多目标优化粒子群算法(MOPSO)、帕累托强度进化算法(SPEA和SPEA2)等等。其中，MOPSO算法收敛速度快、容易实现、低计算代价，容易覆盖基准函数的帕累托阵面。但是MOPSO存在两个问题：如何更新gbest和pbest；如何快速收敛到最优解的帕累托阵面。下面从传统算法和最新研究两个角度梳理多目标优化算法。

二、多目标优化算法近几年改进成果

对多目标优化算法近几年的改进算法进行梳理，并进行简单的介绍和述评。

（一）适应性AMPSO算法

文献[1]新提出一种适应性的多目标优化算法(AdaptiveMultiobject ivePSO，AMPSO)。该算法的工作集中在两点：基于解空间分布熵提出一种适应性的gbest搜索机制；基于种群间距信息(SP)提出一种适应性的飞行参数机制来平衡全局搜索和粒子的局部搜索能力。在这两点的改造下，算法不仅具有了较高的精度，而且搜索出的最优解有很好的多样性。

（二）自适应梯度AGMOPSO算法

文献[2]提出一种自适应梯度的多目标粒子群优化（AGMOPSO）算法、基于多目标梯度(stocktickerMOG)方法和自适应参数的机制，提高了计算性能。算法中，多目标梯度方法用来更新档案提高了算法的收敛速度和进化过程中的局部查找。同时，根据粒子的多样性信息建立了飞行参数的自适应机制，用来平衡算法的收敛性和多样性，可以找到更好的传播解决方案。多目标梯度法和自适应飞行参数的机制使得算法的解决方案有更好的多样性，具有更快的收敛到真正的帕累托最优前沿。此外，作者讨论了AGMOPSO任何成功应用的前提条件。最后，该算法与其他的多目标粒子群优化算法和两个国家的最先进的多目标算法的比较来验证计算性能。

（三）存储导向的MOPS算法

文献[3]提出了一种新的外部档案引导MOPSO算法(AgMOPSO)，其中用于速度更新的领袖是从外部存档中选择。群体领袖pbest和gbest的选择多目标粒子群优化算法的设计是很重要的。这些领袖有望有效地引导蜂群接近真正的帕累托最优前沿。本文创新点体现在三个方面：(1)作者通过分解方法将多目标优化问题（MOPS）转化为一系列子问题，每个粒子是由三个从外部存档选择的领袖决定，转化为相应的优化子问题；(2)作者在外部存档上运行基于免疫的进化策略，因为领袖都选取自外部存档，使用克隆选择范式有助于加速收敛。因此，在外部存档中对个体进行改进，将有助于指导基于粒子群算法的搜索，从而为真实的遗传算法提供快速逼近；(3)新的pbest和gbest的更新方式。一般来说，个体极值、局部最好并进行分别访问每个粒子、当地群、整个群。然而在AgMOPSO算法中，作为分解的方法是利用变换将MOPs转化为一组子问题，同时优化各子问题，加快AgMOPSO收敛。

（四）多目标大规模MPSO算法

文献[3，4]设计了新的多目标大规模优化粒子群算法(Many-objective large-scale optimization problems，MaOLSOPs)。根据分布式并行计算的特点将现有研究成果分为三类：多目标大规模优化、多目标优化和分布式并行，并研究粒子群的并行属性。算法步骤为：首先根据目标将种群分为M+1个，多出的一个为针对所有目标的种群；将种群中多个变量进行拆分分组，称为类别；最后，类别中的多个个体可以进一步分解为多个集合，每个集合对应一个单独的计算资源。作者设计了并行框架，但没有给出具体的实验。

（五）大规模并行加速MPSO算法

文献[5]针对具体的并行加速计算，提出一种基于异构多核和GPU加速的粒子群法。具体是用英特尔的矢量协加速器(Intel Xeon Phicoprocessors)和图形处理单元(Graphics Processing Units，GPUs)，而异构的方法能减轻粒子群算法的时间复杂度。作者在定义的并行可分为函数层面、算法层面。在函数层面，复合函数可通过矩阵乘法并行操作，但是由于大量的条件限制，无法进行进一步并行优化。但是复合函数的Weierstrass分量需要一定数量的计算资源，因此这部分可并行。CUDA提供了线性代数的工具包—— CUDA基本线性代数子程序，实现了用于GPU优化的BLAS程序，因此可方便进行并行的矩阵乘法计算；在算法层面，PSO本身就是一个时间密集型任务，而APSO中定义的距离参数可通过距离矩阵的计算获得。作者将矩阵拆分为多个子矩阵进行分别计算，每个子矩阵又交给多个线程并行计算。

（六）基于几何结构的MPSO算法

文献[6]新提出一种基于几何结构的粒子群算法，具有快速搜索和鲁棒性的特点，适用三个目标以上的多目标优化问题。目标问题之间的三种关联关系：正相关、负相关、不相关。基于此，作者进行了三个以上目标的维度缩减操作。理想情况下，同一个簇内的目标是正相关的，但在目标函数较多的情况下，很容易发生负相关情况。因此，提出一种模糊语义的方法进行簇调整，设置阈值决定关联是否可以接受。

测试算法的两种方法。(1)给定最大迭代次数，不限定精度地运行待测试算法，当达到最大迭代次数时算法终止，比较测试函数运算结果。(2)给定最大迭代次数和精度，运行待测试算法，当达到最大迭代次数或最优值满足所给定的精度时算法终止，比较各算法所需平均迭代次数。

三、总结

多目标优化算法的优势和局限可以通过评价方法进行评估，部分算法沿用了将多目标优化转换为小目标优化问题的思想，并在收敛速度、计算性能、计算精度等其它方面进行改进，其中自适应梯度AGMOPSO算法和存储导向的MOPS算法加快了收敛速度，适应性AMPSO算法提高了计算精度，并增加了最优解的多样性，大规模并行加速MPSO算法减轻了算法的时间复杂度。