混合智能算法在機器人路徑規(guī)劃中的應用

代婷婷，董延壽

（昭通學院 數(shù)學與統(tǒng)計學院，云南 昭通 657000）

在日常生活中機器人無處不在地影響著我們，給生活帶來了許多方便和精彩，在很多領域發(fā)揮著重要的不可替代的作用，特別是在節(jié)省人力、物力方面發(fā)揮的作用日益突出。對它主要研究其通用性和適應性[1-2]。為了滿足人類的各種需求，必須深入分析復雜多變的環(huán)境，設計合理的算法程序實現(xiàn)其自主導航運動目標，而路徑規(guī)劃是移動機器人實現(xiàn)這一目標的核心技術，在研究領域是熱點關注的地方[3]。機器人的智能水平越高表示它的路徑規(guī)劃水平較高。因此，尋找高效的機器人路徑規(guī)劃方法顯得非常有意義[4]。盡管蟻群算法在收斂速度等方面有不足和局限，可在求解機器人路徑規(guī)劃方面由于它具有的諸如正反饋性、強魯棒性、并行性等很多優(yōu)點可以得到充分利用，使得該算法在很多智能化領域被深入研究和廣泛應用。為了充分利用蟻群算法的優(yōu)勢，挖掘文獻[5]和文獻[6]中改進蟻群算的技巧原理，巧妙地柔和兩種改進的優(yōu)點得出了另外一種新的改進蟻群算法。將得到的融合雙因子改進蟻群算法與遺傳算法于機器人路徑規(guī)劃實驗的不同階段混合使用得到了良好效果，選擇柵格法在不同規(guī)模的柵格上使用MATLAB2019 進行機器人路徑規(guī)劃實驗進一步突出混合算法的優(yōu)勢。

1 相關理論

1.1 遺傳算法

遺傳算法是一種廣為人知的智能算法，因為其具有強魯棒性、獨立性、可操作性等優(yōu)點，使得該算法的應用相當廣泛，物理、數(shù)學、計算機、化學等領域都有涉及[7-8]。其主要原理：產生初始種群后，這些種群通過雜交會逐代演化產生適應生存環(huán)境的優(yōu)秀子代，而這個優(yōu)秀的子代就可以看成是遺傳算法的最優(yōu)化的近似解，按照達爾文的進化論適者生存優(yōu)勝劣汰的大自然生物學原理將優(yōu)秀的個體選擇出來，交配挑選出來的個體。在每一代中，按照自然遺傳學的相關理論找出相應的算子，然后依據(jù)算子原理進行讓種群之間進行交叉，在組合交叉的過程中會產變異的種群，一代又一代的種群按照此種方法交叉變異，最后就會產生適應環(huán)境能力強的種群，即最為優(yōu)秀的個體就會產生，當最優(yōu)秀的個體通過解碼后就會對應優(yōu)化問題的最優(yōu)解，則代表新的解集就會得到。由于國內外的學者對此方法的研究很深入，在各方面都取得了不錯的成就，這使得遺傳算法的性能逐步被提高很多，從而使得該算法的應用領域越來越廣泛[9-10]。

1.2 關于遺傳算法的路徑規(guī)劃

基于以上關于遺傳算法的理論可以得到遺傳算法在路徑規(guī)劃中的實現(xiàn)步驟[11]:

（1）隨機產生一定數(shù)目的很多條路經，將這些隨機產生的路徑看成初始種群，機器人在柵格上行走；

（2）在機器人行走中需要連續(xù)的路徑，為了將上述間斷的路徑改成連續(xù)的路徑需要對相鄰的柵格做連續(xù)性判斷，按照上下左右的順序取相鄰柵格，將無障礙的柵格插入不相鄰的柵格，不斷調整直到所有的柵格路徑連續(xù)為止；

（3）按照個體適應度函數(shù)求解個體所占的比率從而選擇出需要的優(yōu)秀個體，為了防止算法陷入局部死循環(huán)，采用輪盤賭的方式進行；

（4）在路徑規(guī)劃中進行交叉操作，在挑選出兩條相同路徑的交點時采用單點交叉的方式進行，依此點為目標點將后面的路徑進行交叉，同時對路徑的連續(xù)性進行判斷，不斷修改判斷知道完成所有的交叉操作。

（5）比較變異概率和特定的數(shù)值，當變異概率大于給定的數(shù)字時，那么路徑上的兩個柵格隨機選取，并對相鄰的情況做出判斷，使用產生初始種群的方法調整柵格的連續(xù)性，直到所有柵格連續(xù)完成變異操作。

1.3 改進的蟻群算法

