基于魚群算法的函數(shù)尋優(yōu)算法-應(yīng)用數(shù)學(xué)畢業(yè)論文

1、<p>　　西 南 交 通 大 學(xué)</p><p>　　本科畢業(yè)設(shè)計(jì)（論文）</p><p>　　基于魚群算法的函數(shù)尋優(yōu)算法</p><p>　　年 級(jí):2013級(jí)</p><p>　　學(xué) 號(hào):20133798</p><p>　　姓 名:林安森</p><p>　　

2、專 業(yè):數(shù)學(xué)與應(yīng)用數(shù)學(xué)</p><p><b>　　指導(dǎo)老師:卿銘</b></p><p>　　2017年 5 月 </p><p>　　院 系 數(shù)學(xué)學(xué)院 專 業(yè) 數(shù)學(xué)與應(yīng)用數(shù)學(xué) </p><p&

3、gt;　　年 級(jí) 2013 姓 名 林安森 </p><p>　　題 目 基于魚群算法的函數(shù)尋優(yōu)算法 </p><p><b>

4、　　指導(dǎo)教師</b></p><p>　　評(píng) 語 </p><p>　　指導(dǎo)教師 (簽章)</p><p><b>　　評(píng) 閱 人</b></p><p>　　

5、評(píng) 語 </p><p>　　評(píng) 閱 人 (簽章)</p><p><b>　　成 績(jī)</b></p><p>　　答辯委員會(huì)主任 (簽章)</p>&l

6、t;p>　　年 月 日</p><p>　　畢業(yè)設(shè)計(jì)（論文）任務(wù)書</p><p>　　班 級(jí) 學(xué)生姓名 學(xué) 號(hào) </p><p>　　發(fā)題日期： 年 月 日 完成日期： 月

7、 日</p><p>　　題 目 </p><p>　　1、本論文的目的、意義 </p><p>　　2、學(xué)生應(yīng)完成的任務(wù)

8、 </p><p>　　3、論文各部分內(nèi)容及時(shí)間分配：（共 12 周）</p><p>　　第一部分 ( 周) </p><p>　　第二部分

9、 ( 周) </p><p>　　第三部分 ( 周)</p><p>　　第四部分 ( 周) </p><p>　　第五部分

10、 ( 周)</p><p>　　評(píng)閱及答辯 ( 周)</p><p>　　備 注

11、</p><p>　　指導(dǎo)教師： 年 月 日</p><p>　　審 批 人： 年 月 日</p><p><b>　　摘 要</b></p><p>　　群體智能算法已經(jīng)成為尋優(yōu)算法的重要研究方向，國內(nèi)外的學(xué)者都在不斷的探索新的智能算法。在一些尋優(yōu)問題中，如在對(duì)R

12、osenbrock函數(shù)這一類非凸，病態(tài)單峰函數(shù)的尋優(yōu)，傳統(tǒng)方法如牛頓法等并不能得到全局最優(yōu)解，容易陷入局部最優(yōu)解，并且計(jì)算過程復(fù)雜，但群體智能算法就能很好的解決此類問題。智能優(yōu)化算法包括遺傳算法、蟻群算法。模擬退火算法和人工魚群算法等。</p><p>　　本文主要講述人工魚群算法。該算法是一種模擬低等生物行為的仿生算法，是一種新型的尋優(yōu)策略，并且具有魯棒性強(qiáng)、全局收斂性好、對(duì)初值敏感度低等眾多優(yōu)點(diǎn)。本文首先對(duì)人

13、工魚群算法的原理以及基本行為思想和實(shí)現(xiàn)方式進(jìn)行了詳細(xì)的描述，給出了流程圖和主要實(shí)現(xiàn)方法，并編寫尋優(yōu)代碼，利用經(jīng)典智能算法驗(yàn)證函數(shù)，帶入實(shí)驗(yàn)進(jìn)行模擬仿真。然后通過對(duì)其中一些關(guān)鍵參數(shù)如視野、步長(zhǎng)等進(jìn)行分析，了解到算法后期收斂精度低收斂速度慢等缺點(diǎn)，對(duì)該算法進(jìn)行改進(jìn)。加入了自適應(yīng)步長(zhǎng)，初始值均勻分布等改進(jìn)方案，使得算法在前期能更好的照顧全局性，在后期加快收斂速度。最后把改進(jìn)后的人工魚群算法應(yīng)用到了組合優(yōu)化問題中。通過旅行商問題（Travell

14、ing Salesman Problem簡(jiǎn)稱TSP）舉例，描述人工魚群算法在該問題上的實(shí)現(xiàn)方式，編程解決了16個(gè)城市的TSP問題。</p><p>　　目前魚群算法的應(yīng)用還局限于無約束、連續(xù)、單目標(biāo)的確定性優(yōu)化問題上，在日后的研究中，應(yīng)當(dāng)注重該算法在多約束、離散、多目標(biāo)等不確定優(yōu)化問題上的研究和應(yīng)用。</p><p>　　關(guān)鍵詞：人工魚群算法 全局 鄰域 最優(yōu)值</p>

15、<p><b>　　Abstract</b></p><p>　　Group intelligence algorithm has become an important research direction of the optimization algorithm, domestic and foreign scholars are constantly exploring n

16、ew intelligent algorithms. In some problems, for example, in the case of Rosenbrock function, we can not obtain the global optimal solution, which is easy to fall into the local optimal solution and the complicated proce

17、ss, but the traditional method such as Newton method can be obtained. The group intelligence algorithm can solve such pro</p><p>　　This paper focuses on the artificial fish swarm algorithm. The algorithm is

18、a kind of bionic algorithm which simulates the low biological behavior. It is a new kind of optimization strategy, and has many advantages such as strong robustness, good global convergence and low sensitivity to the ini

19、tial value. In this paper, the principle of artificial fish swarm algorithm and the basic behavior thought and realization method are described in detail. The flow chart and main implementation method are</p><

20、p>　　At present, the application of fish algorithm is also limited to the problem of deterministic optimization of unconstrained, continuous and single target. In the future research, we should pay attention to the res

21、earch of discrete, multi-objective and other uncertain optimization problems. application.</p><p>　　key words：AFSA Global Area The optimal value</p><p>　　摘 要5</p><p>　　A

22、bstract5</p><p><b>　　7</b></p><p><b>　　緒論8</b></p><p>　　1.課題學(xué)術(shù)背景和意義8</p><p><b>　　2.國內(nèi)外進(jìn)展8</b></p><p>　　3.論文各部分的主要內(nèi)容

23、9</p><p>　　第一章 魚群算法原理9</p><p><b>　　1.1群體智能9</b></p><p>　　1.1.1群體智能遵守五條行為準(zhǔn)則：10</p><p>　　1.1.2 群體智能的特點(diǎn)：10</p><p>　　1.2人工魚群模式10</p>&

24、lt;p>　　1.2.1人工魚群算法的概念11</p><p>　　1.1.2 人工魚群算法的主要行為12</p><p><b>　　1.3人工魚13</b></p><p>　　1.4問題的解決13</p><p>　　第二章 魚群算法的實(shí)現(xiàn)13</p><p>　　2.1變量

25、及函數(shù)定義14</p><p>　　2.2行為描述15</p><p>　　2.3算法描述17</p><p>　　2.4算法驗(yàn)證18</p><p>　　2.5各個(gè)參數(shù)對(duì)結(jié)果的影響20</p><p>　　2.6人工魚群算法的收斂基礎(chǔ)23</p><p>　　第三章 算法的改進(jìn)2

26、4</p><p>　　3.1自適應(yīng)步長(zhǎng)魚群算法24</p><p>　　3.1.2仿真實(shí)驗(yàn)以及分析26</p><p>　　3.2初始均勻分布全局人工魚群算法28</p><p>　　3.2.1初始均勻分布28</p><p>　　3.2.2 全局人工魚群算法29</p><p>　

