劉兆麗 朱運(yùn)海 劉成業(yè) 李向東

摘 要：本文在傳統(tǒng)蟻群算法的基礎(chǔ)上進(jìn)行了相應(yīng)的改善。通過改進(jìn)轉(zhuǎn)移概率、信息素更新策略以及利用多步長策略進(jìn)行二次路徑規(guī)劃。在轉(zhuǎn)移概率中增加權(quán)重系數(shù)，降低螞蟻陷入盲目搜索的可能，減少了螞蟻死鎖的數(shù)量;信息素更新原則，自適應(yīng)調(diào)整提高搜索能力，降低局部收斂性，提高全局收斂性和機(jī)器人尋找目標(biāo)點(diǎn)的工作效率;通過利用多步長策略進(jìn)行二次路徑規(guī)劃，求解路徑長度的最優(yōu)解不僅降低了機(jī)器人的能耗，也降低了機(jī)器人的勞損，節(jié)約成本。實(shí)驗(yàn)結(jié)果顯示，本文提出的算法全局搜索能力較高，收斂速度較快，能夠快速的找到最優(yōu)路徑，可以有效提高機(jī)器人工作的效率，驗(yàn)證了本文算法的適用性和有效性。

關(guān)鍵詞：蟻群算法;全局收斂;移動(dòng)機(jī)器人;信息素

引言

蟻群算法是由Dorigo.M等人提出的一種新型進(jìn)化的算法，在路徑規(guī)劃的問題上具有解決問題的明顯優(yōu)勢[1]。但是蟻群算法也存在易陷入局部最優(yōu)解和死鎖等問題，為此很多學(xué)者做出了大量改進(jìn)工作，比如動(dòng)態(tài)化搜索算子[2]，有效提高解的質(zhì)量和收斂速度;設(shè)定信息素閾值[3]，防止信息素過多或者過少而使算法收斂速度慢或者過早收斂;最大最小螞蟻系統(tǒng)[3]，只在每次迭代的最優(yōu)路徑上強(qiáng)化信息素濃度，減少其他路徑對螞蟻尋找路徑的影響。蟻群算法還可以與其他算法相嵌合，比如：文獻(xiàn)[5]將人工勢場產(chǎn)生的力與蟻群的信息素相結(jié)合，使信息素?cái)U(kuò)大到遠(yuǎn)離障礙區(qū)域的地方，提高了機(jī)器人搜索范圍和速度;文獻(xiàn)[6]將遺傳算法和蟻群算法相結(jié)合，把每一次迭代完成后所產(chǎn)生的路徑作為基礎(chǔ)，通過不斷選擇的交叉不同來獲得本次迭代的最佳路徑。本文做出的改進(jìn)具體有：1）改進(jìn)狀態(tài)轉(zhuǎn)移概率公式，減少螞蟻死鎖的數(shù)量，進(jìn)一步提高收斂速度;2）改進(jìn)信息素更新策略，自適應(yīng)調(diào)節(jié)信息素的揮發(fā)因子，克服螞蟻在尋優(yōu)過程中陷入局部收斂等問題;3）進(jìn)行二次路徑規(guī)劃，優(yōu)化路徑長度和轉(zhuǎn)彎次數(shù)降低能耗，提高移動(dòng)機(jī)器人適應(yīng)性和運(yùn)轉(zhuǎn)效率。

1 蟻群算法核心思想

1.1柵格地圖建模

柵格法是路徑規(guī)劃常用的模型，其中利用每個(gè)柵格的取值來表示障礙物和可移動(dòng)區(qū)域，空白部分用0表示，為自由柵格，即移動(dòng)機(jī)器人可以移動(dòng)的區(qū)域，陰影部分用1表示，為障礙物柵格，即移動(dòng)機(jī)器人不可移動(dòng)的區(qū)域[7]。本文選用柵格地圖建模，將柵格地圖的左下角視為坐標(biāo)原點(diǎn)，將柵格最下端的水平方向視為X軸，將柵格最左端的垂直方向視為Y軸，構(gòu)建出直角坐標(biāo)系，在本文中小于柵格面積1/2的視為自由柵格，大于柵格面積1/2的視為障礙物柵格。另外，本文假設(shè)每個(gè)柵格為邊長為1cm的正方形。如圖1所示。

