許健 許峰

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

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

DOIDOI：10.11907/rjdk.173181

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：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.

英文關(guān)鍵詞Key Words：ant colony algorithm； iterative local search； local convergence； path planning

0 引言

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

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

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

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

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

1.1 MAKLINK圖

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

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

1.2 Dijkstra算法

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

Dijkstra算法流程如下：

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

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

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

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

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

2.1 基本蟻群算法

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

2.2 迭代局部搜索

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

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

迭代局部搜索流程如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 數(shù)值實(shí)驗(yàn)結(jié)果

3.1 問題描述

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

3.2 規(guī)劃結(jié)果

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

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

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

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

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

4 結(jié)語

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

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

參考文獻(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] 張志強(qiáng)，張璟，張翔.基于蟻群優(yōu)化的混合智能算法研究 [J].西安理工大學(xué)學(xué)報，2009，25（3）：314-317.

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

[11] 高超.隨機(jī)局部搜索算法及其應(yīng)用研究 [D].合肥：中國科學(xué)技術(shù)大學(xué)，2015.

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

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

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

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

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

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

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

（責(zé)任編輯：何 麗）