1.3.1 改進啟發(fā)函數(shù)

基于基本蟻群算法的原理分析以及結合相關的參考文獻，發(fā)現(xiàn)影響最短路徑計算結果的主要原因就是節(jié)點之間的概率轉移以及螞蟻行走路徑上不斷更新變化的信息素濃度。而轉移概率對最短路徑的影響主要是通過它里面的啟發(fā)函數(shù)起作用的。常規(guī)遺傳算法的概率轉移取相鄰節(jié)點i 與j的歐氏距離倒數(shù)作啟發(fā)函數(shù)使用。在最初搜索的時候，行走路徑上的螞蟻數(shù)量較少，釋放的信息素較少，造成其他螞蟻偏離正確尋找路徑的概率較大，這樣很容易形成局部的最優(yōu)解或者產生無效解甚至進入死循環(huán)求不出結果[12]。于是文獻[5]在啟發(fā)函數(shù)中引入了當前和目標節(jié)點的歐氏距離，從而使兩個節(jié)點的聯(lián)系更加的緊密，改進啟發(fā)函數(shù)的數(shù)學表達式如公式（1）所示：

在上面的（1）式中dij表示節(jié)點i 與j 的歐氏距離；djE是節(jié)點j 和目標節(jié) 點E 之間的歐氏距離,于是搜索路徑的方向性被加強，加強的方向性使得漫無目的的搜尋的時間大大減少，這一改進從時間上來說就比原有的算法具有優(yōu)勢，計算的效率明顯提高。

1.3.2 改進的信息素濃度更新方式

大量文獻和實驗表明，螞蟻對信息素濃度的更新會對蟻群算法的運行時間、運行效率以及算法的準確性都會產生深遠的影響，即信息素濃度的不同更新方式對蟻群算法的計算效果影響是非常巨大的[13]。文獻[6]給出了一種特別湊效的方法，避開信息素揮發(fā)因子ρ的隨機性，對信息素的濃度進行動態(tài)的控制。即在算法開始的時候，用統(tǒng)一的方式對所有螞蟻進行信息素更新，當?shù)_到設定的次數(shù)之后執(zhí)行不同的更新策略在不同的螞蟻身上。對表現(xiàn)優(yōu)秀的螞蟻進行獎勵，給予正反饋的激勵加強它的信息素濃度。相反，對表現(xiàn)不好的螞蟻進行懲罰，適當?shù)臏p少其信息素的濃度，防止對后面螞蟻的路徑選擇產生誤導引起收斂過快只找到局部的最優(yōu)解。將前面提到的設定次數(shù)記為N,在前N 次的循環(huán)中增加和 減少最優(yōu)最差路徑的信息素按照（2）式進行計算。

除此之外，為了促使路徑朝著最優(yōu)化的方向前進，在每次循環(huán)中將本次迭代中最佳路徑上的信息素進一步加強，增強值具體依據(jù)公式（3）的表達式計算，使得蟻群算法的正反饋機制得到充分的利用。

結合以上兩種改進算法的優(yōu)勢，在基本蟻群算法中同時使用文獻[5]的啟發(fā)函數(shù)改進與文獻[6]的信息素濃度更新方式改進，于是就得到了雙因子改進蟻群算法。

2 雙因子改進蟻群算法與遺傳算法的混合

2.1 混合智能算法原理

結合遺傳算法的優(yōu)點，將上文中通過同時改進啟發(fā)函數(shù)和信息素濃度的更新方式形成的改進蟻群算法結合，構造出了一種新的智能優(yōu)化算法.為了充分利用這兩種算法的優(yōu)點，本文中的混合算法在算法的初期選擇遺傳算法，在后期選用蟻群算法，兩種算法在整個混合算法中的總體趨勢如圖1：

圖1 速度-時間曲線圖Fig.1 Speed-time curve

2.2 新智能算法步驟

通過圖1 可以發(fā)現(xiàn)，在機器人路徑規(guī)劃尋優(yōu)實驗中前半段使用 遺傳算法，而后半段使用文獻[5]和文獻[6]結合得到改進蟻群算法，可以使得混合算法的效率達到最大?；诖死碚摽傻玫絻煞N算法結合混合算法的步驟如下：

Step1：對遺傳算法的各個參數(shù)進行初始化；

Step2：尋找出初始的路徑，依據(jù)遺傳算法的理論隨機生成初始種群;

Step3：通過適應度函數(shù)對每一個體所占的比率逐個計算，根據(jù)比率值的大小找出當代中最優(yōu)個體；

Step4：選擇規(guī)劃路徑中的各值進行交叉變異，找到更好的下一代種群最優(yōu)路徑；

