基于迭代局部搜索的路徑規(guī)劃蟻群算法

許健 許峰

摘要：針對蟻群算法易早熟及局部搜索能力欠佳的缺陷，將迭代局部搜索策略引入蟻群算法。新算法的基本思想是：從初始解出發(fā)，用蟻群算法進行局部搜索，如陷入局部最優(yōu)，則產(chǎn)生一個攝動解作為新的初始解再進行局部搜索，根據(jù)接受規(guī)則決定進入下一步迭代的局部最優(yōu)解。將改進算法應用于二維路徑規(guī)劃，數(shù)值實驗表明，改進算法相比基本蟻群算法有更佳的局部收斂性，可獲得比基本蟻群算法結果更優(yōu)路徑。

關鍵詞：蟻群算法；迭代局部搜索；局部收斂性；路徑規(guī)劃

DOIDOI：10.11907/rjdk.173181

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2018）008-0031-04

英文摘要Abstract：Ant colony algorithm is easy to premature and the ability of local search is poor.The iterative local search strategy is introduced into ant colony algorithm.The basic idea of the new algorithm is that the new algorithm starts from the initial solution and use ant colony algorithm for local search.A perturbation solution is generated as a new initial solution，and then the local search is carried out if it falls into the local optimum，and the local optimal solution of the next iteration is determined according to the acceptance rule.The improved algorithm is applied to two-dimensional path planning，and the numerical experiments show that the improved algorithm has better local convergence than the basic ant colony algorithm，and it can obtain better path than that of the basic ant colony algorithm.

英文關鍵詞Key Words：ant colony algorithm； iterative local search； local convergence； path planning

0 引言

路徑規(guī)劃是指在有障礙物的環(huán)境中尋找一條從起點到終點無碰撞地繞過所有障礙物的運動路徑。路徑規(guī)劃算法眾多，基本可分為局部路徑規(guī)劃和全局路徑規(guī)劃兩類。其中，局部路徑規(guī)劃算法主要有人工勢場法；全局路徑規(guī)劃算法包括柵格劃歸法、頂點圖像法、廣義錐方法和位形空間法?？紤]到路徑規(guī)劃往往是包含復雜約束的大規(guī)模優(yōu)化問題，因此啟發(fā)式智能優(yōu)化算法目前已成為求解路徑規(guī)劃問題的主流方法，如蟻群算法、粒子群算法、模擬退火算法、遺傳算法等。早在1998年，Patcher[1]就討論了路徑規(guī)劃問題中的關鍵優(yōu)化技術及其復雜性；Dong[2]、Zheng[3]和Nikolos等[4]系統(tǒng)研究了路徑規(guī)劃中進化算法的優(yōu)化原理。

蟻群算法 （Ant Colony Optimization，ACO）是由意大利學者M Dorigo[5]于1992年首先提出的一種新型智能進化算法，其基本思想是通過模擬蟻群在搜索食物過程中的尋優(yōu)能力解決優(yōu)化問題。蟻群算法具有正反饋、自組織、分布式等突出優(yōu)點，缺陷是收斂速度較慢，易陷于局部最優(yōu)解。

迭代局部搜索（Iterated Local Search，ILS）最早由Lourenco等[6]于2002年提出，是一種簡單而有效的元啟發(fā)式算法，主要通過攝動的方法改善算法局部搜索能力。迭代局部搜索一經(jīng)提出，立即被用于求解TSP問題[7]和調(diào)度問題[8]，并取得了良好的效果。目前，對迭代局部搜索的應用研究已取得了一系列成果。張志強[9]較早將迭代局部搜索策略應用于蟻群算法；王海斌[10]在粒子群優(yōu)化算法中引入了迭代局部搜索；高超等[11-14]系統(tǒng)地研究了迭代局部搜索，并將其應用于車輛路徑規(guī)劃問題。

本文提出一種基于圖論和迭代局部搜索的二維路徑規(guī)劃蟻群算法（ILS-ACO），并根據(jù)數(shù)值實驗對該算法進行性能測試。

1 二維路徑規(guī)劃問題的空間模型與dijkstra算法

1.1 MAKLINK圖

本文通過構建MAKLINK圖的方法建立二維路徑規(guī)劃空間模型[15]。MAKLINK圖是指兩個障礙物之間不與障礙物相交頂點之間的連線，以及障礙物頂點與邊界相交的連線，主要作用是生成二維路徑規(guī)劃的初始可行空間。圖1即為本文實例中的MAKLINK圖。

若MAKLINK圖中連線的中點依次為v1，v2，…，vl，連接這些中點及起點S與終點T，則構成了二維路徑規(guī)劃的初始可行空間。

1.2 Dijkstra算法

由于二維路徑規(guī)劃初始可行空間中路徑眾多，為了提高路徑搜索效率，采用Dijkstra算法規(guī)劃一條從起點S到終點T的初始路徑。Dijkstra算法是圖論中典型的單源最短路徑算法，用于計算某節(jié)點到其它所有節(jié)點的最短路徑，其基本思路是將節(jié)點分成兩組，第1組包括已確定最短路徑的節(jié)點，第2組為未確定最短路徑的節(jié)點。按遞增次序?qū)⒌?組中的節(jié)點逐個加入第1組，直到從源點出發(fā)可到達的所有節(jié)點都被包含在第1組中。

