采用生物地理學算法的移動機器人路徑規(guī)劃研究

羅 丹，蔣兵兵

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

1 引言

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

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

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

2 環(huán)境模型

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

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

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

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

(1)

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

4 改進生物地理學算法在機器人路徑規(guī)劃中的應用

4.1 機器人路徑的編碼方式

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

4.2 種群初始化

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

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

4.3 生物地理學算法的改進

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

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

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

(2)

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

4.3.2 遷移操作

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

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

2: if rand < λithen

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

4： For j=1 to NP(棲息地數(shù)量)do

5： if rand<μjthen

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

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

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

9: End if

10： End for

11： End if

12: End for

4.3.3 變異操作

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

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

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

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

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

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

5 仿真分析與比較

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

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

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

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

6 結論

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

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