模擬追逐算法

劉　偉，謝月珊

(廣東工業(yè)大學 應(yīng)用數(shù)學學院，廣東 廣州 510006)

模擬追逐算法

劉偉，謝月珊

(廣東工業(yè)大學 應(yīng)用數(shù)學學院，廣東 廣州 510006)

摘要:提出了一種群體智能算法——模擬追逐算法.該算法模擬長跑比賽運動員追逐競爭過程，設(shè)計了追逐算子與探測算子.領(lǐng)先個體執(zhí)行探測算子操作以便獲得更優(yōu)位置，落后個體為取得競爭優(yōu)勢，設(shè)定追趕目標，執(zhí)行追逐算子操作，完成跟隨超越，從而實現(xiàn)群體進化尋優(yōu).仿真實驗表明，模擬追逐算法有較快的收斂速度和較高的求解精度，是一種穩(wěn)定的優(yōu)化算法.

關(guān)鍵詞:模擬追逐；智能算法；探測算子；追逐算子

受生物的智能行為啟發(fā)，一些學者建立數(shù)學模型，模擬其尋優(yōu)能力提出了多種智能優(yōu)化算法.遺傳算法[1-4]是模擬自然界的生物選擇、雜交、變異的進化過程的全局優(yōu)化算法；粒子群算法[5-7]是模擬鳥群覓食過程的一種有效的全局尋優(yōu)算法.這類仿生算法不依賴于問題的具體領(lǐng)域，對問題的種類有很強的魯棒性，為復雜系統(tǒng)優(yōu)化提供了一種通用的求解框架，被廣泛應(yīng)用到函數(shù)優(yōu)化[8]、組合優(yōu)化[9]、自動控制[10-11]、生產(chǎn)調(diào)度[12]、圖像處理[13-15]等領(lǐng)域.

在長跑比賽中，運動員為了獲得好的成績，需要采用正確的戰(zhàn)術(shù)策略.如何調(diào)整自己的步伐，是跟跑還是領(lǐng)跑,沖刺時機選擇等等都是比賽獲勝的重要因素.長跑比賽實質(zhì)就是追逐競賽的過程.領(lǐng)先的運動員按自己的節(jié)奏，不斷調(diào)整步伐奔向終點；落后的運動員結(jié)合自己的實力，設(shè)定視野范圍，確定追逐目標，從而調(diào)整自己步伐，跟跑并超越對手.

借鑒追逐競賽的過程，本文建立了數(shù)學模型并運用于優(yōu)化問題的求解，提出了一種新的智能算法——模擬追逐算法.該算法通過追逐算子和探測算子作用，使個體不斷調(diào)整步長，搜索到更優(yōu)的位置，從而引導解不斷地進化，最終實現(xiàn)全局尋優(yōu).數(shù)值實驗驗證了模擬追逐算法是一種有效的群體優(yōu)化算法.

1模擬追逐算法

1.1基本原理

模擬追逐算法(Simulated Pursuit Algorithm,SPA)是模擬運動員長跑比賽的追逐過程行為所具有的智能性，為優(yōu)化問題的解決提供了一種全局尋優(yōu)算法.算法中運動員被稱為“個體”或“解”，問題優(yōu)化過程就是個體追逐過程.跑在比賽最前列的“個體”(最優(yōu)個體)，為保持領(lǐng)先的位置，執(zhí)行探測算子，嘗試多次調(diào)整自己的步伐，計算出相應(yīng)的新位置，若新位置優(yōu)于原先位置，則選擇較優(yōu)的新位置替換最優(yōu)個體位置，否則，最優(yōu)個體位置保持不變.其他個體(非最優(yōu)個體)執(zhí)行追逐算子，首先個體根據(jù)戰(zhàn)術(shù)需要，設(shè)定視野范圍，確定追逐目標(個體)，若追逐目標數(shù)k>0,則根據(jù)追逐目標，計算出需要調(diào)整的步長，確定新位置，若k=0，即視野范圍內(nèi)沒有追逐目標，則參照最優(yōu)個體的位置調(diào)整步長，計算新位置，直至群體完成設(shè)定的進化迭代次數(shù)，算法終止.

