人工免疫算法在機(jī)器人路徑規(guī)劃中的研究

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

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.

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

1 引言

人工免疫算法模仿生物免疫系統(tǒng)的過程，而提出的一種啟發(fā)式隨機(jī)搜索算法，其具有全局并行分布式搜索、多樣性保持機(jī)制和魯棒性強(qiáng)的特點(diǎn)。在對(duì)問題的解進(jìn)行局部搜索的同時(shí)利用變異算子和種群刷新算子產(chǎn)生新個(gè)體使得算法可以在可行解區(qū)間內(nèi)進(jìn)行搜索，是一個(gè)全局優(yōu)化能力的算法，具有全局收斂性能。生物免疫系統(tǒng)與人工免疫算法概念對(duì)應(yīng)關(guān)系，如表1所示。

表1 生物免疫系統(tǒng)與人工免疫算法概念對(duì)應(yīng)表

人工免疫算法在機(jī)器人路徑規(guī)劃中具有重要研究?jī)r(jià)值，但直接把傳統(tǒng)的免疫算法應(yīng)用于機(jī)器人路徑規(guī)劃方案中，會(huì)存在容易陷入局部最優(yōu)，而非全局最優(yōu)，以及收斂速度慢等缺陷。

2 免疫算法基本概念

2.1 人工免疫算法原理

人工免疫算法將生物免疫過程中的進(jìn)化鏈（產(chǎn)生抗體群→計(jì)算親和度→選擇克隆→變異→計(jì)算抗體濃度→促進(jìn)/抑制→更新抗體群）抽象成為數(shù)學(xué)上的進(jìn)化尋優(yōu)過程。

2.2 人工免疫算法流程

Step1 抗體識(shí)別：將待優(yōu)化的問題抽象為抗原形式。

Step2 產(chǎn)生初始種群：隨機(jī)產(chǎn)生初始種群。

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

Step4 終止條件判斷：如果滿足條件則算法終止；否則繼續(xù)尋優(yōu)運(yùn)算。

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

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

Step7終止條件判斷：若得到最優(yōu)解則結(jié)束，否則返回Step3。

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

圖1 人工免疫算法流程圖

2.3 人工免疫重要算子

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

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

其中，ti是抗原與抗體i的結(jié)合強(qiáng)度，(Ag)i是抗體i與抗原之間的親和度，其值介于0和1之間。當(dāng)(Ag)i=1（ti=0）時(shí),表示抗體i與抗原匹配度極高，即該抗體為最優(yōu)解。

（2）抗體濃度

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

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

（3）交叉算子

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

（4）變異算子

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

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

3 基于傳統(tǒng)免疫算法的機(jī)器人路徑規(guī)劃

3.1 環(huán)境建模

環(huán)境建模是機(jī)器人路徑規(guī)劃中的重要環(huán)節(jié)，目前常見的建模方式主要有人工勢(shì)場(chǎng)法、柵格法、路標(biāo)法等。采用20*20柵格地圖對(duì)機(jī)器人運(yùn)動(dòng)環(huán)境進(jìn)行建模，其中黑色柵格表示障礙物，白色柵格表示自由空間。

3.2 仿真驗(yàn)證

利用Matlab對(duì)基于傳統(tǒng)免疫算法的路徑規(guī)劃方案進(jìn)行仿真，設(shè)置仿真參數(shù)如下。

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

圖2 （a）傳統(tǒng)免疫算法的路徑規(guī)劃圖

圖2 （b）傳統(tǒng)免疫算法的收斂曲線

通過觀察圖2（b）可以發(fā)現(xiàn)，該算法在第150次迭代時(shí)才趨于穩(wěn)定，最短路徑長(zhǎng)度為42.0416。

4 免疫算法的改進(jìn)

4.1 克隆算子和高頻變異

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

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

4.2 算法流程圖

Step1 抗原識(shí)別：識(shí)別環(huán)境并記錄障礙物的信息，設(shè)置起始點(diǎn)和終點(diǎn)。

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

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

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

Step4 克隆繁殖：根據(jù)種群中親和度的高低進(jìn)行排序，選擇親和度高的個(gè)體進(jìn)行克隆繁殖。

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

圖3 改進(jìn)免疫算法流程圖

4.3 仿真結(jié)果分析

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

圖4 （a）改進(jìn)免疫算法的路徑規(guī)劃圖

圖4 （b） 改進(jìn)免疫算法的收斂曲線

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

結(jié)束語(yǔ)

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