羅 丹，蔣兵兵

(1.湖南鐵道職業(yè)技術(shù)學(xué)院，湖南 株州 412000；2.湖南鐵路科技職業(yè)技術(shù)學(xué)院，湖南 株州 412000)

1 引言

隨著人工智能的發(fā)展，移動機(jī)器人的路徑規(guī)劃成為一個研究的熱點(diǎn)。路徑規(guī)劃算法分為兩類：一類是傳統(tǒng)算法，如人工勢場法、可視圖法、柵格法、自由空間法、A*算法等，另一類是仿生進(jìn)化算法，如粒子群算法、蟻群算法、遺傳算法等。由于傳統(tǒng)算法在機(jī)器人路徑規(guī)劃中存在搜索效率低等情況[1]，而仿生進(jìn)化算法在搜索速度方面有較大的優(yōu)勢。因此，近年來，群智能算法是移動機(jī)器人路徑規(guī)中的一個研究熱點(diǎn)[3]。

生物地理學(xué)算法[2](Biogeography-Based Optimization，BBO)是美國學(xué)者Dan Simon將生物地理學(xué)的研究成果與工程研究相結(jié)合，提出的一種新型仿生進(jìn)化算法。BBO算法的全局搜索性能較好，學(xué)者們對BBO算法進(jìn)行了大量的研究，并將其廣泛應(yīng)用到電力系統(tǒng)調(diào)度問題、非線性系統(tǒng)、0-1組合問題、PID參數(shù)整定等實(shí)際問題中，并取得了較好的測試效果，也有少部分學(xué)者將其用到路徑規(guī)劃中，并取得了一定的研究效果[4,5,8]?？紤]到生物地理學(xué)算法的存在收斂速度慢等不足，結(jié)合遺傳算法具有的快速收斂性，本文提出一種新的改進(jìn)生物地理學(xué)算法。

文中將改進(jìn)的生物地理學(xué)算法應(yīng)用到機(jī)器人路徑規(guī)劃中，其本質(zhì)是將路徑規(guī)劃問題轉(zhuǎn)變?yōu)楹瘮?shù)優(yōu)化問題。選取兩種不同靜態(tài)環(huán)境，通過MATLAB進(jìn)行仿真實(shí)驗(yàn)，仿真結(jié)果證明，生物地理學(xué)算法在路徑規(guī)劃中是具有可行性的。

2 環(huán)境模型

常用的環(huán)境建模方法有行車圖法、勢場法、單元分解法。為了編程簡單易實(shí)現(xiàn)，文中采用一種近似的單元分解法，即柵格法。柵格法是用大小相同的柵格單元對將機(jī)器人的工作環(huán)境進(jìn)行劃分，形成柵格地圖，能夠處理任意形狀的障礙物。常用的柵格地圖表示方法有直角坐標(biāo)法和序號法，序號法表述簡潔易懂，文中采用序號法進(jìn)行柵格標(biāo)識。如圖1所示，從柵格序號p從柵格地圖的左下角開始編號，序號p與每一個柵格一一對應(yīng)，圖中黑色部分為障礙物柵格，黑色方格表示障礙物，白色是可行區(qū)間為自由柵格。

圖1 采用序號法的柵格地圖

3 機(jī)器人路徑優(yōu)化的目標(biāo)評價函數(shù)

在機(jī)器人路徑規(guī)劃中，選擇合適的目標(biāo)函數(shù)對算法獲得的優(yōu)化結(jié)果和收斂效果是非常關(guān)鍵的，目標(biāo)函數(shù)的適應(yīng)度值是評價棲息地好壞的一個依據(jù)。文中的研究對象是靜態(tài)環(huán)境中的機(jī)器人路徑優(yōu)化，以獲得最短路徑距離為目標(biāo)，考慮到同樣的路徑存在的拐點(diǎn)數(shù)不一樣，為了更好的達(dá)到路徑優(yōu)化的效果，引入平滑度最小的優(yōu)化目標(biāo)。文中機(jī)器人路徑優(yōu)化的目標(biāo)評價函數(shù)選取如下：