1.2控制參數(shù)

在模擬追逐算法中，關(guān)鍵參數(shù)是預(yù)先設(shè)定好的，參數(shù)設(shè)置對算法運行效率有很大的影響，具體包括種群大小N、當前迭代次數(shù)TCur、最大迭代次數(shù)TMax、嘗試次數(shù)m、視野范圍r.

1.3追逐算子

步長Step為

(1)

(2)

(3)

由式(2)和(3)知,被追逐個體Xj的適應(yīng)度越大，F(xiàn)ectorj越大，對個體Xi位置更新所需的步長貢獻率越大 .所以

當k>0時，個體i的新位置為

(4)

否則k=0,個體i的新位置為

(5)

其中step1=Xb-Xi，其中Xb為最優(yōu)個體 .

1.4探測算子

探測算子是通過一個隨機擾動步長探測出最優(yōu)個體可能的新位置.嘗試次數(shù)為m,步長生成源P>0,向量維數(shù)為W. 擾動步長Step 2隨機生成,其生成的代碼(Matlab)為

Step2=0*ones(1,W);

q=1+fix(rand()·(W));

forj=1:q

a(j)=fix(1+rand()·W);

end

forj=1:q

k=a(j);

if (rand(1)<0.5)

Step2(k)=Step2(k)-rand()·P;

else

Step2(k)=Step2(k)+rand()·P;

end

end

1.5算法流程

模擬追逐算法步驟：

(1) 種群初始化與參數(shù)設(shè)置.

(2) 適應(yīng)度計算，最優(yōu)個體確定.

(3) 種群個體更新：若個體為最優(yōu)個體，則執(zhí)行探測算子；否則執(zhí)行追逐算子.

(4) 算法終止條件是否滿足，若滿足，則算法結(jié)束；否則轉(zhuǎn)步驟(2).

算法流程圖如圖1所示

圖1　模擬追逐算法流程圖

2仿真實驗及結(jié)果分析

2.1追逐算子性能分析

為分析追逐算子的功能，對個體為100，向量維數(shù)為5的種群，視野范圍取不同值，執(zhí)行追逐算子測試.圖2為隨機選擇編號為10，40，90的個體的50次迭代的進化曲線，圖3為視野范圍r分別為0.000 1、0.01、0.1、1時，種群最優(yōu)個體的進化曲線.結(jié)果表明：種群中的個體在迭代過程中不斷進化，并具有跳出局部最優(yōu)解的能力；同時追逐算子對解的搜索精度與收斂速度的影響與視野范圍大小有關(guān)，視野范圍為0.01時算子搜索效果最佳；視野范圍的設(shè)置與優(yōu)化問題有關(guān).

圖2　不同個體的進化曲線

2.2實驗結(jié)果與算法分析

為了檢驗?zāi)M追逐算法的優(yōu)化性能，本文選擇文獻[4]的自適應(yīng)遺傳算法(記為GA), 文獻[7]中的帶粒子釋放和速度限制的粒子群算法(記為PSO)與模擬追逐算法比較, 通過6個標準的測試函數(shù)(如表1所示)測試3種算法的性能，數(shù)值實驗在Matlab中完成.每個測試函數(shù)在相同條件下獨立運行20次，記錄最好結(jié)果、平均結(jié)果，算法成功率.

表1　測試函數(shù)

從表2可知，為了獲得更好的優(yōu)化效果，視野范圍r取值與優(yōu)化問題相關(guān)；對于6個測試函數(shù)，無論是單峰函數(shù)還是多峰函數(shù)，SPA測試的最優(yōu)值、平均最優(yōu)值均優(yōu)于GA與PSO,說明新算法有很好的求解精度，特別是對于函數(shù)f3與f5，SPA均求解出理論最優(yōu)值；對于6個測試函數(shù)分別設(shè)置其目標精度，除f2外，其余5個優(yōu)化問題求解成功率均為100%，說明SPA優(yōu)化求解有很好的穩(wěn)定性.

