基于優(yōu)化蟻群算法的智能機(jī)器人路徑規(guī)劃研究

樊嘯宇

摘 要：由于利用蟻群算法實(shí)現(xiàn)人工智能機(jī)器人路徑規(guī)劃領(lǐng)域中的算法自身缺陷問(wèn)題，本文提出一種用于人工智能機(jī)器人路徑規(guī)劃的改進(jìn)式蟻群算法。在人工智能機(jī)器人路徑規(guī)劃方面，采用基于柵格的技術(shù)實(shí)現(xiàn)路徑量化工作；在獲取全局路徑最優(yōu)解方面，基于排序的精英螞蟻策略，提高全局最優(yōu)解的搜索能力并提高算法的收斂速度。通過(guò)驗(yàn)證，基于人工智能的思想，在蟻群算法改良環(huán)節(jié)中成功引入了集成式算法創(chuàng)新模式，不僅實(shí)現(xiàn)了機(jī)器人路徑規(guī)劃自主選擇性，而且提高路徑尋優(yōu)準(zhǔn)確性和快速響應(yīng)性。

關(guān)鍵詞：人工智能；路徑規(guī)劃；蟻群算法；柵格；精英螞蟻策略

中圖分類號(hào)：TP242 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1671-2064（2018）20-0034-03

1 引言

在人工智能的研究領(lǐng)域中，路徑規(guī)劃是至關(guān)重要的一項(xiàng)研究分支?；诖?，智能機(jī)器人的路徑規(guī)劃是指在給定的環(huán)境模型中，尋找一條從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)無(wú)碰撞路徑的人工智能式自主擇優(yōu)過(guò)程。

其中蟻群算法是一種經(jīng)典的啟發(fā)式優(yōu)化算法[1]，模擬了螞蟻覓食的行為，通過(guò)釋放信息素標(biāo)記路徑，之后經(jīng)過(guò)的螞蟻會(huì)根據(jù)遺留的信息素濃度選擇較優(yōu)的路徑，經(jīng)過(guò)一定次數(shù)的迭代后，能得到全局最優(yōu)路徑。蟻群算法雖然具有較強(qiáng)的魯棒性、并行性和正反饋機(jī)制，具有很強(qiáng)的發(fā)現(xiàn)較好路徑解的能力，但是也存在一些明顯的缺陷：（1）每次迭代搜索后僅保留本次最優(yōu)解，對(duì)歷史信息利用率較低，導(dǎo)致算法的收斂速度相對(duì)較低；（2）易陷入局部最優(yōu)解而使算法迭代停滯，不利于更好解的發(fā)現(xiàn)。針對(duì)蟻群算法的以上缺陷，目前大致有兩種改進(jìn)方案：一種是在經(jīng)典蟻群算法的基礎(chǔ)上進(jìn)行改進(jìn)[2]，另一種是將蟻群算法與其他智能算法結(jié)合，如遺傳算法[3]、免疫算法[4]等。

為了提高蟻群算法的路徑量化分析和獲取全局最優(yōu)解的能力，本文在路徑規(guī)劃構(gòu)建方面，采用了基于柵格的思想；在獲取全局最優(yōu)解方面，采用了基于排序的精英螞蟻策略?；谝陨先斯ぶ悄艿乃惴蓜?chuàng)新，實(shí)現(xiàn)人工智能機(jī)器人路徑規(guī)劃獲取全局最優(yōu)解的過(guò)程。

2 基于柵格思想規(guī)劃路徑的蟻群算法構(gòu)建

2.1 構(gòu)建用于路徑規(guī)劃的蟻群算法

在螞蟻k（k=1，2，…，m）的運(yùn)動(dòng)過(guò)程中，各條路徑上的信息素濃度決定其移動(dòng)方向。表示在t時(shí)刻螞蟻k由柵格i（xi，yi）轉(zhuǎn)移到柵格j（xj，yj）的狀態(tài)轉(zhuǎn)移概率，由各條路徑上殘留的信息素濃度及路徑的啟發(fā)信息計(jì)算，螞蟻在選擇路徑時(shí)會(huì)盡量選擇離自己距離較近且信息素濃度較大的方向。狀態(tài)轉(zhuǎn)移公式為：

（2-1）

其中表示螞蟻k下一步可以選擇的節(jié)點(diǎn)，C為全部節(jié)點(diǎn)集合；

（k=1，2，…，m）表示禁忌表，記錄螞蟻k當(dāng)前已走過(guò)的城市；

α表示信息啟發(fā)因子，反映了信息素濃度的相對(duì)重要程度；

