一種改進的人工魚群優(yōu)化算法

網(wǎng)絡出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150409.1657.001.html

一種改進的人工魚群優(yōu)化算法

吳昌友

(山東工商學院 管理科學與工程學院，山東 煙臺 264005)

摘要：對人工魚群優(yōu)化算法的覓食行為、群聚行為、追尾行為和公告板設置等基本原理進行分析，指出算法在復雜優(yōu)化問題上產生初始人工魚群難和陷入局部最優(yōu)解的原因，提出了改進人工魚群優(yōu)化算法，給出了初始人工魚群產生的方法，在人工魚群優(yōu)化算法的覓食行為、群聚行為、追尾行為中引入了自適應移動步長，同時在算法中引入變異策略，避免算法陷入局部最優(yōu)，提高全局尋優(yōu)能力。最后通過對4個測試函數(shù)進行實驗，對于函數(shù)f1、f2和f4來說，雖然改進的人工魚群算法和標準人工魚群算法都達到了最優(yōu)值，但是改進的人工魚群算法收斂的速度更快；函數(shù)f3來說，標準人工魚群算法運行多次都陷入最優(yōu)解，無法找到全局最優(yōu)解。因此，實驗說明了改進算法的有效性與精確性。

關鍵詞：人工魚群優(yōu)化算法；覓食；群聚；追尾；移動步長；變異策略

DOI:10.3969/j.issn.1673-4785.201404010

中圖分類號：TP18 文獻標志碼：A

收稿日期：2014-04-08. 網(wǎng)絡出版日期：2015-04-09.

基金項目：國家自然科學基金資助項目(71272122，71373148)；山東省社科規(guī)劃項目(13DGLJ05)；山東能源經濟協(xié)同創(chuàng)新中心資助項目(2014SDXT005)；山東省軟科學項目(2014RKB01021).

作者簡介：

中文引用格式：吳昌友. 一種新的改進人工魚群優(yōu)化算法[J]. 智能系統(tǒng)學報, 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.

人工魚群優(yōu)化算法是李曉磊提出的一種智能優(yōu)化算法，該算法通過模擬魚群的覓食、聚群、追尾等行為，實現(xiàn)集群智能的一種優(yōu)化方法，具有較強的魯棒性和并行分布處理能力等優(yōu)點[1-3]。該算法與遺傳算法和粒子群優(yōu)化算法一樣容易陷入局部最優(yōu)解和收斂速度慢，這些問題引起了廣大學者們的注意，分別提出了改進策略[3-13]。如范玉軍[4]為了防止群體中最優(yōu)個體的退化，提出最優(yōu)個體保留策略對覓食行為進行改進，同時對聚群行為和追尾行為進行改進，使全局最優(yōu)值更快地突現(xiàn)出來，從而加速了全局搜索。劉佳[5]利用模擬退火算法中的Metropolis判別準則對人工魚群算法中的覓食行為進行改進。柳毅[6]提出動態(tài)調整人工魚移動步長、視野范圍和鄰域值等方法來提高人工魚群算法的尋優(yōu)能力。張嚴[7]采用特殊覓食行為，約束群聚行為的擁擠度區(qū)間，協(xié)調移動策略，進而保障每條魚的成功覓食，避免魚群出現(xiàn)早熟現(xiàn)象。曲良東[8]利用進化策略、粒子群算法中的信息策略加入到人工魚群算法中，并在理論上證明該算法的收斂性。彭勇[9]提出了動態(tài)調整人工魚視野和步長的方法，解決了人工魚群算法的全局搜索能力和局部搜索能力的矛盾。從以上的學者的研究成果可以看出，主要是從陷入局部最優(yōu)解而提出改進的，而沒有對初始魚群的產生進行研究，而本文提出一種新的初始魚群產生方法，并同時采用自適應移動步長和變異策略，來改進人工魚群算法。

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

設X=(x1,x2,…,xn)為人工魚群個體向量，其中n為各條魚尋優(yōu)的變量個數(shù)，即待優(yōu)化問題的變量個數(shù)，F(xiàn)=f(X)為某條魚當前位置的食物濃度，其中F為目標函數(shù)，Dij=‖Xi-Xj‖表示第i條魚和第j條魚之間的距離，r表示人工魚的感知距離，人工魚只能在其感知距離內發(fā)生覓食行為，λ為人工魚移動的步長，δ表示擁擠度因子。其人工魚群算法的基本原理如下。

1)覓食行為。

(1)

式中：γ表示符合均勻分布[0,1]之間的隨機數(shù)。

2)群聚行為。

(2)

3)追尾行為。

(3)

4)公告板設置。

