一種多算法融合的改進(jìn)人工魚(yú)群算法

摘? 要：為解決傳統(tǒng)人工魚(yú)群算法在求解高維問(wèn)題時(shí)候，存在收斂速度慢且收斂精度不高的問(wèn)題，提出一種多算法融合的改進(jìn)人工魚(yú)群算法。通過(guò)引入粒子群優(yōu)化算法的學(xué)習(xí)機(jī)制和遺傳算法的交叉變異迭代，提升算法的收斂速度和收斂精度。最后通過(guò)仿真實(shí)驗(yàn)，驗(yàn)證了PSO-GA-AFSA算法在高緯度尋優(yōu)中具有更優(yōu)的性能，同時(shí)又具有與傳統(tǒng)方法相融合的基礎(chǔ)，有著良好的應(yīng)用前景。

關(guān)鍵詞：粒子群優(yōu)化算法;人工魚(yú)群算法;遺傳算法;混合算法;算法融合

Abstract：In order to solve the problem of slow convergence speed and low convergence accuracy in solving high-dimensional problems of traditional artificial fish swarm calculations，an improved artificial fish swarm algorithm（PSO-GA-AFSA）with multiple algorithms fusion is proposed. By introducing the learning mechanism of PSO and the cross mutation iteration of GA，the convergence speed and accuracy of the algorithm are improved. Finally，through simulation experiments，it is verified that the PSO-GA-AFSA algorithm has better performance in high-latitude optimization，and at the same time has the basis of fusion with traditional methods，and has a good application prospect.

Keywords：PSO;AFSA;GA;hybrid algorithm;algorithm fusion

0? 引? 言

最優(yōu)化問(wèn)題涉及國(guó)民經(jīng)濟(jì)的各個(gè)領(lǐng)域，例如：工業(yè)、農(nóng)業(yè)、通信、化工、交通、國(guó)防等諸多領(lǐng)域，其對(duì)于推動(dòng)社會(huì)經(jīng)濟(jì)發(fā)展的重要性不言而喻。根據(jù)作者多年從事的興趣愛(ài)好研究得出：傳統(tǒng)的優(yōu)化方法如黃金分割法、梯度下降法、擬牛頓法等，在面對(duì)這些復(fù)雜性高、非線性、變量維度高、多約束條件的項(xiàng)目問(wèn)題時(shí)，不管在計(jì)算速度、結(jié)果的精度、魯棒性等方面遠(yuǎn)遠(yuǎn)不能滿足解決當(dāng)前問(wèn)題的需求。傳統(tǒng)智能算法如遺傳算法，模擬退火算法等雖然能較好解決優(yōu)化問(wèn)題，但也存在收斂速度慢，收斂精度低的問(wèn)題?；诖?，本文提出了以人工魚(yú)群算法（Artificial Fish Swarms Algorithm，AFSA）為框架，融合粒子群算法和遺傳算法的新型算法，同時(shí)解決收斂速度慢和精度低的問(wèn)題。

1? 粒子群優(yōu)化算法

粒子群優(yōu)化（Particle Swarm Optimization，PSO）是Kennedy和Eberhart受人工生命研究結(jié)果的啟發(fā)、通過(guò)模擬鳥(niǎo)群覓食過(guò)程中的遷徙和群聚行為而提出的一種基于群體智能的全局隨機(jī)搜索算法。

在算法的進(jìn)化過(guò)程中，粒子需要一直向兩個(gè)極值進(jìn)行學(xué)習(xí)：一個(gè)是到個(gè)體歷史最優(yōu)位置，即粒子自身迭代到當(dāng)前位置時(shí)最優(yōu)的位置記錄;另一個(gè)是種群歷史最優(yōu)位置，即整個(gè)種群發(fā)展到當(dāng)前出現(xiàn)過(guò)的全局最優(yōu)位置。粒子通過(guò)這兩個(gè)“經(jīng)驗(yàn)”進(jìn)行學(xué)習(xí)，不斷的改變自身的飛行方向和飛行速度，其速度和位置更新公式為：

其中， 為第t次迭代時(shí)候第id個(gè)粒子的速度，pid為第id個(gè)粒子的歷史最優(yōu)位置，pgd為當(dāng)前全局最優(yōu)的位置， 為第t次迭代時(shí)候第id個(gè)粒子的位置信息，r1，r2為（0，1）之間的隨機(jī)數(shù)，c1和c2統(tǒng)稱(chēng)為學(xué)習(xí)因子，c1學(xué)習(xí)因子主要負(fù)責(zé)該粒子向過(guò)去學(xué)習(xí)的權(quán)重，c2主要負(fù)責(zé)該粒子向全部他人學(xué)習(xí)的權(quán)重，其值一般取值為c1+c2=2。

2? 遺傳算法

