基于交叉因子和模拟退火的群搜索优化算法

杨文璐，宁玉富，2

（1.山东师范大学 管理科学与工程学院，山东 济南250014；2.德州学院不确定系统实验室，山东德州253023）

0 引 言

群集智能算法是一些启发于群居性生物的觅食、筑巢等行为而形成的优化算法，正越来越受到人们的重视，吸引了大量国内外学者的学习与研究。与遗传算法和蚁群算法相类似，群搜索优化 （group search optimizer，GSO）算法也是一种基于群集智能的演化计算技术。该算法是由He和Wu在2006年根据群居动物如鸟、鱼、狮子的觅食行为而提出的全局优化算法［1，2］。研究和实践表明，GSO在多维空间函数寻优和动态目标寻优等方面有着收敛速度快、非劣解质量高及鲁棒性好等优点，所以被广泛应用在函数优化、医学及电力系统研究等工程设计中［3，4］。但是，与此同时GSO算法也存在早熟收敛、搜索精度不高、后期迭代效率不高，以及在后期运算中容易陷入局部极优点等缺点［4］。针对其在应用中存在的以上问题，本文在原有GSO算法的基础上进行了改进，提出了一种基于交叉因子和模拟退火的群搜索优化 （integrated cross－factor and metropolis rule group search optimizer，CMGSO）算法。CMGSO 算法不仅可以通过增加粒子的多样性来提高搜索的精确度及迭代效率，而且可以充分利用群集智能的优良特性来跳出局部最优的限制，同时加快了原算法的收敛速度，并提高了解决高维函数全局寻优问题的优化效率。

1 CMGSO算法

1.1 GSO算法

在最优化问题中，未知最优解被随机分布于解集合中的一个未知点所标识，则在GSO算法中，群体的任一个体都可以被假设为在解集合中寻找到的最优解所在的那个点。因此GSO算法基于PS模型，并在此基础上使用了游荡者策略和动物视觉搜索机制。在动物觅食的策略中，主要有：①发现食物；②追随发现者，一同分享事物；③个别游荡寻找食物。该算法根据动物觅食策略将群成员分为发现者（producer）、加入者 （scrounger）和游荡者 （ranger）3种，并利用生物学的视觉搜索原理对食物进行搜索，其中所有成员都有初始化的位置与角度。在算法开始后的迭代计算过程中，都将会对所有个体的适应值进行计算比较，并从中搜索出拥有最佳适应值的个体设置为原始发现者，之后原始发现者会在当前位置上对周围一切可行解区域进行寻优搜索，寻找是否存在比当前位置更好的位置，如果发现更好位置便向新位置移动，否则保持原位置不变；而群体中的其它成员中80% 作为Scrounger按搜索公式跟随Producer进行搜索，其余的20%作为Ranger按搜索方程在觅食区域内进行随机地游弋［5］。在迭代过程中发现者始终保持最优位置，加入者则向发现者靠拢，游荡者起到了加大搜索范围的作用，每个个体都可以在3种角色中切换，直至满足结束条件时，算法结束。

每次迭代中Producer（Xp）的搜索过程如下：

步骤1 Producer（Xp）从度角0开始进行搜索，并按搜索式 （1）在前方寻找一个点，同样分别按搜索式 （2）和 （3）在左方和右方再各自搜索一个点

其中，r1∈R1是均值为0、方差为1的一个正态分布随机数；r2∈Rn－1为 ［0，1］间的均匀分布随机数表示搜索方向。

步骤2 对所有位置的适应值进行比较计算后，若新位置适应值优于老位置适应值，则此时Producer便主动跳至新位置；反之，Producer便保持不动，并按角度调整式（4）进行搜索方向变换，以进入到下面的迭代搜寻中

式中：αmax——最大的搜索角度。