27、　3.2.3仿真實(shí)驗(yàn)以及分析30</p><p>　　第四章 魚群算法應(yīng)用32</p><p>　　4.1組合優(yōu)化問題33</p><p>　　4.2 旅行商問題33</p><p>　　4.3TSP問題求解34</p><p>　　4.3.1TSP求解一般思路34</p><p>

28、　　4.3.2人工魚群算法求解TSP35</p><p>　　4.3.3行為選擇36</p><p>　　4.4.4仿真實(shí)驗(yàn)36</p><p><b>　　結(jié)論38</b></p><p><b>　　參考文獻(xiàn)39</b></p><p><b>　　緒

29、論</b></p><p>　　1.課題學(xué)術(shù)背景和意義</p><p>　　隨著大數(shù)據(jù)時(shí)代的到來，科學(xué)研究正式步入了多學(xué)科相互交叉、滲透、影響的時(shí)代。人類對(duì)宇宙奧秘的探尋從未停止前進(jìn)的步伐，在探索的過程中，越來越多的問題開始呈現(xiàn)在我們的眼前。面對(duì)系統(tǒng)的復(fù)雜性，傳統(tǒng)方法已然陷入困境，尋找一個(gè)適合大規(guī)模并行操作，且具有智能特征的優(yōu)化算法已成為許多有關(guān)學(xué)科的主要研究目標(biāo)。</p

30、><p>　　最優(yōu)化（Optimization）問題，是應(yīng)用數(shù)學(xué)的一個(gè)重要分支，是一門研究問題相當(dāng)廣泛的學(xué)科，它主要目標(biāo)是尋找目標(biāo)函數(shù)的最優(yōu)解，然后來選擇決策問題的最佳方案，并討論這種算法的理論基礎(chǔ)和在實(shí)際問題中的表現(xiàn)。在計(jì)算機(jī)時(shí)代隨著技術(shù)的進(jìn)步，越來越多的大規(guī)模優(yōu)化問題得到了解決方案。所以最優(yōu)化問題才能廣泛的應(yīng)用于經(jīng)濟(jì)計(jì)劃、工程設(shè)計(jì)、生產(chǎn)管理、交通運(yùn)輸、國防等重要領(lǐng)域，并受到政府部門、科研機(jī)構(gòu)和產(chǎn)業(yè)部門的高度重視。

31、</p><p>　　國內(nèi)外的應(yīng)用研究表明，通過經(jīng)過優(yōu)化技術(shù)的處理，能大大提高系統(tǒng)效率，降低能耗，經(jīng)濟(jì)效益和資源利用的方式均有顯著的提升，隨著問題規(guī)模的擴(kuò)大，這種效果越加顯著。</p><p>　　在面對(duì)一些大型問題時(shí)，常規(guī)的尋優(yōu)算法無論是在計(jì)算速度，精度，收斂方式等方面都不能滿足要求。因此，針對(duì)常規(guī)算法的缺點(diǎn)，應(yīng)運(yùn)而生出了一些群體智能優(yōu)化算法，研究群體智能優(yōu)化算法來解決這些問題，對(duì)于時(shí)代

32、具有很重要的意義。</p><p>　　一些常見的群體智能算法，如遺傳算法，粒子群算法，混沌算法和人工魚群算法等。</p><p><b>　　2.國內(nèi)外進(jìn)展</b></p><p>　　人工魚群算法自2002年李曉磊等人提出以來，已經(jīng)獲得了國內(nèi)外學(xué)者的廣泛關(guān)注，算法已經(jīng)應(yīng)用實(shí)施到了許多領(lǐng)域，從一維靜態(tài)問題發(fā)展到解決多維組合動(dòng)態(tài)問題，從連續(xù)問題

33、發(fā)展到解決離散問題。</p><p>　　一些學(xué)者對(duì)本算法的參數(shù)，結(jié)構(gòu)以及各種行為進(jìn)行調(diào)整，從而提出了改進(jìn)的魚群算法，在文獻(xiàn)[1]中，主要針對(duì)人工魚群算法尋優(yōu)精度不高，后期收斂慢等特點(diǎn)，通過采用一種自適應(yīng)步長(zhǎng)的調(diào)整方式對(duì)算法進(jìn)行了改進(jìn)。文獻(xiàn)[2]中從魚群生活的行文特性出發(fā)，從圖論的角度觀察算法的搜索過程，控制搜索過程中每條魚的行進(jìn)方向，對(duì)基本人工魚群算法進(jìn)行改進(jìn)。而其他一些文獻(xiàn)表明，從去除步長(zhǎng)限制，加入“跳躍”行

34、為來改變?nèi)斯~的參數(shù)，或者通過基于多群體競(jìng)爭(zhēng)的改進(jìn)方式對(duì)本算法做出了改進(jìn)。</p><p>　　而為了提高算法的性能，一些學(xué)者把其他的智能算法，如模擬退火算法，粒子算法等智能算法與人工魚群算法相結(jié)合，大大加快了算法的收斂速度，加強(qiáng)了算法的局部搜索性能。</p><p>　　經(jīng)過幾年的發(fā)展，雖然人工魚群算法沒有像蟻群算法，遺傳算法等算法受到廣泛關(guān)注和應(yīng)用，但是在國內(nèi)的電力系統(tǒng)，神經(jīng)網(wǎng)絡(luò)，油田

35、定位，信號(hào)處理，模糊控制器設(shè)計(jì)等方面得到了初步的應(yīng)用。</p><p>　　3.論文各部分的主要內(nèi)容</p><p>　　本文的第一章主要是對(duì)群體智能模式和低級(jí)物種的群體行為來展開敘述，由魚群的一些基本行為來引申出算法的一些基本步驟，圖示給出算法實(shí)現(xiàn)的基本原理。第二章主要給出了基本行為（如覓食行為，聚群行為等）的具體實(shí)現(xiàn)方法和算法描述以及流程圖，再通過驗(yàn)證函數(shù)編程對(duì)算法進(jìn)行驗(yàn)證，再而討論算

36、法的參數(shù)對(duì)算法結(jié)果的影響。第三章根據(jù)目前對(duì)算法的改進(jìn)建議做出改進(jìn)，評(píng)價(jià)改進(jìn)前后算法的優(yōu)劣程度。第四章對(duì)主要介紹了了本算法在組合優(yōu)化問題上的運(yùn)用，以一個(gè)實(shí)際的案例，旅行商（TSP）問題舉例，利用人工魚群算法來求解該問題。</p><p>　　第一章 魚群算法原理</p><p><b>　　1.1群體智能</b></p><p>　　人類在早起就

37、開始對(duì)自然界中存在的群體行為產(chǎn)生了濃厚的研究興趣，比如為什么鳥群在集體遷徙過程中，幾萬只鳥一起飛行而不會(huì)產(chǎn)生碰撞。大雁排成人字形飛行更符合空氣動(dòng)力學(xué)，蝙蝠在黑暗的洞穴中快速飛行卻不會(huì)碰撞到巖壁。對(duì)于這現(xiàn)象，有一種解釋是說群居生物有自己的一套行為準(zhǔn)則，個(gè)體在準(zhǔn)守這種行為準(zhǔn)則的前提下活動(dòng)，就可以表現(xiàn)出上述行為。</p><p>　　群體智能（Swarm/Collection Intelligence）這個(gè)概念是通過對(duì)

