動態(tài)凸包引導的偏優(yōu)規(guī)劃蟻群算法求解TSP問題

馬學森，宮帥，朱建，唐昊

?

動態(tài)凸包引導的偏優(yōu)規(guī)劃蟻群算法求解TSP問題

馬學森1,2，宮帥1，朱建1，唐昊3

（1. 合肥工業(yè)大學計算機與信息學院，安徽 合肥 230009；2. 廣東三水合肥工業(yè)大學研究院，廣東 佛山 528000；3. 合肥工業(yè)大學電氣與自動化工程學院，安徽 合肥 230009）

針對蟻群算法搜索空間大、收斂速度慢、容易陷入局部最優(yōu)等缺陷，提出一種基于動態(tài)凸包引導的偏優(yōu)規(guī)劃蟻群算法。改進后的算法動態(tài)控制螞蟻的待選城市范圍，有助于在跳出局部最優(yōu)并向全局最優(yōu)逼近的基礎上減少螞蟻搜索空間；同時，引入延陷漂流因子和基于待選城市構建的凸包來干預當前螞蟻的城市選擇，增加算法前期解的多樣性并提高螞蟻的偏優(yōu)規(guī)劃能力；再利用局部與整體相結合的完整路徑信息、凸包的構建信息來協(xié)調信息素的更新，引導后繼螞蟻路徑偏優(yōu)規(guī)劃，提高算法的求解精度；設計具有收斂性的信息素最大最小值限制策略，既加快算法的求解速度又避免算法過早停滯；最后在4種經典TSP模型上應用改進后的算法。仿真結果表明，所提算法在求解精度和收斂速度等方面均有顯著提高，且具有較好的適用性。

蟻群算法；二維凸包；TSP；偏優(yōu)規(guī)劃

1 引言

TSP（travelling salesman problem）[1]又被稱為旅行商問題，該問題具體描述為：有位旅行商需要訪問個城市，他必須要走完所有城市，然后回到原點，每個城市只能選擇一次，目標是形成一條最短路徑。TSP作為一種經典NP難題，受到眾多專家和學者的關注。他們利用組合優(yōu)化提出很多啟發(fā)式搜索算法，如遺傳算法[2-3]、模擬退火算法[4]、人工神經網(wǎng)絡[5]、禁忌搜索算法[6]、蟻群算法[7]、免疫算法[8]等。其中，蟻群算法作為一種仿生學算法，在20世紀90年代由Dorigo等[9-10]提出，由于它具有較好的分布式計算能力和較強的頑健性，同時易與其他算法融合，被廣泛應用于一些NP難題的求解上。

蟻群算法是從自然界中螞蟻覓食的群體行為得到啟發(fā)而提出的，螞蟻覓食時會在已走路徑上釋放信息素，信息素濃度越高的路徑被后繼螞蟻選擇的概率越大。蟻群算法求解TSP過程為：將只螞蟻隨機放到個城市節(jié)點上，每個螞蟻按照一定的依據(jù)從沒有訪問過的城市中選擇下一跳城市節(jié)點，同時每行走一步或完成整個城市訪問后更新所有路徑上的信息素濃度。

但蟻群算法求解時螞蟻的城市選擇范圍較大，同時非優(yōu)路徑的多次出現(xiàn)和有些路徑上的信息素會增加算法的迭代次數(shù)及收斂于局部最優(yōu)解的概率。為彌補上述缺陷，本文基于二維凸包對蟻群算法進行改進，首先動態(tài)篩選螞蟻的待選鄰居城市節(jié)點，在有助于算法跳出局部最優(yōu)的基礎上，減少螞蟻的城市選擇范圍；其次將延陷漂流因子和二維凸包融入城市選擇策略，增加算法前期解的多樣性，減少非優(yōu)路徑的出現(xiàn)并提高算法收斂速度；最后將完整的路徑信息、二維凸包信息融入信息素更新策略，提高螞蟻的路徑尋優(yōu)能力，并用改進的信息素最大最小值限制策略來進一步加快算法的收斂速度。

