人工免疫算法在機器人路徑規劃中的研究

南京大學金陵學院 孫海洋 郭黎黎 謝鵬飛 王先一

Aiming at the shortcomings of traditional immune algorithm applied to robot path planning, such as premature convergence, easy to fall into local optimum and weakening of late acquisition ability, this paper introduces clonal selection operator and selects clone according to the affinity of antibody in the population. The improvement of the antibody using high frequency variation is also made. The Matlab is used to build the robot path planning simulation platform. In the grid map environment, the traditional algorithm and the improved algorithm are compared and simulated. The simulation results show that the artificial immune algorithm is improved, which avoids local convergence and improves the convergence speed. The planning path is closer to the optimal path, and the search range is expanded, and problems such as poor local search ability are improved. Verify that the improvements proposed in this paper is feasible and effective.

針對傳統免疫算法應用于機器人路徑規劃中，存在的早熟收斂、容易陷入局部最優及后期收索能力減弱等缺陷，本文引入克隆選擇算子,按照種群中抗體親和度的大小進行選擇克隆，并對抗體采用高頻變異的方式進行改進。使用Matlab搭建機器人路徑規劃仿真平臺，在柵格地圖環境下，對傳統算法和改進算法進行對比仿真分析，仿真結果表明改進后的人工免疫算法，有效地避免了局部收斂，提高了收斂速度，所規劃路徑更接近最優路徑，并且擴大了搜索范圍，改善了局部搜索能力差等問題。驗證了本文所提改進方案的可行性和有效性。

1 引言

人工免疫算法模仿生物免疫系統的過程，而提出的一種啟發式隨機搜索算法，其具有全局并行分布式搜索、多樣性保持機制和魯棒性強的特點。在對問題的解進行局部搜索的同時利用變異算子和種群刷新算子產生新個體使得算法可以在可行解區間內進行搜索，是一個全局優化能力的算法，具有全局收斂性能。生物免疫系統與人工免疫算法概念對應關系，如表1所示。

表1 生物免疫系統與人工免疫算法概念對應表

人工免疫算法在機器人路徑規劃中具有重要研究價值，但直接把傳統的免疫算法應用于機器人路徑規劃方案中，會存在容易陷入局部最優，而非全局最優，以及收斂速度慢等缺陷。

2 免疫算法基本概念

2.1 人工免疫算法原理

人工免疫算法將生物免疫過程中的進化鏈（產生抗體群→計算親和度→選擇克隆→變異→計算抗體濃度→促進/抑制→更新抗體群）抽象成為數學上的進化尋優過程。

2.2 人工免疫算法流程

Step1 抗體識別：將待優化的問題抽象為抗原形式。

Step2 產生初始種群：隨機產生初始種群。

Step3 計算親和度：通過計算抗體與抗原之間的親和度，選擇親和度大的抗體進行增殖。

Step4 終止條件判斷：如果滿足條件則算法終止；否則繼續尋優運算。

Step5 計算抗體濃度和激勵度：計算抗體群的濃度，促進濃度低且具有較高親和度的抗體，抑制濃度高且具有較低親和度的抗體。

Step6 更新抗體群：用親和度高的抗體代替親和度低的抗體，產生新的抗體。

Step7終止條件判斷：若得到最優解則結束，否則返回Step3。

人工免疫算法的流程圖如圖1所示。

圖1 人工免疫算法流程圖

2.3 人工免疫重要算子

（1）抗體i與抗原親和度

親和度是免疫算法中最重要也是最復雜的計算，通常，其計算如公式（1）所示。

其中，ti是抗原與抗體i的結合強度，(Ag)i是抗體i與抗原之間的親和度，其值介于0和1之間。當(Ag)i=1（ti=0）時,表示抗體i與抗原匹配度極高，即該抗體為最優解。

（2）抗體濃度

在人工免疫算法中采用基于抗體濃度調節的機制來保持種群中抗體的多樣性。在免疫調節算法中，那些高抗原親和度且樣本濃度較低的抗體將被增強；相反，那些低抗原親和度且樣本濃度較高的抗體將被抑制?？贵w濃度的計算如公式（2）所示。