遺傳算法（Genetic Algorithm，GA）是以達(dá)爾文的進(jìn)化論和孟德?tīng)柕倪z傳變異理論為科學(xué)理論依據(jù)的算法。

基礎(chǔ)遺傳算法的遺傳操作主要有三種：選擇操作、雜交操作和變異操作。接下來(lái)分別對(duì)這三種操作進(jìn)行詳細(xì)介紹，以下的方法都在實(shí)數(shù)編碼的方式下進(jìn)行。

2.1? 選擇操作

選擇操作（selection）提供了遺傳算法種群進(jìn)化的驅(qū)動(dòng)力，其作用是保證種群中的優(yōu)良基因能延續(xù)遺傳給下一代，提高后代的適應(yīng)能力，從而提高遺傳算法的全局收斂性，使算法收斂于全局最優(yōu)解。

2.2? 交叉操作

交叉操作（crossover）通常先按照一定的選擇機(jī)制從群體中選擇兩個(gè)優(yōu)秀的父輩個(gè)體，然后按照一定交叉策略來(lái)交換兩個(gè)個(gè)體的某個(gè)或某些位的基因信息。交叉算子的設(shè)計(jì)對(duì)遺傳算法的影響非常大，如果交叉算子涉及的基因位數(shù)太小，即基因重組減少，就不利于較優(yōu)后代的產(chǎn)生，如果交叉算子太過(guò)于單一，也會(huì)造成算法搜索能力的減弱。因此交叉算子的制定需要根據(jù)實(shí)際問(wèn)題來(lái)進(jìn)行調(diào)整。

2.3? 變異操作

變異操作（mutation）可以增強(qiáng)算法的局部搜索能力并且也能很好的維持群體的多樣性，幫助算法逃離局部極值點(diǎn)。交叉和變異相互配合，共同完成對(duì)搜索空間的全局搜索和局部搜索，從而使遺傳算法能夠以良好的搜索性能完成最優(yōu)化問(wèn)題的尋優(yōu)過(guò)程。

3? AFSA原理

在AFSA中，人工魚(yú)有3種基本行為：覓食、聚群、追尾。

3.1? 覓食行為

在求極大值問(wèn)題中，設(shè)第i條人工魚(yú)在當(dāng)前環(huán)境位置狀態(tài)向量為Xi，適應(yīng)度值為Yi，在視野范圍Visual范圍內(nèi)隨機(jī)選擇下一個(gè)位置的狀態(tài)向量為Xj，適應(yīng)度值為Yj，若Yj>Yi，則該條人工魚(yú)朝著食物濃度更多（即可行解空間較優(yōu)）的方向游動(dòng)一步;如若Yj

3.2? 聚群行為

設(shè)第i只人工魚(yú)在當(dāng)前環(huán)境狀態(tài)向量為Xi，適應(yīng)度值為Yi，其視野范圍內(nèi)（即di，jδYi（δ為擁擠度因子），表明魚(yú)群中央食物較豐富并且視野范圍內(nèi)的群體不太擁擠，此時(shí)該條人工魚(yú)朝魚(yú)群中央位置方向游動(dòng)，否則執(zhí)行覓食行為。

3.3? 追尾行為

設(shè)第i只人工魚(yú)在當(dāng)前狀態(tài)為Xi，適應(yīng)度值為Yi，其視覺(jué)范圍內(nèi)（即di，jδYi（δ為擁擠度因子），表明人工魚(yú)Xj在該環(huán)境位置狀態(tài)下食物濃度較為豐盛并且該最優(yōu)個(gè)體魚(yú)周邊不太擁擠，此時(shí)該人工魚(yú)朝Xj的方向前進(jìn)一步;否則執(zhí)行覓食行為。

4? 多算法融合人工魚(yú)群算法

結(jié)合上面對(duì)各項(xiàng)算法的優(yōu)劣勢(shì)的分析，本文提出了一種基于PSO和GA多算法融合的人工魚(yú)群智能優(yōu)化算法（PSO-GA-AFSA）。為進(jìn)一步提高算法的收斂速度，將PSO算法中的“社學(xué)認(rèn)知”這一特點(diǎn)，引入到人工魚(yú)群中，讓魚(yú)群在每次做完行為選擇之后，同步向種群全體中最優(yōu)個(gè)體進(jìn)行學(xué)習(xí)，讓魚(yú)群中的所有個(gè)體都具有朝最優(yōu)解方向的趨向性;為進(jìn)一步克服算法陷入局部極值并增加算法的探索能力，將遺傳算法引入到人工魚(yú)群當(dāng)中，并將該算法作為魚(yú)群的一個(gè)算子，魚(yú)群的繁殖遵循“精英繁殖策略”，即每一次迭代只有種群中適應(yīng)度最高的個(gè)體，才有機(jī)會(huì)和其他人工魚(yú)進(jìn)行交叉變異，即增強(qiáng)種群的多樣性也將上一代種群最優(yōu)良個(gè)體的基因保留了下來(lái);最后為了增加算法的收斂精度，為人工魚(yú)群引入依賴(lài)于迭代情況的自適應(yīng)算子，讓算法在前期能以較大的步長(zhǎng)和視野進(jìn)行探索，在后期以很小的步長(zhǎng)和視野進(jìn)行探索，以增加收斂精度。PSO-GA-AFSA算法流程為：