二維凸包對本文算法的作用體現(xiàn)為：利用每個當前城市節(jié)點與待選鄰居節(jié)點構建的凸包區(qū)域范圍之間的關系來影響螞蟻下一跳城市節(jié)點的選擇；當所有螞蟻遍歷完成，對迭代最優(yōu)螞蟻行走路徑上的城市節(jié)點分別與其待選鄰居節(jié)點再次構建凸包，通過構建的凸包及存在的凸包角（如圖1(a)和圖1(b)所示，其中，圖1(b)不存在城市的凸包角）來獲取螞蟻遍歷的方向與深度，協(xié)調后繼螞蟻的走向。將已構建凸包的區(qū)域范圍與凸包角融入蟻群算法，更加有利于螞蟻的行走與協(xié)作，并可以加快算法逼近于最優(yōu)解。

最后，在Oliver30、Eil51、St70、Eil76這4個經典的TSP模型上驗證具有收斂性的信息素最大最小值限制策略的有效性以及本文算法的精確性、收斂的快速性與適用性。其中，在Eil51上以迭代次數(shù)作為衡量指標對所提出的信息素最大最小值限制策略進行驗證，同時延伸到其他3個TSP模型上也是有效的；以Oliver30和Eil51為例對本文算法的精確性和收斂的快速性進行詳細驗證，并引用到具有不同城市規(guī)模和位置的St70和Eil76中進行實驗，進一步表明本文算法能在保證求解精度的基礎上快速收斂，驗證了本文算法的適用性。

2 相關工作

眾多專家和學者針對蟻群算法的諸多缺陷進行了不同的改進研究。在信息素或節(jié)點選擇策略方面[11-14]，文獻[11]提出了一種釋放在城市節(jié)點上的方向性信息素和探索因子，但沒有考慮城市節(jié)點的位置及相對方向，隨著城市規(guī)模的逐漸擴大，求解誤差隨之增加，同時收斂速度的提高并不顯著。在最大最小螞蟻系統(tǒng)方面[15-18]，文獻[17]提出基于混沌的最大最小蟻群算法，采用tent混沌映射的方法產生初始信息素，當算法陷入長時間停滯狀態(tài)時利用混沌映射擾動信息素，雖能擴大蟻群的搜索范圍，但也進一步增加了算法的迭代次數(shù)。在圖論優(yōu)化蟻群方面[19-21]，文獻[19]對整體TSP模型構建凸包，以凸包頂點作為螞蟻出發(fā)點進行搜索，來減少算法的迭代次數(shù)，但該文只是對TSP模型進行凸包的構建，從而影響螞蟻的初始位置分布，后續(xù)并沒有把凸包融入蟻群算法，對蟻群算法本身沒有實質性的改變。在螞蟻多態(tài)方面[22-25]，文獻[22]提出一種基于動態(tài)局部搜索的蟻群算法，為每個螞蟻分配一個偵查蟻，增加螞蟻局部搜索能力，并根據(jù)迭代效果動態(tài)更新信息素，但該算法實質上是動態(tài)增加參與迭代的螞蟻數(shù)，并沒有顯著提高算法的求解精度。

在上述研究的基礎上并針對其存在的缺陷，本文利用凸包的構建及構建的區(qū)域范圍與凸包角，提出一種基于動態(tài)凸包引導的偏優(yōu)規(guī)劃蟻群算法（ACADCG, ant colony algorithm based on dynamic convex guidance），來求解TSP全部城市節(jié)點遍歷問題。ACADCG限制螞蟻下一跳的待選鄰居節(jié)點范圍，減小搜索空間，此外，隨著螞蟻待選鄰居節(jié)點改變而動態(tài)變化的凸包（如圖1(c)和圖1(d)所示，其中，圖1(d)存在的2個凸包分別為和,有助于算法跳出局部最優(yōu)；ACADCG還引入延陷漂流因子來增加城市選擇的隨機性，提高算法前期解的多樣性；同時將凸包的區(qū)域范圍應用到螞蟻選擇城市節(jié)點概率式中，引導螞蟻下一跳的偏優(yōu)規(guī)劃，減少交叉路徑的出現(xiàn)；當所有螞蟻遍歷完，通過改進的路徑信息、已構建的凸包及凸包角來修改信息素的更新規(guī)則，利用該規(guī)則來弱化導向非優(yōu)解路徑上的信息素及非優(yōu)解包含的非優(yōu)路徑上的信息素，引導后繼螞蟻路徑偏優(yōu)規(guī)劃，并引入與當前迭代次數(shù)相關的策略限制信息素上下限，進一步減少算法的迭代次數(shù)。

