基于动态平衡的多目标粒子群优化算法

张海波

摘 要： 传统粒子群优化算法在求解动态优化问题时，种群将逐渐收敛，从而在问题变化后无法进一步寻优，针对上述问题，提出了一种基于动态平衡的多目标粒子群优化算法。采用双种群策略以动态平衡算法的探索能力与开发强度，其中一个子种群在动态调整的网格中运行混沌搜索，确保种群多样性符合要求的同时，能够有效提升搜索的效率。利用快速收缩多目标粒子群算法，对另外的子种群进行计算，收敛到Pareto前沿。通过一组标准测试问题对所提方法进行了驗证，实验结果显示所提算法无论在收敛速度还是在优化精度上都优于其它典型多目标进化算法。

关键词： 动态平衡; 混沌; 自适应网格; 多目标优化; 粒子群算法

中图分类号： TP311

文献标志码： A

文章编号：1007-757X（2019）06-0150-04

Abstract： In the traditional particle swarm optimization algorithm for solving the dynamic optimization problem， the population will gradually converge， thus the algorithm may lose further optimization ability after the environment dynamically changes. In order to solve this problem， a dynamic adaptive grid is presented based on multi-objective particle swarm optimization. In the algorithm， a double-population strategy is designed to explore and develop intensity balance algorithm， one of the subpopulation runs for adaptive grid search， so as to ensure the population diversity and the adaptive mechanism to improve the search efficiency， another subpopulation uses multi-objective particle swarm algorithm for rapid contraction. The algorithm can rapidly converge to the Pareto front under environmental change. Through a set of standard test problems， the experimental results show that the proposed algorithm both in convergence speed and optimization accuracy are better than other typical multi-objective evolutionary algorithms.

Key words： Dynamic balance; Chaos; Adaptive grid; Multi-objective optimization; Particle swarm algorithm

0 引言

动态多目标优化问题集合了当前优化问题的两个难点即需要优化的目标不仅为多个、相互冲突[1-3]，解决上述问题不仅需要算法能搜索到分布尽可能广泛的Pareto最优解，而且还要快速适应环境变化，使优化结果能跟踪Pareto最优前沿移动。

进化计算、粒子群优化算法等基于种群随机搜索的自然启发式算法被用来求解动态多目标优化问题[4]。这些算法与传统算法之间的差异性总结为：第一，基于种群随机搜索的目标优化算法能够同时获取多个Pareto最优解[5]。第二、这些算法对环境变化具有自适应能力，而不需要重新优化[6]。第三、不要求获得模型信息，并且适用于求解计算复杂的优化问题[7]。

NSGA2是由Kalyanmoy Deb等人提出的多目标遗传算法，其特点表现在三个方面，一是尽可能的减少用户主观决定的参数;二是非支配集排序时间复杂程度更低;三是维护精英个体，以便更加有效的提高多目标遗传算法的效果。空间搜索是通过跟踪当前最优粒子的方式来实现的，所以算法相对简单、采用的参数少、算法计算速度较快[8]。Moore 和Chapman首次提出了粒子群优化算法在多目标问题求解方面的应用设想，并通过问题分析加以验证[9]。传统的进化算法、粒子群优化算法在求解动态优化问题时，在运算后期，种群慢慢收敛，无法获取环境动态变化信息之后，就无法继续寻优[10]。

本文针对上述问题，改进对多目标粒子群优化算法，提出MOEA-AR算法。采用双种群策略以动态平衡算法的探索能力与开发强度，其中一个子种群在动态调整的网格中运行混沌搜索，确保种群多样性符合要求并有效提升搜索的效率。利用快速收缩多目标粒子群算法，对另外的子种群进行计算，在环境变化后能快速收敛到Pareto前沿。通过一组标准测试问题对算法进行验证，结果显示所提算法在收敛速度和优化精度上都优于其它典型的多目标进化算法。

1 多目标优化概念

2 动态多目标粒子群优化算法

2.1 主程序

MOEA-AR算法不仅能够保证种群多样性，种群可以平展的扩散到Pareto前沿，提升算法收敛的效果，有效缩短最优结果寻找时间。MOEA-AR算法的流程和实施步骤如图1所示。

第一步：算法初始化。在决策空间中，对种群之中的粒子位置严格给予随机赋值，且粒子运动速度为零。粒子个体向导为其位置，档案集为空。

第二步：种群的评价。判断每个粒子在目标函数中的赋值情况，按照现有目标函数的取值将维度空间分为10个部分。

第三步：更新粒子个体向导。如果粒子运动目标值决定个体向导，那么粒子的当前位置就是该粒子的最新个体向导。如果目标值向量和个体向导之间不相互匹配，那么将个

体向导更新为当前位置，如果二者相互匹配，则不进行更新。

第四步：按照粒子的支配关系，选择种群的非支配集，对档案集进行更新。此处设计档案集的规模为100，如果现有数量已经超出最大规模，那么沿着粒子密度从大到小的顺序开始删除密度大的档案集粒子网格。

第五步：算法迭代的最高次数为300次，如果超出这个规模则停止继续搜索，输出运算后的档案集。

