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

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

吳昌友

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

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

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

DOI:10.3969/j.issn.1673-4785.201404010

中圖分類號：TP18 文獻(xiàn)標(biāo)志碼：A

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

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

作者簡介：

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

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

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

1)覓食行為。

(1)

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

2)群聚行為。

(2)

3)追尾行為。

(3)

4)公告板設(shè)置。

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

2改進(jìn)人工魚群算法

2.1初始人工魚群的產(chǎn)生

(4)

(5)

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

(6)

(7)

(8)

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

2.2覓食行為的改進(jìn)

(9)

(10)

(11)

(12)

2.3群聚行為的改進(jìn)

(13)

(14)

2.4追尾行為的改進(jìn)

(15)

2.5變異策略的引入

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

(16)

3仿真實驗

為了驗改進(jìn)的人工魚群算法的有效性，選取4個測試函數(shù)進(jìn)行仿真實驗，其測試函數(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

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

改進(jìn)人工魚群算法和標(biāo)準(zhǔn)人工魚群算法在測試函數(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ù)標(biāo)準(zhǔn)人工魚群算法最優(yōu)值迭代次數(shù)改進(jìn)人工魚群算法最優(yōu)值迭代次數(shù)f101408f2021010f32748.85036006f4027013

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

4結(jié)束語

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

參考文獻(xiàn):

[1]李曉磊，錢積新.基于分解協(xié)調(diào)的人工魚群優(yōu)化算法研究[J]. 電路與系統(tǒng)學(xué)報, 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)化問題的人工魚群算法應(yīng)用[J].山東大學(xué)學(xué)報：工學(xué)版, 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ìn)的人工魚群算法[J]. 重慶師范大學(xué)學(xué)報, 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ìn)人工魚群算法研究[J].計算機(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ìn)工魚群算法[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]張嚴(yán)，楚曉麗.一種改進(jìn)的人工魚群算法[J].計算機(jī)系統(tǒng)應(yī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]曲良東，何登旭.基于自適應(yīng)高斯變異的人工魚群算法[J].計算機(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ìn)人工魚群算法的梯級水庫群優(yōu)化調(diào)度[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]吳昌友,王福林，馬力.一種新的改進(jìn)粒子群優(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ā)表學(xué)術(shù)論文30余篇，出版專著1部，主編教材1部。