(1)

式(1)中，α和β是路徑距離和平滑度的權(quán)重因子，d是一組無間斷可行路徑的路徑規(guī)劃距離，s表示路徑的平滑度，即路徑的拐點(diǎn)個數(shù)。

4 改進(jìn)生物地理學(xué)算法在機(jī)器人路徑規(guī)劃中的應(yīng)用

4.1 機(jī)器人路徑的編碼方式

BBO算法是采用實(shí)數(shù)進(jìn)行編碼的一種優(yōu)化算法，而機(jī)器人路徑規(guī)劃問題是一個離散問題。因此本研究提出一種改進(jìn)生物地理學(xué)算法應(yīng)用于求解機(jī)器人路徑規(guī)劃問題，以柵格標(biāo)識號進(jìn)行編碼確定一條可行路徑，以圖3為例，序號[1，2，3，4，15，24，35，36，46，47，48，50，60，70，80，90，100]夠成一條可行路徑。

4.2 種群初始化

(1)根據(jù)起始點(diǎn)到目標(biāo)點(diǎn)的最短直線距離，獲得需要的自由柵格數(shù)，然后從每一行自由柵格中隨機(jī)選取一個可行的自由柵格，構(gòu)成一組間斷的可行路徑。以圖3為例，一組間斷的可行路徑為[1，15，24，35，46，60，70，80，90，100]。

(2)通過按照一定的規(guī)律插入自由柵格將上述間斷可行路徑中的間斷節(jié)點(diǎn)之間轉(zhuǎn)變成無障礙物的連續(xù)可行路徑[1，15，24，35，46，60，70，80，90，100]。

4.3 生物地理學(xué)算法的改進(jìn)

為克服生物地理學(xué)算法在收斂速度上的不足，引入遺傳算法的操作算子，通過相互“取長補(bǔ)短”對算法進(jìn)行改進(jìn)，以期獲得更好的優(yōu)化效果。其中，遺傳算法的選擇算子通常是采用輪盤賭法進(jìn)行操作，存在較大的隨機(jī)性，文中采用BBO算法的遷入遷出率完成遺傳算法選擇和交叉操作，改進(jìn)操作可以實(shí)現(xiàn)生物地理學(xué)算法進(jìn)行離散編碼，增強(qiáng)BBO算法在搜索效率和精度上的優(yōu)化性能。

4.3.1 遷移模型的選擇。BBO算法采用的是如圖4所示的線性遷移模型計(jì)算遷入率和遷出率，而文獻(xiàn)[6,7]有提出一種余弦遷移模型，通過數(shù)據(jù)驗(yàn)證，在算法的優(yōu)化性能上，余弦遷移模型要優(yōu)于線性遷移模型。

文中采用余弦遷移模型進(jìn)行物種遷移，設(shè)第s個島嶼擁有的物種數(shù)量是s個，余弦遷移模型計(jì)算[5]公式為：

(2)

式(2)中，表示島嶼之間物種最大遷入率，表示島嶼之間物種最大遷出率。

4.3.2 遷移操作

BBO算法的遷移操作主要是根據(jù)遷入遷出率確定需要遷入的棲息地和遷出的棲息地,然后將選定的兩個棲息地進(jìn)行互換。這種全部信息交換機(jī)制容易丟失部分更優(yōu)的子路徑，導(dǎo)致算法的收斂速度下降，文中引入遺傳算法的交叉機(jī)制，可以保留部分更優(yōu)的路徑，從而使算法的優(yōu)化性能進(jìn)行提高。融入遺傳算法交叉機(jī)制的遷移操作偽代碼如下：

1：For i=1 to NP (棲息地?cái)?shù)量) do

2: if rand < λithen

3: 選取Xi執(zhí)行遷入操作

