一种改进的群搜索优化算法

安晓伟， 苏宏升

(兰州交通大学 自动化与电气工程学院，甘肃 兰州 730070)

一种改进的群搜索优化算法

安晓伟， 苏宏升

(兰州交通大学 自动化与电气工程学院，甘肃 兰州 730070)

摘要：群搜索优化算法是建立在群居动物觅食行为基础上的新型启发式算法，具有算法简单、易于实现的特点.标准群搜索优化算法(GSO)基于发现-追随的寻优策略，由于追随者搜索模式过于单一，从而容易陷入局部最优.为了提高标准GSO算法的收敛速度与收敛精度，提出一种改进群搜索优化算法(IGSO).在该算法中，发现者保持原有的寻优方式，追随者执行鱼群算法的寻优模式，通过引入鱼群算法的觅食、追尾、聚群与随机行为，使搜索方式多样化，可以同时考虑种群的个体最优与群体最优，从而有效避免陷入局部最优.通过6个基准测试函数对两种算法进行比较，实验结果表明，改进的群搜索优化算法优于标准群搜索优化算法.

关键词：群搜索优化算法；函数优化；人工鱼群算法

0引言

启发式算法由于其运行方式受到自然运行规律启发而得到应用，其特点是通过模拟动物组织的群体行为进行寻优，如蜂群、鸟群等.群搜索优化算法(GSO)是一种常见的启发式算法.

GSO是基于一般动物群体的觅食模式的原理，即发现-搜寻(PS)模式[1-2]，将种群个体分为发现者，追随者与游荡者.目前群搜索优化算法已在解决实际问题的应用中得到实现.Wu等人提出了一种多发现者的群搜索优化算法(GSOMP)，该方法在柔性交流输电系统的多目标优化问题中得到应用[3].He和Li利用经过GSO算法训练的人工神经网络进行机器设备的在线状态监测[4].Yan和Shi提出结合了PSO和GSO优点的混合算法(GSPSO)[5].

传统GSO算法的搜索方式是种群中的最优个体(发现者)进行随机搜索，并将最优食物位置信息传递给种群中的其余个体.然而，该方法依赖于追随者的搜索速度与精度，从而容易陷入局部最优解.笔者提出一种改进的群搜索优化算法(IGSO)，将鱼群算法的行为策略融入追随者的搜寻行为，在该算法中，发现者保持标准GSO算法搜索程序，而追随者将执行鱼群算法的寻优程序.该算法特点在于不仅考虑种群的先前信息，而且通过引入鱼群算法的拥挤度因子与视觉参数来评估当前种群的个体情况，从而改变了追随者以往随机搜索的方式，增加了搜索方式的多样性，从而使优化算法的收敛速度和精度提高.

1标准群搜索优化算法

GSO算法是一种融合了动物觅食搜索行为与群居理论的仿生算法，该算法采用发现-追寻模式作为算法的基本框架，以群居动物的社会觅食策略作为算法寻优的基本策略.将群体中的个体按照觅食行为中的角色分为发现者、追随者与游荡者.

(1)

在GSO算法的迭代过程中，选取每一次迭代中具有最佳个体适应度值的个体作为发现者，其余的个体作为追随者与游荡者.发现者从0°开始，然后随机搜索3个方向(分别为初始点的前方，右方和左方)，若搜索到适应度值更佳的位置，则发现者前进至该位置；反之，发现者停留在当前位置，并转换搜索角度，继续搜寻.若发现者历经多次迭代无法找到比当前适应度值更优的位置，则返回初始点.

发现者位置迭代公式为

前方区域

(2)

右侧区域

(3)

左侧区域

(4)

表示发现者从0°处开始搜索，并分别搜索0°的前、右，左3个方向.

转向角度

φk+1=φk+r2αmax,

(5)

式中：r1是均值为0,方差为1的正态分布的随机数;r2为[0,1]间均匀分布的随机数;lmax与αmax是最大搜索距离与最大转向角.

除发现者外，在种群中随机选择一部分个体作为追随者，追随者沿着发现者的路径进行追寻搜索.并在适当时机与发现者相互转换，转换公式为

式中：r3为[0,1]间均匀分布的随机数.

此外，种群中的剩余成员被选为游荡者，游荡者在搜索区域随机搜索如式(6)所示

φk+1=φk+r2αmax，

(6)

式中：αmax是最大转向角；r2为[0,1]间均匀分布的随机数。

在追随者和游荡者的寻优过程中，若找到某位置比当前发现者及其剩余个体的位置更优，则在下次迭代时该个体将转换为发现者.

2人工鱼群算法

