改進混合蟻群算法求解關聯(lián)旅行商問題

朱 君，蔡延光，湯雅連

（廣東工業(yè)大學 自動化學院，廣東 廣州 510006）

旅行商問題 TSP[1-2]（Traveling Salesman Problem）是運籌學領域中的經(jīng)典優(yōu)化組合問題，并且屬于NP-Hard（NPH）問題，其計算復雜性隨輸入規(guī)模呈指數(shù)函數(shù)增長，其實際模型在連鎖店的貨物配送、電子地圖、印刷電路板的鉆孔路線方案、超大規(guī)模集成電路單元布局、網(wǎng)格布線、管道鋪設等優(yōu)化問題中有著廣泛的應用。游客在訪問城市時，會有各種約束，關聯(lián)約束就是其中一種，由于兩個或多個城市依次舉行展會、博覽會、藝術(shù)節(jié)、廣交會及馬拉松比賽等，這些演藝類、體育類、文化類及商業(yè)類的大型活動往往吸引著廣大游客，游客會盡可能地參觀或者參加節(jié)事旅游，比如3個旅游城市A、B和C依次舉辦大型活動，那么游客訪問的次序應該是A→B→C，這就是關聯(lián)旅行商問題ITSP（Incident Traveling Salesman Problem），由于該問題模型在現(xiàn)實生活中普遍存在，因而具有研究意義。

目前已經(jīng)有很多求解TSP的算法。SILBERHOLZ J等人[3]研究了多彩TSP（Colourful Travelling Salesman Problem，CTSP），提出了兩種新的啟發(fā)式算法對其求解，并證明了所提出方法的有效性。ROY S[4]應用帶單點交叉算子的遺傳算法求解TSP，實驗證明能搜索到最優(yōu)解。MAVROVOUNIOTIS M[5]等人針對帶交通因素的動態(tài)TSP，應用移民策略的蟻群優(yōu)化算法ACO（Aat Colony Optimization）求解，實驗證明提出的算法優(yōu)于傳統(tǒng)的ACO。SINGH H等人[6]應用遺傳算法求解多旅行商問題 MTSP（Multiple Traveling Salesman Problem）。柳寅等人[7]基于模糊化處理和蜂群尋優(yōu)的特點，提出一種模糊人工蜂群算法，通過對旅行商問題的仿真證明了該算法有良好的魯棒性和有效性。王剛等人[8]應用多項式時間近似方案PTAS（PolynomialTimeApproxination Scheme）研究曲面上的TSP，一般性的深刻結(jié)論還有待研究。劉勇等人[9]研究了以總路程和總收益之比為目標函數(shù)的最小比率旅行商問題MRTSP（Minimum Ratio Traveling Salesman Problem），應 用基于萬有引力定律和牛頓第二定律的引力搜索算法GSA（Gravitational Search Algorithm）尋優(yōu)，實驗結(jié)果證明該算法能有效解決最小比率旅行商問題。饒衛(wèi)振等人[10]應用添加邊所在位置信息的改進貪婪算法IMGRA（Improved Greedy Algorithm）求解歐幾里得旅行商問題ETSP（Euclidean Travelling Salesman Problem），結(jié)果表明IMGRA優(yōu)于貪婪算法 GRA（Greedy Algorithm）。蔡榮英等人[11]針對傳統(tǒng)ACO的不足，提出了迭代改進蟻群優(yōu)化算法，并用此算法求解TSP，仿真結(jié)果表明該算法能在更少迭代次數(shù)內(nèi)獲得更好解?？铝架姷热薣12]應用精確算法和蟻群算法求解不確定旅行商問題的魯棒模型，結(jié)果證明提出的蟻群算法能在短時間內(nèi)求得最優(yōu)或近優(yōu)解，且魯棒解是有效的。王穎等人[13]提出一種克服局部最小點的自適應蟻群算法，在保證收斂速度的條件下提高解的全局性，仿真證明在收斂速度和解的性能方面優(yōu)于傳統(tǒng)蟻群算法。吳斌等人[14]在蟻群算法的基礎上提出了相遇算法并將相遇算法與分段算法相結(jié)合，求解TSP，實驗證明了算法的有效性。葉志偉等人[15]研究了蟻群算法中的參數(shù)α、β、ρ，并對最優(yōu)的參數(shù)配置問題作了分析，同時求解TSP，證明有較好的實用價值。孫力娟等人[16]應用遺傳算法 GA（Genetic Algorithm）對 ACO的參數(shù)α、β、ρ進行優(yōu)化，對 TSP的求解表明算法的優(yōu)化質(zhì)量和效率優(yōu)于傳統(tǒng)蟻群算法和遺傳算法。段海濱等人[17]應用改進的ACO求解對Bayes 29TSP問題，實驗結(jié)果表明該算法具有很好的全局收斂性能。本文重點是引入混沌搜索和平滑機制，結(jié)合GA和ACO的優(yōu)點，應用改進的混合蟻群算法對ITRP求解。