步骤3 在算法的迭代中，使用者设定哨兵 “n”，用于重置搜索过程。当Producer经过多次迭代计算直到n次迭代，仍未搜索更优解，则它将会按照公式 （5）把角度重新转回到0度

同时，群体中的Scrounger跟随Producer并加入到对更优解的搜索过程中，如式 （6）中所示

Ranger用于避免算法陷入到局部最优解的情况，所以分布于整个群体的内部，且以随机步长来进行独立搜索，这种随机走动策略是极为有效地随机资源分布寻找方法。假设第m次迭代中的第i个个体为Ranger，则它将按照角度搜索式 （7）、步长搜索式 （8）和位置搜索式 （9）进行迭代计算

据此，群搜索优化算法中的发现者、加入者和游荡者这3种角色，分别按照上文中提到的各自的迭代公式来进行搜索，从而使其寻找到最优的食物来源［6］。

1.2 交叉因子算法

我们在标准GSO算法的基础上借鉴了遗传算法中的组合交叉思想［7］，通过采用交叉因子产生出代表新解集的种群来替换原有种群。该过程将导致像自然进化一样的后代种群比前代更加适应环境，从而加快搜索到问题的全局最优解。

在CMGSO算法中，根据精英保留策略在每次迭代过程中选取Scrounger中适应度值较高的一半群成员直接进入下一代，同时用适应度好的前一半群成员，与后一半群成员两两之间随机通过位置和搜索角度进行交叉，产生子代，再和父代作比较，并通过利用Metropolis准则作为判定谁为新的群成员进入下一次迭代的标准，得到新的群体，这样通过交叉操作既可以增加群成员多样性，跳出局部最优，同时还可以加快算法的收敛速度。交叉操作公式如下

其中，x是D 维的位置向量；fCi（x）和fPi（x）两个函数分别指明的是孩子成员还是父母成员的位置；p是D维均匀分布的随机数向量，p的每个分量都在 ［0，1］取值

1.3 模拟退火算法

模拟退火算法是根据固体退火原理提出的，它是一种基于Metropolis准则的通用随机优化算法。该算法基于物理中固体从较高初始温度出发，随着温度的不断下降，固体内部能力发生相应变化这一特质，并结合概率的突跳特性使其在解空间中可以随机对目标函数的全局最优解进行寻找，利用这一特点可以有效避免陷入局部最优解的问题［8］。冷却进度表 （cooling schedule）是用来控制退火过程这一机制的。在冷却进度表中主要包括一下几个参数，固体温度的初始值t、衰减因子Δt、迭代次数L及停止条件S［9］。由Metropolis准则可知，当固体受到扰动时固体状态发生改变，状态通过固体的内能来表示，固体内能Ei小于Ej时，Ej＝Ei；反之当Ei大于Ej时，则根据固体处于该状态时的概率P来进行判断［10－11］，概率P的公式如下

式中：ΔE为其改变量；K 为Boltzmann常数［12－13］。

1.4 CMGSO算法

在CMGSO算法中对于由交叉操作更新所得到的新加入者Xik＋1来说，如何确定其能否成为替代原有个体，加入到本次迭代中，主要通过Metropolis准则的优值增量Δf＝f（）－f）计算来作为判定标准。上式中的f（x）为所要满足的目标函数。将由交叉操作得到的的位置和搜索角度代入目标函数中来计算，如果Δf＜0，则替换原有的成员，进行下一步的计算，否则通过Metropolis准则中的概率exp（－Δf／MaxIter）来判定是否用替换原有成员进入第k次迭代，即公式 （16）。这样保存了较好的移动方向以便预测到更好的移动位置的同时又能达到概率性跳出局部最优值的目的

式中：rand—— ［0，1］间的随机数，MaxIter——最大迭代次数。

对于群体中的Ranger来说，在第k次的迭代中，对于新产生的，如果f（）－f（）＞0，则不选择更新，即，否则，进行更新。