38、自然界中的群居生物是觀察而得來的。在自然界中，如螞蟻一般的群居生物在對(duì)覓食方法和交流方式上與獨(dú)居生物的表現(xiàn)形式不同，其中不具備人類所認(rèn)為的高級(jí)智能是最明顯的特征。群居生物通過合作交互來表現(xiàn)出的宏觀智能即為群體智能。</p><p>　　1.1.1群體智能遵守五條行為準(zhǔn)則：</p><p>　　(1) 鄰近原則( Proximity Principle) ,群體能夠進(jìn)行簡(jiǎn)單的空間和時(shí)間計(jì)算;

39、</p><p>　　(2) 品質(zhì)原則(Quality Principle) ,群體能夠響應(yīng)環(huán)境中的品質(zhì)因子;</p><p>　　(3) 多樣性反應(yīng)原則( Principle of Diverse Response) ,群體的行動(dòng)范圍不應(yīng)該太窄;</p><p>　　(4) 穩(wěn)定性原則(Stability Principle) ,群體不應(yīng)在每次環(huán)境變化時(shí)都改變自身

40、的行為;</p><p>　　(5) 適應(yīng)性原則(Adaptability Principle) ,在所需代價(jià)不太高的情況下,群體能夠在適當(dāng)?shù)臅r(shí)候改變自身的行為。</p><p>　　1.1.2 群體智能的特點(diǎn)：</p><p>　　(1) 控制是分布式的,不存在中心控制。具有很強(qiáng)的魯棒性，對(duì)工作環(huán)境的適應(yīng)性強(qiáng)，不會(huì)應(yīng)為個(gè)體的故障而影響群體的性能。</p>

41、;<p>　　(2) 個(gè)體之間通過“激發(fā)工作”方式來間接通信，這種工作模式下個(gè)體都具有改變環(huán)境的能力。與非直接通信方式相比，這種模式通信具有更高的可擴(kuò)充性和更低的通信損耗。</p><p>　　(3) 由于群體中個(gè)體能力的行為規(guī)則相對(duì)簡(jiǎn)單，所以能更方便的實(shí)現(xiàn)群體智能，因此具有簡(jiǎn)單性。</p><p>　　(4) 群體的復(fù)雜行為都是通過個(gè)體的簡(jiǎn)單交互來實(shí)現(xiàn) ,因此群體具有自組織

42、性。</p><p><b>　　1.2人工魚群模式</b></p><p>　　魚群生活在水里，通過覓食來養(yǎng)活自身，在覓食的過程中，魚個(gè)體主要通過探尋環(huán)境和尾隨其它個(gè)體來尋找食物濃度更高的地方，所以在個(gè)體大規(guī)模聚集的地方一般是本水域中食物濃度較高的地方，也是尋優(yōu)過程中函數(shù)值較優(yōu)的區(qū)域。人工魚群算法主要是通過模仿魚群覓食和追尾這一系列特征來實(shí)現(xiàn)函數(shù)尋優(yōu)。</p&

43、gt;<p>　　1.2.1人工魚群算法的概念</p><p>　　人工魚群算法（Artificial Fish Swarm Algorithm，AFSA）是2002年，李曉磊博士等人受魚群行為的啟發(fā)，基于群體智能而提出的優(yōu)化算法，該算法主要是通過模仿魚群生活習(xí)性，在搜索域中尋找最優(yōu)值，是群體智能思想的一個(gè)具體應(yīng)用。</p><p>　　生物的視覺功能是極其復(fù)雜的，即使是尖端

44、的影像技術(shù)也不能達(dá)到生物視覺的能力。為了簡(jiǎn)單的實(shí)現(xiàn)魚類視覺概念，通過以下方式來實(shí)現(xiàn)人工魚的視覺功能。圖1- 1 人工魚視覺</p><p>　　如圖1-1所示，設(shè)置在位置處放置一條人工魚,視野表示它能觀察到環(huán)境的最遠(yuǎn)距離，記為,每次移動(dòng)的最大距離稱為步長(zhǎng)記為.位置是當(dāng)前時(shí)刻人工魚的一個(gè)視點(diǎn)，如果視點(diǎn)位置處的食物濃度高于當(dāng)前所處位置，那么人工魚則向視點(diǎn)方向前進(jìn)一步，即到達(dá)位置;如果視點(diǎn)位置的食物濃度低于當(dāng)前位置的食

45、物濃度，那么人工魚繼續(xù)觀察視野范圍內(nèi)其他的視點(diǎn),如等位置。隨著巡視的次數(shù)增多，人工魚對(duì)環(huán)境中食物的分布情況了解更全面，這樣有助于做出下一步相應(yīng)的判斷和決策。在巡視狀態(tài)無限循環(huán)的情況下可以通過隨機(jī)行為來跳出巡視，這樣能一定程度的幫助算法擺脫局部最優(yōu)，有利于全局尋優(yōu)。</p><p>　　設(shè)上圖中人工魚所處的位置為，視點(diǎn)位置為那么巡視過程如式（1-1）、移動(dòng)過程如式（1-2）：</p><p>

46、;<b>　?。?-1）</b></p><p><b>　　（1-2）</b></p><p>　　其中，為區(qū)間[0,1]之間的隨機(jī)數(shù)，和分別為視野和步長(zhǎng)的最大值。由于在環(huán)境中同伴的個(gè)體數(shù)目有限，所以人工魚個(gè)體在環(huán)境中感應(yīng)其他同伴的距離和同伴處的食物濃度并作出相應(yīng)決策并調(diào)整自身位置的方式與以上方法類似。</p><p>

47、　　1.1.2 人工魚群算法的主要行為</p><p><b>　　覓食行為</b></p><p>　　魚群通過覓食生存，個(gè)體覓食的行為稱為覓食行為，該行為主要體現(xiàn)在人工魚向食物濃度高的地方移動(dòng)。該行為的主要實(shí)現(xiàn)方式是通過視覺等功能，尋找環(huán)境中的食物分布。基本原理和上訴視覺概念的實(shí)現(xiàn)方式相同。該過程的算法描述為向著較優(yōu)的方向前進(jìn)。食物濃度即為函數(shù)值。</p&g

48、t;<p><b>　　聚群行為</b></p><p>　　魚類在生活中，為了躲避天敵來保證生存，會(huì)自然的聚集在一起，而聚集更多魚的地方一般為食物濃度較高的地方，這是魚類生活的常見現(xiàn)象，稱為聚群行為。聚群要保證盡量避免過多的個(gè)體擁擠在一起，個(gè)體的方向保持是一致，盡量向伙伴的中心一動(dòng)。</p><p><b>　　追尾行為</b>&

49、lt;/p><p>　　當(dāng)鄰近的一條或者幾條魚發(fā)現(xiàn)食物后，附近范圍內(nèi)的魚會(huì)尾隨其后，向它游來，進(jìn)而會(huì)招致更遠(yuǎn)的魚游向該方向。算法可以理解為向附近最優(yōu)的方向移動(dòng)。</p><p><b>　　隨機(jī)行為</b></p><p>　　當(dāng)魚在水中自由的游動(dòng)時(shí)，可以認(rèn)為該魚的游動(dòng)方向是隨機(jī)的，事實(shí)上這是為了在大范圍中搜尋食物和伙伴。在尋優(yōu)算法中可以描述為隨機(jī)

50、尋找一個(gè)初值，計(jì)算其函數(shù)值。</p><p>　　以上行為是魚的典型行為，基本行為每時(shí)每刻都會(huì)發(fā)生，他們之間既能相互轉(zhuǎn)換也能相互聯(lián)系。在算法實(shí)施過程中，如何利用有效的方法來實(shí)現(xiàn)以上行為將會(huì)是未來尋優(yōu)算法建立所面臨的重要問題。</p><p><b>　　1.3人工魚</b></p><p>　　生物魚的虛擬實(shí)體稱為人工魚，主要是用來存儲(chǔ)數(shù)據(jù)和通