人工鱼群算法是一种基于鱼群群体智能的仿生算法[6-7].其模型建立在鱼群觅食过程中会向着食物浓度高的区域进行游动这一行为.搜索过程是通过构建鱼群中个体的底层行为，以局部寻优来实现全局最优.不同于传统优化算法，其同时考虑了个体最优和群体最优，不仅考虑每只鱼的当前状态而且考虑种群中相邻鱼的状态.

算法可以表述为在一个n维的目标搜索空间中存在由N条人工鱼组成的一个群体.第i条人工鱼的状态可表示为向量Xi=(xi1,xi2,…,xiQ)，其中i=1,2,…,N.目标函数的适应度值Y=f(X)，将Xi带入其中求得Yi.相邻两条鱼的距离可以表示为

在人工鱼群算法中，人工鱼群中的个体具有彼此不同的移动方向.根据鱼群个体的当前状态将行为分为四类.

(1) 觅食行为

觅食行为反映了鱼具有向食物富集区域移动的能力.设人工鱼当前处于状态为Xi，适应值为Yi，在其视野范围内随机选择一个状态Xj，并计算Yj，若Yj

(7)

Xj=Xi+Visual·rand().

(8)

试探trynumber次后，如果仍不能找到更好的食物聚集位置，则执行随机行为

Leap(Xi)=Xi+rand()step.

(9)

(2) 追尾行为