在SGSO的基础上通过引入交叉因子和模拟退火算法的思想改进了SGSO算法，提高了该算法的优化效率，其算法描述如下：

（1）选定GSO种群规模S；

（2）初始化每个群成员的位置和角度；

（3）对每个成员计算其适应度值；

（4）比较各个群成员的适应度值，记录其自身最优值Xbest和群体最优成员Producer；

（5）根据公式 （1）（2）（3）和公式 （4）改变粒子的位置和搜索角度；

（6）执行轮盘赌选择和本文2.2中提到的交叉操作，生成新一代种群；

（7）将更新得到的运用本文2.3中提到的模拟退火算法选择是否对其进行保留；

（8）检查是否满足GSO算法终止条件，若否，转至第（4）步，继续；若是，则求出最优解。

2 CMGSO算法分析及性能测试

2.1 测试函数

本文在这里主要选取了4中较常用的测试函数，它们分别为Sphere函数、Rosenbrock函数、Griewank函数和Rastrign函数，其中前两种函数常被用于某算法对于单模态优化能力的测试，而后两种函数则常被用于某算法对于多模态函数优化能力的测试。这4个测试函数见表1。

表1 4个常用测试函数表达式

2.2 性能测试及结果分析

本节中拟用4个常用的测试函数对CMGSO的全局寻优性能进行了测试，并将其与标准GSO算法和PSO算法进行了比较。在测试中，将种群大小设为30，每个测试函数运行次数设为50次，每次运行代数设为1000代。表2和表3分别显示了函数f1－f4在30维和3维的情况下运行50次的结果平均值和标准差，实验结果见表2和表3。

表2 f1－f4在30维时运行的平均值和标准差

表3 f1－f4在3维时运行的平均值和标准差

从表2中可以看出，在高维情况下标准GSO算法比PSO算法寻优效率更高，寻优结果更好，并且结果相对稳定。通过标准测试函数f1－f4的测试，本文的CMGSO所得到的结果更趋向于已知最优解。在多次运算后，所得结果的平均值明显优于标准GSO算法得到的结果。进一步证明了CMGSO算法继承了标准GSO算法在高维情况下所具有的优势，且进一步提高了优化的效果。同时，通过对比3个算法在多次试验中结果的标准，可以看出CMGSO算法标准差相对较小，这充分说明了该算法具有比较稳定的优化性能。表3则是3个算法在低维中的优化表现，CMGSO算法与标准GSO算法和PSO算法相比都有较好的数据结果，且算法的稳定性较高。由测试结果可知，CMGSO算法相对于标准的GSO和PSO等优化算法而言，提高了全局搜索能力和收敛速度，减小了陷入局部最优的可能性，并对整体的优化性能有了很好的改善和提高。

图1至图4分别为标准PSO、GSO和CMGSO算法在4个测试函数f1－f4中的收敛性能及寻优性能的曲线比较图，从这四个图中能清晰地看出经过改进后的GSO在收敛速度和寻优效果上与标准的PSO和GSO相比存在一定程度的优越性。

图1 f1（x）的收敛曲线效果对比

3 结束语

本文提出一种基于交叉因子和模拟退火的群搜索优化算法CMGSO，它主要是在原有GSO的基础上加入并融合了交叉因子和模拟退火的算子，解决了标准GSO中存在的早熟收敛、搜索精度不高、后期迭代效率不高，以及在后期运算中容易陷入局部极优点等问题，并能取得更好的最优解。

本文通过实验证明了CMGSO与标准的PSO和GSO相比，有较好的整体收敛性能及较优的寻优效果，并在整体上提高了原有GSO算法的优化性能，为解决优化问题又提供了—种新的选择与方案。

但是在低维函数情况下其优化效果并不如高维函数的理想，说明CMGSO算法在低维中的优化性能还有待于进一步的改进和提高，这将成为该算法下一步研究方向。

：