β表示期望啟發(fā)因子，反映了期望值的相對(duì)重要程度；

表示邊（i，j）上的信息素濃度；

表示邊（i，j）上的啟發(fā)信息，一般取柵格i到柵格j距離dij的倒數(shù)，即。

為了防止殘留信息素濃度過(guò)大導(dǎo)致啟發(fā)信息的作用不明顯，在螞蟻完成一次迭代后，對(duì)信息素濃度進(jìn)行更新處理。信息素更新規(guī)則為：

， （2-2）

（2-3）

其中ρ表示信息素?fù)]發(fā)系數(shù)，則表示信息素殘留系數(shù)；

表示邊（i，j）上的信息素增量；

表示螞蟻k在邊（i，j）上的信息素增量。

2.2 信息素增量的計(jì)算

根據(jù)信息素增量的不同，M.Dorigo提出三種蟻群算法模型[5-6]：蟻周模型、蟻量模型、蟻密模型。蟻周模型的原理是利用螞蟻經(jīng)過(guò)路徑的總長(zhǎng)度（整體信息）計(jì)算信息素增量；蟻量模型的原理是利用螞蟻經(jīng)過(guò)的節(jié)點(diǎn)間的距離（局部信息）計(jì)算信息素增量；蟻密模型的原理是將信息素增量取為恒值，沒有考慮不同螞蟻經(jīng)過(guò)路徑的長(zhǎng)短。

鑒于信息素增量計(jì)算的普遍適用性和非特定條件約束的前提下，蟻周模型的性能優(yōu)于其他兩種模型[7]，因此本文采用蟻周模型：

（2-4）

其中Q為常量，表示螞蟻在一次迭代中釋放的信息素總量。

Lk表示第k只螞蟻在本次迭代中經(jīng)過(guò)路徑的總長(zhǎng)度。

3 基于排序的精英螞蟻策略改進(jìn)的蟻群算法設(shè)計(jì)

由于蟻群算法存在收斂速度慢和容易出現(xiàn)停滯現(xiàn)象等缺陷，本文將采用基于排序的精英螞蟻策略并對(duì)之優(yōu)化，修正蟻群算法的上述缺陷，進(jìn)而優(yōu)化蟻群算法獲取全局最優(yōu)解的過(guò)程。

基于排序的精英螞蟻策略改進(jìn)蟻群算法的具體思路：通過(guò)信息素更新，實(shí)現(xiàn)螞蟻的解的多種可能性，為最大—最小螞蟻策略突破蟻群算法過(guò)早收斂于局部最優(yōu)解的局面做鋪墊；同時(shí)，引入自適應(yīng)特性的信息素?fù)]發(fā)系數(shù)更新機(jī)制，完善全局解的搜索能力并提高算法自身的收斂速度。

3.1 信息素更新設(shè)計(jì)

傳統(tǒng)的精英蟻群系統(tǒng)[8]為了使當(dāng)前找到的最優(yōu)解在下一次迭代中對(duì)螞蟻更有吸引力，在每次迭代結(jié)束后給予所有已經(jīng)找到的最優(yōu)解額外的信息素增量。這些獲得額外信息素增量的路徑視為被精英螞蟻?zhàn)哌^(guò)，這些路徑上的某些邊可能屬于全局最優(yōu)解。

然而精英螞蟻對(duì)應(yīng)的路徑上的額外信息素增量，使得某一條路徑上的信息素濃度急劇增加，降低了后續(xù)螞蟻選擇其他最優(yōu)解的概率，影響了后續(xù)螞蟻的解的多樣性，容易造成算法的早熟，使得算法收斂于某一局部最優(yōu)解。因此，本文在精英螞蟻策略中加入排序策略[9]，將不同的路徑根據(jù)信息素濃度進(jìn)行排序，分別給予不同程度的信息素增量（賦予精英螞蟻的優(yōu)秀程度越高，給予的信息素增量越大），同時(shí)對(duì)于每一次迭代中的最優(yōu)解給予一定的額外信息素增量。這樣提高了后續(xù)螞蟻的解的多樣性，解決了因收斂過(guò)快而停滯于局部最優(yōu)解的問(wèn)題。

具體方法如下：每次迭代完成后，螞蟻按路徑長(zhǎng)度排序，即L1≤L2≤……≤L3，根據(jù)螞蟻的排名μ對(duì)信息素增量進(jìn)行加權(quán)。設(shè)ω為當(dāng)前最優(yōu)路徑上信息素的權(quán)重，ω必然大于等于其它權(quán)重。第μ個(gè)最優(yōu)路徑的權(quán)重為max{0，ω-μ}。同時(shí)，給予當(dāng)前最優(yōu)路徑額外的信息素增量?；谂判虻木⑽浵伈呗韵碌男畔⑺馗略O(shè)計(jì)則為：

