人工鱼群算法详解
1、起源
??人工魚群算法是李曉磊等人于2002年在動(dòng)物群體智能行為研究的基礎(chǔ)上提出的一種新型方盛優(yōu)化算法，該算法根據(jù)水域中魚生存數(shù)目最多的地方就是本水域中富含營養(yǎng)物質(zhì)最多的地方這一特點(diǎn)來模擬魚群的覓食行為而實(shí)現(xiàn)尋優(yōu)。算法主要利用魚的三大基本行為：覓食、聚群和追尾行為，采用自上而下的尋優(yōu)模式從構(gòu)造個(gè)體的底層行為開始，通過魚群中各個(gè)體的局部尋優(yōu)，達(dá)到全局最優(yōu)值在群體中凸顯出來的目的。
??該方法采用自下而上的尋優(yōu)思路，首先設(shè)計(jì)單個(gè)個(gè)體的感知、行為機(jī)制，然后將一個(gè)或一群實(shí)體放置在環(huán)境中，讓他們在環(huán)境的交互作用中解決問題。
2、生態(tài)學(xué)基礎(chǔ)
??在一片水域中，魚存在的數(shù)目最多的地方就是本水域富含營養(yǎng)物質(zhì)最多的地方，依據(jù)這一特點(diǎn)來模仿魚群的覓食、聚群、追尾等行為，從而實(shí)現(xiàn)全局最優(yōu)，這就是魚群算法的基本思想。魚類活動(dòng)中，覓食行為、群聚行為、追尾行為和隨機(jī)行為與尋優(yōu)命題的解決有較為密切的關(guān)系，如何利用簡單有效的方式來構(gòu)造和實(shí)現(xiàn)這些行為將是算法實(shí)現(xiàn)的主要為題。
3、人工魚的結(jié)構(gòu)模型
??人工魚是真實(shí)魚抽象化、虛擬化的一個(gè)實(shí)體，其中封裝了自身數(shù)據(jù)和一系列行為，可以接受環(huán)境的刺激信息，做出相應(yīng)的活動(dòng)。其所在的環(huán)境由問題的解空間和其他人工魚的狀態(tài)，它在下一時(shí)刻的行為取決于自身的狀態(tài)和環(huán)境的狀態(tài)，并且它還通過自身的活動(dòng)來影響環(huán)境，進(jìn)而影響其他人工魚的活動(dòng)。
??人工魚對外的感知是依靠視覺來實(shí)現(xiàn)的，人工魚的模型中使用如下方法實(shí)現(xiàn)人工魚的虛擬視覺：
Xnext=X+XV?X||XV?X||?Step?Rand()
其中 Rand()為隨機(jī)函數(shù)，產(chǎn)生0到1之間的隨機(jī)數(shù)， Step為步長。
人工魚視覺的概念
3.1、人工魚中封裝的變量和函數(shù)
變量部分：人工魚的總數(shù)N、人工魚個(gè)體的狀態(tài)X=(x1,x2,...,xn)（其中xi(i=1,2,...,n)為尋優(yōu)的變量）、人工魚移動(dòng)的最大步長Step、人工魚的視野Visual、嘗試次數(shù)Try?number、擁擠度因子δ、人工魚個(gè)體i,j之間的距離dij=|xi?xj|。
函數(shù)部分：人工魚當(dāng)前所在位置食物濃度表示為Y=f(x)（Y為目標(biāo)函數(shù)值）、人工魚各種行為函數(shù)（覓食行為Prey()、聚群行為Swarm()、追尾行為Follow()、隨機(jī)行為Move()以及行為評價(jià)函數(shù)Evaluate()）。
3.2、人工魚的四種基本行為算法描述
3.2.1、覓食行為Prey()
??這是魚趨向食物的一種活動(dòng)，一般認(rèn)為它是通過視覺或味覺來感知水中的食物量或食物濃度來選擇行動(dòng)的方向。設(shè)置人工魚當(dāng)前狀態(tài)，并在其感知范圍內(nèi)隨機(jī)選擇另一個(gè)狀態(tài)，如果得到的狀態(tài)的目標(biāo)函數(shù)大于當(dāng)前的狀態(tài)，則向新選擇得到的狀態(tài)靠近一步，反之，重新選取新狀態(tài)，判斷是否滿足條件，選擇次數(shù)達(dá)到一定數(shù)量后，如果仍然不滿足條件，則隨機(jī)移動(dòng)一步。
算法描述：人工魚Xi在其視野內(nèi)隨機(jī)選擇一個(gè)狀態(tài)Xj
分別計(jì)算 Xi與 Xj的目標(biāo)函數(shù)值 Yi與 Yj，如果發(fā)現(xiàn) Yj比 Yi好，則 Xi向 Xj的方向移動(dòng)一部：
Xt+1i=Xti+Xj?Xti||Xj?Xti||?Step?Rand()
否則， Xi繼續(xù)在其視野內(nèi)選擇狀態(tài) Xj，判斷是否滿足前進(jìn)條件，反復(fù)嘗試 Tray?number次后，仍沒有滿足前進(jìn)條件，則執(zhí)行隨機(jī)行為。
3.2.2、聚群行為Swarm()
??大量或少量的魚聚集成群，進(jìn)行集體覓食和躲避敵害，這是它們在進(jìn)化過程中形成的一種生存方式。人工魚探索當(dāng)前鄰居內(nèi)的伙伴數(shù)量，并計(jì)算伙伴的中心位置，然后把新得到的中心位置的目標(biāo)函數(shù)與當(dāng)前位置的目標(biāo)函數(shù)相比較，如果中心位置的目標(biāo)函數(shù)優(yōu)于當(dāng)前位置的目標(biāo)函數(shù)并且不是很擁擠，則當(dāng)前位置向中心位置移動(dòng)一步，否則執(zhí)行覓食行為。魚聚群時(shí)會(huì)遵守兩條規(guī)則：一是盡量向鄰近伙伴的中心移動(dòng)，二是避免過分擁擠。
算法描述：人工魚Xi搜索當(dāng)前視野內(nèi)（dij<Vaisual）的伙伴數(shù)目nf和中心位置Xc，若Yc/nf>δYi，則表明伙伴中心位置狀態(tài)較優(yōu)且不太擁擠，則Xi朝伙伴的中心位置移動(dòng)一步：
否則進(jìn)行覓食行為。
3.2.3、追尾行為Follow()
??當(dāng)某一條魚或幾條魚發(fā)現(xiàn)食物時(shí)，它們附近的魚會(huì)尾隨而來，導(dǎo)致更遠(yuǎn)處的魚也會(huì)尾隨過來。人工魚探索周圍鄰居魚的最優(yōu)位置，當(dāng)最優(yōu)位置的目標(biāo)函數(shù)值大于當(dāng)前位置的目標(biāo)函數(shù)值并且不是很擁擠，則當(dāng)前位置向最優(yōu)鄰居魚移動(dòng)一步，否則執(zhí)行覓食行為。
算法描述：人工魚Xi搜索當(dāng)前視野內(nèi)（dij<Vaisual）的伙伴中函數(shù)Yj最優(yōu)伙伴Xj，如果Yj/nf>δYi，表明最優(yōu)伙伴的周圍不太擁擠，則Xi朝詞伙伴移動(dòng)一步：
否則執(zhí)行覓食行為。
3.2.4、隨機(jī)行為Move()
??它是覓食行為的一個(gè)缺省行為，指人工魚在視野內(nèi)隨機(jī)移動(dòng)。當(dāng)發(fā)現(xiàn)食物時(shí)，會(huì)向食物逐漸增多的方向快速的移動(dòng)。
算法描述人工魚Xi隨機(jī)移動(dòng)一步，到達(dá)一個(gè)新的狀態(tài)：
4、人工魚群算法描述
公告牌是記錄最優(yōu)人工魚個(gè)體狀態(tài)的地方。每條人工魚在執(zhí)行完一次迭代后將自身當(dāng)前狀態(tài)與公告牌中記錄的狀態(tài)進(jìn)行比較，如果優(yōu)于公告牌中的狀態(tài)則用自身狀態(tài)更新公告牌中的狀態(tài)，否則公告牌的狀態(tài)不變。當(dāng)整個(gè)算法的迭代結(jié)束后，公告牌的值就是最優(yōu)解。
行為評價(jià)是用來反映魚自主行為的一種方式，在解決優(yōu)化問題時(shí)選用兩種方式評價(jià)：一種是選擇最優(yōu)行為執(zhí)行；另一種是選擇較優(yōu)方向。對于解決極大值問題，可以使用試探法，即模擬執(zhí)行群聚、追尾等行為，然后評價(jià)行動(dòng)后的值選擇最優(yōu)的來執(zhí)行，缺省的行為為覓食行為。
迭代終止條件：通常的方法是判斷連續(xù)多次所得值得均方差小魚允許的誤差；或判斷聚集于某個(gè)區(qū)域的人工魚的數(shù)目達(dá)到某個(gè)比例；或連續(xù)多次所得的均值不超過已尋找的極值；或限制最大迭代次數(shù)。若滿足終止條件，則輸出公告牌的最優(yōu)記錄；否則繼續(xù)迭代。
人工魚群算法的步驟：
5、人工魚群算法的尋優(yōu)原理
??人工魚群算法在尋優(yōu)的過程中，可能會(huì)集結(jié)在幾個(gè)局部最優(yōu)解的周圍，使人工魚跳出局部最優(yōu)解，實(shí)現(xiàn)全局尋優(yōu)的因素主要有：
- 覓食行為中重復(fù)次數(shù)較少時(shí)，為人工魚提供了隨機(jī)移動(dòng)的機(jī)會(huì)，從而可能跳出局部最優(yōu)解；
- 隨機(jī)步長使得人工魚在前往局部最優(yōu)解的途中，有可能轉(zhuǎn)向全局最優(yōu)解；
- 擁擠度因子 δ 限制了聚群的規(guī)模，使得人工魚能夠更廣泛的尋優(yōu)；
- 聚群行為能夠促使少出陷于局部最優(yōu)解的人工魚趨向全局最優(yōu)解的人工魚方向聚集，從而逃出局部最優(yōu)解；
- 追尾行為加快了人工魚向更優(yōu)狀態(tài)游動(dòng)。
6、參數(shù)設(shè)置與性能
6.1、收斂基礎(chǔ)
??人工魚群算法中，覓食行為奠定了算法收斂的基礎(chǔ)；聚群行為增強(qiáng)了算法收斂的穩(wěn)定性；追尾行為增強(qiáng)了算法收斂的快速性和全局性；其評價(jià)行為也對算法收斂的速度和穩(wěn)定性提供了保障。
6.2、各種參數(shù)對收斂性的影響
??人工魚群算法有5個(gè)基本參數(shù)：群規(guī)模N、人工魚的視野Visual、步長step、擁擠度因子δ、重復(fù)次數(shù)Try?number。
1. 視野Visual：由于視野對算法中個(gè)行為都有較大影響，因此，它的變化對收斂性能影響也比較復(fù)雜。當(dāng)視野范圍較小時(shí)，人工魚的覓食行為和隨機(jī)行為比較突出；視野范圍較大時(shí)，人工魚的追尾行為和聚群行為將變得比較突出，相應(yīng)的算法的復(fù)雜度也會(huì)有所上升?？偟膩碚f：視野越大，越容易使人工魚發(fā)現(xiàn)全局最優(yōu)解并收斂。
2. 步長step：對于固定步長，隨著步長的增加，收斂的速度得到了一定的加速，但在超過一定的范圍后，有使得收斂速度減緩，步長過大時(shí)會(huì)出現(xiàn)震蕩現(xiàn)象而大大影響收斂速度。采用隨機(jī)步長的方式在一定程度上防止了震蕩現(xiàn)象的發(fā)生，并使得該參數(shù)的敏感度大大降低了，但最快的收斂速度還是最優(yōu)固定步長的收斂速度，所以，對于特定的優(yōu)化問題，我們可以考慮采用合適的固定步長或者變尺度方法來提高收斂速度。
3. 群規(guī)模N：人工魚的數(shù)目越多，跳出局部最優(yōu)解的能力越強(qiáng)，同時(shí)，收斂的速度也越快。當(dāng)然，付出的代價(jià)就是算法每次迭代的計(jì)算量也越大，因此，在使用過程中，滿足穩(wěn)定收斂的前提下，應(yīng)當(dāng)盡可能的減少個(gè)圖數(shù)目。
4. 嘗試次數(shù)Try?number：嘗試次數(shù)越多，人工魚的覓食行為能力越強(qiáng)，收斂的效率也越高。在局部極值突出的情況下，應(yīng)該適當(dāng)?shù)臏p少以增加人工魚隨機(jī)游動(dòng)的概率，克服局部最優(yōu)解。
5. 擁擠度因子δ：在求極大值問題中，δ=1/(αnmax),α∈(0,1]；在求極小值問題中，δ=αnmax,α∈(0,1]。其中α為極值接近水平，nmax為期望在該鄰域內(nèi)聚集的最大人工魚數(shù)目。擁擠度因子與nf相結(jié)合，通過人工魚是否執(zhí)行追尾和聚群行為對優(yōu)化結(jié)果產(chǎn)生影響。以極大值為例（極小值的情況正好與極大值相反），δ越大，表明允許的擁擠程度越小，人工魚擺脫局部最優(yōu)解的能力越強(qiáng)；但是收斂速度會(huì)有所減緩，這主要因?yàn)槿斯~在逼近最優(yōu)解的同時(shí)，會(huì)因避免過分擁擠而隨機(jī)走開或者受其他人工魚的排斥作用，不能精確逼近極值點(diǎn)?？梢?#xff0c;雖然δ的引入避免了人工魚過度擁擠而陷入局部最優(yōu)解，但是另一方面，該參數(shù)會(huì)使得位于極值點(diǎn)附件的人工魚之間存在相互排斥的影響，而難以想極值點(diǎn)精確逼近。所以，對于某些局部極值不是很嚴(yán)重的具體問題，可以忽略擁擠的因素，從而在簡化算法的同時(shí)也加快算法的收斂速度和提高結(jié)果的精確程度。
對追尾行為的描述
上圖中，人工魚 af0為人工魚 af1?5在各自視野內(nèi)的最優(yōu)人工魚，其食物濃度為 Yj， C1為以 af0為圓心，以視野為半徑的圓，即能探知 af0的最遠(yuǎn)距離，人工魚越靠近 af0，狀態(tài)越優(yōu)。在極大值情況下：當(dāng) δnf≤1時(shí)，所有人工魚 af1?5都執(zhí)行追尾行為，向 af0移動(dòng)；當(dāng) δnf>1時(shí)，若 C2的食物濃度為 Yj/δnf的等濃度食物圈，則 C2與 C1之間的人工魚 af1、 af2、 af3執(zhí)行追尾行為，向 af0移動(dòng)，人工魚 af4、 af5執(zhí)行覓食行為。此時(shí) δnf越大，執(zhí)行追尾行為的人工魚越少，反之越多。
7、人工魚群算法的特點(diǎn)
總結(jié)
- 上一篇： 使用C#和Excel进行报表开发（四）－
- 下一篇： Linux中的Interrupted s