一种新的小生境鱼群优化算法

(西南交通大学数学学院，四川 成都 611731)

·计算机软件理论、技术与应用·

一种新的小生境鱼群优化算法

徐翔燕，黄天民

(西南交通大学数学学院，四川 成都 611731)

针对鱼群算法后期收敛速度慢和难以找到精确最优解的缺点，结合进化论中的小生境技术，提出一种新的小生境鱼群优化算法。通过鱼群个体之间的距离找到具有相似距离的个体组成小生境种群，在该种群内执行鱼群算法的聚群、追尾及觅食行为，所有个体经过其小生境群体的进化后，找到最优的个体存到下一代的鱼群中，直到找到满意的适应值。通过几个典型的多峰测试函数验证算法的性能。仿真结果表明，算法的收敛性、寻优性均达到良好的效果。

鱼群算法；小生境技术；多峰测试函数

人工鱼群算法(artificial fish—swarm algorithm，AFSA)，是2002年由李晓磊等[1]提出的一种新型自适应寻优算法。AFSA算法具有对初值选择不敏感、鲁棒性强、全局收敛性好、简单易实现和使用灵活等优良性能。目前，人工鱼群算法已应用于组合优化[2-3]、数据挖掘[4]、神经网络优化[5]、信号处理[6]、水库优化调度[7]、图象分割[8]等诸多领域，然而，随着优化问题的复杂化，基本人工鱼群算法也存在不足:1)对于局部极值非常突出或收敛十分平缓的情况，人工鱼易在局部极值或全局极值点附近过早的聚集，导致后期精度改善明显变缓；2)视野和步长的随机性和随机行为的存在，使得寻优难以得到很高的精度。针对鱼群算法的不足，AFSA的改进算法主要有以下几个方面：1)引入生存机制和竞争机制[9]；2)动态调整人工鱼的视野和步长[10]；3)与其他智能优化算法融合[11-13]。

进化论中，生物总是选择与自己形状、特征相近的物种聚在一起，并在同类中交配繁衍后代，“人以群分，物以类聚”是一种很常见的现象，而物种赖以生存的资源环境，我们称之为小生境(niches)[14]。小生境技术中最著名且用得最多的就是1987年Goldberg等提出的基于共享机制(fitness sharing)的小生境实现方法(简称FSGA)[15]。该小生境技术的基本理论思想为：利用反映群体中个体之间的相似程度的共享函数调整群体中个体的适应值，以保证群体多样性，因而在以后的小生境群体的进化过程中，算法能根据调整后的新的适应值进行选择运算。

近年来，人们将小生境技术引入到遗传算法、粒子群算法等智能优化算法中，提高了算法的性能。为了避免鱼群算法出现早熟现象，算法后期收敛速度慢，收敛精度低等缺点，本文提出一种新的小生境鱼群算法优化算法，其基本思想为：在每一代进化前，根据鱼群个体之间的距离划分小生境种群，每个小生境种群由具有相似距离的个体组成，利用鱼群算法更新小生境内个体状态。实验仿真说明，该算法提高了收敛速度和精度。

1 基本人工鱼群算法(AFSA)

在一片水域中，鱼往往能通过视觉或嗅觉自行或尾随其他鱼找到食物浓度高的地方，所以鱼聚集多的地方一般都是食物浓度高的地方。人工鱼群算法就是根据鱼的这一特性，模拟鱼的觅食、聚群及追尾行为，从而实现寻优。其数学模型描述如下：

1.1觅食行为

设人工鱼当前状态为Xi，在其视野感知范围内随机选择一个状态Xj，如果Yi

(1)

反之，则在其视野范围内重新选择随机状态，判断是否满足前进条件，反复尝试Try-number次后，若仍不满足前进条件，则随机移动一步：

Xi=Xi+Rand() 。

(2)

1.2聚群行为

设人工鱼当前状态为Xi，搜索其视野感知范围内的伙伴数目nf及中心位置Xc，如果Yc>δ·Yi·nf(0<δ<1)，表明中心位置不太拥挤且中心位置状态优于当前人工鱼状态，则向中心位置前进一步：

(3)

否则，执行觅食行为。

1.3追尾行为

设人工鱼当前状态为Xi，搜索其视野感知范围内的伙伴数目nf及Ym最大的状态Xm，若此时Ym>δ·Yi·nf(0<δ<1)，则状态Xm优于人工鱼的当前位置状态，向Xm的位置前进一步：

(4)

