嵌入遗传算子的混合万有引力搜索算法

魏焕新+++胡招娣

摘 要：一种以遗传算子为基础的混合引力搜索算法被提出用于无约束优化问题的求解，可以避免容易局部最优、收敛速度慢等基本引力搜索算法的弊端。首先，种群多样性通过混沌序列进行维持；其次，对粒子进行引导靠近全局最优区域，通过当前最优粒子与通过概率选择的粒子算出交叉得到的。最后，通过多样性变异操作对当前全局最优粒子操作，避免了局部最优的发生。该方法优秀的寻优性通过8个标准函数运算该算法得到证明。

关键词：混沌；算术交叉；万有引力搜索算法；多样性变异

引言

无约束优化问题可以为工程应用求解数值。通常以下公式对无约束优化问题进行描述。

全局优化方法算法，如蚁群优化、差分进化、粒子群优化、遗传算法是以种群迭代为基础的智能优化算法，其特点是，原理简单、成功率高、独立于求解问题的梯度信息、大概率收敛到问题等。所以，被大量用在无约束优化问题解析中。2009年，Rashedi教授，在科曼大学提出了万有引力搜索算法。该方法极富启发性，通过模拟万有引力定律，利用粒子之间的相互吸引力引发的群体智能，作为指导来进行搜索优化。GSA特点是，少阐述、易操作，其寻优精度和收敛速度都比PSO和GA等智能算法更为优化。

GSA也存在和其它全局优化算法一样的缺点，比如，收敛速度在后期降低，容易局部化经常出现在基于种群迭代搜索的优化算法。很多学者致力对GSA进行优化。Khatibinia和Khosravi共同提出混合GSA算法，通过对其和正交交叉算子进行改进。混凝土重力坝体型应用该算法被优化；Soleimanpour把量子理论融合到GSA中，提出可以优化函数的量子GSA；基于混沌优化的GSA由Gao等提出，其搜索算子是混沌；GSA在权重的基础上被徐遥和王士同改进，将惯性质量作为权重。

本文讲述通过将遗传算子嵌入GSA，来改善目前GSA算法不能开发和勘探同时的问题，解决无约束优化问题。群体多样性是通过混沌序列生成的初始群种进行维持。收敛速度通过变异、交叉操作实现加速的同时可以避免局部最优的出现。该算法通过8个标准测试函数进行验证，结果证明各异的无约束优化问题可以被该算法有效处理。

1 万有引力搜索算法

施力与受力粒子、惯性质量、位置是所有GSA中粒子的特质。粒子在粒子间引力的作用下向大质量例子所处方向移动。适应度相当于粒子的惯性质量，问题的解相当于例子位置。

粒子i在t时刻第d维空间中速度：vid（t）

GAS算法步骤如下：

Step1. 参数设定：在搜索空间，设t=0，随机选取N个粒子的速度、位置进行初始化。

Step2. 所有粒子进行适应度计算；

Step3. 所有粒子进行惯性质量更新计算，运用公式（3）和（4）

Step4.引力系数G（t）使用式（9）更新；

Step5.所有粒子的合力用式（10）计算；

Step6.所有粒子的加速度通过式（11）计算

Step7.所有粒子的速度、位置通過式（12）和（13）计算

Step8. 经过判断，如果结束条件被满足，结束计算，得到最佳答案，如果条件没被满足，重复步骤2。

2 混合万有引力搜索算法（HGSA）

2.1 种群初始化

根据Huapt等的研究，初始群种具有很好的多样性，对以种群迭代搜索为基础的智能优化算法非常有利于得出全局最佳解。对于基础GSA，搜索算法的起点由粒子的初始位置决定的。所以，粒子在一个好的初始群里中位置是呈现一个全面对搜索空间覆盖的趋势。但是，随机产生初始群体一般发生在迭代前的基本GSA，算法的搜索效率被降低的原因是粒子在不是均匀分布在解空间。