4： For j=1 to NP(棲息地?cái)?shù)量)do

5： if rand<μjthen

6： 選取Xi執(zhí)行遷出操作

7： 確定Xi和Xj存在的相同節(jié)點(diǎn)的子路徑

8： 根據(jù)遺傳算法的交叉算子對Xi和Xj進(jìn)行交叉

9: End if

10： End for

11： End if

12: End for

4.3.3 變異操作

在基本BBO算法中[1,5]，采用的是隨機(jī)變異。隨機(jī)變異的隨機(jī)性較大，能夠增加物種跳出局部最優(yōu)，但是隨機(jī)變異后獲得的路徑節(jié)點(diǎn)可能構(gòu)成一條不可行的路徑。這將使機(jī)器人路徑優(yōu)化的迭代次數(shù)增加。文中采用一種新的改進(jìn)的路徑規(guī)劃變異算子，以減少變異后獲得不可行路徑的概率。變異操作的改進(jìn)步驟如下。

(1)根據(jù)島嶼物種數(shù)量s的突變概率函數(shù)，選取需要突變的島嶼Xi，Xi=[x1,x2,x3,…xs]為第i個島嶼棲息的物種，即對應(yīng)路徑規(guī)劃中的一條可行路徑。

(2)為提高種群的多樣性，采用基于高斯分布的變異操作。按高斯分布概率選擇兩個節(jié)點(diǎn)，將兩節(jié)點(diǎn)之間的無間斷可行路徑刪除，然后生成新的可行路徑替代。

4.4 求解機(jī)器人路徑規(guī)劃的生物地理學(xué)算法

將公式(1)作為路徑規(guī)劃的目標(biāo)函數(shù)，每一個島嶼代表一條可行路徑，根據(jù)改進(jìn)生物地理學(xué)算法的遷移操作和變異操作，可以確定求解機(jī)器人路徑規(guī)劃的算法流程如圖2所示。

圖2 基于BBO算法的機(jī)器人路徑規(guī)劃流程

5 仿真分析與比較

為了驗(yàn)證該算法的可行性和有效性，選用簡單和復(fù)雜兩種工作環(huán)境，用MATLAB進(jìn)行仿真驗(yàn)證。

簡單環(huán)境下：障礙物數(shù)量為5，柵格地圖為10*10，機(jī)器人路徑規(guī)劃的算法參數(shù)設(shè)置如下：島嶼數(shù)量NP=20，迭代次數(shù)K=250，最大遷入遷出率I=E=1。采用MATLAB7.11進(jìn)行仿真，在迭代20次左右可以的到獲得最優(yōu)路徑如圖3所示(圖中綠色點(diǎn)是起始點(diǎn)，紅色點(diǎn)是目標(biāo)點(diǎn))。

圖3 10*10環(huán)境下最優(yōu)路徑

復(fù)雜環(huán)境下：障礙物數(shù)量為16，柵格地圖為20*20，機(jī)器人路徑規(guī)劃的算法參數(shù)設(shè)置如下：島嶼數(shù)量NP=20，迭代次數(shù)K=300，最大遷入遷出率I=E=1。采用MATLAB7.11進(jìn)行仿真，在迭代250次可以的到獲得最優(yōu)路徑如圖4所示(圖中綠色點(diǎn)是起始點(diǎn)，紅色點(diǎn)是目標(biāo)點(diǎn))。

6 結(jié)論

通過上述的仿真結(jié)果可以看出，在上述的簡單環(huán)境下，相同的種群數(shù)量下，迭代20次左右就可以找到最優(yōu)解；復(fù)雜環(huán)境下，迭代250次左右才能獲得最優(yōu)解。仿真結(jié)果表明，BBO算法在機(jī)器人路徑規(guī)劃上是具有可行性和有效性的。但是對動態(tài)環(huán)境機(jī)器人路徑規(guī)劃效果還有待研究。

圖4 20*20環(huán)境下最優(yōu)路徑