第六步：利用混沌算子，其初始值随机，迭代后的种群具有分布均匀、种类多样的特征，可以由其替代原始的例子种群。

第七步：全部向导选择网格密度最小的例子，如果多个例子同时符合条件，则随机选择。然后按照自适应网格粒子群优化算法对粒子群的位置和速度进行计算更新。

2.2 自适应网格粒子群优化算法

在自适应网格例子群优化算法的设计过程中，包含两个子种群，其中一个执行自适应网格搜索算子，另外一个执行收缩的PSO搜索算子，获得种群最优解，根据反馈结果调整种群的网格或者向导。自适应网格粒子群算法流程如图2所示。

第五步：调整网格

按照gbest粒子所在的位置调整其运动搜索的范圍。网格的调整案例如图3所示。

为了简化表达，假设每一个维度的决策变量能够均分为3段，形成一个两维的空间，gbest处于第五区间。调整之前，粒子在网格1范围内搜索，调整之后，粒子要在1、2、4、5的网格内搜索。调整之前，粒子2在网格2的范围内搜索，调整后要在网格2和网格5构成的范围内搜索。

上式中，Ω2q表示的是第q个空间粒子的网格搜索范围，rand（Ω2q）表示的是在Ω2q的区间内随机生成的点。

2.3 混沌映射算子

引入混沌映射算子，可以获取伪随机的遍历非重复迭代结果，所以对于初始化种群的求解来说是非常适用的。Logistic映射的应用是最为广泛的，在[0， 1]的区间内不存在稳定的周期点或者是不动的点，所以一直处于一种非常理想的混沌运动中。但是，Logistic映射的点在[0， 1]的区间内是符合雪夫分布的。Tent映射完全映射在[0， 1]的区间内，但计算时小数部分的二进制数会左移，受到字长限制，迭代之后分布会趋于零。因此，Logistic映射和Tent映射都不适合种群初始化。

本文提出一种混沌映射算子模型，利用Logistic扰动来有效消除Tent混沌映射后的不动点。可以将上述算法表示为式（10）。

3 仿真实验

按照标准的仿真测试手段来比较分析NSGA2和MOEA-AR算法之间的差异，验证算法性能。

3.1 标准的测试函数

用DTLZ2问题来测试算法的运算性能，并将其数学模型表示如下式（12）。

上式中，n表示的是决策变量的个数，M表示的是目标的个数，XM是第n-M+1个变量。

3.2 性能评价方案

在判断多目标粒子群优化算法的求解效果时，可以将搜索空间Pareto最优解作为评价指标。收敛距离定义为真实的Pareto的最优前沿和Pareto之间的欧氏距离如式（13）

（m，n）表示的是m和n之间的欧氏距离，Ω表示的是优化的真实Pareto最优前沿，Ψ表示的是近似Pareto最优解集，L（ψ）表示的是获得最优解的收敛距离。f表示的是以综合单目标排序优化算法计算得出的最优解，L（f）表示其收敛距离。

3.3 实验结果

实验中选择三组参数，一组：n=10，M=2、4、5、6、8;二组：n=15，M=10、12;三组：n=20，M=15，分析目标不断增加时的算法优化下过，各组分别运行10次，取平均值，消除随机因素影响。结果如图4—图7所示。

4 总结

由实验结果可以发现，在优化问题较简单即具有两个目标时，两种方法都具有较好的优化效果，然而随着优化问题复杂度增大，NSGA2优化效果越来越差，而本文所提算法能够始终保持较好的收敛精度，因此本文所提方法好于经典的NSGA2算法。

参考文献

[1] 安伟刚， 李为吉. 单纯形-多目标粒子群优化方法的

混合算法[J]. 西北工业大学学报， 2004， 22（5）：563-566.

[2] Pareto档案多目标粒子群优化[J]. 模式识别与人工智能， 2006， 19（4）：475-480.

[3] Sebastian E. Feedback control for optimal process operation[J]. Journal of Process Control， 2007， 17（3）： 203-219.

[4] 陈民铀， 张聪誉， 罗辞勇. 自适应进化多目标粒子群优化算法[J]. 控制与决策， 2009， 24（12）：1851-1855.

[5] 赵宏伟.云计算环境下基于改进粒子群优化算法的多目标资源调度策略研究[C]//大数据学术会议. 2014：.

[6] 胡旺， Gary G YEN，张鑫.基于Pareto熵的多目标粒子群优化算法[J].软件学报， 2014（5）：1025-1050.

[7] 耿焕同， 陈正鹏， 陈哲，等.基于平衡搜索策略的多目标粒子群优化算法[J].模式识别与人工智能， 2017， 30（3）：224-234.

[8] 杨培宏， 刘连光， 刘春明，等. 基于粒子群优化算法的电网GIC-Q多目标优化策略[J]. 电力自动化设备， 2017， 37（3）：93-99.

[9] Moore J， Chapman R. Application of particle swarm to multiobjective optimization[R]. Department of Computer Science and Software Engineering， Auburn University， 1999.

[10] 韩红桂， 卢薇， 乔俊飞. 一种基于多样性信息和收敛度的多目标粒子群优化算法[J]. 电子学报， 2018， 46（2）：315-324.

（收稿日期： 2019.02.28）