， （3-1）

其中表示只螞蟻在邊（i，j）上根據(jù)排名的信息素增量：

（3-2）

（3-3）

（3-4）

其中μ為最優(yōu)螞蟻排名，為第μ只最優(yōu)螞蟻在邊（i，j）上的信息素增量，為第μ只最優(yōu)螞蟻的路徑總長(zhǎng)度，為精英螞蟻在邊（i，j）上的信息素增量，為當(dāng)前最優(yōu)路徑的總長(zhǎng)度。

3.2 最大—最小螞蟻策略

在基于排序的精英螞蟻策略的基礎(chǔ)上，為了進(jìn)一步避免算法過(guò)早收斂于局部最優(yōu)解，可以引入最大—最小螞蟻策略[10]，即在每次迭代后將各條路徑可能的信息素濃度限制在區(qū)間內(nèi)，超出這個(gè)范圍的值被強(qiáng)制設(shè)為或者是。這樣可以有效地避免某條路徑上的信息素濃度遠(yuǎn)大于其余路徑，使得所有的螞蟻都集中到同一條路徑上，從而使算法不再擴(kuò)散。

在此基礎(chǔ)上增加信息素濃度平滑機(jī)制可以提高性能，即當(dāng)信息素濃度收斂或接近收斂于最大值時(shí)，通過(guò)增加選擇低強(qiáng)度信息素濃度路徑的概率以提高發(fā)現(xiàn)新解的能力。

， （3-5）

其中和分別為平滑化之前和之后的信息素濃度。

3.3 信息素?fù)]發(fā)系數(shù)自適應(yīng)

在基于排序的精英螞蟻策略的基礎(chǔ)上，信息素?fù)]發(fā)系數(shù)ρ直接影響算法的全局搜索能力及收斂速度[11]。為了既使算法擁有較強(qiáng)的全局搜索能力，又避免其出現(xiàn)停滯狀態(tài)，引入信息素?fù)]發(fā)系數(shù)自適應(yīng)策略：

， （3-6）

其中為ρ的最小值，γ為揮發(fā)系數(shù)衰減常數(shù)，取0.95。

算法運(yùn)行初期ρ較大，信息的正反饋?zhàn)饔谜贾鲗?dǎo)，從未搜索過(guò)的路徑上的信息素濃度趨近于0，再次選擇已搜索過(guò)的路徑的可能性較大，收斂速度比較快，易出現(xiàn)局部收斂。后期ρ逐漸減小，信息的正反饋?zhàn)饔弥饾u減弱，從未搜索過(guò)的路徑信息素濃度增大，搜索的隨機(jī)性能增強(qiáng)，全局搜索能力提高，但會(huì)降低蟻群算法收斂速度，所以設(shè)置一個(gè)最小值，防止ρ過(guò)小而使算法停滯。

信息素?fù)]發(fā)系數(shù)自適應(yīng)更新規(guī)則為：

（3-7）

4 技術(shù)路線流程設(shè)計(jì)（圖1）

步驟1：構(gòu)建柵格模型，初始化改進(jìn)蟻群算法中的原始參數(shù)，設(shè)置螞蟻數(shù)量m、信息啟發(fā)因子α、期望啟發(fā)因子β、信息素?fù)]發(fā)系數(shù)ρ、信息素總量Q、最大迭代次數(shù)NCmax。初始化禁忌表，迭代次數(shù)NC=1。

步驟2：螞蟻k（k=1，2，…，m）開始遍歷。更新螞蟻k當(dāng)前位置的禁忌表，根據(jù)狀態(tài)轉(zhuǎn)移公式（2-1）計(jì)算每個(gè)可行柵格的轉(zhuǎn)移概率，使用輪盤賭的方法選擇下一個(gè)柵格。

步驟3：一次迭代完成后，螞蟻按路徑長(zhǎng)度排序，根據(jù)排名μ對(duì)信息素增量進(jìn)行加權(quán)，同時(shí)根據(jù)信息素?fù)]發(fā)系數(shù)自適應(yīng)策略更新信息素?fù)]發(fā)系數(shù)ρ，共同作用對(duì)信息素濃度進(jìn)行更新。

步驟4：使用最大—最小螞蟻策略，進(jìn)一步更新信息素濃度。

步驟5：令迭代次數(shù)。若，則清空禁忌表，跳轉(zhuǎn)至步驟2，直到為止；否則輸出全局最優(yōu)解。

