一种改进的人工鱼群优化算法

网络出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150409.1657.001.html

一种改进的人工鱼群优化算法

吴昌友

(山东工商学院 管理科学与工程学院，山东 烟台 264005)

摘要：对人工鱼群优化算法的觅食行为、群聚行为、追尾行为和公告板设置等基本原理进行分析，指出算法在复杂优化问题上产生初始人工鱼群难和陷入局部最优解的原因，提出了改进人工鱼群优化算法，给出了初始人工鱼群产生的方法，在人工鱼群优化算法的觅食行为、群聚行为、追尾行为中引入了自适应移动步长，同时在算法中引入变异策略，避免算法陷入局部最优，提高全局寻优能力。最后通过对4个测试函数进行实验，对于函数f1、f2和f4来说，虽然改进的人工鱼群算法和标准人工鱼群算法都达到了最优值，但是改进的人工鱼群算法收敛的速度更快；函数f3来说，标准人工鱼群算法运行多次都陷入最优解，无法找到全局最优解。因此，实验说明了改进算法的有效性与精确性。

关键词：人工鱼群优化算法；觅食；群聚；追尾；移动步长；变异策略

DOI:10.3969/j.issn.1673-4785.201404010

中图分类号：TP18 文献标志码：A

收稿日期：2014-04-08. 网络出版日期：2015-04-09.

基金项目：国家自然科学基金资助项目(71272122，71373148)；山东省社科规划项目(13DGLJ05)；山东能源经济协同创新中心资助项目(2014SDXT005)；山东省软科学项目(2014RKB01021).

作者简介：

中文引用格式：吴昌友. 一种新的改进人工鱼群优化算法[J]. 智能系统学报, 2015, 10(3): 465-469.

英文引用格式：WU Changyou. An improved artificial fish swarm optimization algorithm[J]. CAAI Transactions on Intelligent Systems, 2015, 10(3): 465-469.

An improved artificial fish swarm optimization algorithm

WU Changyou

(School of Management Science and Engineering, Shandong Institute of Business And Technology, Yantai 264005, China)

Abstract：In this paper, the basic principles of artificial fish's behaviors of prey, swarm, follow and bulletin board set were analyzed. Investigations were conducted to explore the reasons why it is difficult to produce the initial artificial fish swarm, and why it always falls into local optional solution. The proposed solution improves the artificial fish algorithm with the method of the produce of initial artificial fish swarm, in the artificial fish's behaviors of prey, swarm and follow introduced the adaptive mobile step length with mutation strategy into the artificial fish at the same time, avoiding fish caught in local optima, improving the ability of global optimization. Finally, through the experiment of the 4 test functions concluded that as for the function of f1, f2 and f4, while the improved artificial fish swarm algorithm and artificial fish swarm algorithm have reached the optimal value, but the convergence of the improved artificial fish swarm algorithm is faster. As to the function of f3, the standard artificial fish swarm algorithm run in to the optimal solution in several times' operation and the global optimal solution cannot be found. Therefore, the experiment shows the effectiveness and accuracy of the improved algorithm.

Keywords：artificial fish swarm optimization algorithm; prey; swarm; follow; moving step length; mutation strategy

通信作者：吴昌友. E-mail: wuchangyou_81@163.com.

人工鱼群优化算法是李晓磊提出的一种智能优化算法，该算法通过模拟鱼群的觅食、聚群、追尾等行为，实现集群智能的一种优化方法，具有较强的鲁棒性和并行分布处理能力等优点[1-3]。该算法与遗传算法和粒子群优化算法一样容易陷入局部最优解和收敛速度慢，这些问题引起了广大学者们的注意，分别提出了改进策略[3-13]。如范玉军[4]为了防止群体中最优个体的退化，提出最优个体保留策略对觅食行为进行改进，同时对聚群行为和追尾行为进行改进，使全局最优值更快地突现出来，从而加速了全局搜索。刘佳[5]利用模拟退火算法中的Metropolis判别准则对人工鱼群算法中的觅食行为进行改进。柳毅[6]提出动态调整人工鱼移动步长、视野范围和邻域值等方法来提高人工鱼群算法的寻优能力。张严[7]采用特殊觅食行为，约束群聚行为的拥挤度区间，协调移动策略，进而保障每条鱼的成功觅食，避免鱼群出现早熟现象。曲良东[8]利用进化策略、粒子群算法中的信息策略加入到人工鱼群算法中，并在理论上证明该算法的收敛性。彭勇[9]提出了动态调整人工鱼视野和步长的方法，解决了人工鱼群算法的全局搜索能力和局部搜索能力的矛盾。从以上的学者的研究成果可以看出，主要是从陷入局部最优解而提出改进的，而没有对初始鱼群的产生进行研究，而本文提出一种新的初始鱼群产生方法，并同时采用自适应移动步长和变异策略，来改进人工鱼群算法。

