人工鱼群算法解决TSP问题
一、問題詳述
旅行商問題，是數學領域中著名問題之一，被證明具有NPC計算復雜性。該問題假設有一個旅行商人要拜訪N個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。
二、人工魚群算法原理描述
2.1人工魚群算法原理
人工魚群算法(artificial fish-swarm algorithm,AFSA)是一種基于魚群的群智能優化算法，群智能指的使“無智能的主體通過合作表現出智能行為的特征”，是一種基于生物群體行為規律的計算技術，用來解決分布式問題。人工魚群算法的基本思想是仿照魚群在一片水域當中尋找最優解的覓食、聚群和追尾等行為，水域中的每一條魚都對應其中的一個優化解，該水域即為被優化問題的解空間。通過分析人工魚群的優化理念，可得其人工魚群環境模型。假設水域中一條魚現時狀態是X，其可見范圍為Visual(公式中用Zvisual表示)，在某一時間點對應的視點位置為X k，如果該方位較此時狀態更優，則可往該地點處向前一步，即抵達X next；若該方位無此時狀態更優，則一直在可見視線內找尋其他較優地點。
2.2人工魚群算法步驟
1）初始化設置。對魚群中的各個參數進行初始設置，包括：該人工魚群的群體規模、視野、最大迭代次數、每一條魚的最大移動步長Step(公式中用Lstep)等參數。
2）此時迭代的次數是0，由N條魚組成初始魚群，每個魚表示從初始位置到目標位置的一條路徑。
3）對每一條人工魚都進行行為模擬：覓食、追尾、聚群與隨機移動行為，選取其中最優的一種行為來操作。
4）聚群行為：魚在游動過程中為了保證自身的生存和躲避危害會自然地聚集成群。人工魚X i X_iXi搜索其視野內的伙伴數目及中心位置，若Y c / n f < δ Y i Y_c/n_f< δY_iYc/nf<δYi，表明伙伴中心位置狀態較優且不太擁擠，則X i X_iXi朝伙伴的中心位置移動一步，否則執行覓食行為；
5）追尾行為：指魚向其視野區域內的最優方向移動的一種行為。人工魚X i X_iXi搜索其視野內（d i j < v i s u a l d_{ij}<visualdij<visual）適應度最高的個體X j X_jXj，其適應度值為Y j Y_jYj，并探索人工魚X j X_jXj視野內的伙伴數目n f n_fnf，若Y j / n f < δ Y i Y_j/n_f< δY_iYj/nf<δYi，表明X j X_jXj狀態較優且不太擁擠，則X i X_iXi朝X j X_jXj位置移動一步，否則執行覓食行為；
6）綜上，算法在運算過程中，會同時進行聚群和追尾行為。而覓食行為屬于這兩種行為中發現聚群對象或者追尾對象附近擁擠度過大時，人工魚選擇的行為方式，若在覓食過程中，未發現比自身適應度高的人工魚，則按步長step隨機移動。最后對聚群行為和追尾行為得到的適應度值進行比較，選擇優秀的人工魚作為下一代的個體。
圖1 人工魚群算法流程圖
三、重要參數分析
1)魚群規模：人工魚群算法的實現是建立在大量的人工魚基礎之上，人工魚的總數增多，促使收斂的速度和精度有明顯提高，并減少陷入局部最優解的可能性。但是，人工魚的數量過多會導致計算量劇增，算法運行時耗時過大。因此，在具體優化應用中，應適當地設置人工魚的數目。
2)視野visual：人工魚群的聚群、追尾、覓食、隨機行為都是在視野內執行的，所以參數視野的設置對算法的效果有著很大影響。根據經驗判斷，當視野范圍較小時往往更加突出覓食行為和隨機行為在算法中的作用，人工魚在較小的視野范圍有更強的搜索能力，而在一定程度上限制了聚群行為和追尾行為的作用；在視野較大時，算法更加突出了聚群行為和追尾行為的作用，一定程度上減少覓食行為和隨機行為的發生。通常，視野越大，人工魚在發現全局極值的能力和收斂的能力越突出。
3)步長step：在一定范圍內，步長越大收斂速度越快，步長越小收斂速度越慢。但是，當步長過大超出范圍后，收斂的速度會明顯下降，甚至會使人工魚在局部極值點來回震蕩，從而降低速度和收斂精度。當設置較小的步長時，收斂速度會下降，而算法的收斂精度會提高。
4)嘗試次數try_number：經研究，人工魚在執行覓食行為時，嘗試次數對執行效果的影響是十分重要的，隨著嘗試次數增大，人工魚覓食行為的能力越強，收斂的效率越高，但是嘗試次數的增多會降低人工魚避開局部極值的能力，從而不能收斂全局極值點。所以，較大的嘗試次數，更為突出覓食行為，加快收斂速度，但容易陷入局部極值；較小的嘗試次數，更為突出隨機行為，降低收斂速度，避免陷入局部極值。在解決一些局部極值不是很突出的問題上，可以增加嘗試次數提高收斂的效率。
5)擁擠度δ：在聚群行為和追尾行為中引入擁擠度算子δ是為了避免人工魚過度聚集在局部極值點。
四、算法改進思路
4.1算法參數的改進
人工魚群算法中的參數較多，其中有人工魚群的個體數目N,擁擠度因子δ,視野和步長，前面兩個參數通常可以采用數值實驗的方法來確定它的大致范圍.后兩個參數直接影響人工魚運行的軌跡，因此對算法的效果有著更直接的影響，對于這兩個參數的選擇研究得更多一些。
1）基于視野的改進
???? ?由于視野對算法中各行為都有較大的影響，因此，它的變化對收斂性能的影響也是比較復雜的。當視野范圍較小時，人工魚群的覓食行為和隨機游動比較突出;視野范圍較大時，人工魚的追尾行為和聚群行為將變得較突出。總體來看，視野越大，越容易使人工魚發現全局極值并收斂。因此對人工魚的視野進行適當的改進，是提高人工魚群算法優化性能的一種方法。
???? ??魚群的覓食行為在解決離散型優化問題時有很重要的作用。在魚群覓食的過程中，其視野范圍是固定不變的。當人工魚逐漸逼近最優解時，X僅僅有一個或兩個變量不同于最優解，因此人工魚在最優解附近以原始的視野進行覓食是盲目的，這種情況將增加算法的計算復雜性。另外，收斂速度的快慢和最后尋優結果的質量都依靠視野值。如果視野范圍太大，收斂速度將很慢;另一方面，如果視野范圍太小，人工魚群算法可能導致陷入局部最優解。為了克服這些缺點，可選用如下的改進策略:在人工魚群算法的初始階段，每條人工魚以一個大的視野尋找解，這樣能擴大尋優的范圍。隨著算法的運行，魚群的視野范圍將適當的減小以加快收斂的速度。
2）基于步長的改進
????在人工魚群算法中，人工魚個體的三個行為:覓食、聚群和追尾都依賴于一定的可視域和步長范圍。為了進一步提高人工魚群算法的尋優能力，一方面可以通過改進視野范圍來施行:另一方面，也可以通過改進步長范圍對原有算法進行了改進。基本思路就是將人工魚群算法的實際步長改為參數定義域內的隨機數，以保證更好的全局搜索能力。
4.2覓食行為優化
正弦余弦算法 ( sine and cosine algoritm，SCA)是由Mirjalili教授提出的一種新型群體智能優化算法，依靠正弦函數和余弦函數具有周期性和波動性的特點保證魚群個體具有“全局搜索” 和“局部開發”的特點，在保證算法在大范圍內進行結果更新的全面性，同時在局部范圍內能夠有效的避免算法陷入局部最優的問題，其表達式如式(1 )
（1）
( 1) 式中，xt+1 i 表示當前種群中的個體 i 在使用更新 方式之后在第 t + 1 次循環更新后的位置，xti 和 xtk 分 別表示種群中的任意 2 個個體 i，k 在第 t 次循環更 新時的具體位置，r1，r2，r3 和 r4 為搜索方向、搜素距離、隨機選擇和正余弦切換的 4 個控制參數。其中r1 = a － a × t/ tmax ( tmax 為最大迭代次數，t 為迭代次數,a 為常數值) ,r2 ～ U［0，2π］，r3 ∈ ( 0，+ ∞ ) ，r4 控 制這正弦余弦的更新切換且 r4 ～ U［0，1］正弦余弦 優化策略的嵌入。通過這樣的處理方式一定程度上 能夠彌補個體在位置更新時候出現的缺陷，通過正 弦機制或者余弦機制，能夠使得個體魚群個體與食 物源進行交流，促進位置信息的共享，使得魚群個體向著位置更好的前進，促進個體向著最優解移動; 同 時，無論正弦還是余弦機制都能夠進行相互的彌補，正弦算法減少個體陷入局部最優，余弦算法提高探 索能力，加快算法收斂。
五、系統方案設計
5.1 功能分析
此次課程設計旨在使用人工魚群優化算法解決旅行商問題，求解最優化路線。此方案通過人工魚群算法及其優化算法來求解最優化路線，交互界面可輸入初始參數等。
5.2?總體方案設計
1）初始化設置，包括種群規模、每條人工魚的初始位置、人工魚的視野、步長、擁擠度因子、重復次數；
2） 計算初始魚群各個體的適應值，取最優人工魚狀態及其值賦予給公告牌；
3）對每個個體進行評價，對其要執行的行為進行選擇，包括覓食、聚群、追尾和隨機行為；
4）執行人工魚的行為，更新自己，生成新魚群；
5）評價所有個體。若某個體優于公告牌，則將公告牌更新為該個體；
6）當公告牌上最優解達到滿意誤差界內或者達到迭代次數上限時算法結束，
否則轉步驟3。
6圖2 總體方案結構圖
5.3?GUI界面設計
5.3.1登錄界面設計
系統登錄界面為人機交互界面的第一部分，用戶需輸入用戶名和密碼方可登錄操作界面。
圖3 人工魚群算法登錄界面
5.3.2系統界面設計
圖4所示的GUI界面包括：參數設置版塊、運行狀態顯示版塊、路線圖與迭代圖版塊以及開始與退出。參數設置版塊可對人工魚群算法的各種參數進行修改；運行狀態顯示版塊可顯示此次算法的運行時間、最短路徑以及最短距離；路線圖與迭代圖版塊可顯示此次算法運行后的城市路線圖與迭代曲線圖。
圖4 人工魚群算法可視化界面
六、實現結果及分析
6.1初始化環境數據
6.2初始算法運行結果統計數據
表 2?10次獨立實驗的運行結果統計（距離：米）
| 第1次 | 第2次 | 第3次 | 第4次 | 第5次 | |
| AFSA | 34830 | 34258 | 34607 | 34663 | 33976 |
| 第6次 | 第7次 | 第8次 | 第9次 | 第10次 | |
| AFSA | 33465 | 34258 | 34513 | 34418 | 34642 |
表 3實驗運行結果的統計(距離：米)
| AFSA算法 | Max | Min | Mean | Var |
| 距離 | 34830 | 33465 | 34363 | 685942.5 |
6.3初始算法程序運行過程展示
圖5 初始參數算法運行圖
6.4關鍵參數重要性對比
人工魚群算法中的參數較多，其中有人工魚群的群規模N,擁擠度因子δ,視野和步長，前面兩個參數通常可以采用數值實驗的方法來確定它的大致范圍.后兩個參數直接影響人工魚運行的軌跡，因此對算法的效果有著更直接的影響。在控制其他關鍵參數不變的情況下，更改視野與步長的數值，來觀察最終的結果。實驗測試結果如表4與表5。
1）通過固定人工魚群的群規模N,擁擠度因子δ和步長step，改變視野visual的數值，通過重復實驗觀察視野對于整體算法的重要程度。
表 4 改變視野
| 群規模 | 嘗試次數 | 擁擠度因子 | 步長 | 視野 | 距離 |
| 50 | 100 | 0.3 | 0.2 | 1 | 33872 |
| 2 | 33588 | ||||
| 3 | 34210 | ||||
| 4 | 34513 | ||||
| 5 | 34250 | ||||
| 6 | 34393 | ||||
| 7 | 34385 |
實驗結果表明，如果視野visual取值范圍在[1，2]內中的時候，其visual =2左右的時候可以取到最優解，visual = 2 為本次所采用的人工魚群算法的一個最優參考數值。
2）通過固定人工魚群的群規模N,擁擠度因子δ和視野visual，改變步長step的數值，通過重復實驗觀察視野對于整體算法的重要程度。
表 5 改變步長
| 群規模 | 嘗試次數 | 擁擠度因子 | 視野 | 步長 | 距離 |
| 50 | 100 | 0.3 | 1 | 0.2 | 33831 |
| 0.4 | 33791 | ||||
| 0.6 | 34197 | ||||
| 0.8 | 34334 | ||||
| 1.0 | 34207 | ||||
| 1.2 | 34071 | ||||
| 1.4 | 34358 |
實驗結果表明，步長step在0.4左右的時候表現出了較好的效果，在一定范圍內，步長越大收斂速度越快，步長越小收斂速度越慢。但是，當步長過大超出范圍后，收斂的速度會明顯下降，甚至會使人工魚在局部極值點來回震蕩，從而降低速度和收斂精度。當設置較小的步長時，收斂速度會下降，而算法的收斂精度會提高。
6.5實驗結論
通過對比初始值與修改參數后算法運行情況，我們發現當視野visual = 2，步長為0.4時可以取得一個較好的結果。同時，通過比較數據結果，我們得出以下結論：
1)通常，視野越大人工魚在發現全局極值的能力和收斂的能力越突出。當視野范圍較小時往往更加突出覓食行為和隨機行為在算法中的作用，人工魚在較小的視野范圍有更強的搜索能力，而在一定程度上限制了聚群行為和追尾行為的作用；在視野較大時，算法更加突出了聚群行為和追尾行為的作用，一定程度上減少覓食行為和隨機行為的發生。
2)在一定范圍內，步長越大收斂速度越快，步長越小收斂速度越慢。但是，當步長過大超出范圍后，收斂的速度會明顯下降，甚至會使人工魚在局部極值點來回震蕩，從而降低速度和收斂精度。當設置較小的步長時，收斂速度會下降，而算法的收斂精度會提高。
總結
以上是生活随笔為你收集整理的人工鱼群算法解决TSP问题的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： lightoj 1020 （博弈）
- 下一篇： ASP.NET MVC + ADO.NE