圖1 凸包圖

3 基于動態(tài)凸包引導的改進蟻群算法

本文針對蟻群算法搜索空間大、易陷入局部最優(yōu)及收斂速度慢等缺陷，在螞蟻的待選鄰居城市范圍、城市選擇策略、信息素更新與控制策略上進行了改進。

3.1 待選鄰居城市范圍的控制

3.2 城市選擇策略

3.2.1 延陷漂流因子

由于隨著迭代次數(shù)的增加而遞減，在初始階段，螞蟻選擇城市的隨機性大，會增加算法解的多樣性。不過值最終變?yōu)榉钦龜?shù)，螞蟻按照本文所設概率計算式(3)進行選擇后，信息素在最優(yōu)路徑上會持續(xù)增加，算法將最終收斂于最優(yōu)解。

3.2.2 引導當前螞蟻偏優(yōu)規(guī)劃的凸包

當螞蟻位于城市時，如果下一跳城市與螞蟻在上一跳城市時未遍歷的待選鄰居城市偏離較遠，則螞蟻后續(xù)可能會偏離這些未遍歷的待選鄰居城市，一旦持續(xù)偏離將引起螞蟻折回遍歷，而螞蟻在折回遍歷時極易產生交叉路徑，降低解的精度。

為解決上述問題，本文提出引導當前螞蟻偏優(yōu)規(guī)劃方法GCAPOP，用二維凸包引導螞蟻下一跳城市的選擇，使螞蟻優(yōu)先對最近已遍歷城市凸包區(qū)域范圍交集中未遍歷的城市進行訪問（不包括交集中邊上城市節(jié)點），減少螞蟻因折回遍歷而可能引起的路徑交叉（含有交叉路徑的解為非優(yōu)解）。其具體過程為：ACADCG算法中的螞蟻位于城市時，需要從城市凸包的區(qū)域范圍中（除城市外）選取下一個城市，當螞蟻到達城市時，將需要再次從城市凸包的區(qū)域范圍中（除城市外）選取下一跳城市，此時增加城市凸包與城市凸包區(qū)域范圍交集C中城市被選為下一跳城市的概率，若螞蟻依據(jù)概率選擇城市，則具體采用輪盤賭的方式選出下一跳城市節(jié)點。傳統(tǒng)蟻群算法中螞蟻選擇下一跳節(jié)點的概率如式(2)所示。ACADCG算法中螞蟻選擇下一跳節(jié)點的概率如式(3)所示。

基于GCAPOP方法的ACADCG算法增加了凸包區(qū)域范圍交集中城市節(jié)點被選為下一跳節(jié)點的概率，提高了算法的收斂速度及解的質量，但并沒有排除其他待選鄰居節(jié)點被選擇的可能，不會減少解的多樣性，同時為了避免算法較易陷入局部最優(yōu)，可利用本文所提的延陷漂流因子及改進的信息素更新策略。

3.3 信息素更新策略

ACADCG算法中的螞蟻每行走一步便局部更新信息素，當所有螞蟻一次遍歷完成后，便全局更新信息素，最后對信息素范圍進行控制。

3.3.1 引導后繼螞蟻偏優(yōu)規(guī)劃的凸包

圖2 一次遍歷中螞蟻路徑選擇情況（Eil51）