Step5：適應度值的計算，計算完之后與當前的最優(yōu)值對比，對當前最優(yōu)個體是否更新；

Step6：判斷遺傳算法停止的條件最大循環(huán)次數(shù)N是否出現(xiàn)，若是轉向步驟7執(zhí)行改進蟻群算法，否則轉步驟4；

Step7：放置所有螞蟻在初始點，運用遺傳算法得到最優(yōu)路徑長度lmax，把lmax作為改進蟻群算法的信息素部分初值；

Step8：所有螞蟻都從S 點出發(fā)，隨后將S 加入到禁忌表中；

Step9：依據(jù)公式（1）尋找下一個節(jié)點，將找到屬于可行節(jié)點集合的節(jié)點作為下一個可行節(jié)點，并且將其放入到禁忌表中；

Step10：對螞蟻當前的行走路徑做標記，判斷螞蟻是否已到終點，如果否，返回至Step9；若是螞蟻到達了終點，接對是否已走完全程進行判斷，若是全部走完則執(zhí)行Step11，否則返回到Step8 安排另外一只螞蟻重新出發(fā)；

Step11：等到全部螞蟻到達目標節(jié)點之后，求解出螞蟻行走過的路徑中的最優(yōu)和最差路徑，然后增加迭代次數(shù)并對信息素更新；

Step12：在迭代次數(shù)最大時輸出最短路徑，否則轉到Step8。

3 實證分析

雖然從理論上講混合的智能算法綜合了遺傳算法和改進蟻群算法的優(yōu)點，但是方法的優(yōu)劣最終需要在實際案例中驗證，使用得到的混合智能算法在規(guī)模為20×20 和30×30 的機器人規(guī)劃路徑問題上，實驗的具體操作是尋找路徑的開始階段要用到遺傳算法，因此需要對該算法的實驗參數(shù)進行設置，即初始化遺傳改進蟻群混合算法的各個參數(shù)，下面的表1 是具體的參數(shù)設置。

表1 遺傳改進蟻群混合算法的參數(shù)設置Tab.1 Parameter setting of genetically improved ant colony hybrid algorithm

設置完遺傳改進蟻群混合算法的參數(shù)之后，在規(guī)模為20×20 和30×30 柵格的環(huán)境地圖中應用混合遺傳改進蟻群算法進行實驗，設置相同的迭代次數(shù)，從尋找最短路徑所用的時間上尋找該方法的優(yōu)勢。兩種環(huán)境下機器人從起點到終點無碰撞的尋找最短路的實驗結果如圖2 和圖3所示。

圖2 20×20 柵格下混 合算法的收斂曲線Fig.2 Convergence curve of hybrid algorithm under grid

圖3 30×30 柵格下混合 算法的收斂曲線Fig.3 Convergence curve of hybrid algorithm under grid

由圖2 和圖3 可以看出，應用遺傳改進蟻群混合算法使機器人在20×20 柵格環(huán)境中尋找最優(yōu)路徑時，在第3 次迭代時算法就會收斂即可得到最短路徑；在30×30 柵格環(huán)境下，第5 次迭代時算法收斂就會得到最短路徑。這只時說明了此算法在求解機器人路徑規(guī)劃方面具有較快的速度，大大縮短了求解最優(yōu)解的時間。通過文獻[5]和文獻[6]可知改進的蟻群算法比基本的蟻群算法具有優(yōu)勢，所以要說明混合了遺傳算法的改進蟻群算法比其他方法優(yōu)秀，只需要與改進的蟻群算法在相同的實驗和環(huán)境下作如表2 的比較。

表2 改進蟻群算法與混合智能算法求解結果比較Tab.2 Comparison of the solution results of the improved ant colony algorithm and the hybrid intelligent algorithm

由表2 可以看出混合算法可以用較少的迭代次數(shù)求解出最短路徑，算法的復雜度較低，也更節(jié)省時間。

4 結束語

本文主要內容是闡述遺傳算法的原理以及如何得到改進的蟻群算法，并且將兩種智能算法結合起來形成一種解決機器人路徑規(guī)劃的問題的遺傳改進蟻群混合算法，其原理是在整體求解過程中先采用遺傳算法求解最短路，對于雙因子改進蟻群算法信息素的部分初值使用最短路的長度，這樣加強了改進蟻群算法的方向性，減少了搜索的盲目性。這對螞蟻盡快找到最優(yōu)路徑起到了促進作用。將這種混合的算法分別使用于20×20 柵格和30×30 柵格環(huán)境下對機器人規(guī)劃路徑問題進行了求解，得到結果顯示此方法的求解結果更令人滿意。