其中，(Ag)i表示抗體i與抗原的親和度，θ為親和度常數，一般取值為0.9 ≤ θ ≤ 1，M表示親和度大于θ的抗體個數，N為抗體總數。

（3）交叉算子

交叉通常又稱為重組，是以較大的概率從種群中選擇兩個個體，對兩個個體編碼串上的某個或某些位進行交換。交叉是產生新個體的主要方式。交叉操作方式主要有單點交叉、多點交叉、均勻交叉和算術交叉等。

（4）變異算子

變異通常以較小的概率對個體編碼串上的某個或某些位進行改變，是產生新個體的輔助方式，但是必不可少的一個環節，它可以改善算法的局部搜索能力，并且可以維持樣本的多樣性，避免出現“早熟”現象。

交叉算子和變異算子相結合，可進一步保證算法的局部和全局搜索能力，從而使得免疫算法以較優的性能完成尋優過程。

3 基于傳統免疫算法的機器人路徑規劃

3.1 環境建模

環境建模是機器人路徑規劃中的重要環節，目前常見的建模方式主要有人工勢場法、柵格法、路標法等。采用20*20柵格地圖對機器人運動環境進行建模，其中黑色柵格表示障礙物，白色柵格表示自由空間。

3.2 仿真驗證

利用Matlab對基于傳統免疫算法的路徑規劃方案進行仿真，設置仿真參數如下。

設置初始種群數為20，迭代次數為200，交叉概率為0.6，變異概率為0.2。仿真結果如圖2(a)和圖2(b)所示。

圖2 （a）傳統免疫算法的路徑規劃圖

圖2 （b）傳統免疫算法的收斂曲線

通過觀察圖2（b）可以發現，該算法在第150次迭代時才趨于穩定，最短路徑長度為42.0416。

4 免疫算法的改進

4.1 克隆算子和高頻變異

（1）克隆選擇算子：對種群中的抗體按照親和度由高到低進行排序，選擇親和度高的抗體進行克隆繁殖。

（2）高頻變異算子：克隆變異能夠在父代抗體的種群內進行有效搜索的同時，通過變異操作使抗體群跳出局部最優，從而得到全局最優解。本文采用高頻變異，即讓親和度較高的抗體進行高頻變異，減少了相似抗體在種群的繁殖速度，從而提高了抗體種類的多樣性，同時，也改善了克隆選擇過程導致的算法收斂速度較慢的缺點。

4.2 算法流程圖

Step1 抗原識別：識別環境并記錄障礙物的信息，設置起始點和終點。

Step2 計算抗體親和度：對抗體抗原的親和度進行計算，親和度的計算如公式（3）所示。

其中，ds表示機器人與障礙物之間的距離，de表示機器人到目的地的距離，X（0～2pi）是路線與機器人和終點連線的夾角。

Step3 終止條件判斷：初始化時設置一個中間變量time和迭代次數N，time初始為0，如果N次迭代后得到了無碰撞的路徑，則執行Step4，否則，令time=time+1。

Step4 克隆繁殖：根據種群中親和度的高低進行排序，選擇親和度高的個體進行克隆繁殖。

Step5 克隆變異：以較高的概率對種群中的抗體進行高頻變異操作。

圖3 改進免疫算法流程圖

4.3 仿真結果分析

定義初始種群數為20，迭代次數為200，交叉概率為0.6，變異概率設為0.8。即在相同的地圖環境及仿真參數設置中，引入克隆算子，并將種群中抗體變異操作改為高頻變異。仿真結果如圖4(a)和圖4(b)所示。

圖4 （a）改進免疫算法的路徑規劃圖

圖4 （b） 改進免疫算法的收斂曲線

從圖4(b)可以看出，改進后的算法大概在第10代就已經趨于穩定，路徑長度為28.6274。改進后的算法與傳統算法相比，不僅具有較高的收斂速度。而且最短路徑長度也有較大縮短。

結束語

本文基于人工免疫算法的機器人路徑規劃方案，在傳統免疫算法的基礎上引入了克隆算子，并對種群中的抗體采用高頻變異的方式，以便保持群體中抗體的多樣性，擴大了搜索范圍。通過Matlab仿真驗證，改進后的算法無論在算法收斂還是所尋最短路徑方面都取得了較好的性能。