為解決上述問題，提出引導后繼螞蟻偏優(yōu)規(guī)劃方法GSAPOP，將二維凸包融入信息素更新策略來弱化引起交叉的路徑上的信息素及已形成交叉的路徑上的信息素，引導后繼螞蟻路徑選擇，減少非優(yōu)路徑的產生。

算法每完成一次迭代，對迭代最優(yōu)螞蟻走過的路徑進行信息素更新時，GSAPOP方法把更新分為2種情況（把迭代最優(yōu)路徑上的城市節(jié)點分別與其待選鄰居節(jié)點構建凸包）。

2) 城市節(jié)點在凸包內部（圖1(b)）。此時，按照式(8)中凸包內部的取值來更新城市節(jié)點與下個被選節(jié)點之間邊的信息素。

ACADCG算法中GSAPOP方法會削減起始城市為凸點的交叉路徑及引起交叉的路徑（圖2）上的信息素更新幅度，有利于后繼螞蟻向更優(yōu)路徑遍歷。

3.3.2 偏優(yōu)信息素更新

1) 信息素局部更新：螞蟻從當前節(jié)點移動到下個節(jié)點后，利用式(4)更新路徑邊—上信息素。

采用信息素局部更新可以適度地減少螞蟻所走過路徑的信息素，使后繼螞蟻選中該路徑的可能性減小，增加解的多樣性，抑制算法過早停滯。

3.3.3 具有收斂性的信息素最大最小值限制區(qū)間

當信息素更新完成后，為了抑制由于邊與邊上信息素濃度差距過大而引起算法停滯現(xiàn)象的發(fā)生，本文引入信息素最大最小值限制策略。

含有傳統(tǒng)公式的信息素最大最小值限制策略雖然能防止信息素過多地聚集在某些路徑上，但一定程度上也抑制了算法收斂速度。本文將迭代次數(shù)考慮到信息素最大最小值限制策略中，對算法前期、中期及后期進行適當干預，既避免了因不同路徑上信息素濃度差距過大導致算法陷入局部最優(yōu)，又提高算法中后期向全局最優(yōu)解逼近的概率。

改進后的最大信息素和最小信息素的取值分別如式(13)與式(14)所示，其中，式(14)的形式與傳統(tǒng)公式相一致。

3.4 ACADCG算法的實現(xiàn)

ACADCG算法實現(xiàn)步驟如下，算法流程如圖3所示。

5) 判斷遍歷是否完成。禁忌表中是否包含所有城市，若未包含則轉步驟2)；否則轉步驟6)。

6) 若只螞蟻都構造完成各自的解，則轉步驟7)；否則轉步驟2)。

3.5 ACADCG算法復雜度

ACADCG算法復雜度包括時間復雜度與空間復雜度。

圖3 ACADCG算法求解TSP流程

3.5.1 ACADCG算法時間復雜度

表1 本文蟻群算法的時間復雜度分析

3.5.2 ACADCG算法空間復雜度

4 仿真實驗結果與分析

美國RAND公司將城鎮(zhèn)的實際地理位置抽象成坐標節(jié)點，從而來構建經典的TSP標準數(shù)據(jù)庫。眾多專家和學者基本都以該庫作為基礎來測試所研究的近似求解算法，因此本文將ACADCG算法應用于標準數(shù)據(jù)庫里的不同經典TSP模型（Oliver30、Eil51、St70、Eil76）中求解，來驗證本文信息素最大最小值限制策略的有效性以及算法的精確性、收斂的快速性與適用性。算法開發(fā)環(huán)境為：在配有Intel 2.3 GHz，4 GB RAM的Windows 7 PC機上采用Java語言和Matlab開發(fā)了ACADCG算法，并對此算法進行了仿真實驗測試。

4.1 算法參數(shù)

參數(shù)確定的具體過程和篩選原則如下。

表2 本文算法在4種TSP模型中相同參數(shù)值設置

表3 本文算法在4種TSP模型中不同參數(shù)值設置

4.2 信息素最大最小值限制區(qū)間對算法的影響

圖4 3種不同信息素最大最小值限制區(qū)間算法收斂速度的比較