2 改進(jìn)蟻群算法

2.1 狀態(tài)轉(zhuǎn)移概率公式的改進(jìn)

蟻群在路徑搜索初期無法避免的會(huì)產(chǎn)生大量交叉路徑，另外由于算法禁忌表的限制，螞蟻很容易陷入死鎖狀態(tài)，最終導(dǎo)致“迷失”，大量螞蟻停滯不前[8]。如圖2所示。

螞蟻k 從當(dāng)前位置i 移動(dòng)到下一個(gè)位置j 受到兩個(gè)指標(biāo)的影響：概率選擇和信息素的更新。本文在狀態(tài)轉(zhuǎn)移概率公式中引入加權(quán)因子T（T∈（0，1）） ，提高算法的收斂速度。改進(jìn)后的公式如下：

2.2信息素更新策略

2.3通過多步長策略進(jìn)行二次路徑規(guī)劃

目前國內(nèi)外學(xué)者針對移動(dòng)機(jī)器人步長選擇主要為單步長策略，這種單步長搜索方式會(huì)使移動(dòng)機(jī)器人搜索到的路徑過長，時(shí)間成本增加，本文算法選擇多步長策略，當(dāng)移動(dòng)機(jī)器人采用多步長二次路徑規(guī)劃策略時(shí)，先通過本文的改進(jìn)蟻群算法搜索出移動(dòng)機(jī)器人最優(yōu)單步長路徑，如圖3中的虛線所示，其中將虛線路徑作為二次路徑規(guī)劃的參考，依次把當(dāng)前節(jié)點(diǎn)與下一個(gè)節(jié)點(diǎn)相連，同時(shí)判斷移動(dòng)機(jī)器人是否與障礙物相撞，如果沒有碰撞，則繼續(xù)往下一個(gè)節(jié)點(diǎn)轉(zhuǎn)移，直至撞到障礙物，那么當(dāng)前節(jié)點(diǎn)與此節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)連心為最佳路徑，如圖3中實(shí)線所示，兩條路徑的對比結(jié)果很明顯，多步長選擇策略具有明顯的優(yōu)勢，縮短了移動(dòng)機(jī)器人的路徑長度、轉(zhuǎn)彎次數(shù)以及降低了時(shí)間成本。

3 算法仿真對比

在同一柵格地圖環(huán)境下，圖4所示為本文改進(jìn)算法的情況下移動(dòng)機(jī)器人的路徑規(guī)劃軌跡，可以看出移動(dòng)機(jī)器人的路徑長度更短，轉(zhuǎn)彎次數(shù)更少。圖5所示為文獻(xiàn)[4]的改進(jìn)蟻群算法的移動(dòng)機(jī)器人的軌跡，可以看出在同一柵格地圖模型下，出現(xiàn)了陷入局部收斂的情況，轉(zhuǎn)彎次數(shù)增多，從而增加了移動(dòng)機(jī)器人的能源消耗。圖6是傳統(tǒng)蟻群算法，很容易看出雖然移動(dòng)機(jī)器人可以到達(dá)終點(diǎn)，但是路徑長度明顯增長，轉(zhuǎn)彎次數(shù)明顯增多，這樣不僅增加了移動(dòng)機(jī)器人的能耗也增加了機(jī)器人的勞損，相比較而言成本較大，不適合現(xiàn)實(shí)場景的應(yīng)用和收益。圖7 是本文算法和文獻(xiàn)[4]的收斂曲線和最短路徑長度，通過本文算法的優(yōu)化，移動(dòng)機(jī)器人的收斂次數(shù)降到了13次就可達(dá)到穩(wěn)定，而文獻(xiàn)[4]的算法需要22次才能達(dá)到穩(wěn)定，實(shí)驗(yàn)結(jié)果顯示本文的算法具有較高的適用性和穩(wěn)定性。在柵格地圖中，文獻(xiàn)[4]的算法的結(jié)果顯示最短路徑的長度是41.796，而本文的算法的結(jié)果顯示最優(yōu)路徑的長度是36.382，提高了12.9%;文獻(xiàn)[4]的算法的迭代次數(shù)是22，而本文算法的迭代次數(shù)是13，減少了40%。本文算法根據(jù)解的分布情況，自適應(yīng)的進(jìn)行信息素濃度的更新，動(dòng)態(tài)強(qiáng)化最優(yōu)路徑上的信息素強(qiáng)度，并且利用多步長策略進(jìn)行二次規(guī)劃，因此在同一個(gè)柵格地圖環(huán)境下，相對于文獻(xiàn)[4]的算法，本文算法大大提高了收斂速度以及縮短了路徑長度，使本文算法收斂速度快并且達(dá)到全局性最優(yōu)，驗(yàn)證了本文算法的有效性和優(yōu)越性，兩種算法比較如表1所示。