1人工鱼群算法的基本原理

设X=(x1,x2,…,xn)为人工鱼群个体向量，其中n为各条鱼寻优的变量个数，即待优化问题的变量个数，F=f(X)为某条鱼当前位置的食物浓度，其中F为目标函数，Dij=‖Xi-Xj‖表示第i条鱼和第j条鱼之间的距离，r表示人工鱼的感知距离，人工鱼只能在其感知距离内发生觅食行为，λ为人工鱼移动的步长，δ表示拥挤度因子。其人工鱼群算法的基本原理如下。

1)觅食行为。

(1)

式中：γ表示符合均匀分布[0,1]之间的随机数。

2)群聚行为。

(2)

3)追尾行为。

(3)

4)公告板设置。

人工鱼群在优化寻优过程中，设置公告板，在公告板中记录鱼群的最优位置和每条鱼寻优过程中的最优位置。在每次觅食行为、群聚行为和追尾行为完毕后都要检查自身位置和公告板的位置，如果自身的位置优于公告板的位置，则更新公告板。

2改进人工鱼群算法

2.1初始人工鱼群的产生

(4)

(5)

式中：λ0表示[0,1]之间的一个常数。

(6)

(7)

(8)

对于其他的人工鱼的产生方法与第2条人工鱼产生方法相同，共产生N条初始人工鱼。

2.2觅食行为的改进

(9)

(10)

(11)

(12)

2.3群聚行为的改进

(13)

(14)

2.4追尾行为的改进

(15)

2.5变异策略的引入

为了避免人工鱼群算法在优化后期陷入局部最优解，以及保持鱼群分布的多样性，本文引入了变异策略。如果连续几次找不到更好的人工鱼状态，则进行变异，设其变异概率为Pm，则变异的人工鱼数为mPm，其变异的计算过程如式(16)所示。

(16)

3仿真实验

为了验改进的人工鱼群算法的有效性，选取4个测试函数进行仿真实验，其测试函数如下：

-10≤x1,x2≤10

-25≤x1,x2≤25

-6.15≤x1,x2≤6.15

(a)函数 f 1

(b)函数 f 2

(c)函数 f 3

(d)函数 f 4 图1　测试函数 f 1~ f 4的三维立体图 Fig. 1　The three-dimensional map test function f 1~ f 4

改进人工鱼群算法和标准标准人工鱼群算法在4个目标测试函数f1、f2、f3和f4中迭代次数与函数值的关系曲线，如图2~5所示。

改进人工鱼群算法和标准人工鱼群算法在测试函数f1~f4优化中，其函数最优值和迭代次数如表1所示。

图2　函数 f 1的迭代曲线 Fig. 2　The iterative curve of function f 1

图3　函数 f 2的迭代曲线 Fig. 3　The iterative curve of function f 2

图4　函数 f 3的迭代曲线 Fig. 4　The iterative curve of function f 3

图5　函数 f 4的迭代曲线 Fig. 5　The iterative curve of function f 4

Table 1 The optimal value of improved and standard AFSA

and the comparison of the number of iterations

函数标准人工鱼群算法最优值迭代次数改进人工鱼群算法最优值迭代次数f101408f2021010f32748.85036006f4027013

由图2~5和表1可以看出，改进的人工鱼群算法无论在优化速度和优化精度明显好于标准的人工鱼群算法，对于函数f1、f2和f4来说，虽然改进的人工鱼群算法和标准人工鱼群算法都达到了最优值，但是改进的人工鱼群算法收敛的速度较快；对于函数f3来说，标准人工鱼群算法运行多次都陷入最优解，无法找到全局最优解。综上所述，搜索目标函数全局最优值，标准人工鱼群算法不是陷入局部极值，就是计算逐步趋于停顿，而改进标准人工鱼群算法则表现出更为强大的搜索能力、更快的收敛速度以及更为准确的计算精度。

4结束语

对于标准人工鱼群算法容易陷入局部极小点和收敛速度慢等特点，本文提出了一种改进的人工鱼群算法。在人工鱼群算法应用复杂的约束条件下，很难产生可行的初始人工鱼群，本文给出了初始人工鱼群的产生方法，大大提高初始人工鱼群产生速度，并提出了自适应步长，加速人工鱼群算法的收敛速度，同时为了保证人工鱼群的多样性，避免陷入局部最优解，引进了变异策略。从测试实验的结果可以看出，改进人工鱼群算法是可行的。