由圖4所知，T-ACADCG算法的總體收斂速度比F-ACADCG算法快，而ACADCG算法相比T-ACADCG算法其收斂性又進一步提升。F-ACADCG算法和T-ACADCG算法分別在830多次和760多次收斂到最優(yōu)解，而ACADCG算法在700次左右就已經收斂到最優(yōu)解了。

T-ACADCG算法中的信息素最大最小值限制范圍的上下限會隨著解的改變而變化，相比于固定上下限的F-ACADCG算法收斂速度要快。但T-ACADCG算法中的上下限有時會減慢算法向最優(yōu)解逼近，而本文中信息素最大最小值限制范圍的上下限相比于T-ACADCG算法中的上下限會在算法迭代中期，隨著迭代的推移平穩(wěn)增加，能適當減少較優(yōu)路徑上信息素遞增幅度的限制，增加算法逼近于最優(yōu)解的概率；在算法后期，相比于T-ACADCG算法中的上下限其倍數(shù)的增量非常緩慢直至不變，本文中信息素最大最小值限制范圍的上下限隨著算法的迭代，避免不同路徑上信息素差別過大；但在算法前期，本文中信息素最大最小值限制范圍的上下限與T-ACADCG算法中的上下限變化相似，以抑制算法前期解的多樣性。將上述不同策略的ACADCG算法拓展到4.4節(jié)中的Oliver30、St70、Eil76中進行仿真實驗，變化趨勢與圖4相似，在此不再重復繪圖與分析。

4.3 ACADCG算法對收斂速度的影響

仍以Eil51作為詳細分析對象來測試本文算法的收斂速度。將蟻群系統(tǒng)（ACS, ant colony system）、最大最小螞蟻系統(tǒng)（MMAS, max-min ant system）、基于方向信息素協(xié)調的蟻群算法[11]（AADC, ant algorithm based on direction-coordinating）和本文ACADCG算法進行尋優(yōu)結果比較，實驗結果如圖5所示。

圖5 4種算法收斂速度的比較

由圖5可知，ACS算法、MMAS算法、AADC算法在迭代400次之后開始逐步收斂，分別在迭代1 400次左右、1 200次左右、1 000次左右才能最終收斂；ACADCG算法在迭代700多次，就收斂到429.18，逼近于理論最優(yōu)解426。因此，ACADCG算法收斂速度有顯著提高，求解精度也有進一步的改進。將4.4節(jié)中的Oliver30、St70、Eil76作為仿真對象測試上述不同算法，變化趨勢與圖5相似，在此也不再重復繪圖與分析。

針對收斂速度的問題，本文以Oliver30和Eil51為例，將ACADCG算法與ACS算法、MMAS算法、AADC算法進行仿真實驗比較，結果如表4所示。表4中結果均為30次實驗所得。為避免贅述，St70、Eil76的仿真實驗結果將在4.4節(jié)中詳細列出。

表4 ACADCG算法與其他算法收斂速度上下限對比

求解快速性的主要原因是：ACADCG算法中的螞蟻是從當前所有剩余城市中篩選出若干個城市作為待選鄰居城市集合，縮小了搜索空間。此外，待選鄰居城市集合的動態(tài)擴充有助算法在陷入局部最優(yōu)時跳出局部最優(yōu)，加快算法的收斂速度；當螞蟻進行城市選擇時，GCAPOP方法增加了凸包區(qū)域范圍交集中城市被選概率，使螞蟻優(yōu)先訪問最近已遍歷城市附近未選擇的城市節(jié)點，增加螞蟻向無交叉路徑解逼近的概率，推動ACADCG算法向全局最優(yōu)解逼近；當所有螞蟻完成遍歷后，含有GSAPOP方法的信息素更新策略能削弱非優(yōu)路徑及其周邊路徑上的信息素，提高后繼螞蟻向較優(yōu)路徑集合逼近的概率，加快算法尋優(yōu)過程中的收斂速度；同時，本文的信息素最大最小值限制策略能對算法進行適當?shù)母深A，進一步減少了算法的迭代次數(shù)。