设第i条人工鱼的当前状态为Xi，其适应值为Yi.探索当前邻域内(Dij

Yp1,

(9)

则按式(10)向Xp移动一步，否则执行觅食行为,

(10)

(3) 聚群行为

聚群行为反映了鱼的个体在避免过分拥挤的条件下向邻近的伙伴中心靠近的行为.设第i条人工鱼当前状态为Xi，适应值为Yi，以自身为中心向周围区域探索，搜索到邻域的伙伴数目为nf，形成集合Si，

Si={Xi‖Xj-Xi‖≤Visual,j=1,2,…i-1,i+1,…,N}.

如果Si非空，则该集合中心位置为

计算该中心适应度值，如果满足

Ycentre1,

(11)

则表明伙伴中心有较多的食物并且不太拥挤，则按式(12)向中心位置前进一步，否则执行觅食行为.

(12)

(4) 随机行为

指鱼的个体执行随机移动的行为，可表示为

Leap(Xi)=Xi+rand()step.

3改进的群搜索优化算法

通过采用人工鱼群算法的搜索模式改变了标准GSO算法中追随者的搜索过程.在此算法中，发现者-追随者模型仍然被沿用，追随者执行人工鱼群算法的寻优策略，分为觅食、追尾、聚群与随机行为.

追随者的行为选择方式为先进行各种行为试探，如追尾、聚群等行为，选择向最优方向前进最快的行为，然后选择执行操作后状态较优的行为来实际执行，缺省的行为为觅食行为.也就是选择各行为中使得人工鱼的下一个状态最优的行为，若无最优行为，则采取随机行为.

追尾行为被应用于追随者追寻发现者的寻优过程中，其位置变换公式如式(13)所示.r1是均值为0,方差为1正态分布的随机数.函数rand()表示返回(0,1)区间中的一个任意数，

(13)

采用聚群行为对追随者寻优方式进行优化，此方式利用鱼群中的个体靠近邻近伙伴中心的特点，使追随者充分获得种群中其他个体的位置信息，提高了种群间的信息交流，从而综合考虑了群体最优与个体最优，使寻优方式得以优化.其位置更新公式如式(14)所示,

对于觅食行为，追随者在自己可见的区域去寻找一个更好的位置.如果经过最大试探次数trynumber获得成功，追随者会执行公式(15)进行位置更新,

(15)

如果追随者经过经过最大试探次数trynumber仍然无法找到更好的个体适应值，追随者将随机移动见公式(16).r1是均值为0,方差为1正态分布的随机数.函数rand()表示返回(0,1)区间中的一个任意数,

(16)

发现者和游荡者的搜索方式与标准GSO算法相同.

综上所述，改进的群搜索优化算法步骤如下：① 确定种群数量，进行初始化操作;② 求出所有成员的个体适应度值，选取适应度值最优的个体成为发现者;③ 根据式(2)～式(5)更新发现者的寻优行为;④ 选剩余成员的80%成为追随者，按式(13)～式(16)更新追随者的行为;⑤ 根据式(6)更新游荡者的行为;⑥ 若满足终止条件，则输出当前发现者的适应度值,否则，返回步骤(2).

4实验与仿真分析

为了验证该算法的性能，笔者将IGSO算法与标准GSO算法作比较.验证过程是在MATLAB7.6的环境下进行的.算法的性能由以下6个测试函数所衡量，参数见表1.

球体模型

广义Rosenbrock函数

广义Schwefel函数

广义Rastrigin函数

Ackley函数

广义Griewank函数

为了便于比较，IGSO中的参数设定与文献[1]中的一致，即初始搜索角度φ0为π/4，常数a

从图1(a)中可以看出，标准GSO出现了不收敛的情况，而IGSO在1 500次迭代之后就开始稳定的收敛，逐渐趋近于全局最优值.由图(b)和(c)可以看出，标准GSO迭代初期有较大的斜率，表明该算法有持续的快速收敛能力，但在搜索进行过程中陷入局部极值，此时人工鱼群搜索策略的引入使得改进群搜索优化算法快速跳出局部极值，开始分组寻优，继续向全局最优解的方向搜索，虽耗时略长，但是收敛值明显优于标准GSO算法，显示出较高的精度.从(d)图中可以看出标准GSO收敛较快，迭代次数较少，但是水平部分的线段表明搜索过早进入停滞阶段，易陷入早熟，寻优精度不如引入改进后的群搜索优化算法.从图(e)、(f)的优化曲线可以看出，改进的群搜索优化算法在搜索后期表现出较强的优势，而标准GSO算法则陷入局部最优.

从表2中所知：改进的群搜索优化算法(IGSO)的测试平均值的优化结果优于标准GSO算法.

5结论

对标准GSO算法进行改进，将人工鱼群算法中人工鱼个体的聚群、追尾、觅食行为引入追随者的搜索策略之中，从而较大程度地提高算法的收敛速度.而在文献[8-10]中，针对发现者的行为作出一些改进，并且是算法的收敛速度得到一定程度的提升.接下来的进一步的研究工作是尝试将本文针对追随者的改进方法与上述文献中针对发现者的改进方法进行有机结合，进一步提高算法的效率.

参考文献：

[1]张雯雰,滕少华,李丽娟.改进的群搜索优化算法[J].计算机工程与应用,2009,45(4):48-52.

[2]HE S,WU Q H,SUNDERS J R.Group search optimizer:an optimization algorithm inspired by animal searching behavior[J].Evolutionary Computation,2009,13(5):973-990.

[3]KANG Q,LAN T,YAN Y,et al.Group search optimizer based optimal location and capacity of distributed generations[J]. Neuro Computing,2012,78(1):55-63.

[4]CHEN Y,ZHU Q,XU H.Finding rough set reducts with fish swarm algorithm[J].Knowledge Based Systems,2015(2):74-77.

[5]XIE H B,LIU F,LI L J,et al.Research on topology optimization of truss structures based on the improved group search optimizer[J].Neuro Computing, 2013,12 (11):707-712.

[6]刘宪林,乔云飞.基于人工鱼群算法的电力系统稳定器参数优化研究[J].郑州大学学报:工学版,2013,34(5):68-72．

[7]刘锋,覃广,李丽娟.快速被动群搜索优化算法及其在空间结构中的应用[J].工程设计学报,2010,17(6):420-425.

[8]李鹏.基于群搜索优化算法的配电网重构[J].电网技术,2012,6(28):43-47.

[9]房娟艳.混合群搜索优化算法及其应用研究[D].太原:太原科技大学机电学院,2010.

[10]姚健.群搜索算法与二次插值法的混合算法及其应用研究[D].太原:太原科技大学机电学院,2010.

An Improved Group Search Optimization Algorithm

AN Xiao-wei1, SU Hong-sheng2

(1.School of Automation and Electrical Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China; 2.School of Automation and Electrical Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)

Abstract:Group Search Optimization (GSO) is a swarm intelligence approach inspired by animal searching behavior and group living theory. It is simple and efficient, and easy to implement. The searching mode of the scrounger is oversimplified, so it falls into local optimum easily. In order to enhance its convergence speed and precision, the improved Group Search Optimization (IGSO) is proposed. Inheriting the strategy of producer-scrounger of GSO, IGSO introduces the strategy of the Artificial Fish Swarm (AFS) algorithm to the behavior of the scrounger. By introducing prey, fellow, swarm and leap of the AFS algorithm, searching forms is diversified, as well as the best individuals of group and best groups of population can be considered, IGSO can effectively avoid the local optimum. Six benchmark functions are used to evaluate the performance of two algorithms. Experimental results show that IGSO is able to achieve better results than standard GSO.

Key words:group searching optimization; function optimization; artificial fish swarm algorithm

中图分类号：TM301.6

文献标志码：A

doi:10.3969/j.issn.1671-6833.2015.02.023

文章编号:1671-6833(2015)02-0105-05

作者简介：安晓伟 (1987-)，男，新疆乌鲁木齐人，硕士研究生，主要从事人工智能算法在电力系统中的应用相关研究，E-mail:neuqauto@126.com.

基金项目：国家自然科学基金资助项目(61263004);甘肃省自然科学基金资助项目(1212RJZA071)

收稿日期:2014-10-12；

修订日期：2014-12-03