参考文献:

[1]李晓磊，钱积新.基于分解协调的人工鱼群优化算法研究[J]. 电路与系统学报, 2003, 8(1): 1-6.

LI Xiaolei, QIAN Jixin. Studies on artificial fish swarm optimization algorithm based on decomposition and coordination techniques[J]. Journal of Circuits and Systems, 2003, 8(1): 1-6.

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

LI Xiaolei, SHAO Zhijiang, QIAN Jixin. An optimizing method based on autonomous animals fish-swarm algorithm[J]. Systems Engineering—Theory & Practice, 2002, 22(11): 32-38.

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

LI Xiaolei, LU Fei, TIAN Guohui, et al. Applications of artificial fish school algorithm in combinatorial optimization problems[J]. Journal of Shangdong University: Engineering Science, 2004, 34(5): 64-67.

[4]范玉军，王冬冬，孙明明.改进的人工鱼群算法[J]. 重庆师范大学学报, 2007, 24(3): 23-26.

FAN Yujun, WANG Dongdong, SUN Mingming. Improved artificial fish-school algorithm[J]. Journal of Chongqing Normal University, 2007, 24(3): 23-26.

[5]刘佳，刘丽娜，李靖.基于模拟退火算法的改进人工鱼群算法研究[J].计算机仿真, 2011, 28(10): 195-198.

LIU Jia, LIU Lina, LI Jing.Research of improved artificial fish swarm algorithm based on simulated annealing algorithm[J]. Computer Simulation, 2011, 28(10): 195-198.

[6]柳毅.求解模糊需求可回程取货车辆路径问题的改进工鱼群算法[J].模式识别与人工智能, 2010, 23(4): 560-564.

LIU Yi. Improved artificial fish swarm algorithm for vehicle routing problem with backhaul and fuzzy demand[J]. Pattern Recognition & Artificial Intelligence, 2010, 23(4): 560-564.

[7]张严，楚晓丽.一种改进的人工鱼群算法[J].计算机系统应用, 2011, 20(5): 199-201.

ZHANG Yan, CHU Xiaoli. Advanced artificial fish swarm algorithm[J]. Computer Systems & Applications, 2011, 20(5): 199-201.

[8]曲良东，何登旭.基于自适应高斯变异的人工鱼群算法[J].计算机工程, 2009, 35(15): 182-189.

QU Liangdong, HE Dengxu. Artificial fish-school algorithm based on adaptive Gauss mutation[J]. Computer Engineering, 2009, 35(15): 182-189.

[9]彭勇，唐国磊，薛志春.基于改进人工鱼群算法的梯级水库群优化调度[J].系统工程理论与实践, 2011, 31(6): 1118-1126.

PENG Yong, TANG Guolei, XUE Zhichun. Optimal operation of cascade reservoirs based on improved artificial fish swarm algorithm[J]. Systems Engineering—Theory & Practice, 2011, 31(6): 1118-1126.

[10]SHEN Wei, GUO Xiaopen, WU Chao, et al. Forecasting stock indices using radial basis function neural networks optimized by artificial fish swarm algorithm[J]. Knowledge-Based Systems, 2011, 24(3): 378-385.

[11]WANG Cuiru, ZHOU Chunlei, MA Jianwei. An improved artificial fish-swarm algorithm and its application in feed-forward neural networks[C]//Proceedings of 2005 International Conference on Machine Learning and Cybernetics. Guangzhou, China, 2005, 5: 2890-2894.

[12]FARZI S. Efficient job scheduling in grid computing with modified artificial fish swarm algorithm[J]. International Journal of Computer Theory and Engineering, 2009, 1(1): 13-18.

[13]LUO Yi, ZHANG Juntao, LI Xinxin. The optimization of PID controller parameters based on artificial fish swarm algorithm[C]//2007 IEEE International Conference on Automation and Logistics. Ji’nan, China, 2007: 1058-1062.

[14]吴昌友,王福林，马力.一种新的改进粒子群优化算法[J].控制工程, 2010, 17(5): 359-362.

WU Changyou, WANG Fulin, MA Li. An improved particle swarm optimization algorithm[J]. Control Engineering of China, 2010, 17(5): 359-362.

吴昌友，男，1981年生，副教授，博士，主要研究方向为系统工程和人工智能算法。主持和参与省部级项目6项，发表学术论文30余篇，出版专著1部，主编教材1部。