4.4 ACADCG算法在多種模型中綜合性能分析

將ACADCG算法與其他蟻群算法分別應用于4個典型TSP模型中進行誤差率、收斂速度、適用性等綜合性能仿真實驗，結果如表5所示。此外，ACADCG算法在4個模型上求解獲得的最優(yōu)路徑如圖6所示。

圖6 ACADCG算法最優(yōu)路徑遍歷結果

表5 典型TSP問題求解對比模型

ACADCG算法引入了二維凸包，而二維凸包的構建與城市節(jié)點的位置相關，因此具有不同城市節(jié)點位置和城市數(shù)量的TSP模型，其求解誤差可能不一樣，但ACADCG算法的誤差控制能力優(yōu)于與其對比的算法且收斂速度較快，主要原因是：本文算法能有效避免螞蟻在TSP模型中遍歷時出現(xiàn)交叉路徑，提高了算法的整體求解精度和收斂速度。同時，本節(jié)4個TSP模型上的仿真結果也體現(xiàn)了ACADCG算法具有較好的適用性。

5 結束語

針對蟻群算法搜索空間大、求解精度差、迭代輪數(shù)多的缺陷，本文基于二維凸包對蟻群算法進行了改進。通過仿真對比分析可知，改進后的蟻群算法全局搜索能力得到提高，收斂速度進一步加快，而且在此過程中，能夠較好地克服算法過早收斂到局部解的缺點，同時能夠得到更精確解，且具有較好的適用性。實驗結果表明，本文所提出的改進是切實可行的。

然而本文算法還存在一些不足之處，首先蟻群算法的隨機性和凸包構建的動態(tài)性導致了算法復雜度的不確定性；其次凸包的構建有一定的代價，但本文不把凸包構建作為影響算法的性能指標，因凸包構建的代價不影響算法的迭代次數(shù)。未來，將深入分析和探討凸包構建，以便進一步提高算法的性能，并將算法應用于數(shù)據(jù)規(guī)模更大的問題上來進行求解。

[1] DORIGO M, GAMBARDELL L M. Ant colonies for the travelling salesman problem[J]. Bio Systems, 1997, 43(2): 73-81.

[2] MAEKAWA K, TAMAKI H, KITA H, et al. A method for the traveling salesman problem based on the genetic algorithm[J]. Transactions of the Society of Instrument & Control Engineers, 1995, 31(5): 598-605.

[3] WANG J, ERSOY O K, HE M, et al. Multi-offspring genetic algorithm and its application to the traveling salesman problem[J]. Applied Soft Computing, 2016, 43(3): 415-423.

[4] MURRAY A T, CHURCH R L. Applying simulated annealing to location-planning models[J]. Journal of Heuristics, 1996, 2(1): 31-53.

[5] YU D, JIA J. A neural network algorithm with optimized parameters and used to solve the TSP[J]. Acta Electronica Sinica, 1993, 21(7): 16-22.

[6] LIN Y, BIAZ Z, LIU X. Developing a dynamic neighborhood structure for an adaptive hybrid simulated annealing – tabu search algorithm to solve the symmetrical traveling salesman problem[J]. Applied Soft Computing, 2016, 49(9):937-952.

[7] LIU Z, LI X, WANG H. Improvement of self-adaptive ant colony algorithm based on cloud model[J]. Computer Engineering and Applications, 2016, 52(19): 68-71.

[8] PAN G, LI K, OUYANG A, et al. Hybrid immune algorithm based on greedy algorithm and delete-cross operator for solving TSP[J]. Soft Computing, 2016, 20(2):555-566.

[9] DORIGO M, MANIEZZO V, COLORNI A, et al. Ant system: optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems Man and Cybernetics-Part B, 1996, 26(1): 29-41.

[10] 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.

[11] 孟祥萍, 片兆宇, 沈中玉, 等. 基于方向信息素協(xié)調的蟻群算法[J]. 控制與決策, 2013, 28(5): 782-786.