5 仿真和說(shuō)明

本文以實(shí)際真實(shí)路徑作為參考，分別采用常規(guī)的蟻群算法和改進(jìn)的蟻群算法在逼近真實(shí)路徑方面進(jìn)行對(duì)比。具體仿真參數(shù)設(shè)定如表1所示。

通過(guò)上述參數(shù)數(shù)值設(shè)定，常規(guī)的蟻群算法和改進(jìn)的蟻群算法分別對(duì)路徑進(jìn)行規(guī)劃，其路徑規(guī)劃效果對(duì)比如圖2所示。

從圖2可知，縱坐標(biāo)代表與理想真實(shí)路徑的吻合度，橫坐標(biāo)表示路徑規(guī)劃的耗時(shí)。由于改進(jìn)的蟻群算法較正常的蟻群算法復(fù)雜，故路徑規(guī)劃前期效果較差；但是，隨著路徑規(guī)劃過(guò)程不斷迭代，最終采用改進(jìn)的蟻群算法路徑規(guī)劃吻合度高達(dá)98.7%，高于采用蟻群算法的路徑規(guī)劃吻合度89.4%；同時(shí)，在路徑規(guī)劃效果達(dá)到穩(wěn)定狀態(tài)的過(guò)程中，改進(jìn)的蟻群算法耗時(shí)257.4ms小于蟻群算法耗時(shí)329.2ms。

仿真結(jié)果表明：在路徑規(guī)劃吻合度方面，改進(jìn)的蟻群算法搜索全局最優(yōu)解的能力得到提升；在節(jié)約時(shí)間成本方面，改進(jìn)的蟻群算法收斂速度更快。

6 結(jié)語(yǔ)

本文針對(duì)人工智能路徑規(guī)劃領(lǐng)域的蟻群算法進(jìn)行改進(jìn)，設(shè)計(jì)基于排序的精英螞蟻策略改進(jìn)的蟻群算法模型，采用排序策略、信息素?fù)]發(fā)系數(shù)自適應(yīng)策略和最大—最小螞蟻策略改進(jìn)信息素更新規(guī)則，以完善對(duì)全局最優(yōu)解的搜索能力并提高算法的收斂速度。通過(guò)仿真，證明本設(shè)計(jì)具有理論優(yōu)勢(shì)和實(shí)際應(yīng)用價(jià)值，并為后續(xù)的人工智能機(jī)器人路徑規(guī)劃研究提供了參考方案。

參考文獻(xiàn)

[1]Colorni A， Dorigo M， Maniezzo V. Distributed Optimization by Ant Colonies[C]// Ecal91-European Conference on Artificial Life. 1991：134-142.

[2]喻環(huán).改進(jìn)蟻群算法在機(jī)器人路徑規(guī)劃上的應(yīng)用研究[D].安徽大學(xué)，2017.

[3]趙凱，李聲晉，孫娟，趙鋒.改進(jìn)蟻群算法在移動(dòng)機(jī)器人路徑規(guī)劃中的研究[J].微型機(jī)與應(yīng)用，2013，32（04）：67-70.

[4]邱莉莉.基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃[D].東華大學(xué)，2015.

[5]Gambardella M，Dorigo M. Solving symmetricand asymmetric TSPs by ant colonies[C]//Proc of the IEEE Conf on Evol Compu， 1996：622-627.

[6]Dorigo M， Maniezzo V， Colorni A. Ant system： optimization by a colony of cooperating agents[J]. IEEE Transaction on System， Man and Cybernetics： Part B， 1996， 26（1）： 29-41.

[7]胡小兵.蟻群優(yōu)化原理、理論及其應(yīng)用研究[D].重慶大學(xué)，2004.

[8]B.Bullnheimer， R.F.Hart， C.Strauss. Applying the ant System to the Vehicle Routing Problem. Meta-Heuristics： Advances and Trends in Local Search Paradigms for Optimization. Kluwer， Boston， 1998：109-120.

[9]任瑞春.基于排序加權(quán)的蟻群算法[D].大連海事大學(xué)，2006.

[10]王鴻豪.基于蟻群算法的機(jī)器人路徑規(guī)劃及其在港口上的應(yīng)用探討[D].武漢理工大學(xué)，2007.

[11]申鉉京，劉陽(yáng)陽(yáng)，黃永平，徐鐵，何習(xí)文.求解TSP問(wèn)題的快速蟻群算法[J].吉林大學(xué)學(xué)報(bào)（工學(xué)版），2013，43（01）：147-151.