51、過一些列行為對(duì)環(huán)境實(shí)現(xiàn)探索。通過感知環(huán)境刺激來做出一些列的行為，從而改變自身的參數(shù)。人工魚所處的環(huán)境是問題的定義域，目標(biāo)函數(shù)的函數(shù)值表示當(dāng)前位置食物濃度。它下一時(shí)刻的行為選擇取決于自身狀態(tài)和目前的環(huán)境，還通過自身的行為，影響其他同伴的活動(dòng)。</p><p>　　人工魚能夠自主游動(dòng)是通過行為評(píng)價(jià)的方式來實(shí)現(xiàn)的。在優(yōu)化問題中，可以選用以下兩種評(píng)價(jià)方式：①選擇最優(yōu)行為執(zhí)行，即在當(dāng)前狀態(tài)下，哪一種行為的前進(jìn)方向最優(yōu)，則選

52、擇哪種行為；②選擇較優(yōu)行為前進(jìn)，即任意選擇一種行為，只要該行為能向優(yōu)的方向前進(jìn)，則選擇該行為。兩種評(píng)價(jià)方式的選擇應(yīng)該根據(jù)具體問題具體分析。</p><p><b>　　1.4問題的解決</b></p><p>　　問題的解決是通過人工魚自治體的活動(dòng)以某種形式表現(xiàn)出來的。在尋優(yōu)過程中，通過兩種方式表現(xiàn)出：一種是通過人工魚在尋優(yōu)的最終結(jié)果分布情況在確定最優(yōu)解，隨著在尋優(yōu)的

53、過程的進(jìn)行，人工魚最終會(huì)向極值點(diǎn)附近聚集，在全局極值點(diǎn)周圍的人工魚會(huì)更多；另一種表現(xiàn)方式是通過個(gè)體來表現(xiàn)出來的，在尋優(yōu)過程中，記錄最優(yōu)個(gè)體的狀態(tài)，并在尋優(yōu)結(jié)束后比較分析所以狀態(tài)中的最優(yōu)值。</p><p>　　第二章 魚群算法的實(shí)現(xiàn)</p><p>　　通過上一章對(duì)人工魚模式的介紹，我們對(duì)人工魚有了初步的理解，對(duì)人工魚個(gè)體的自治行為有所了解，本章將從深層意義上對(duì)人工魚群算法的機(jī)制原理進(jìn)行探

54、討分析，實(shí)現(xiàn)人工魚行為的算法描述，從解決問題的角度對(duì)基本人工魚群算法的數(shù)學(xué)模型進(jìn)入深入的分析，給出具體的實(shí)現(xiàn)步驟和程序流程圖并編程計(jì)算函數(shù)尋優(yōu)問題。算法基于animals模式，采用自上而下的設(shè)計(jì)方法，所有代碼通過matlab實(shí)現(xiàn)。帶入具體函數(shù)尋優(yōu)問題，用本算法解決該問題，尋找最優(yōu)值。</p><p>　　2.1變量及函數(shù)定義</p><p>　　算法中所用到的變量名以及變量含義如表2-1所

55、示，各個(gè)行為所用的函數(shù)命名以及功能如表2-2所示，實(shí)現(xiàn)的代碼在附件中。</p><p><b>　　表2- 1變量名稱</b></p><p><b>　　表2- 2函數(shù)名稱</b></p><p><b>　　2.2行為描述</b></p><p>　　1.初始化魚群(ini

56、t)</p><p>　　魚群中每條人工魚初始值為一組實(shí)數(shù)，該實(shí)數(shù)在待優(yōu)化問題的定義域隨機(jī)生成。例如，一個(gè)二元的優(yōu)化問題，生成魚群的大小為N，待優(yōu)化參數(shù)x,y的取值范圍分別為[x1,y1][x2,y2],那么產(chǎn)生2行N列的初始魚群，每條人工魚的兩個(gè)參數(shù)由列向量表示，所以人工魚初值儲(chǔ)存在一個(gè)2行N列的矩陣中，以后對(duì)個(gè)體的參數(shù)改變均通過改變?cè)摼仃嚨膮?shù)實(shí)現(xiàn)。</p><p>　　覓食行為(pr

57、ey)</p><p>　　設(shè)當(dāng)前人工魚的狀態(tài)（即位置）為,在其視野范圍內(nèi)按式（2-1）感知環(huán)境中的某一隨機(jī)位置。表示生成一個(gè)[0,1]內(nèi)的隨機(jī)數(shù)。</p><p><b>　?。?.1）</b></p><p>　　如果在求極大值為問題中（極大值問題和極小值問題之間可以相互轉(zhuǎn)化，所以下文均只討論極大值問題。），那么人工魚則向該方向前進(jìn)一步到下

58、一位置，前進(jìn)方式如式（2-2）所示：</p><p><b>　?。?.2）</b></p><p>　　如果不滿足，則再按式（2.1）重新選擇視點(diǎn)，判斷是否滿足前進(jìn)條件，這樣總共嘗試次后，如果任不滿足條件，則隨機(jī)移動(dòng)一步。該過程算法流程如圖2-1所示：</p><p><b>　　圖2- 1</b></p>

59、<p>　　聚群行為(swarm)</p><p>　　設(shè)人工魚當(dāng)前狀態(tài)為，探索當(dāng)前視野范圍內(nèi)()的伙伴數(shù)目以及伙伴中心位置，其中心位置計(jì)算方式如式（2.3）：</p><p><b>　　（2.3）</b></p><p>　　如果滿足，那么則表示當(dāng)前視野內(nèi)伙伴中心有較多的食物并且不太擁擠，則按照式（2.4）向伙伴中心方向移動(dòng)&l

60、t;/p><p><b>　?。?.4）</b></p><p>　　；否者執(zhí)行覓食行為。流程圖如2-2：</p><p><b>　　圖2- 2</b></p><p><b>　　追尾行為</b></p><p>　　設(shè)人工魚當(dāng)前狀態(tài)為，巡視視野范圍內(nèi)(

61、)的伙伴數(shù)目及伙伴中食物濃度最大的伙伴位置，如果滿足，則伙伴所處位置不擁擠且有多遠(yuǎn)的食物，那么則按照式（2.5）向伙伴方向移動(dòng)；</p><p><b>　?。?.5）</b></p><p>　　否者執(zhí)行覓食行為。流程圖如2-3如下</p><p><b>　　圖2- 3</b></p><p>

62、<b>　　隨機(jī)行為</b></p><p>　　在視野內(nèi)隨機(jī)選擇一個(gè)視點(diǎn)，向該視點(diǎn)方向移動(dòng)，這種行為是覓食行為的默認(rèn)行為。移動(dòng)方式如式（2-6）</p><p><b>　　（2.6）</b></p><p><b>　　2.3算法描述</b></p><p>　　人工魚群算

63、法開始時(shí)并行指定算法的必要參數(shù)如人工魚的條數(shù)，函數(shù)定義域，視野迭代次數(shù)等參數(shù)，然后利用init函數(shù)根據(jù)定義域初始化魚群，計(jì)算初始魚群當(dāng)前的食物濃度，每條人工魚根據(jù)自身的參數(shù)開始執(zhí)行覓食行為，魚群在一次迭代中，分別根據(jù)聚群行為和追尾行為得到的食物濃度進(jìn)行判斷，選擇較為優(yōu)秀的結(jié)果方向前進(jìn)，并把本次迭代的較優(yōu)結(jié)果記錄下來，在進(jìn)行MAXGEN次后，選擇最優(yōu)的結(jié)果視為尋優(yōu)結(jié)果。</p><p>　　流程圖如2-4所示：&l