MENG X P, PIAN Z Y, SHEN Z Y, et al. Ant algorithm based on direction-coordinating[J]. Control and Decision, 2013(5): 782-786.

[12] 吳華鋒, 陳信強, 毛奇凰, 等. 基于自然選擇策略的蟻群算法求解TSP問題[J]. 通信學報, 2013, 34(4): 165-170.

WU H F, CHEN X Q, MAO Q F, et al. Improved ant colony algorithm based on natural selection strategy for solving TSP problem[J]. Journal on Communications, 2013(4): 165-170.

[13] 林建兵, 陳智雄, 姚國祥. 一種基于域密度的蟻群系統(tǒng)(AS)改進算法及結果解析[J]. 武漢大學學報(工學版), 2016, 49(4): 627-634.

LIN J B, CHEN Z X, YAO G X. An improved AS algorithm and result analyzing based on domain and its density[J]. Engineering Journal of Wuhan University, 2016, 49(4): 627-634.

[14] 馬學森, 曹政, 韓江洪, 等. 改進蟻群算法的無線傳感器網(wǎng)絡路由優(yōu)化與路徑恢復算法[J]. 電子測量與儀器學報, 2015, 29(9): 1320-1327.

MA X S, CAO Z, HAN J H, et al. Routing optimization and path recovery algorithm in wireless sensor network based on improved ant colony algorithm[J]. Journal of Electronic Measurement and Instrument, 2015, 29(9): 1320-1327.

[15] 孫力娟, 王良俊, 王汝傳. 改進的蟻群算法及其在TSP中的應用研究[J]. 通信學報, 2004, 25(10): 111-116.

SUN L J, WANG L J, WANG R C, Research of using an improved ant colony algorithm to solve TSP[J]. Journal on Communications, 2004, 25(10): 111-116.

[16] BU Y, LI T Q, ZHANG Q. A weighted max-min ant colony algorithm for TSP instances[J]. IEICE Transactions on Fundamentals of Electronics Communications & Computer Sciences, 2015(3): 894-897.

[17] 耿志強, 邱大洪, 韓永明. 基于混沌的MMAS算法及其在旅行商問題中的應用[J]. 計算機工程, 2016, 42(3): 192-197.

GENG Z Q, QIU D H, HAN Y M. Max-min ant system algorithm based on chaos and its application in TSP[J]. Computer Engineering, 2016, 42(3): 192-197.

[18] WANG Y. Hybrid max-min ant system with four vertices and three lines inequality for traveling salesman problem[J]. Soft Computing, 2015, 19(3): 585-596.

[19] 張層. 基于二維凸包的改進蟻群算法求解TSP問題[D]. 廣州: 華南理工大學, 2013.

ZHANG C. An improved ant colony algorithm based on two-dimensional convex hull for TSP[D]. Guangzhou: South China University of Technology, 2013.

[20] 黨小超, 李小艷. 基于圖論的WSN節(jié)點定位路徑規(guī)劃[J]. 計算機工程, 2012, 38(11): 100-103.

DANG X C, LI X Y. WSN node localization path planning based on graph theory[J]. Computer Engineering, 2012, 38(11): 100-103.

[21] PRAGYA, DUTTA M, PRATYUSH. TSP solution using dimensional ant colony optimization[C]//International Conference on Advanced Computing & Communication Technologies. 2015: 506-512.

[22] QIN H, ZHOU S, HUO L, et al. A new ant colony algorithm based on dynamic local search for TSP[C]//International Conference on Communication Systems and Network Technologies. 2015: 913-917.

[23] GU S, ZHANG X. An improved ant colony algorithm with soldier ants[C]//2015 11th International Conference on Natural Computation (ICNC). 2016: 205-209.

[24] LUO W, LIN D, FENG X X. An improved ant colony optimization and its application on TSP problem[C]//2016 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData). 2017: 136-141.

[25] 盛國軍, 溫濤, 郭權, 等. 基于改進蟻群算法的可信服務發(fā)現(xiàn)[J]. 通信學報, 2013, 34(10): 37-48.