否则，执行觅食行为。

2 小生境鱼群优化算法

小生境技术源于生物学中的小生境(Niche)概念，是指生物界中相同种类的个体生活在一起，共同繁衍后代，而不同种类的个体相互分离。小生境技术中最著名及用得最多的可能是1987年Goldberg等提出的基于共享机制(fitness sharing)的小生境实现方法(简称FSGA)[14]。所谓“共享”是指在特定环境中共同生存的同种生物分享有限的资源，生物之间通过协调达到共同进化，对于适应能力弱的生物，在资源不足的前提下，将会被逐渐淘汰。该小生境技术的基本理论思想为：利用反映群体中个体之间的相似程度的共享函数调整群体中个体的适应值，以保证群体多样性，因而在以后的小生境群体的进化过程中，算法能根据调整后的新的适应值进行选择运算。

新的小生境鱼群优化算法基本思想为：首先根据小生境技术确定小生境群体；然后在小生境群体中执行鱼群优化算法对鱼群进行更新(其中鱼群的群体最优值仅在该小生境群体中起作用)；最后对于更新后的群体，利用共享机制提高个体的适应度, 对于适应度最低的个体，利用罚函数对相应的鱼群个体进行处罚，保留每个鱼群的群体最优个体，直到满足终止条件。

1)小生境群体的划分。

对于人工鱼个体Xi=(xi1,xi2,…,xin),i=1,2,…N, 它的小生境群体确定方式为：对于给定的σsh，若满足dikσsh，则将该个体加入到小生境群体Xpi中。

其中，σsh为小生境半径，

dik=‖Xi-Xk‖,k=1,2,…N。

(5)

2)鱼群个体之间的共享函数。

个体i与个体j之间的共享函数sh(dij) 表达式如下：

(6)

其中，λ为控制函数的参数。

3)适应值函数的更新。

经调整后个体的适应值为

(7)

算法流程如下：

步骤1 初始化人工鱼群规模N、人工鱼的初始位置X、视野Visual和步长Step、拥挤度因子δ、人工鱼觅食的最大试探次数Try-number、最大迭代次数Lmax、小生境半径σsh。

步骤2 确定小生境种群个体：

(2.1)置i=1；

(2.2)由公式(5)计算个体之间的距离；

(2.3)根据dik<σsh,k=i,i+1,…,N，确定小生境子群Xpi，其中pi为Xpi中元素的个数。

步骤3 根据鱼群优化算法对小生境群体进行更新：

(3.1)人工鱼通过执行聚群、追尾、觅食行为更新自己的状态，计算个体的食物浓度，其中群体最优值是小生境群体的最优值，不再是整个群体的最优值；

(3.3)利用更新后的适应值fj′及处罚函数对子群体中适应度值低的个体进行处罚；

(3.4)当i+pi

步骤4 计算每条人工鱼的适应值，保留最优的适应值和个体，检查是否达到优化条件，如果达到最大迭代次数，则结束。否则，进入下一个鱼群的小生境群体进行优化。

步骤5 若没有找到最优值，则让每条人工鱼的小生境群体保留的最优个体组成新的群体空间，重复步骤 2。

以上算法利用鱼群个体的距离与小生境半径的关系划分人工鱼的小生境群体，然后在小生境群体内根据鱼群算法对每条人工鱼进行状态更新。对于更新后的群体，利用共享算法对适应值进行更新，对于适应度最低的粒子利用处罚函数进行处罚，最终得到最优解。

3 算法的性能测试

为了验证算法的有效性，将这种算法用于如下多峰函数进行测试：

1)F1(schaffer’s function)

-10≤xi≤10。

此函数是极为困难的多峰值函数，虽然该函数仅在(0,0)处取得最小值，但此解附近有无穷多个局部极小值的解;因此，算法搜索极为困难。图1为schaffer函数在-10≤xi≤10范围内的函数图像。

图1 schaffer函数图像

2)F2(needle-in-a-haystack)

-5.12≤xi≤5.12。

此函数为典型的大海捞针类问题，在定义域范围内仅在(0,0)点处取得全局最优解，而在点(-5.12,5.12)、(-5.12,-5.12)、(5.12,-5.12)、(5.12,5.12)处均能取得局部最优解。图2为函数在-5.12≤xi≤5.12范围内的函数图像，由图可以看出全局最优解被次优解包围。

图2 needle-in-a-haystack函数图像