人工魚群在優(yōu)化尋優(yōu)過程中，設置公告板，在公告板中記錄魚群的最優(yōu)位置和每條魚尋優(yōu)過程中的最優(yōu)位置。在每次覓食行為、群聚行為和追尾行為完畢后都要檢查自身位置和公告板的位置，如果自身的位置優(yōu)于公告板的位置，則更新公告板。

2改進人工魚群算法

2.1初始人工魚群的產生

(4)

(5)

式中：λ0表示[0,1]之間的一個常數(shù)。

(6)

(7)

(8)

對于其他的人工魚的產生方法與第2條人工魚產生方法相同，共產生N條初始人工魚。

2.2覓食行為的改進

(9)

(10)

(11)

(12)

2.3群聚行為的改進

(13)

(14)

2.4追尾行為的改進

(15)

2.5變異策略的引入

為了避免人工魚群算法在優(yōu)化后期陷入局部最優(yōu)解，以及保持魚群分布的多樣性，本文引入了變異策略。如果連續(xù)幾次找不到更好的人工魚狀態(tài)，則進行變異，設其變異概率為Pm，則變異的人工魚數(shù)為mPm，其變異的計算過程如式(16)所示。

(16)

3仿真實驗

為了驗改進的人工魚群算法的有效性，選取4個測試函數(shù)進行仿真實驗，其測試函數(shù)如下：

-10≤x1,x2≤10

-25≤x1,x2≤25

-6.15≤x1,x2≤6.15

(a)函數(shù) f 1

(b)函數(shù) f 2

(c)函數(shù) f 3

(d)函數(shù) f 4 圖1　測試函數(shù) f 1~ f 4的三維立體圖 Fig. 1　The three-dimensional map test function f 1~ f 4

改進人工魚群算法和標準標準人工魚群算法在4個目標測試函數(shù)f1、f2、f3和f4中迭代次數(shù)與函數(shù)值的關系曲線，如圖2~5所示。

改進人工魚群算法和標準人工魚群算法在測試函數(shù)f1~f4優(yōu)化中，其函數(shù)最優(yōu)值和迭代次數(shù)如表1所示。

圖2　函數(shù) f 1的迭代曲線 Fig. 2　The iterative curve of function f 1

圖3　函數(shù) f 2的迭代曲線 Fig. 3　The iterative curve of function f 2

圖4　函數(shù) f 3的迭代曲線 Fig. 4　The iterative curve of function f 3

圖5　函數(shù) 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

函數(shù)標準人工魚群算法最優(yōu)值迭代次數(shù)改進人工魚群算法最優(yōu)值迭代次數(shù)f101408f2021010f32748.85036006f4027013

由圖2~5和表1可以看出，改進的人工魚群算法無論在優(yōu)化速度和優(yōu)化精度明顯好于標準的人工魚群算法，對于函數(shù)f1、f2和f4來說，雖然改進的人工魚群算法和標準人工魚群算法都達到了最優(yōu)值，但是改進的人工魚群算法收斂的速度較快；對于函數(shù)f3來說，標準人工魚群算法運行多次都陷入最優(yōu)解，無法找到全局最優(yōu)解。綜上所述，搜索目標函數(shù)全局最優(yōu)值，標準人工魚群算法不是陷入局部極值，就是計算逐步趨于停頓，而改進標準人工魚群算法則表現(xiàn)出更為強大的搜索能力、更快的收斂速度以及更為準確的計算精度。

4結束語

對于標準人工魚群算法容易陷入局部極小點和收斂速度慢等特點，本文提出了一種改進的人工魚群算法。在人工魚群算法應用復雜的約束條件下，很難產生可行的初始人工魚群，本文給出了初始人工魚群的產生方法，大大提高初始人工魚群產生速度，并提出了自適應步長，加速人工魚群算法的收斂速度，同時為了保證人工魚群的多樣性，避免陷入局部最優(yōu)解，引進了變異策略。從測試實驗的結果可以看出，改進人工魚群算法是可行的。

參考文獻:

[1]李曉磊，錢積新.基于分解協(xié)調的人工魚群優(yōu)化算法研究[J]. 電路與系統(tǒng)學報, 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]李曉磊，邵之江，錢積新.一種基于動物自治體的尋優(yōu)模式：魚群算法[J].系統(tǒng)工程理論與實踐, 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]李曉磊，路飛，田國會，等.組合優(yōu)化問題的人工魚群算法應用[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].計算機系統(tǒng)應用, 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]彭勇，唐國磊，薛志春.基于改進人工魚群算法的梯級水庫群優(yōu)化調度[J].系統(tǒng)工程理論與實踐, 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]吳昌友,王福林，馬力.一種新的改進粒子群優(yōu)化算法[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年生，副教授，博士，主要研究方向為系統(tǒng)工程和人工智能算法。主持和參與省部級項目6項，發(fā)表學術論文30余篇，出版專著1部，主編教材1部。