改進(jìn)混合蟻群算法求解關(guān)聯(lián)旅行商問(wèn)題

朱 君，蔡延光，湯雅連

（廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣東 廣州 510006）

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

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

1 ITSP問(wèn)題模型

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

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

2 改進(jìn)混合蟻群算法

2.1 混沌搜索

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

2.2 平滑機(jī)制

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

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

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

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

過(guò)多殘留信息素會(huì)引起殘留信息素覆蓋啟發(fā)信息，所以在每只螞蟻?zhàn)咄暌徊交蛘咄瓿蓪?duì)所有城市的遍歷之后，要對(duì)殘留信息進(jìn)行更新處理。t+n時(shí)刻在路徑（i，j）上的信息量可先按式（6）和（7）作調(diào)整。

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

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

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

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

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

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

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

2.5 信息素更新

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

（2）自適應(yīng)改變?chǔ)选Ｍㄟ^(guò)減小ρ雖然可以提高算法的全局搜索能力，但也會(huì)使收斂速度降低，因此需要自適應(yīng)改變 ρ。ρ的初始值 ρ（t0）=1；當(dāng)算法求得最優(yōu)值在此循環(huán)中無(wú)明顯改進(jìn)時(shí)，ρ如式（10）所示。

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

2.6 改進(jìn)混合蟻群算法求解流程

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

（2）進(jìn)行選擇、交叉和變異操作。

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

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

表1 50個(gè)城市坐標(biāo)信息

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

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

圖3 IHACO求解TSP的一次收斂過(guò)程

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

圖5 IHACO求解ITSP的一次收斂過(guò)程

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

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

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

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

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

[2]李明.詳解MATLAB在最優(yōu)化計(jì)算中的應(yīng)用[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]柳寅，馬良.模糊人工蜂群算法的旅行商問(wèn)題求解[J].計(jì)算機(jī)應(yīng)用研究，2013，30（9）：2694-2696.

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

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

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

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

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

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

[14]吳斌，史忠植.一種基于蟻群算法的TSP問(wèn)題分段求解算法[J].計(jì)算機(jī)學(xué)報(bào)，2001，24（12）：1328-1333.

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

[16]孫力娟，王良俊，王汝傳.改進(jìn)的蟻群算法及其在TSP中的應(yīng)用研究[J].通信學(xué)報(bào)，2004，25（10）：111-116.

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

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