從圖4～圖9可知，SPA比GA,PSO有更快的收斂速度，并且有跳出陷入局部最優(yōu)解的能力；在相同精度下，算法SPA比算法GA,PSO需要的迭代次數(shù)更少；圖8中，對于f5，雖然PSO與SPA算法均收斂于最優(yōu)值，但算法SPA只需要62次迭代，而PSO需要128次迭代.

表2　計算結(jié)果

圖4　各函數(shù)進化曲線

從上實驗分析可以看出，與GA,PSO比較，SPA在收斂速度、求解精度、穩(wěn)定性等方面均顯示出其優(yōu)越性，說明模擬追逐算法是一種有較強尋優(yōu)能力的群體智能算法.

3實際應(yīng)用

案例(選址問題) 假設(shè)要選定一個供應(yīng)中心的位置,為城市中固定的m個用戶服務(wù)，供應(yīng)的商品可以是水、電、牛奶或其他貨物.求供應(yīng)中心的位置，使其到各個用戶的距離(之和)最小.假設(shè)現(xiàn)有10個用戶，位置為{(xi,yi)|

(2.517 8,3.246 3),(-2.984 1,3.307 0),(1.058 9,-3.219 7),(-1.772 0,0.375 1),(3.660 1,3.719 1),(-2.739 1,3.764 7),

(3.657 3,-0.117 0),(2.402 2,-2.864 9),(-0.625 9,3.325 9),(2.337 7,3.675 9)}.

解假設(shè)供應(yīng)中心的位置C=(x，y),建立優(yōu)化問題模型.

采用Matlab給出選址問題的精確最優(yōu)解為(0.877 1， 2.117 1)，最優(yōu)值為34.569 3.為使用模擬追逐算法求解，設(shè)置控制參數(shù)：TMax=10，N=10,r=0.5,m=5，G0=50,α=80.算法SPA計算出最優(yōu)解與精確解一致,C*=(0.877 111 032 786 5，2.117 105 766 708 5),f*=34.569 318 766 834 06.算法進化曲線如圖5所示，算法所求供應(yīng)中心位置如圖6所示.

圖5　算法進化曲線

4結(jié)束語

SPA是一種對人類行為進行智能仿生的優(yōu)化算法.融合了試探性開拓與有目的性的追逐相結(jié)合的優(yōu)點，具有模型簡單，優(yōu)化性能高的優(yōu)點.實驗仿真結(jié)果證實了模擬追逐算法的優(yōu)越性.

圖6　供應(yīng)中心位置

參考文獻：

[1] RUNARSSON T P, YAO X. Stochastic ranking for constrained evolutionary optimization[J].IEEE Transactions on Evolutionary Computation, 2000,4(3):284-294.

[2] DEEP K, THAKUR M.A new mutation operator for real coded genetic algorithms[J]. Applied Mathematics and Computation，2007,193:211-230.

[3] 劉偉,劉海林.基于外點法的混合遺傳算法求解決約束優(yōu)化問題[J].計算機應(yīng)用, 2007, 27(1):238-240

LIU W,LIU H L. A hybrid genetic algorithm based on external point method for constrained optimization[J]. Journal of Computer Applications, 2007, 27(1):238-240.

[4] 梁旭，黃明.現(xiàn)代智能優(yōu)化混合算法及其應(yīng)用[M]. 北京：電子工業(yè)出版社，2012.

[5] RATNAWEERA A，HALGAMUGE S.Nonlinear inertia variation for dynamic adaption in particle swarm optimization[J]．Computers & Operation Research,2006,33(3):859-971．

[6] 劉偉,蔡前鳳,劉海林.基于參數(shù)方程處理等式約束優(yōu)化的粒子群算法[J]. 計算機工程與設(shè)計, 2008, 29(3):697-699.