1 ITSP問題模型

假設一個游客要去 i（i=1，2，…，l）個城市，這些城市兩兩之間均可到達，且可以用距離來量化，其中有h個城市具有關聯(lián)性，游客必須規(guī)劃所要走的路徑，h個城市必須按時間先后依次訪問，每個城市只能拜訪一次，最后要回到原來出發(fā)的城市，目的是路徑總里程最小。

建立數(shù)學模型：式（1）為目標函數(shù)，即總路程最短；式（2）為約束條件，對于每個地方，都必須經(jīng)過1次，對于任何n-2個節(jié)點，不能有回路，存在關聯(lián)約束，根據(jù)時間的先后依次訪問有關聯(lián)約束的城市，關聯(lián)城市個數(shù)小于總城市個數(shù)。

2 改進混合蟻群算法

2.1 混沌搜索

混沌搜索具有隨機性、遍歷性和確定性，由混沌搜索產(chǎn)生初始種群，克服了生成大量非可行解的缺陷，加速染色體向最優(yōu)解收斂。文中選用Logistic映射[18]，如式（3）所示。i表示混沌變量的序號，i=1，2，…，r；u 表示種群序號，u=0，1， …，n；βi表示混沌變量，0≤βi≤1； μi表 示 吸 引 子 。 當 μi=4時 ，Logistic映射完全處于混沌的狀態(tài)，此時的混沌變量βi具有很好的遍歷性。

2.2 平滑機制

平滑機制可用于提高蟻群算法的性能的思想是通過增加選擇有低強度信息素解元素的概率以提高探索新解的能力。如式（4）所示，0＜δ＜1，τij（t）和 τij*（t）分別為平滑化之前和之后的信息素軌跡量。其優(yōu)點是對于δ＜1，在算法運行過程中所積累的信息不會完全被丟失，而僅僅是被削弱；δ=1時，相當于信息素軌跡的重新初始化；δ=0，則該機制被關閉。

2.3 基本蟻群算法系統(tǒng)模型

設 m 為螞 蟻數(shù)量，dij（i，j=1，2，…，n）表示 i與 j之間的距離，τij（t）表示 t時刻在 ij連線上殘留的信息素強度。 初始時刻，各路徑上信息量相等，設 τij（0）=C（C 為常數(shù)）。 螞蟻 k（k=1，2，…，m）在運動過程中，根據(jù)各條路徑上信息量決定轉(zhuǎn)移方向，Pijk表示t時刻螞蟻k由位置i轉(zhuǎn)移到 j的概率，如式（5）所示。

其中，allowedk為螞蟻 k下一步可選擇的城市；ηijβ為能見度因數(shù)，常取 ηij（t）=1/dij；α 和 β 分別反映了螞蟻在運動過程中所積累的信息和啟發(fā)信息在螞蟻選擇路徑中的相對重要性，α為信息啟發(fā)式因子，β為期望啟發(fā)式因子。

過多殘留信息素會引起殘留信息素覆蓋啟發(fā)信息，所以在每只螞蟻走完一步或者完成對所有城市的遍歷之后，要對殘留信息進行更新處理。t+n時刻在路徑（i，j）上的信息量可先按式（6）和（7）作調(diào)整。

其中，ρ為信息素揮發(fā)因子，ρ∈（0，1）；△τij（t）表示本次循環(huán)中信息素增量；△τijk（t）表示第 k只螞蟻在本次循環(huán)中留下的信息素，計算方法可以根據(jù)計算模型而定。

本文采用蟻周模型，如式（8）所示。

其中，Q表示信息素強度，會影響算法的收斂速度，過大會導致局部收斂，過小會影響收斂速度；dij表示在本次循環(huán)中所走路徑的長度。

2.4 構(gòu)造狀態(tài)轉(zhuǎn)移規(guī)則