［1］HE S，WU Q H.A novel group search optimizer inspired by animal behavioural ［C］／／IEEE Congress on Evolutionary Computation，2006：4415－4421.

［2］WU Q H，HE S，Saunders J R.Group search optimizer：An optimization algorithm inspired by animal searching behavior［J］.IEEE Transactions on Evolutionary Computation，2009，13 （5）：973－990.

［3］ZHANG Wenwen，TENG Shaohua，LI Lijuan.Improved group search optimization algorithm ［J］.Computer Engineering and Applications，2009，45 （4）：48－51 （in Chinese）. ［张雯雯，腾少华，李丽娟.改进的群搜索优化算法 ［J］.计算机工程与应用，2009，45 （4）：48－51.］

［4］LIU Feng，TAN Guang，LI Lijuan.A quick group search optimizer with passive congregation and its application in spatial structures［J］.Journal of Engineering Design，2010，17 （6）：420－425 （in Chinese）.［刘锋，覃广，李丽娟.快速被动群搜索优化算法及其在空间结构中的应用 ［J］.工程设计学报，2010，17 （6）：420－425.］

［5］FANG Juanyan，ZENG Jianchao，CUI Zhihua.A mixed group search optimization algorithm and its application ［D］.Taiyuan：Taiyuan University of Science and Technology，Computer Science and Technology Institute，2010 （in Chinese）.［房 娟艳，曾建潮，崔志华.混合群搜索优化算法及其应用研究［D］.太原：太原科技大学，计算机科学与技术学院，2010.］

［6］SHEN Hai，ZHU Yunlong，NIU Ben，et al.An improved group search optimizer for mechanical design optimization problems［J］.Progress in Natural Science，2009 （19）：91－97.

［7］LIU Qinjie，CHEN Guiming，LIU Xiaofang，et al.Genetic algorithm based SVM parameter composition optimization ［J］.Computer Applications and Software，2012，29 （4）：94－100（in Chinese）.［刘鲭洁，陈桂明，刘小方，等.基于遗传算法的SVM参数组合优化 ［J］.计算机应用与软件，2012，29（4）：94－100.］

［8］CHEN Xiaojuan，XHEN Jing.QoS routing algorithm based on genetic simulated anncaling algorithm ［J］.Application Research of Computers，2012，29 （12）：4680－4682 （in Chinese）.［陈晓娟，陈婧.基于遗传模拟退火的QoS单播路由算法 ［J］.计算机应用研究，2012，29（12）：4680－4682.］

［9］ZHOU Yuting，LIU Guangyuan，LAI Xiangwei.Applications of simulated annealing－immune particle swarm optimization in emotion recognition of galvanic skin response signal［J］.Journal of Computer Applications，2011，31 （10）：2814－2817 （in Chinese）.［周钰婷，刘光远，赖祥伟.模拟退火免疫粒子群算法在皮肤电信号情感识别中的应用 ［J］.计算机应用，2011，31 （10）：2814－2817.］

［10］Lukasik S，Zak S.Firefly algorithm for continuous constrained optimization task ［J］.72ICCCI，Lecture Notes in Artificial Intelligence，2009，57 （96）：97－100.

［11］YANY Xinshe.Firefly algorithm，stochastic test functions and design optimisation ［J］.International Journal of Bio－inspired Computation，2010，2 （2）：78－84.

［12］XU Pengfei，MIAO Qiguan，LI Weisheng，et al.Adaptive simulated annealing algorithm and tabu search algorithm based on the function complexity ［J］.Acta Electronica Sinica，2012，40 （6）：1218－1222 （in Chinese）.［许鹏飞，苗启广，李伟生，张军英.基于函数复杂度的自适应模拟退火和禁忌搜索新算法 ［J］.电子学报，2012，40 （6）：1218－1222.］

［13］LI L J，XU X T，LIU F.The group search optimizer and its application to truss structure design ［J］.Advances in Structural Engineering，2010，13 （1）：43－51.