混沌的特点是随机性，能根据规律在特定范围进行状态的不断复制，属于是非线性现象。为了实现搜索空间内个体的均匀分布，可以通过初始化混沌序列来实现。在本文中，种群通过混沌序列进行初始化，混沌序列由维Logistic映射产生，是一个一维映射。可用以下公式表达：

2.2 算术交叉算子

GSA局部搜索能力差，全局搜索能力强。本文通过对算术交叉算子，（将当前最优粒子和随机从群体中选择的粒子进行交叉运算）以实现对GSA收敛速度的提升，以及增强其局部搜索能力的目的。表达式为算数交叉：

GSA局部搜索能力差，全局搜索能力强。本文通过对算术交叉算子，（将当前最优粒子和随机从群体中选择的粒子进行交叉运算）以实现对GSA收敛速度的提升，以及增强其局部搜索能力的目的。表达式为算数交叉：

子代粒子x'1和x'2在经过算术交叉操作后，位置一定是位于给定的父代粒子x1和x2之间。所以，为了得到更接近最优解的子代粒子，进行算数交叉操作计算应选取当前最优粒子和群体中随机粒子。算法的收敛速度被提高，局部搜索能力得到加强，由于群通过以上操作被快速的引导去靠近最优粒子，而一般交叉操作的盲目和随机的特性不会出现。

2.3 多样性变异算子

以种群搜索为基础的群智能优化算法在进入GSA进化后期，会出局部最优的现象。群体多样性降低导致算法收敛速度被降低甚至被终止。根本原因是全部2.4 HGSA算法步骤

HGSA算法可以总结为：

Step1.设t=0，算法参数：G0（引力系数），pm（变异概率），（参数），pc（交叉概率），最大迭代次数（），N（种群规模）；

Step2.N个粒子的位置xit、速度vit通过混沌序列进在搜索空间行初始化

Step3.所有粒子适应度被计算；

Step4.粒子的惯性质量通过式（3） 和 （4） 计算更新；

Step5.引力系数G（t） 通过式 （9） 计算更新；

Step6. 全部粒子的合力之和通过式（10）进行计算；全部粒子的加速度通过式（11） 进行更新；

Step7.全部粒子的速度通过式（12） 计算更新；同时其位置通过式 （13） 进行计算更新；

Step8. 并找出当前最优粒子的位置；最优粒子的位置通过计算全部粒子的适应度得出；

Step9.下一代群里中保留当前全局最优解，新的子代粒子是通过当前最优粒子与随机选取群体中粒子进行算数交叉操作得到的。即评估当前群体，确保最优保存。

Step10. 新粒子通过变异操作多样性当前全局最优粒子位置得到；

Step11. 判断算法是否满足终止条件，若满足，则算法结束，输出全局最优解；否则，令t=t+1，返回Step3。进行条件判断。如果满足，结束算法并得到全局最优解；如果不满足，重复Step3，并设t=t+1

3 结束语

通过对物理学中的有引力作用的模拟而开发的群智能随机搜索方法，即万有引力搜索算法。本文通过将遗传算子嵌入万有引力搜索算法而对其进行改进。根据运行8个标准测试函数数据，改进算法针对不同函数（单峰、多封）和基本万有引力搜索算法相比有明显优势，表现为高稳定性和高寻优精度。算法性能是否受参数的影响和如何在约束优化问题中对其应用是下一步的研究方向。

参考文献

[1]许波，彭志平，余建平.一种基于云模型的改进型量子遗传算法[J].计算机应用研究，2011，28（10）：3684-3686.

[2]徐遥，王士同.引力搜索算法的改进[J].计算机工程与应用，2011，4

7（35）：188-192.

[3]Huapt R， Huapt S. Practical genetic algorithm[M]. USA： John Wiley & Sons， 2004.

[4]梁昔明，龙文，龙祖强，等.自适应梯度指导交叉的进化算法[J].小型微型计算机系统，2011，39（7）：1331-1335.