采用將確定性選擇組合和隨機性選擇相結(jié)合的策略，適當加大隨機選擇概率，對解空間進行更完全的搜索，從而克服傳統(tǒng)蟻群算法缺陷。按照式（9）確定螞蟻由轉(zhuǎn)移到的狀態(tài)轉(zhuǎn)移概率。

其中，q 是[0，1]內(nèi)的隨機數(shù)，是一個參數(shù)；q0∈[0，1]，一般取 0.85～0.90。

螞蟻在選擇下一客戶時，根據(jù)先驗知識，如式（9）所示來選擇最好的邊，否則按式（5）來選擇一條邊，將求得的各個節(jié)點的轉(zhuǎn)移概率進行累加，再與產(chǎn)生的隨機數(shù)相比較，直到滿足要求，螞蟻可轉(zhuǎn)移到下一節(jié)點。

2.5 信息素更新

（1）保留最優(yōu)解。在每次循環(huán)結(jié)束后，保留最優(yōu)解。

（2）自適應改變ρ。通過減小ρ雖然可以提高算法的全局搜索能力，但也會使收斂速度降低，因此需要自適應改變 ρ。ρ的初始值 ρ（t0）=1；當算法求得最優(yōu)值在此循環(huán)中無明顯改進時，ρ如式（10）所示。

其中，ρmin可以防止ρ因過小而降低算法收斂速度。

2.6 改進混合蟻群算法求解流程

（1）混沌搜索，產(chǎn)生初始種群，設計遺傳算法參數(shù)。

（2）進行選擇、交叉和變異操作。

（3）滿足條件則生成優(yōu)化解，不滿足則返回步驟（1）。

（4）根據(jù)優(yōu)化解生成信息素初始分布，設計蟻群算法參數(shù)。

（5）螞蟻根據(jù)轉(zhuǎn)移概率選擇下一節(jié)點。

（6）遍歷所有點，最優(yōu)螞蟻圈進行信息素增加。

（7）更新信息素，引入平滑機制，根據(jù)式（11）進行平滑化。

（8）若滿足終止條件，達到最大迭代次數(shù)，則結(jié)束；否則，返回步驟（5）。

3 仿真實驗

改進混合蟻群算法中參數(shù)設計，蟻群規(guī)模m=20，最大迭代次數(shù) Nc=200，α=1，β=1，ρ（t0）=0.15，q0=0.88，Q=100；遺傳算法部分參數(shù)設計，初始化種群N=20，最大迭代次數(shù) gen=50，交叉概率 pc=0.9，變異概率 pm=0.04，采用輪盤賭選擇，路徑編碼，均勻雜交，單點變異。關聯(lián)約束：t32＜t23＜t2＜t1＜t18，t38＜t11＜t39＜t40。 本 文中 的實 驗及算例是在Intel（R）CoreTMi3 CPU 2.53 GHz、內(nèi)存為 2.0 GB、安裝系統(tǒng)為Win7的PC上采用MATLAB R2010b編程實現(xiàn)。城市信息如表1所示。應用 PSAGA、ACO、GA、禁忌搜索 TS（Tabu Serch）和改進的混合蟻群優(yōu)化算法IHACO（Improving Hybird Ant Colony Optimization）對 TSP 和ITSP問題模型分別求解20次，然后應用IHACO和ACO求解TSPlib中的 3個算例，eil76（76個城市）、eil101（101個城市）和 pr136（136個城市），運行程序20次。首先將具有關聯(lián)約束的城市連接起來，如圖1所示，然后應用算法求解。

表1 50個城市坐標信息

圖1 關聯(lián)約束圖示

圖2 IHACO求解TSP的最佳旅游路線最優(yōu)旅游路線（ITSP）

圖3 IHACO求解TSP的一次收斂過程

圖4 IHACO求解ITSP的最佳旅游路線

圖5 IHACO求解ITSP的一次收斂過程

結(jié)果比較如表2所示，在求解TSP時，基于遺傳算法的粒子群算法 PSOGA（Particle Swarm Algorithm based on Genetic Algorithm）和IACO能搜索到較好解，TSP最優(yōu)路徑長度為：516.687 4 km。IHACO求解TSP的最佳旅游路線及IHACO求解TSP的一次收斂過程如圖2和圖3所示。在求解ITSP時，ACO和IHACO能搜索到較好解，ITSP最優(yōu)路徑長度為：520.191 2 km。IHACO求解ITSP的最佳旅游路線及IHACO求解ITSP的一次收斂過程如圖4和圖5所示。進一步驗證ACO和IHACO的性能，對TSPlib中的3個算例仿真的結(jié)果如表3所示，與ACO相比，IHACO的運行時間更短，偏差也較小，說明IHACO優(yōu)化能力更強，求解更優(yōu)。