64、t;/p><p><b>　　圖2- 4</b></p><p><b>　　2.4算法驗(yàn)證</b></p><p>　　本次驗(yàn)證我們選擇Rastrigin函數(shù)的反函數(shù)，該函數(shù)式如（2-7）</p><p><b>　?。?-7）</b></p><p>　

65、　該函數(shù)是一個(gè)多峰函數(shù)，在時(shí)取得全局最大值點(diǎn)，最大值為0。由于為了實(shí)驗(yàn)的直觀性，我們本次函數(shù)選取的維數(shù)D=2。</p><p>　　該函數(shù)的三維圖象如圖2-5所示，極值點(diǎn)位于（0,0）處，極值為0并且可以看出該函數(shù)在極值周圍有許多的局部極值點(diǎn)，通常算法易陷入局部極值或者在局部極值附近震蕩，所以該函數(shù)比較適和用于智能算法的驗(yàn)證。</p><p><b>　　圖2- 5</b&

66、gt;</p><p>　　本次實(shí)驗(yàn)我們?cè)O(shè)定魚群數(shù)量N=50,迭代次數(shù)MAXGEN=50,Try_number=50,視野visual=2，擁擠度δ=0.618，步長(zhǎng)step=1.2。</p><p>　　經(jīng)過仿真實(shí)驗(yàn)可以得到如下四幅圖，圖中的黑點(diǎn)表示當(dāng)前迭代次數(shù)內(nèi)的最優(yōu)值。可以看出，魚群迭代的最優(yōu)值開始比較離散，魚群沒有向最優(yōu)值附近靠近。隨著迭代次數(shù)的增加，魚群越來越向(0,0)點(diǎn)靠近。

67、最后幾乎都在極值點(diǎn)附近搜尋。但是從圖2-10可以看出，在迭代的過程中，魚群陷入了局部最優(yōu)，在第37次迭代才跳出局部最優(yōu)，找到了全局最優(yōu)，所以該算法目前還是有瑕疵的（容易長(zhǎng)時(shí)間停留在局部最優(yōu)，損失迭代精度）。以后的改進(jìn)可以從該方面入手。</p><p>　　圖2- 6.10次迭代結(jié)果 圖2- 7.25次迭代結(jié)果</p><p>　　圖2- 8.40

68、次迭代結(jié)果 圖2- 9.50次迭代結(jié)果</p><p>　　圖2- 10.迭代過程</p><p>　　運(yùn)行10次算法，所得結(jié)果如表2-3所示</p><p><b>　　表2- 3</b></p><p>　　表中結(jié)果可以看出，算法目前的精度還不夠高，需要進(jìn)一步的改進(jìn)。&l

69、t;/p><p>　　2.5各個(gè)參數(shù)對(duì)結(jié)果的影響</p><p>　　算法存在一定的隨機(jī)性，在相同的參數(shù)下，收斂的結(jié)果也存在差異，所以在接下來的討論中所有的驗(yàn)證函數(shù)為Rastrigin函數(shù)，設(shè)置不同的參數(shù)，對(duì)每一組參數(shù)的多次尋優(yōu)結(jié)果作為一組數(shù)據(jù)，然后再多組數(shù)據(jù)中進(jìn)行分析，從而確定參數(shù)的性質(zhì)和影響。</p><p>　　擁擠度因子δ（delta）</p>&

70、lt;p>　　擁擠度因子δ是人工魚群算法中的一個(gè)基本參數(shù)之一，算法是通過擁擠度因子來限制人工魚的聚群規(guī)模，使得在較優(yōu)的領(lǐng)域內(nèi)盡可能多的聚集人工魚，在次優(yōu)或者更為次的領(lǐng)域內(nèi)少的聚集人工魚最好能做的不聚集。</p><p>　　在聚群行為和追尾行為中，分別用到了和兩個(gè)公式，分別用來判斷魚群伙伴中心位置和人工魚視野中心的位置是否能前進(jìn)。如果不擁擠則前進(jìn)，擁擠則不前進(jìn)，執(zhí)行覓食行為。</p><

71、p>　　通過文獻(xiàn)[3]中的介紹可以得知δ的由來是根據(jù)一下公式（2-8）得到</p><p><b>　?。?-8）</b></p><p>　　其中α為極值接近水平，為該期望鄰域內(nèi)聚集的最大人工魚數(shù)目。例如，希望在接近極值70％水平的領(lǐng)域內(nèi)不會(huì)聚集超過3只人工魚，那么=1/(0.7x3)=0.47。</p><p>　　那么當(dāng)，則認(rèn)為當(dāng)前

72、鄰域內(nèi)人工與聚集過多，不適合向位置移動(dòng)。</p><p>　　為了驗(yàn)證擁擠度因子對(duì)算法的影響，我們通過兩個(gè)求極大值的函數(shù)來驗(yàn)證進(jìn)行仿真實(shí)驗(yàn)，其中人工魚的總數(shù)設(shè)為10，迭代次數(shù)為50，Try_number=10,視野和步長(zhǎng)根據(jù)函數(shù)的定義域來選取。</p><p>　　F1函數(shù)如式（2-9）</p><p><b>　?。?-9）</b></

73、p><p>　　該函數(shù)在（0,0）處有極大值為1，設(shè)其閥值為0.99</p><p>　　F2函數(shù)如式（2-10）</p><p><b>　?。?-10）</b></p><p>　　該函數(shù)在（0,0）處有全局極值點(diǎn)為3600，四個(gè)局部極值點(diǎn)分別為（-5.12，5.12）（-5.12，-5.12）（5.12，-5.12）（

74、5.12，5.12）局部極值為2758.7823</p><p>　　設(shè)其閥值為3500.</p><p>　　其中平均迭代次數(shù)為收斂到閥值內(nèi)所需迭代次數(shù)的平均值。仿真結(jié)果如表2-4所示。</p><p><b>　　表2- 4</b></p><p>　　由仿真結(jié)果可以看出擁擠度因子的變化對(duì)收斂性能的影響沒有明顯的規(guī)律

75、，對(duì)收斂結(jié)果的影響也不大，基本上可以忽略不計(jì)。在此后的改進(jìn)過程中，基本可以忽略擁擠度因子對(duì)算法的影響，也可把算法設(shè)計(jì)成不需要擁擠度因子的簡(jiǎn)單魚群算法。</p><p>　　Step對(duì)算法的影響</p><p>　　在覓食行為中，人工魚個(gè)體在鄰域內(nèi)搜尋更優(yōu)的前進(jìn)方案，這就奠定了算法的收斂基礎(chǔ)。</p><p>　　分別設(shè)步長(zhǎng)Step=10和0.5，人工魚數(shù)目為50，迭

76、代次數(shù)為100，進(jìn)行算法仿真，圖2-11中，橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為本次迭代最優(yōu)結(jié)果，有圖可以看出，大步長(zhǎng)的震蕩大，迭代精度也不如小步長(zhǎng)。而對(duì)于不同步長(zhǎng)值所用時(shí)間，我們計(jì)算仿真十次取平均時(shí)間可以得到大步長(zhǎng)所用時(shí)間為5.3s，小步長(zhǎng)所用時(shí)間為7.9s。</p><p><b>　　圖2- 11</b></p><p>　　由以上仿真結(jié)果可以看出，選擇較大的步長(zhǎng)，有利于

77、人工魚快速的向極值點(diǎn)收斂，而且收斂速度比小步長(zhǎng)快，但是在算法迭代過程中會(huì)造成人工魚在全局極值點(diǎn)附近來回震蕩。</p><p>　　小步長(zhǎng)雖然不能快速的收斂到想要的結(jié)果，但是對(duì)于算法的后期，靠近極值點(diǎn)的精度會(huì)有所提高，震蕩幅度也沒有大步長(zhǎng)大。</p><p>　　對(duì)于算法的改進(jìn)，可以考慮在計(jì)算前期采用較大的步長(zhǎng)，以使算法能快速的收斂，而在算法的后期，可以減小步長(zhǎng)，然算法能得到更高的精度。&l