SHENG G J, WEN T, GUO Q, et al. Trustworthy service discovery based on a modified ant colony algorithm[J]. Journal on Communications, 2013, 34(10): 37-48.

[26] 詹士昌, 徐婕, 吳俊. 蟻群算法中有關算法參數(shù)的最優(yōu)選擇[J]. 科技通報, 2003, 19(5): 381-386.

ZHAN S C, XU J, WU J. The optimal selection on the parameters of the ant colony algorithm[J]. Bulletin of Science and Technology, 2003, 19(5): 381-386.

Ant colony algorithm of partially optimal programming based on dynamic convex hull guidance for solving TSP problem

MA Xuesen1,2, GONG Shuai1, ZHU Jian1, TANG Hao3

1. School of Computer and Information, Hefei University of Technology, Hefei 230009, China 2. Research Institute of Sanshui & Hefei University of Technology in Guangdong, Foshan 528000, China 3. School of electrical and Automation Engineering, Hefei University of Technology, Hefei 230009, China

To solve basic ant colony algorithm’s drawbacks of large search space, low convergence rate and easiness of trapping in local optimal solution, an ant colony algorithm of partially optimal programming based on dynamic convex hull guidance was proposed. The improved algorithm dynamically controlled the urban selection range of the ants, which could reduce the search space of ants on basis of helping the algorithm to jump out of local optimal solution to global optimal solution. Meanwhile, the delayed drift factor and the convex hull constructed by the cities to be chosen were introduced to intervene the current ants’ urban choice, it could increase the diversity of the early solution of the algorithm and improve the ability of ants’ partially optimal programming. Then the pheromone updating was coordinated by using construction information of convex hull and the complete path information that combined local with whole, it could improve the accuracy of the algorithm by guiding the subsequent ants to partially optimal programming. The pheromone maximum and minimum limit strategy with convergence was designed to avoid the algorithm’s premature stagnation and accelerate the solving speed of the algorithm. Finally, the proposed algorithm was applied to four classic TSP models. Simulation results show that the algorithm has better optimal solution, higher convergence rate and better applicability.

ant colony algorithm, convex hull, TSP, partially optimal programming

TP18

A

10.11959/j.issn.1000?436x.2018218

馬學森（1976?），男，安徽廬江人，合肥工業(yè)大學副教授、碩士生導師，主要研究方向為無線傳感器網(wǎng)絡、嵌入式系統(tǒng)、大數(shù)據(jù)處理、網(wǎng)絡與信息安全。

宮帥（1993?），男，安徽滁州人，合肥工業(yè)大學碩士生，主要研究方向為無線傳感器網(wǎng)絡、物聯(lián)網(wǎng)、網(wǎng)絡與信息安全。

朱建（1992?），男，安徽五河人，合肥工業(yè)大學碩士生，主要研究方向為高可靠性嵌入式系統(tǒng)、無線傳感器網(wǎng)絡、物聯(lián)網(wǎng)。

唐昊（1972?），男，安徽廬江人，合肥工業(yè)大學教授、博士生導師，主要研究方向為離散事件動態(tài)系統(tǒng)、隨機決策與優(yōu)化理論、強化學習等智能優(yōu)化與控制方法、自動化生產線、物聯(lián)網(wǎng)和微網(wǎng)等系統(tǒng)優(yōu)化設計與控制技術。

2017?07?17；

2018?07?02

國家自然科學基金資助項目（No.61573126）；廣東省科技發(fā)展專項基金資助項目（No.2017A010101001）；中央高?；究蒲袠I(yè)務費專項基金資助項目（No.JZ2016HGBZ1032）；國家留學基金資助項目

The National Natural Science Foundation of China (No.61573126), The Special Funds for Science and Technology Development of Guangdong Province (No.2017A010101001), The Central University Basic Business Expenses Special Funding for Scientific Research Project (No.JZ2016HGBZ1032), China Scholarship Council Foundation