Dijkstra算法流程如下：

（1）初始化存儲未確定最短路徑的節(jié)點集合V與已確定最短路徑的節(jié)點集合S，并利用鄰接矩陣初始化最短路徑長度D。

（2）在D中選擇最小值D[i]，D[i]為源點到點i的最短路徑長度，將點i從集合V中取出并放入集合S中。

（3）根據(jù)節(jié)點i修改更新D中源點到集合V中節(jié)點對應的路徑長度值。

（4）重復步驟（2）和步驟（3），直到找出源點到所有節(jié)點的最短路徑為止。

2 蟻群算法與迭代局部搜索

2.1 基本蟻群算法

螞蟻之所以能找到從巢穴到食物的最短路徑，并且能適應性地搜索新的路徑，根本原因是螞蟻能在其走過的路上釋放信息素。路徑上通過的螞蟻越來越多時，其留下的信息素也越來越多，后來的螞蟻選擇該路徑的概率也越大，從而形成一種正反饋機制。通過這種正反饋機制，螞蟻最終可以發(fā)現(xiàn)最短路徑。蟻群算法的核心步驟為信息素軌跡強度的更新和螞蟻轉移概率的確定。本文采用下列螞蟻圈模型[5，16]：

2.2 迭代局部搜索

蟻群算法與其它智能優(yōu)化方法一樣，不可避免地存在一些缺陷，如初始信息素生成速度較慢及局部搜索能力較差、易早熟等。

為了提高啟發(fā)式算法的局部搜索能力，Lourenco[6] 2002年提出了迭代局部搜索的策略，其基本思想是：從一個初始解s出發(fā)，應用局部搜索方法，一旦局部搜索陷入停滯狀態(tài)，局部最優(yōu)解s^產(chǎn)生攝動，移動到不同于局部搜索使用解的領域中。攝動產(chǎn)生的解s′是局部搜索的新起始解，它將產(chǎn)生新的局部最優(yōu)s′^。最后，一個接受規(guī)則負責決定選擇兩個局部最優(yōu)解中的哪一個進入下一階段的攝動過程。

迭代局部搜索流程如下：

（1）輸入?yún)?shù)，生成最初解s。

（2）應用局部搜索，生成局部最優(yōu)解s^，它是當前最優(yōu)解sbest。

（3）通過對當前解s^的攝動，生成一個中間解s*。

（4）對中間解s*進行局部搜索，再生成局部最優(yōu)解s^*。

（5）判斷新的局部最優(yōu)解s^*是否比當前最優(yōu)解sbest更符合接受規(guī)則。若否，輸出最優(yōu)解sbest，程序結束；若是，判斷局部最優(yōu)解s^和s^*中的哪一個進入下一階段的攝動過程，轉入流程（3）。

2.3 基于迭代局部搜索的蟻群算法

一系列研究表明[9，16-18]，將蟻群算法與其它優(yōu)化策略相融合，可以取長補短，提高優(yōu)化效果。本文將迭代局部搜索引入蟻群算法，提出了一種改進的路徑規(guī)劃蟻群算法，流程如下：

（1）給定蟻群算法參數(shù)。

（2）用dijkstra算法產(chǎn)生一個初始較優(yōu)解。

（3）利用式（1）更新信息素，并轉流程（5），否則轉流程（4）。

（4）根據(jù)式（2）選擇下一節(jié)點。

（5）根據(jù)梯度閾值原則[16]判定當前解是否陷入局部收斂，若是則轉流程（6），否則轉流程（7）。

（6）對蟻群算法搜索到的局部最優(yōu)解進行迭代局部搜索，得到攝動后的最優(yōu)解。

（7）若算法的整體迭代次數(shù)達到最大迭代次數(shù)，則輸出最優(yōu)解，算法結束，否則轉流程（3）。

3 數(shù)值實驗結果

3.1 問題描述

在200×200的二維空間區(qū)域內(nèi)尋找一條從起點S到終點T的最優(yōu)路徑，該二維空間區(qū)域內(nèi)有4個障礙物。障礙物1的4個頂點分別為（40，140； 60，160； 100，140； 60，120）；障礙物2的4個頂點分別為（50，30； 30，40； 80，80； 100，40）；障礙物3的4個頂點分別為（120，160； 140，100； 180，170； 165，180）；障礙物4的3個頂點分別為（120，40； 170，40； 140，80）。起點S的坐標為（20，180），終點T的坐標為（160，90）。二維規(guī)劃空間如圖2所示。

3.2 規(guī)劃結果