本文引出了關聯(lián)旅行商問題并對其分析，建立了數(shù)模型；采用混沌搜索產(chǎn)生初始種群克服了生成大量非可行解的缺陷，加速染色體向最優(yōu)解收斂；引入平滑機制，該機制通過增加選擇有低強度信息素解元素的概率以提高蟻群算法探索新解的能力。蟻群算法搜索初期信息素累積時間長，求解效率低，結(jié)合遺傳算法具有快速全局搜索能力，構(gòu)成改進混合蟻群算法，算例證明該算法能搜索到較好解，并且提高了計算效率。

表2 GA-PSO、ACO、GA、TS和 IACO求解TSP和 ITSP的結(jié)果比較

表3 ACO和IHACO求解TSPlib中3個算例的結(jié)果

[1]趙秋紅，肖依永，MLADENOVIC N.基于單點搜索的元啟發(fā)式算法[M].北京：科學出版社，2013.

[2]李明.詳解MATLAB在最優(yōu)化計算中的應用[M].北京：電子工業(yè)出版社，2011.

[3]SILBERHOLZ J， RAICONI A， CERULLI R， et al.Comparison of heuristics for the colourful travelling salesman problem[J].International Journal of Metaheuristics， 2013， 2（2）： 141-173.

[4]ROY S.Genetic algorithm based approach to solve travelling salesman problem with one pointcrossoveroperator[J].INTERNATIONAL JOURNAL OF COMPUTERS&TECHNOLOGY， 2013， 10（3）：1393-1400.

[5]MAVROVOUNIOTIS M，YANG S.Ant colony optimization with immigrants schemes for the dynamic travelling salesman problem with traffic factors[J].Applied Soft Computing，2013，13（10）：4023-4037.

[6]SINGH H，KAUR R.Resolving multiple travelling salesman problem using genetic algorithms[J].International Journal of Computer Science Engineering and Information Technology Research， 2013，3（2）：209-212.

[7]柳寅，馬良.模糊人工蜂群算法的旅行商問題求解[J].計算機應用研究，2013，30（9）：2694-2696.

[8]王剛，駱志剛.曲面上旅行商問題的多項式時間近似方案[J].計算機研究與發(fā)展，2013，50（3）：657-665.

[9]劉勇，馬良.最小比率旅行商問題的引力搜索算法求解[J].小型微型計算機系統(tǒng)，2013，4（34）：847-849.

[10]饒衛(wèi)振，金淳，陸林濤.考慮邊位置信息的求解 ETSP問題改進貪婪算法[J].計算機學報，2013，36（4）：836-850.

[11]蔡榮英，王李進，吳超，等.一種求解旅行商問題的迭代改進蟻群優(yōu)化算法[J].山東大學學報（工學版），2012，42（1）：6-11.

[12]柯良軍，尚可，馮祖仁.不確定旅行商問題的魯棒模型及 其 算 法 研 究 [J].計 算 機 科 學 ，2012，39（B06）：238-241.

[13]王穎，謝劍英.一種自適應蟻群算法及其仿真研究[J].系統(tǒng)仿真學報，2002，14（1）：31-33.

[14]吳斌，史忠植.一種基于蟻群算法的TSP問題分段求解算法[J].計算機學報，2001，24（12）：1328-1333.

[15]葉志偉，鄭肇葆.蟻群算法中參數(shù) α，β，ρ設置的研究——以TSP問題為例[J].武漢大學學報（信息科學版），2004，29（7）：597-601.

[16]孫力娟，王良俊，王汝傳.改進的蟻群算法及其在TSP中的應用研究[J].通信學報，2004，25（10）：111-116.

[17]段海濱，王道波.蟻群算法的全局收斂性研究及改進[J].系統(tǒng)工程與電子技術(shù)，2004，26（10）：1506-1509.

[18]湯雅連，蔡延光，郭帥，等.單車場關聯(lián)物流運輸調(diào)度問題的混沌遺傳算法[J].廣東工業(yè)大學學報，2013（30）：53-57.