LIU W, CAI Q F, LIU H L. A particle swarm optimization algorithm based on parametric equation method to handle equality constraints[J].Journal of Computer Engineering and Design, 2008, 29(3):697-699.

[7] 吳正科,楊青真. 帶粒子釋放和速度限制的粒子群算法[J]. 計算機應(yīng)用研究, 2013, 30(3):682-684.

WU Z K,YANG Q Z. Particle swarm optimization with particle release and speed limit[J].Journal of Application Research of Computers,2013, 30(3):682-684.

[8] 倪全貴.粒子群遺傳混合算法及其在函數(shù)優(yōu)化上的應(yīng)用[D].廣州：華南理工大學數(shù)學科學學院, 2014.

[9] 馬立肖,王江晴.遺傳算法在組合優(yōu)化問題中的應(yīng)用[J].計算機工程與科學, 2005, 27(7):72-74.

MA L X, WANG J Q.Application of genetic algorithms in solving the optimal combination problem[J].Computer Engineering and Science, 2005, 27(7):72-74.

[10] 楊智民,王旭,莊顯義.遺傳算法在自動控制領(lǐng)域中的應(yīng)用綜述[J].信息與控制, 2000,29(4):329-339.

YANG Z M,WANG X,ZHUANG X Y. Survey of genetic algortihm′s application in field of automatic control[J].Information and Control, 2000,29(4):329-339.

[11] 張雅妮.基于粒子群算法模糊控制自動舵的研究與仿真[D].哈爾濱:哈爾濱工程大學自動化學院,2010.

[12] 黃勝忠.遺傳算法在企業(yè)車間調(diào)度中的應(yīng)用[J].微計算機信息, 2008, 7(3):266-267.

HUANG S Z.Application of genetic algorithm in the enterprise shop scheduling[J].Microcomputer Information, 2008, 7(3):266-267.

[13]朱峰,宋余慶,金華,等.改良遺傳算法在圖像多閾值分割中的應(yīng)用[J].江蘇大學學報(自然科學版),2003,24(6):66-69.

ZHU F, SONG Y Q,JIN H,et al.Improved genetie algorithm for multi-level threshold image segmentation[J].Journal of Jiangsu University(Natural Science Edition), 2003, 24(6):66-69.

[14] 喬軍.遺傳算法在圖像處理中的應(yīng)用[J].中國農(nóng)業(yè)大學學報, 1998, 3(4):80-82.

QIAO J.Application of genetic algorithm for image proceeding[J].Journal of China Agricultural University,1998, 3(4):80-82.

[15] 宣兆新,陸金桂,石云,等.基于改進的遺傳算法的圖像恢復[J].計算機應(yīng)用與軟件, 2010, 27(3):252-254.

XUAN Z X,LU J G, SHI Y, et al. Image restoration based on improved genetic algorithm[J].Computer Applications and Software, 2010, 27(3):252-254.

A Simulated Pursuit Algorithm

Liu Wei， Xie Yue-shan

(School of Applied Mathematics, Guangdong University of Technology, Guangzhou 510520, China)

Abstract:A new simulated pursuit intelligent swarm algorithm is proposed. In the process of pursuit for athletes simulated in Long-distance Race, a pursuit operator and an exploring operator are presented. In the algorithm, the leader uses an exploring operator to obtain the better position, and the rest of individuals often use a pursuit operator to follow or surpass competitors and the population evolution is realized. The simulation results show that simulated pursuit algorithm is an effective and robust method with better solution accuracy and higher convergence speed.

Key words:simulated pursuit; intelligent algorithm; exploring operator; pursuit operator

收稿日期:2015-04-17

基金項目:國家自然科學基金資助項目(61202269)

作者簡介:劉偉(1970-)，男，副教授，碩士生導師，主要研究方向為優(yōu)化理論、智能計算.

doi:10.3969/j.issn.1007-7162.2016.02.006

中圖分類號:TP301.6

文獻標志碼:A

文章編號:1007-7162(2016)02-0031-06