在蟻群算法中，取定的初始參數(shù)如下：信息素計算參數(shù)為2，信息素選擇閾值為0.7，信息素更新參數(shù)為0.1和0000 3；啟發(fā)信息參數(shù)為0.5和1.1，種群數(shù)量為10，進化代數(shù)為200；判定是否陷入局部最優(yōu)的閾值ε=0.01。圖3給出了最終的最優(yōu)規(guī)劃路徑，圖4、圖5分別給出了ACO和ILS-ACO的典型進化曲線。

對比ACO和ILS-ACO的典型進化曲線可直觀地看出，ILS-ACO比ACO有更好的局部收斂性。

為了更進一步定量比較ACO和ILS-ACO的全局收斂性及局部收斂性，表1中給出了ACO和ILS-ACO兩種算法的最優(yōu)值、平均值、標準差、20次仿真中求得最優(yōu)值（達到理論最優(yōu)解的95%即視為最優(yōu)值）的頻率及平均最小進化代數(shù)?？紤]到計算結果的隨機性，表1中20次實驗結果的平均值更有意義。本文研究的路徑規(guī)劃問題理論最優(yōu)解為191.5。

從表1中可見，ILS-ACO在解的質(zhì)量、穩(wěn)定性和收斂速度方面均優(yōu)于ACO。

綜上，有理由相信，在二維路徑規(guī)劃中若采用ILS-ACO，將獲得比基本ACO更優(yōu)的路徑規(guī)劃。

4 結語

通過分析基本蟻群算法和迭代局部搜索算法，設計了一種用于二維路徑規(guī)劃的新的混合蟻群遺傳算法。新算法實現(xiàn)了蟻群算法與迭代局部搜索的優(yōu)勢互補，改善了蟻群算法的局部收斂性。數(shù)值實驗結果顯示，該算法可在很大程度上克服基本蟻群算法的早熟現(xiàn)象，可較好地解決二維路徑規(guī)劃問題。

蟻群算法的收斂性較為復雜，尚未完全解決。目前可以證明的結論是：基于螞蟻圈模型的蟻群算法與其它優(yōu)化算法的混合算法是收斂的。因此，本文提出的算法在理論上是收斂的。最后需要指出，蟻群算法與粒子群算法、人工免疫系統(tǒng)、分布估計算法、協(xié)同進化算法等均為近年來出現(xiàn)的新型進化范例，理論體系尚不完善，收斂性等關鍵理論問題有待進一步研究。

參考文獻：

[1] PATCHER M，CHANDLER P R.Challenges of autonomous control [J].IEEE Control Systems Magazine，1998，18（4）：93-97.

[2] DONG J，VAGNERS J.Parallel evolutionary algorithms for UAV path planning [C].Chicago：AIAA 1st Intelligent Systems Technical Conference，2004.

[3] ZHANG C，LI L，XU F.Evolutionary route planning for unmanned air vehicles [J].IEEE Transactions on Robotics，2005，21：609-620.

[4] NILOLOS I，VALAVANIS K.Evolutionary algorithm based offline/online path planning for UAV navigation.[J].IEEE Transaction on Systems，Man and Cybernetics-Part B，2003，33：898-912.

[5] DORIGO M，THOMAS S.Ant colony optimization[M].Massachusetts ：MIT Press，2006.

[6] LOURENCO H R， MARTIN O， STUTZLE T. Iterated local search [J].International Series in Operations Research and Management Science，2002，57：321-353.

[7] CONGRAM R K，POTTS C N.An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling program [J].INFORMS Journal on Computing，2002，14（1）：52-67.

[8] APPLEGATE D，COOK W，ROHE A.Chained Lin-Kernighan for large traveling salesman problems [J].INFORMS Journal on Computing，2003，15（1）：82-92.

[9] 張志強，張璟，張翔.基于蟻群優(yōu)化的混合智能算法研究 [J].西安理工大學學報，2009，25（3）：314-317.

[10] 王海斌，劉維亭，徐卉.基于迭代局部搜索和自適應粒子群優(yōu)化的SVM短期負荷預測 [J].船舶工程，2013，35（1）：57- 60.

[11] 高超.隨機局部搜索算法及其應用研究 [D].合肥：中國科學技術大學，2015.

[12] 溫真真.需求可拆分車輛路徑問題的迭代局部搜索算法研究 [D].北京：北京交通大學，2015.

[13] 劉萬峰.求解車輛路徑問題的啟發(fā)式算法及其在注塑排程問題中的應用 [D].深圳：深圳大學，2015.

[14] 趙軒.求解RCPSP問題的迭代局部搜索算法研究 [D].北京：北京交通大學，2016.

[15] 史峰，王輝.Matlab智能算法30個案例分析 [M].北京：北京航空航天大學出版社，2011.

[16] 劉雪東，許峰.基于目標函數(shù)變化率的混合蟻群遺傳算法 [J].計算機工程與應用，2013，49（18）：41-44.

[17] 張瀟，王江晴.混合蟻群算法在車輛路徑問題中的應用[J].計算機工程，2011，37（24）：190-192.

[18] 彭碧濤，周永務.多時間窗車輛路徑問題的混合蟻群算法[J].計算機工程與應用，2010，46（31）：28-31.

（責任編輯：何 麗）