人工魚群算法應用

基于人工魚群算法的機器人路徑規劃

環境描述

? 路徑規劃的第一步是建立適當的環境模型，建模的方法有多種，例如：柵格法、實際坐標系建模及鏈接圖法建模等。柵格法當規劃范圍較大時計算量相當大，用實際坐標系建模，雖然建模簡單，但很難和其他成熟的規劃方法結合。在障礙物形狀不是太復雜的情況下，采用鏈路圖（即自由空間法）方法建立的機器人工作空間模型會大大減少建模的復雜性。用人工魚群算法求解問題時，算法操作比較簡單，而且可以和成熟的圖搜索遍歷技術相結合，比較容易求到最優路徑。

? 作為全局路徑規劃方法的一種，自由空間法采用預先定義的如廣義錐形和凸多邊形等基本形狀構造自由空間，并將自由空間表示為連通圖，通過搜索連接圖來進行路徑規劃。自由空間的構造方法是：從障礙物的一個頂點開始，依次作其他頂點的連接線，刪除不必要的連接線，使得連接線與障礙物邊界所圍成的每一個自由空間都是面積最大的凸多邊形；連接各連接線的重點形成的網絡圖即為機器人可自由運動的路線。自由空間法的優點是比較靈活，起始點和目標點的改變不會造成連通圖的重構，并且不需要像柵格法一樣需要大量的存儲空間；缺點是其復雜程度與障礙物多少成正比，且有時無法獲得最短路徑。

? 鏈接線的中點作為機器人路徑點，這些路徑點順序標識為1,2,3，… ，n；連接各路徑點形成的網絡圖即為機器人可自由運動的線路。其中黑色多邊形為障礙物，點線為自由鏈接線，虛線為自由鏈接線中點連接而成的機器人可自由運動的網絡。

路徑編碼方法

? 通過引進Dijkstra算法可以得到鏈接圖中的最短路徑P0,P1,P2,…,Pn,Pn+1,其中：P0 = start為路徑的起點，Pn+1 = goal為路徑的終點。優化工作就是調整Pi(i =1,2,3,…,n)的位置，使此路徑最短，從而得到機器人在規劃空間的最優（或近似最優）移動路徑。

? 對于Pi點，讓它在由Pi1,pi2兩點所組成的直線段上變動，其具體位置可由下述參數方程式中的ti來決定。

? 對此路徑上的每個路徑點都這樣處理后，這些新的路徑點就組成了一條新的行走路徑。則每一條新的行走路徑就代表一條人工魚。

? 對于這一條新的調整后的路徑，可由n個取值在[0,1]范圍內的ti值的排列來唯一地表示其各個路徑點的新位置，即確定了這條路徑。要注意的是，機器人行走路徑的起點和終點不參與調整。個體的編碼形式為P = t1t2t3…tl…tn。例如：P = 0.5 0.8 0.3 … 0.8 0.6 0.2 就表示一條機器人行走路徑。其中各個數字表示對初路徑點的調整量。

算法步驟

步驟1

設定魚群的參數，包括魚群規模m，最大迭代次數gen，人工魚的感知范圍Visual，最大移動步長step，擁擠度因子δ等；

步驟2

在參數區間內隨機生成m條人工魚個體，作為初始魚群；

步驟3

計算每條魚的食物濃度函數，把最小的值放入公告板中；

步驟4

對于每條人工魚執行以下操作;

1） 計算出追尾行為、聚群行為的值，采用行為選擇策略，選擇優的行為作為魚的前進方向，缺省行為是覓食行為。該魚向前移動一步。

2）計算每條魚的食物濃度函數，其最小值與公告板中的值進行比較，最終公告板中始終保持較小的值。

步驟5

判斷 如果滿足結束條件，轉步驟6；否則轉步驟4。

步驟6

程序結束，則公告板中的值就是全局路徑優化后的最優值，其對應的路徑則是優化了的全局路徑的最優路徑。

結論

? 對于機器人路徑規劃問題，在利用鏈路圖對路徑空間進行建模的基礎上，先使用圖論中的成熟算法找到一條從起點到終點的最優路徑，然后再利用人工魚群算法來調整路徑上的點，最終得到全局的最優路徑。實驗結果顯示，算法在很少的迭代次數內就能得到最優值，很明顯這種方法滿足機器人路徑規劃的實時性，是有效的。

基于人工魚群算法求解數值積分

求解思路

基于人工魚群算法求數值積分求解思路：首先在積分區間上隨機的產生一些分割點，看做一條人工魚；然后通過人工魚的自尋優方法來對分割點進行優化，最后以優化后的分割點為最優分割點，再依據求和公式進行求和，最終得到所求被積函數的值。

算法步驟

人工魚群（分割方法）產生及優化過程如下：

步驟1

設定魚群的參數，包括魚群規模m，最大迭代次數gen，人工魚的感知范圍Visual，最大移動步長step，擁擠度因子δ等；

步驟2

初始化魚群：在定積分的積分區間內隨機生成m條人工魚個體，作為初始魚群；

步驟3

計算每條魚的食物濃度函數，把最小的值放入公告板中；

步驟4

對于每條人工魚執行以下操作;

1） 計算出追尾行為、聚群行為的值，采用行為選擇策略，選擇優的行為作為魚的前進方向，缺省行為是覓食行為。該魚向前移動一步。

2）計算每條魚的食物濃度函數，其最小值與公告板中的值進行比較，最終公告板中始終保持較小的值。

步驟5

判斷 如果滿足結束條件（達到最大迭代次數或滿足精度要求），轉步驟6；否則轉步驟4。

步驟6

程序結束。則公告板中的值就是采用不等距分割法尋優后的最優解，而后使用傳統的積分方法：代入表達式
$$\sum _{j=1}^{n+1}midYjdj$$
來求積分值，其中 midYj為由積分區間的左端點、優化后的不等距分割點和右端點劃分成的n+1個小段的中點對應的函數值;

dj為 由積分區間的左端點、優化后的不等距分割點和右端點劃分成的n+1個小段的長度。

應用舉例

結論

利用人工魚群算法來求解數值積分問題，充分發揮了人工魚群算法的群體搜索和并行的特性。從以上的實例可以看出，采用人工魚群算法來求解數值積分問題具有以下幾個特點：

1）該算法適應性強，計算精度比一些傳統的積分方法要高；

2）既可以較精確的計算一般函數的數值積分，還可以計算奇異積分、震蕩積分和原函數不易求得的被積函數的積分；

3）收斂性好，算法能在很少的代數內收斂到比較滿意的解；

4）參數的敏感性低，參數的變動對結果的影響不大。

總結

以上是生活随笔為你收集整理的人工鱼群算法应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。