一种基于佳点集原理与引力搜索的新型蜻蜓算法
马骏+项铁铭
摘要：为改进标准蜻蜓算法（DA）存在的收敛质量不高、全局寻优能力欠佳、易陷入局部最优等问题，利用基于佳点集原理的方法初始化种群，将其与万有引力搜索算法（GSA）结合，改进步长更新公式，并引入考虑维度变化的更新全局最优解方法，提出一种新的改进蜻蜓算法（DGSDA）。通过对10个测试函数的测试结果表明，改进后的DGSDA收敛速度快，全局寻优能力强，寻优精度高。
关键词：蜻蜓算法；引力搜索算法；Tent映射；维度变化
DOIDOI：10.11907/rjdk.172139
中图分类号：TP312
文献标识码：A文章编号文章编号：16727800（2018）001008504
Abstract：In order to improve the convergence quality of the standard dragonfly algorithm （DA） is not high， the global optimization ability is poor， and it is easy to fall into the local optimum. In this paper， the population is initialed by the method of good point set， and it is combined with the universal gravitational search algorithm （GSA）， a new improved dragonfly algorithm （DGSDA） is proposed by introducing the formula of updating the global optimal solution considering the change of dimension. The test of 10 test functions shows that the improved DGSDA has a fast convergence speed and strong global search ability.
Key Words：dragonfly algorithm； gravitational search algorithm； tent mapping； dimension
0引言
群体智能（SI）[12]算法近年来引起了人们的广泛重视。通过模拟蜻蜓个体之间的社会行为交流，SeyedaliMirjalili[3]于2015年提出一种新的群体智能优化方法——蜻蜓算法（DA）。在静态群体中，蜻蜓组成若干小群体在某个小型区域来回飞行觅食，对应于全局搜索；在动态群体中，大量蜻蜓聚集在一起朝某个方向飞行一长段距离进行迁移，对应局部开发。作为一种提出时间较短的群体优化算法，标准蜻蜓算法（DA）存在收敛质量不高、全局寻优能力有待提高、易陷入局部最优等问题，因而有待改进。为提高种群初期的探索能力与多样性，本文采用基于佳点集原理的方法初始化种群[4]，将该算法与万有引力搜索算法（GSA）相结合，推动算法向全局最优所在区域集中搜索，降低在局部停滞的可能性。同时，考虑到在全局最优解更新时只注重整体而忽略了维度因素，因此将不同维度上的最优值也纳入考量。通过对给定的10个测试函数进行仿真测试对比表明，改进后的算法具有较强的全局探索能力、理想的收敛速度和较高的鲁棒性。
1标准蜻蜓算法
Reynolds指出[5]，群体行为遵循3个最原始的准则：分离度、对齐度与聚合度。分离度指一个个体避免与之相邻的个体发生碰撞；对齐度指个体与相邻个体沿着某一方向上的速度匹配；聚合度指个体朝着与之相邻个体中心靠拢的趋势。以下是它们在数学上的定义：
定义1每个个体的分离度定义为：
4.2实验结果分析
实验中，仿真运行环境为Windows10操作系统，Intel i5处理器2.90GHz，8G内存，仿真软件MATLAB R2015b。测试结果与标准蜻蜓算法（DA）、粒子群算法（PSO）、遗传算法（GA）、混合引力搜索粒子群算法（PSOGSA）进行对比。为保持数据的客观性，采用相同设置：粒子数30，迭代次数500次，对每个测试函数独立重复运行30次。表3列出了DGSDA和其它4种算法在相同条件下在测试函数上的结果对比。
表3的结果显示，在f1、f2、f7、f8测试函数上，DGSDA能够在5种算法中得到最好的值，全面优于标准DA。从多次运行取均值看，改进后的算法在f1、f2、f3、f4、f5、f7能够得到最好的均值，全面优于标准DA、PSO、GA，有效改进了收敛性，在标准差方面也有相当明显的优势。这是由于本文在初始化时引入佳点集，从而有效改进了易陷入局部最优解的问题，对全局最优解的取舍引入了维度变化的策略。由于文献[9]已经说明PSO、GSA相较于混合改进后的PSOGSA，无论是收敛速度和精度方面都存在着不小的差距，为增强说服力，考虑将PSOGSA、标准蜻蜓算法DA以及改进后的算法作收敛进程的对比。图3分别取两个有代表性的单峰测试函数（f1、f3）和两个多峰测试函数（f6、f7）进行收敛轨迹的对比。由于本文对步长更新的公式进行了改进，同时引入了加速度项，收敛速度有了一定程度提高。从图中还能看到，在标准蜻蜓算法DA停滞，无法向更好的全局最优值靠拢时，DGSDA能够及时跳出局部最优，向更好的全局最优值靠拢，体现了改进算法的有效性。
5结语
本文提出的基于佳点集原理的混合引力搜索蜻蜓算法从种群初始化、步长更新公式、基于维度变化的全局最优解更新方式方面对标准蜻蜓算法进行了改进，在解决高维复杂问题的能力上有了很大提升。不足之處是未能从理论上加以分析，这是今后需要继续研究的方向。同时在应用方面，下一步需要研究如何将算法应用到实际的工程优化上。
摘要：为改进标准蜻蜓算法（DA）存在的收敛质量不高、全局寻优能力欠佳、易陷入局部最优等问题，利用基于佳点集原理的方法初始化种群，将其与万有引力搜索算法（GSA）结合，改进步长更新公式，并引入考虑维度变化的更新全局最优解方法，提出一种新的改进蜻蜓算法（DGSDA）。通过对10个测试函数的测试结果表明，改进后的DGSDA收敛速度快，全局寻优能力强，寻优精度高。
关键词：蜻蜓算法；引力搜索算法；Tent映射；维度变化
DOIDOI：10.11907/rjdk.172139
中图分类号：TP312
文献标识码：A文章编号文章编号：16727800（2018）001008504
Abstract：In order to improve the convergence quality of the standard dragonfly algorithm （DA） is not high， the global optimization ability is poor， and it is easy to fall into the local optimum. In this paper， the population is initialed by the method of good point set， and it is combined with the universal gravitational search algorithm （GSA）， a new improved dragonfly algorithm （DGSDA） is proposed by introducing the formula of updating the global optimal solution considering the change of dimension. The test of 10 test functions shows that the improved DGSDA has a fast convergence speed and strong global search ability.
Key Words：dragonfly algorithm； gravitational search algorithm； tent mapping； dimension
0引言
群体智能（SI）[12]算法近年来引起了人们的广泛重视。通过模拟蜻蜓个体之间的社会行为交流，SeyedaliMirjalili[3]于2015年提出一种新的群体智能优化方法——蜻蜓算法（DA）。在静态群体中，蜻蜓组成若干小群体在某个小型区域来回飞行觅食，对应于全局搜索；在动态群体中，大量蜻蜓聚集在一起朝某个方向飞行一长段距离进行迁移，对应局部开发。作为一种提出时间较短的群体优化算法，标准蜻蜓算法（DA）存在收敛质量不高、全局寻优能力有待提高、易陷入局部最优等问题，因而有待改进。为提高种群初期的探索能力与多样性，本文采用基于佳点集原理的方法初始化种群[4]，将该算法与万有引力搜索算法（GSA）相结合，推动算法向全局最优所在区域集中搜索，降低在局部停滞的可能性。同时，考虑到在全局最优解更新时只注重整体而忽略了维度因素，因此将不同维度上的最优值也纳入考量。通过对给定的10个测试函数进行仿真测试对比表明，改进后的算法具有较强的全局探索能力、理想的收敛速度和较高的鲁棒性。
1标准蜻蜓算法
Reynolds指出[5]，群体行为遵循3个最原始的准则：分离度、对齐度与聚合度。分离度指一个个体避免与之相邻的个体发生碰撞；对齐度指个体与相邻个体沿着某一方向上的速度匹配；聚合度指个体朝着与之相邻个体中心靠拢的趋势。以下是它们在数学上的定义：
定义1每个个体的分离度定义为：
4.2实验结果分析
实验中，仿真运行环境为Windows10操作系统，Intel i5处理器2.90GHz，8G内存，仿真软件MATLAB R2015b。测试结果与标准蜻蜓算法（DA）、粒子群算法（PSO）、遗传算法（GA）、混合引力搜索粒子群算法（PSOGSA）进行对比。为保持数据的客观性，采用相同设置：粒子数30，迭代次数500次，对每个测试函数独立重复运行30次。表3列出了DGSDA和其它4种算法在相同条件下在测试函数上的结果对比。
表3的结果显示，在f1、f2、f7、f8测试函数上，DGSDA能够在5种算法中得到最好的值，全面优于标准DA。从多次运行取均值看，改进后的算法在f1、f2、f3、f4、f5、f7能够得到最好的均值，全面优于标准DA、PSO、GA，有效改进了收敛性，在标准差方面也有相当明显的优势。这是由于本文在初始化时引入佳点集，从而有效改进了易陷入局部最优解的问题，对全局最优解的取舍引入了维度变化的策略。由于文献[9]已经说明PSO、GSA相较于混合改进后的PSOGSA，无论是收敛速度和精度方面都存在着不小的差距，为增强说服力，考虑将PSOGSA、标准蜻蜓算法DA以及改进后的算法作收敛进程的对比。图3分别取两个有代表性的单峰测试函数（f1、f3）和两个多峰测试函数（f6、f7）进行收敛轨迹的对比。由于本文对步长更新的公式进行了改进，同时引入了加速度项，收敛速度有了一定程度提高。从图中还能看到，在标准蜻蜓算法DA停滞，无法向更好的全局最优值靠拢时，DGSDA能够及时跳出局部最优，向更好的全局最优值靠拢，体现了改进算法的有效性。
5结语
本文提出的基于佳点集原理的混合引力搜索蜻蜓算法从种群初始化、步长更新公式、基于维度变化的全局最优解更新方式方面对标准蜻蜓算法进行了改进，在解决高维复杂问题的能力上有了很大提升。不足之處是未能从理论上加以分析，这是今后需要继续研究的方向。同时在应用方面，下一步需要研究如何将算法应用到实际的工程优化上。