78、t;/p><p>　　2.6人工魚群算法的收斂基礎(chǔ)</p><p>　　對(duì)于一種優(yōu)化算法，其收斂性往往是大家所關(guān)心的問題。在人工魚群算法中，人工魚的覓食行為奠定了算法的收斂基礎(chǔ)，聚群行為能增強(qiáng)算法收斂的全局性和穩(wěn)定性，追尾行為則能加快算法的收斂速度和保持算法的全局性。總體看來，算法對(duì)于各個(gè)參數(shù)的取值范圍要求還是很寬松的，并且對(duì)于算法的初始值并無基本要求。</p><p>

79、;　　在人工魚群算法中，查找文獻(xiàn)[3]可知，以下幾點(diǎn)因素可以使得人工魚逃離局部極值實(shí)現(xiàn)全局最優(yōu)。</p><p>　?、僭谝捠承袨橹?，如果有較少的Try_number次數(shù)，那么人工魚在視野范圍內(nèi)能覓食的更加食物濃度的幾率大大減少，那么人工魚執(zhí)行隨機(jī)行為，從而能實(shí)現(xiàn)跳出局部極值范圍。</p><p>　?、诰廴盒袨槟軐?shí)現(xiàn)讓少數(shù)陷入局部極值領(lǐng)域內(nèi)的人工魚向全局極值的人工魚方向聚集。從而跳出局部

80、極值領(lǐng)域。</p><p>　?、圩肺残袨閯t加快了人工魚向更優(yōu)方向移動(dòng)，使得陷入局部極值的人工魚跳出局部極值范圍。</p><p>　?、苊看我苿?dòng)的步長(zhǎng)是在[-step,step]范圍內(nèi)的一個(gè)隨機(jī)步長(zhǎng),那么當(dāng)人工魚向局部極值方向游動(dòng)時(shí)，也有可能轉(zhuǎn)向游向更優(yōu)方向。當(dāng)然也有可能游向更壞的方向，但是通過聚群行為等趨于更優(yōu)的行為的加入，魚群大體能保持向更優(yōu)方向移動(dòng)。</p><

81、p>　?、輷頂D度因子的加入，使得魚群不會(huì)無限制的聚集在一個(gè)領(lǐng)域中，食物濃度越大的地方越能聚集更多的魚群，控制了魚群的聚集規(guī)模，使得魚群能更為廣泛的分布在整個(gè)領(lǐng)域。但是這種性質(zhì)也限制了人工魚在全局最優(yōu)點(diǎn)附近不能聚集更多的人工魚。</p><p>　　該方法的設(shè)計(jì)思想采用自上而下的設(shè)計(jì)方式，各個(gè)人工魚之間即相互獨(dú)立也相互聯(lián)系，使得算法具有更為穩(wěn)定的收斂基礎(chǔ)。</p><p><b&

82、gt;　　第三章 算法的改進(jìn)</b></p><p>　　雖然魚群算法有著穩(wěn)定，收斂速度快，對(duì)初值不敏感等一些列優(yōu)點(diǎn)，但是算法后期也有尋優(yōu)結(jié)果精度低并且運(yùn)行的速度慢，容易陷入局部極值等缺點(diǎn)。通過對(duì)算法的實(shí)驗(yàn)數(shù)據(jù)分析，和查找文獻(xiàn)了解，可以對(duì)算法做出一些簡(jiǎn)單的改進(jìn)。從而獲得更優(yōu)的性能。</p><p>　　3.1自適應(yīng)步長(zhǎng)魚群算法</p><p>　　魚群算

83、法具有克服局部極值，取得全局極值的能力，但是該算法在后期，搜索的盲目性較大，尋優(yōu)的結(jié)果精度很低并且運(yùn)行的速度慢。</p><p>　　通過對(duì)大量文獻(xiàn)資料的閱覽，在文獻(xiàn)[5]中得到啟示，在人工魚覓食行為中直接移動(dòng)到較優(yōu)位置，能加快算法的搜索速度，同時(shí)采用動(dòng)態(tài)調(diào)整人工魚的視野和步長(zhǎng)的方法，能顯著增強(qiáng)算法探索與開發(fā)的能力，提高算法的優(yōu)化精度。</p><p>　　研究表明，當(dāng)視野范圍較大時(shí)，人工

84、魚的全局搜索能力強(qiáng)且收斂速度快，視野范圍小，人工魚的局部搜索能力強(qiáng)。步長(zhǎng)越大，收斂速度越快，但有時(shí)會(huì)產(chǎn)生振蕩現(xiàn)象；步長(zhǎng)小，收斂速度慢，但求解精度高。</p><p>　　由此可見，對(duì)于難以優(yōu)化的函數(shù)，需要加強(qiáng)全局搜索能力，一旦定位到最優(yōu)解的大概位置，就需要加強(qiáng)局部搜索能力。所以，在算法前期，在取值范圍內(nèi)，盡可能的采用較大的視野和步長(zhǎng)，使人工魚能在更大的范圍內(nèi)進(jìn)行粗搜索，能增強(qiáng)算法的全局搜索能力和收斂速度。隨著搜索

85、的進(jìn)行，則需要更高的精度，所以在后期需要減小視野和步長(zhǎng)，使算法變?yōu)榫植克阉?，在最?yōu)解附近進(jìn)行更為精細(xì)的搜索。</p><p>　　基于此原理，剛開始計(jì)算時(shí)，視野和步長(zhǎng)盡可能的大。尋找值域在（0,1）內(nèi)并隨著迭代次數(shù)單調(diào)遞減的函數(shù)，逐步縮小視野和步長(zhǎng)，但是考慮到視野和步長(zhǎng)不能縮小到0，則為函數(shù)添加一個(gè)盡可能不影響函數(shù)值的下限和。</p><p>　　視野和步長(zhǎng)按照式（3-1）動(dòng)態(tài)調(diào)整<

86、/p><p><b>　?。?-1）</b></p><p>　　其中，gen為當(dāng)前迭代次數(shù)，MAXGEN為最大迭代次數(shù)，S為[1,30]之間的整數(shù)</p><p>　　圖3-1為函數(shù)中s取值分別為1，5,10,15的曲線圖，其中MAXGEN為100</p><p><b>　　圖3- 1</b><

87、;/p><p>　　對(duì)覓食行為的改進(jìn)：在原來覓食行為中，人工魚隨機(jī)選擇一個(gè)狀態(tài)，如果該位置優(yōu)于當(dāng)前位置，則向該位置方向移動(dòng)一步。這種方法的搜索方式速度較慢，且向該位置方向移動(dòng)的過程中不一定能移動(dòng)到更優(yōu)的值，為了加快搜索速度，可以讓該人工魚直接移動(dòng)到該位置，從而能提高尋優(yōu)速度。</p><p>　　3.1.2仿真實(shí)驗(yàn)以及分析</p><p>　　以三個(gè)最小值函數(shù)為例進(jìn)行仿

88、真實(shí)驗(yàn)。</p><p>　?。?）Rastrigin函數(shù)，如式（3-2）</p><p><b>　　（3-2）</b></p><p>　　此函數(shù)是多峰函數(shù)，在時(shí)達(dá)到全局最小值0。</p><p>　　Griewank函數(shù)，如式（3-3）</p><p><b>　?。?-3）<

