[發(fā)明專利]基于改進的蟻群算法的路徑規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 201710454872.9
• 申請日: 2017-06-15
• 公開（公告）號: CN107272679B
• 公開（公告）日: 2020-06-16
• 發(fā)明（設計）人: 黃杰;萬棄寒;衛(wèi)錦;朱仟;曹山山;閔溪青;張云龍
• 申請（專利權(quán)）人: 東南大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 柏尚春

本發(fā)明公開了一種基于改進的蟻群算法的路徑規(guī)劃方法，相對于經(jīng)典蟻群算法，本方法具有以下改進之處：(1)將常數(shù)信息素揮發(fā)系數(shù)調(diào)整為自適應信息素揮發(fā)系數(shù)，隨著蟻群方法迭代次數(shù)的增加而自適應地改變系數(shù)大小；(2)在不同路徑長度相同的基礎上，采取拐點較少規(guī)則，擇優(yōu)選擇出局部最優(yōu)路徑；(3)對局部最優(yōu)路徑采取簡化路徑規(guī)則，對該路徑中所經(jīng)過的每一個節(jié)點與起始節(jié)點進行是否為鄰節(jié)點判斷，消除路徑上的冗余節(jié)點；(4)在對蟻群之前所走過的路徑進行信息素更新時，采取預先排序規(guī)則，只更新路徑長度排序前三分之一的路徑。通過以上改進之處，本發(fā)明能夠有效減少蟻群算法的算法收斂時間，提高運行效率。

技術領域

本發(fā)明涉及人工智能領域，具體涉及一種基于蟻群算法的路徑規(guī)劃方法。

背景技術

路徑規(guī)劃是當下研究的熱點之一，路徑指的是連接起點位置和終點位置的序列點或曲線，構(gòu)成路徑的策略稱之為路徑規(guī)劃。路徑規(guī)劃的目的，是使得移動主體(如智能小車、移動機器人、無人機等)能夠根據(jù)內(nèi)定的程序，按照一定的最優(yōu)解準則(如行駛路徑長度最短、行駛耗時最短等)，在存在著諸多障礙物的路況中自行避障，從而選擇出一條從起始點到終點的最優(yōu)路徑。

針對路徑規(guī)劃的研究主要聚焦于以下三個方面：第一，移動主體能否順利地從起始點到達終點；第二，移動主體能否在行駛過程中自動避開沿途的障礙物；第三，在完成上述兩個指標的基礎上，移動主體是否能按照一定的最優(yōu)解準則，選擇出最優(yōu)路徑。傳統(tǒng)的路徑規(guī)劃算法有模擬退火算法、人工勢場法、模糊邏輯算法、禁忌搜索算法等，但是傳統(tǒng)算法在解決實際問題時往往存在著建模難的問題，并且面對環(huán)境變化的應變性較差。

在處理復雜動態(tài)環(huán)境信息情況下的路徑規(guī)劃問題時，來自于自然界的啟示往往能起到很好的作用。智能仿生學算法就是人們通過仿生學研究發(fā)現(xiàn)的算法，常用到的有蟻群算法、神經(jīng)網(wǎng)絡算法、粒子群算法、遺傳算法等。其中，蟻群算法(Ant Colony Algorithm，ACA)由于其求解的快速性、較強的全局搜索能力以及較強的魯棒性在路徑規(guī)劃領域得到了廣泛的應用。蟻群算法的思想來自于對蟻群覓食行為的探索，每個螞蟻覓食時都會在走過的道路上留下一定濃度的信息素，當存在某條從起點到終點的較短路徑時，單位時間內(nèi)通過該路徑的螞蟻數(shù)量也會較多，從而在該路徑上留有更多的信息素，吸引更多的螞蟻選擇該路徑，這就形成了一種正反饋效應，因此信息素濃度高的最短路徑很快就會被發(fā)現(xiàn)。算法通過迭代來模擬蟻群覓食的行為達到目的，具有良好的全局優(yōu)化能力、本質(zhì)上的并行性、易于用計算機實現(xiàn)等優(yōu)點。但是在經(jīng)典蟻群算法中，信息素揮發(fā)系數(shù)是一個常數(shù)，新搜索到的較優(yōu)路徑與上一輪所搜索到的路徑遵循相同的信息素揮發(fā)準則，而該準則不能夠最大化地促進蟻群算法的正反饋效應，導致經(jīng)典蟻群算法收斂速度過慢，并且會伴隨著出現(xiàn)一些非穩(wěn)定最優(yōu)解。所以，如何進一步縮短蟻群算法的算法收斂時間與剔除一些非穩(wěn)定最優(yōu)解，成為蟻群算法急需改進的部分。

發(fā)明內(nèi)容

發(fā)明目的：基于以上不足，本發(fā)明提出一種基于改進的蟻群算法的路徑規(guī)劃方法，引入自適應信息素揮發(fā)系數(shù)思想以及在此基礎上的路徑?jīng)Q策規(guī)則，從而能夠縮短算法收斂時間并剔除一些非穩(wěn)定最優(yōu)解。

技術方案：一種基于改進的蟻群算法的路徑規(guī)劃方法，包括以下步驟：

(1)利用柵格法對地圖環(huán)境進行建模，包括設置起始節(jié)點、目標節(jié)點、障礙物柵格；

(2)初始化蟻群算法基本參數(shù)，并使蟻群初始化在起始節(jié)點處；

(3)每只螞蟻從起始節(jié)點開始搜索遍歷，根據(jù)轉(zhuǎn)移概率選擇下一節(jié)點，螞蟻走過的每個節(jié)點記錄在禁忌表中，當螞蟻到達目標節(jié)點時，計算螞蟻所選路徑長度和路徑上的拐點個數(shù)；

(4)當所有螞蟻完成搜索后，應用拐點較少原則選取當次迭代的最優(yōu)路徑；

(5)對當次迭代的最優(yōu)路徑應用簡化路徑原則，得到優(yōu)化后的當次迭代最優(yōu)路徑；