4 結(jié)論

針對傳統(tǒng)蟻群算法在復(fù)雜路徑規(guī)劃中的種種不足，本文提出一種改進(jìn)的蟻群優(yōu)化算法。該算法利用起始位置點(diǎn)的信息，增加權(quán)重因子，從而改進(jìn)轉(zhuǎn)移概率公式，用小于1對解空間更全面的搜索，有效篩選死鎖的螞蟻，提高了螞蟻的搜索能力和速度;信息素的更新策略，提高了螞蟻全局性的指導(dǎo)搜索能力;利用多步長策略進(jìn)行二次路徑規(guī)劃，明顯減少了節(jié)點(diǎn)的數(shù)量，節(jié)省了算法運(yùn)行時(shí)間，有效的降低了移動(dòng)機(jī)器人的損耗和能耗，降低成本。實(shí)驗(yàn)結(jié)果表明，本文算法具有更高的穩(wěn)定性和收斂性。

參考文獻(xiàn)：

[1]DORIGO M，GAMBARDELLA L M.Ant colony system：A cooperative learning approach to the traveling salesman problem [J].IEEE Transactions on Evolutionary Computation，1997，1（1） ： 53-66.

[2]游曉明，劉升，呂金秋.一種動(dòng)態(tài)搜索策略的蟻群算法及其在機(jī)器人路徑規(guī)劃中的應(yīng)用[J].控制與決策，2017，32（03）：552-556.

[3]姚艷.一種最大最小螞蟻系統(tǒng)的改進(jìn)算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2014，44（15）：242-247.

[4]楊萍，趙珍，鄭海霞.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃方法研究[J].機(jī)械制造與自動(dòng)

[5]王曉燕，楊樂，張宇，等.基于改進(jìn)勢場蟻群算法的機(jī)器人路徑規(guī)劃[J].控制與決策，2018，33（10）：1775-1781.

[6]汪杰君，劉江寬，黃喜軍，等.基于混合遺傳蟻群算法的數(shù)字微流控芯片測試路徑規(guī)劃[J].電子測量與儀器學(xué)報(bào)，2017，31（08）：1183-1191.

[7]曲小康，芮小平，韓瑩，等.柵格成本距離計(jì)算的改進(jìn)蟻群算法[J].地球信息科學(xué)學(xué)報(bào)，2016，18（08）：1052-1059.

[8]夏小云，周育人.蟻群優(yōu)化算法的理論研究進(jìn)展[J].智能系統(tǒng)學(xué)報(bào)，2016，11（01）：27-36.

基金項(xiàng)目：山東省科學(xué)院院地產(chǎn)學(xué)研協(xié)同創(chuàng)新基金（2018XXY-19、2019-CXY12）

作者簡介：劉兆麗（1992），研究生：研究方向：物聯(lián)網(wǎng)工程

*通訊作者：朱運(yùn)海（1974），研究員;研究方向：機(jī)器人控制決策;

*通訊作者：劉成業(yè)（1979），助理研究員;研究方向：移動(dòng)機(jī)器人;

（齊魯工業(yè)大學(xué)（山東省科學(xué)院）自動(dòng)化研究所 ?濟(jì)南 ?250353）