89、;/b></p><p>　　此函數(shù)是多峰函數(shù)，極其難找到全局最優(yōu)點(diǎn)，查閱資料得知該函數(shù)在時(shí)，達(dá)到全局最優(yōu)點(diǎn)，最優(yōu)值為0。</p><p>　　Rosenbrock函數(shù)，如式（3-4）</p><p><b>　?。?-4）</b></p><p>　　此函數(shù)是一個(gè)非凸，病態(tài)單峰函數(shù)，在時(shí)，達(dá)到全局最優(yōu)點(diǎn)，最優(yōu)值為

90、0。</p><p>　　本次仿真實(shí)驗(yàn)參數(shù)設(shè)置如表3-1：</p><p><b>　　表3- 1</b></p><p>　　對(duì)三個(gè)函數(shù)進(jìn)行仿真模擬，運(yùn)行條件為cpu:i5 3230m 內(nèi)存：8gb </p><p>　　每個(gè)函數(shù)的程序獨(dú)立運(yùn)行50次，把50次結(jié)果相加后，取平均值為最終結(jié)果并且記錄下50次模擬中的最小值

91、（取小數(shù)點(diǎn)后六位），填入表3-2：</p><p>　　算法性能采用如下評(píng)價(jià)方法：①固定迭代次數(shù)，評(píng)估算法的收斂精度和速度②固定收斂精度目標(biāo)值，比較算法達(dá)到改精度的迭代次數(shù)</p><p><b>　　表3- 2</b></p><p>　　如上表所示，3個(gè)測(cè)試函數(shù)改進(jìn)前后結(jié)果可以看出，改進(jìn)后的魚群算法能明顯提高計(jì)算結(jié)果的精度，并且從模擬50次

92、的時(shí)間來看，改進(jìn)后的算法用時(shí)更少，更快的達(dá)到目標(biāo)。</p><p>　　以算法運(yùn)行模擬次數(shù)為橫坐標(biāo)，單次輸出結(jié)果為縱坐標(biāo)，統(tǒng)計(jì)Rastrigin函數(shù)運(yùn)行結(jié)果得到如下圖3-2和3-3</p><p>　　圖3-2.改進(jìn)前運(yùn)行結(jié)果 圖3-3.改進(jìn)后運(yùn)行結(jié)果</p><p>　　如圖所示，明顯能看出，改進(jìn)后的程序，每次運(yùn)行的結(jié)果比改進(jìn)前的結(jié)果更加穩(wěn)定

93、，單次運(yùn)行結(jié)果精度更高。</p><p>　　3.2初始均勻分布全局人工魚群算法</p><p>　　3.2.1初始均勻分布</p><p>　　在魚群算法主程序開始計(jì)算時(shí)，需要對(duì)人工魚群初始化，魚群初始化的過程就是對(duì)魚群中每一條人工魚賦初始值。然而在基本魚群算法中，初始值的賦值由式（3-5）產(chǎn)生：</p><p><b>　?。?

94、-5）</b></p><p>　　應(yīng)而可能存在人工魚初始時(shí)聚集在一個(gè)小范圍的情況，從而使人工魚在初始化后就陷入局部最優(yōu)值，雖然該種情況可以通過覓食行為等基本行為跳出局部最優(yōu)值，但是如果我們能讓魚群在初始時(shí)就均勻的分布在全局范圍內(nèi)，就能有效的避免此情況的發(fā)生，使得魚群在算法初期就能對(duì)極值分布情況有所了解。</p><p>　　本思想的基本原理很簡(jiǎn)單，在魚群算法的主函數(shù)中增加一個(gè)

95、魚群數(shù),該值把一個(gè)魚群分為群，每個(gè)小種群中的人工魚個(gè)數(shù)為。然后再把定義域分為q段，然后每一個(gè)小種群在一段小定義域內(nèi)隨機(jī)初始化。這樣就能實(shí)現(xiàn)魚群初始化的均勻分布。</p><p>　　通過仿真實(shí)驗(yàn)得知，魚群初始化的過程中，人工魚初始就隨機(jī)聚集在一個(gè)小范圍的這種情況極其罕見，該想法若獨(dú)立實(shí)現(xiàn)，基本對(duì)算法的影響不大。所以根據(jù)初始的全局性我們通過文獻(xiàn)[4]了解到全局人工魚群算法。我們把初始化均勻分布的思想和全局人工魚算法

96、相結(jié)合。</p><p>　　3.2.2 全局人工魚群算法</p><p>　　在人工魚群算法中，人工魚個(gè)體的行為都是局部行為，只在視野范圍內(nèi)覓食，所以很難避免個(gè)體趨同，容易陷入局部最優(yōu)。為了提高人工魚的全局搜索能力，克服算法后期精度低，收斂慢等一些列缺點(diǎn)，我們把全局最優(yōu)人工魚的位置加入到聚群行為等基本行為中。</p><p>　　在第二章中介紹了人工魚群算法的主要

97、行為，可以看出，人工魚的位置更新都是在局部范圍內(nèi)實(shí)現(xiàn)的，為了使得人工魚個(gè)體位置更新能具有全局性，我們加入一個(gè)新的量，此變量代表所有人工魚個(gè)體中，當(dāng)前食物濃度最高的人工魚。通過執(zhí)行每個(gè)行為與相聯(lián)系，可以做到更好的全局通信。</p><p><b>　　改進(jìn)覓食行為</b></p><p>　　在原來的覓食行為中我們可以得知，人工魚當(dāng)前位置為在其視野范圍內(nèi)隨機(jī)感知一個(gè)位置

98、，如果該位置的食物濃度大于當(dāng)前位置，那么魚群向該位置方向移動(dòng)一步。我們把該模式改為如果該位置的食物濃度大于當(dāng)前位置，那么人工魚向該位置和全局最優(yōu)位置的向量和方向前進(jìn)一步。前進(jìn)方法如式（3-6）：</p><p><b>　　（3-6）</b></p><p>　　同覓食行為一樣滿足則前進(jìn)一步，否則繼續(xù)覓食，直到嘗試次后，執(zhí)行隨機(jī)行為。</p><p

99、><b>　　改進(jìn)聚群行為</b></p><p>　　人工魚初始位置為,在其視野范圍內(nèi)伙伴的數(shù)目和及其中心位置。如果滿足，則表示伙伴中心有較多的食物且不擁擠，那么則向伙伴中心和全局最優(yōu)位置移動(dòng)一步，前進(jìn)的公式改為式（3-7）：</p><p><b>　?。?-7）</b></p><p>　　否者則執(zhí)行覓食行為。

100、</p><p><b>　　改進(jìn)追尾行為</b></p><p>　　人工魚初始位置為,在其視野范圍內(nèi)伙伴的數(shù)目和及食物濃度最大位置。如果滿足，則表示伙伴中心有較多的食物且不太擁擠，那么則向伙伴中心和全局最優(yōu)位置移動(dòng)一步，前進(jìn)的公式為式（3-8）：</p><p><b>　?。?-8）</b></p>&

101、lt;p><b>　　否者執(zhí)行覓食行為。</b></p><p>　　加入自適應(yīng)步長(zhǎng)視野：在3.1中我們提出了自適應(yīng)視野的人工魚群算法，該改進(jìn)方法能加快算法后期的收斂速度提高后期的精度。所以我們?cè)诟倪M(jìn)過程中，默認(rèn)加入自適應(yīng)步長(zhǎng)魚群算法，在此算法的基礎(chǔ)上進(jìn)行改進(jìn)。</p><p>　　3.2.3仿真實(shí)驗(yàn)以及分析</p><p>　　我們引入

102、三個(gè)測(cè)試函數(shù)，對(duì)算法進(jìn)行仿真，選擇高，中，低維三個(gè)典型的多極值函數(shù)進(jìn)行測(cè)試在試驗(yàn)中，人工魚的初始位置均勻分布，由于函數(shù)的維數(shù)不同，我們?cè)O(shè)置了不同的迭代次數(shù)，分別為50，100和250，步長(zhǎng)由所用函數(shù)的定義域給出，初始步長(zhǎng)盡可能的大。所有函數(shù)的人工魚數(shù)目N=20，Try_number=2.5,δ=8。</p><p>　　F1.如式（3-9）:</p><p><b>　?。?-9