为了测试算法的性能，这里分别用AFSA算法和NAFSA算法求解上述测试函数，表1为所得的寻优结果和平均运行时间。参数设置如下：鱼群规模N=100，视野Visual=7，步长Step=0.8，拥挤度因子δ=0.5，最大试探次数Try-number=3，最大迭代次数Lmax=20，小生境半径σsh=0.2。实验结果如表1所示。

表1 AFSA算法和NAFSA算法计算结果

由表1可以看出，NAFSA算法的寻优结果明显好于AFSA算法，同时平均运行时间也比AFSA算法少。

4 结论

针对人工鱼群算法优化精度低和后期收敛速度慢等缺点，对其进行改进。与小生境技术结合，提出了一种新的小生境鱼群优化算法。该算法通过鱼群个体之间的距离找到小生境群体，然后在小生境种群里执行聚群、追尾及觅食行为，个体经过进化后最优个体保存到下一代，最终找到满意解。仿真结果表明，该算法有效可行。

[1]李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式：鱼群算法[J].系统工程理论与实践,2002,22(11):32-38.

[2]朱孔村.人工鱼群算法在组合优化问题中的应用[D].济南:山东大学,2008.

[3]李晓磊,路飞,田国会,等.组合优化问题的人工鱼群算法应用[J].山东大学学报:工学版,2004,34(5):64-67.

[4]Zhang M F,Shao C,Li M J,et al.Mining Classification Rule with Artificial Fish Swarm[C]//Proceedings of the Sixth Word Congress on Intelligent Control and Automation.Dalian：[s.n.]，2006：5877-5881.

[5]刘耀年,李迎红,刘俊峰,等.基于人工鱼群算法的径向基神经网络的研究[J].东北电力大学学报:自然科学版,2006,26(4):23-27.

[6]舒维杰,袁志刚,尹忠科.利用人工鱼群算法实现基于MP的信号稀疏分解[J].计算机应用研究,2009,26(1):66-73.

[7]白小勇,苏华英,舒凯,等.人工鱼群算法在水库优化调度中的应用[J].水电能源科学,2008,26(5):51-53.

[8]Ma M,Liang J H,Sun L,et al.SAR Image Segmentation Based on SWT and Improved AFSA[C]//Proceedings of the Third International Symposium on Intelligent Information Technology and Security Informatics.Jianggangshan:[s.n.],2010：146-149.

[9]李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式：鱼群算法[J].系统工程理论与实践,2002,22(11):32-38.

[10]王联国,洪毅,赵付青,等.一种改进的人工鱼群算法[J].计算机工程,2008,34(19):192-194.

[11]修春波,张雨虹.基于蚁群与鱼群的混合优化算法[J].计算机工程,2008,34(14):206-208.

[12]张梅凤,邵诚.多峰函数优化的生境人工鱼群算法[J].控制理论与应用,2008,25(4):773-776.

[13]宋潇潇.求解大规模0-1背包问题的改进人工鱼群算法[J].西华大学学报：自然科学版,2013,32(4):5-9.

[14]Horn J. The Nature of Niching: Genetic Algorithms And The Evolution of Optimal, Cooperative Populations[D]. Urbana-Champaign:University of Illinois ,1997.

[15]Goldberg D E, Richardson J J. Genetic Algorithms with Sharing for Multimodal Function Optimization[C]// Proceedings of the Second International Conference.Genetic Algorithms:[s.n.] 1987: 41-49.

(编校：叶超)

NicheFishSwarmOptimizationAlgorithm

XU Xiang-yan,HUANG Tian-min

(DevelopmentofMathematic,SouthwestJiaotongUniversity,Chengdu611731China)

In order to deal with the problem of slow convergence speed and difficult to find the accurate optimal solutions, combined with the theory of niche technology, Niche Artificial Fish Swarm Algorithm(NAFSA) is proposed. Niche population is consisted by individual fishes which has similar distance. The algorithm performs swarm first and then follow and prey behavior of Artificial Fish Swarm Algorithm(AFSA) in this population, and find the best one deposit to the next generation until a satisfactory value is searched. Finally, the performance of the algorithm is verified through several multimodal function. The simulation results show that the convergence and the optimization of algorithm are achieved good effect.

artificial fish swarm algorithm(AFSA); niche; multimodal function

2014-06-28

徐翔燕(1990—)，女，硕士研究生，主要研究方向为优化与决策。

TP183

：A

：1673-159X(2015)06-0064-03

10.3969/j.issn.1673-159X.2015.06.013