（1）設(shè)定算法參數(shù)包括人工魚(yú)條數(shù)為N，視野為V，步長(zhǎng)為S，擁擠度因子為δ，最大嘗試次數(shù)為try_number，最大迭代次數(shù)為T(mén)max，學(xué)習(xí)參數(shù)為c1、c2;

（2）計(jì)算適應(yīng)度值，選出最優(yōu)個(gè)體，并將最優(yōu)個(gè)體更新到公告板上;

（3）魚(yú)群模擬進(jìn)行覓食，聚群，追尾行為，選擇最優(yōu)行為后，結(jié)合PSO進(jìn)行行為更新;

（4）最優(yōu)個(gè)體和其他個(gè)體進(jìn)行交叉變異并更新種群;

（5）更新種群適應(yīng)度值并更新公告板;

（6）所有人工魚(yú)新型更新完成之后，判斷是否達(dá)到最大迭代次數(shù)，如果否，則轉(zhuǎn)到（3）繼續(xù)，否則結(jié)束算法。

5? 仿真結(jié)果與分析

本文分別用4個(gè)多維度函數(shù)Sphere、Ackley、Levy、Griewank在20維的高維條件下測(cè)試算法的性能，并與自適應(yīng)人工魚(yú)群和粒子群算法進(jìn)行性能比較。表1展示了本文算法和AAFAS算法，PSO算法在4個(gè)測(cè)試函數(shù)下的最好，平均和最壞的變現(xiàn)情況。圖1展示了本文算法和其他算法的迭代速度對(duì)比。

從表1可以看出，本文提出的算法在收斂精度上面高于其他兩個(gè)算法很多個(gè)數(shù)量級(jí)，同時(shí)通過(guò)圖1可以明顯看出，混合算法在收斂的速度上面均優(yōu)于或者等于其他兩個(gè)算法。

6? 結(jié)? 論

針對(duì)AFSA全局尋優(yōu)能力不足，最后尋優(yōu)精度低的問(wèn)題，本文通過(guò)引入PSO的“自我認(rèn)知”和“社會(huì)認(rèn)知”來(lái)提升AFSA的全局尋優(yōu)能力，同時(shí)引入遺傳算法的概念讓魚(yú)群能一直保持較高的多樣性，并且讓算法具有較好的性能穩(wěn)定性。

參考文獻(xiàn)：

[1] 吳愛(ài)燕.人工智能的未來(lái)與挑戰(zhàn) [J].唐山學(xué)院學(xué)報(bào)，2009，22（6）：69-71+100.

[2] BONABEAU E，DORIGO M，THERAULAZ G.Inspiration for optimization from social insect behavior [J].Nature，2000，406（6791）：39-42.

[3] 張梅鳳.人工魚(yú)群智能優(yōu)化算法的改進(jìn)及應(yīng)用研究 [D].大連：大連理工大學(xué)，2008.

[4] 陳斐.改進(jìn)的人工魚(yú)群算法分析與研究 [D].西安：西安電子科技大學(xué)，2012.

[5] 李曉磊.一種新型的智能優(yōu)化方法-人工魚(yú)群算法 [D].杭州：浙江大學(xué)，2003.

[6] 范玉軍，王冬冬，孫明明.改進(jìn)的人工魚(yú)群算法 [J].重慶師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2007，24（3）：23-26.

[7] 張梅鳳.人工魚(yú)群智能優(yōu)化算法的改進(jìn)及應(yīng)用研究 [D].大連：大連理工大學(xué)，2008.

[8] 王培崇，雷鳳君，錢(qián)旭.改進(jìn)人工魚(yú)群算法及其收斂性分析 [J].科學(xué)技術(shù)與工程，2013，13（3）：616-620.

[9] 葛君偉，郭強(qiáng)，方義秋.一種基于改進(jìn)蟻群算法的多目標(biāo)優(yōu)化云計(jì)算任務(wù)調(diào)度策略 [J].微電子學(xué)與計(jì)算機(jī)，2017，34（11）：63-67.

作者簡(jiǎn)介：金曉波（1992—），男，漢族，浙江臺(tái)州人，碩士研究生，研究方向：大數(shù)據(jù)和智能優(yōu)化算法。