103、）</b></p><p>　　其函數(shù)的最優(yōu)值在x=y=0處取得為0。</p><p>　　F2.公式如式（3-10）：</p><p><b>　?。?-10）</b></p><p>　　其最優(yōu)值在處取得為0.</p><p>　　F3.如式（3-11）：</p>&

104、lt;p><b>　?。?-11）</b></p><p>　　其最優(yōu)值在處取得為0.</p><p>　　每個(gè)函數(shù)算法獨(dú)立運(yùn)行10次，當(dāng)每次運(yùn)行結(jié)果與理論最優(yōu)值的差值在0.001以內(nèi)就認(rèn)為實(shí)驗(yàn)成功。其中平均迭代次數(shù)是每次迭代過程中第一次達(dá)到所需精度的平均值。平均最優(yōu)解是最優(yōu)解的平均值，最優(yōu)解為10次允許中的最優(yōu)值。</p><p>&l

105、t;b>　　表3- 3</b></p><p>　　由仿真結(jié)果可以看出，初始均勻分布的魚群算法的性能明顯比魚群算法的性能更加優(yōu)異。算法迭代到所需精度的迭代次數(shù)明顯減少，精度更高。全局人工魚群算法的由于步長(zhǎng)視野隨著迭代次數(shù)的減小，加快了前期和后期的迭代，提高了算法的運(yùn)行速度，算法的執(zhí)行時(shí)間可以得到明顯的降低，且在全局最優(yōu)解的附近，能有更多的人工魚個(gè)體。</p><p>　　

106、第四章 魚群算法應(yīng)用</p><p>　　人工魚群算法自2002年面世以來，已經(jīng)經(jīng)歷了15個(gè)年頭，該算法在這15年內(nèi)，已經(jīng)有了很多種改進(jìn)，而且也實(shí)際運(yùn)用在了各個(gè)方面，例如科學(xué)工程領(lǐng)域的應(yīng)用在車間調(diào)度問題，信號(hào)處理去噪，圖像處理，數(shù)據(jù)挖掘等各個(gè)方面。而在數(shù)學(xué)方面的應(yīng)用主要是由優(yōu)化組合問題，積分計(jì)算，函數(shù)尋優(yōu)等。但大多數(shù)還是用在連續(xù)性問題尋優(yōu)上，對(duì)于離散問題求解和少。</p><p><

107、b>　　4.1組合優(yōu)化問題</b></p><p>　　最優(yōu)化問題主要可以分為兩大類，函數(shù)優(yōu)化問題和組合優(yōu)化問題，我們前三章做的仿真模擬主要是函數(shù)優(yōu)化問題，在一個(gè)給定的區(qū)域內(nèi)尋求函數(shù)的最優(yōu)值（最大值或者最小值）。而組合優(yōu)化問題是通過對(duì)數(shù)學(xué)方法的研究去解決離散問題，尋找最優(yōu)編排，分組，篩選等，是運(yùn)籌學(xué)的的一個(gè)重要分組。 </p><p>　　優(yōu)化組合問題的數(shù)學(xué)模型可以描述為

108、式（4-1）：</p><p><b>　?。?-1）</b></p><p>　　其中。是目標(biāo)函數(shù)；為約束函數(shù)，是決策變量，D是有限個(gè)點(diǎn)組成的集合。</p><p>　　在組合優(yōu)化問題中用D表示決策變量的定義域，表示可行解域，在中的任意一個(gè)元素是該問題的一個(gè)可行解，用表示目標(biāo)函數(shù),那么該問題可用表示。只要可行解滿足，那么則稱為問題的最優(yōu)解。原

109、始思想是只要把D中的元素逐一判別是是否滿足的約束條件然后比較目標(biāo)值的大小，那么該問題的最優(yōu)解一定能找到?，F(xiàn)實(shí)中的優(yōu)化問題即是從有限個(gè)狀態(tài)中選取的最好的，所以大量的優(yōu)化的問題就是組合優(yōu)化問題。</p><p><b>　　4.2 旅行商問題</b></p><p>　　旅行商問題（Travelling Salesman Problem）簡(jiǎn)稱為TSP問題。問題描述為一個(gè)商

110、人計(jì)劃到n個(gè)城市推銷商品，每?jī)蓚€(gè)城市i和j間的距離為，如何選擇一條道路，使得商人從起點(diǎn)城市出發(fā)，每個(gè)城市走一遍后再回到起點(diǎn)城市所走的路徑最短。</p><p>　　TSP問題可以分為兩大類：對(duì)稱問題和非對(duì)稱問題。當(dāng)從i出發(fā)到j(luò)的距離和從j到i出發(fā)的距離相等時(shí)，這類問題稱為對(duì)稱距離TSP，否者為非對(duì)稱距離TSP。</p><p>　　該問題是一個(gè)NP難問題，其計(jì)算復(fù)雜性隨著輸入數(shù)據(jù)的規(guī)模呈現(xiàn)

111、出指數(shù)式的增長(zhǎng)。</p><p>　　該問題的簡(jiǎn)單描述為：</p><p>　　設(shè)有n個(gè)城市，每個(gè)城市用1到n進(jìn)行編號(hào)，每個(gè)城市之間的距離都是固定的，記為其中。TSP問題是要找到能夠遍歷每個(gè)城市一次的一條回來，且這條回路的總路徑為最短。如下圖4-1所示，右邊的路程要明顯小于左邊的路程：</p><p><b>　　圖4- 1</b></p

112、><p>　　該問題的數(shù)學(xué)描述為式（4-2）：</p><p><b>　?。?-2）</b></p><p>　　4.3TSP問題求解</p><p>　　TSP的求解有很多種中方法，本文主要介紹人工魚群算法解決TSP問題。</p><p>　　4.3.1TSP求解一般思路</p>&

113、lt;p>　　該問題的求解可以通過排列組合的方式求解，即把每一種可行的路線方案列舉出來，然后再逐一比較，選擇其中最優(yōu)的方案。該方法在遍歷城市比較少的時(shí)候是可行的，但是隨著城市個(gè)數(shù)的增加，該方法的可行方案呈現(xiàn)出階乘式增長(zhǎng)。例如20個(gè)城市，那么選擇其中一個(gè)城市作為起點(diǎn)就有種方案，如果每個(gè)方案都計(jì)算一次，即使用計(jì)算機(jī)模擬，工作量非常大的。</p><p>　　4.3.2人工魚群算法求解TSP</p>

114、<p>　　求解tsp問題的算法面描述：</p><p>　　編碼方式：以遍歷城市的次序進(jìn)行編碼。如14678235則表示為依次走過1，4,6,7...,5，最后返回1號(hào)城市，所有的編碼均從1號(hào)城市開始。每條人工魚所記錄的即為編碼次序如。</p><p>　　目標(biāo)函數(shù)：遍歷所有城市的路徑的總長(zhǎng)度為目標(biāo)函數(shù)，最優(yōu)路徑即為總長(zhǎng)度最小時(shí)對(duì)應(yīng)的路徑。</p><p&

115、gt;　　新路徑的產(chǎn)生：將k和m兩個(gè)城市的行走順序交換，即產(chǎn)生了新的路徑。</p><p>　　距離表示：兩條人工魚和之間的距離可以表示為式（4-3）：</p><p><b>　?。?-3）</b></p><p>　　解空間：每一條人工魚中的參數(shù)為一種可行解，所有的解構(gòu)成解空間。</p><p>　　該算法流程圖如圖