基于T-ACO算法的旅行商問題求解優(yōu)化研究

費(fèi)騰 趙斌 黃俊東 劉澤田

摘 ?要：為了有效求解旅行商問題，本文提出了一種基于T分布的改進(jìn)蟻群算法。針對(duì)基本蟻群算法易陷入局部最優(yōu)、尋優(yōu)精度低等缺陷，在優(yōu)化過程中，在信息素更新原則上，引入T分布，有益于基本蟻群算法彌補(bǔ)其不足。在基本蟻群算法中增加了信息素的突變，使得螞蟻群的多樣性提高，從而跳出局部最優(yōu)的限制。與此同時(shí)，T-ACO算法在旅行商問題搜尋精度與收斂速度方面也得到了提高。對(duì)T-ACO求解旅行商問題的性能進(jìn)行了實(shí)驗(yàn)仿真，實(shí)驗(yàn)分析表明，T-ACO算法有更好的尋優(yōu)能力。

關(guān)鍵詞：T分布;蟻群算法;旅行商問題;優(yōu)化

中圖分類號(hào)：TP391.9 ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

1 ? 引言（Introduction）

旅行商問題由Ramser B博士在1959年根據(jù)車輛路徑的選擇問題提出，該問題屬于數(shù)學(xué)領(lǐng)域的經(jīng)典問題。TSP問題的實(shí)質(zhì)為一個(gè)供貨商為不同的需求客戶送貨，要求配送路徑不可以重復(fù)的情況下，選擇路程最短的路徑作為最終的配送路徑[1]。眾多學(xué)者已經(jīng)證明了TSP問題是一個(gè)經(jīng)典的NP-hard問題。因此，近些年來，學(xué)者都將研究的重點(diǎn)放在求解TSP問題的算法設(shè)計(jì)上。目前解決TSP問題的方法大致分為兩種，一種是包括分支定界法、線性規(guī)劃法和動(dòng)態(tài)規(guī)劃法在內(nèi)的啟發(fā)式搜索算法[2]，另外一種是包括模擬退火算法[3]、禁忌搜索算法[4]、遺傳算法[5]、蟻群算法[6]、遺傳算法[7]，以及粒子群算法[8]等的人工智能優(yōu)化算法。由于現(xiàn)在有眾多實(shí)際問題可以轉(zhuǎn)化為TSP模型[9]，因而TSP問題諸如電網(wǎng)規(guī)劃[10]、網(wǎng)絡(luò)優(yōu)化[11]、交通運(yùn)輸[12]、物流配送[13]等重要領(lǐng)域都有著廣泛的應(yīng)用。

為了有效求解旅行商問題，本文提出了一種基于T分布的改進(jìn)蟻群算法。針對(duì)基本蟻群算法易陷入局部最優(yōu)、尋優(yōu)精度低等缺陷，在優(yōu)化過程中，在信息素更新原則上，引入T分布，有益于基本蟻群算法彌補(bǔ)其不足。在基本蟻群算法中增加了信息素的突變，使得螞蟻群的多樣性提高，從而跳出局部最優(yōu)的限制。與此同時(shí)，T-ACO算法在旅行商問題搜尋精度與收斂速度方面也得到了提高。對(duì)T-ACO求解旅行商問題的性能進(jìn)行了實(shí)驗(yàn)仿真，實(shí)驗(yàn)分析表明，T-ACO算法有更好的尋優(yōu)能力。

2 ? 旅行商問題（Traveling salesman problem）

旅行商問題可以簡單描述為在給定的個(gè)城市里，每個(gè)城市只經(jīng)過一次，然后回到出發(fā)點(diǎn)，找出使該回路最短的路徑的問題。TSP問題的數(shù)學(xué)模型如下[14]：

式中，表示指定的點(diǎn)集;表示邊集;表示賦值圖;表示點(diǎn)到點(diǎn)的距離;表示點(diǎn)在回路路徑上，表示不在回路路徑上;表示的子圖，對(duì)應(yīng)的約束條件保證沒有任何子回路解的產(chǎn)生。旅行商問題的目的是為了獲得一個(gè)最優(yōu)回路，在該回路上，除了起點(diǎn)之外的每一個(gè)點(diǎn)只能經(jīng)過一次。

3 ? T-ACO算法（T-ACO algorithm）

3.1 ? T分布

T分布又被稱為學(xué)生分布，威廉·戈塞于1908年[15]首先推導(dǎo)發(fā)表，自由度為的T分布的概率密度函數(shù)為：

根據(jù)式（5）可以卡看出，T分布的分布曲線與參數(shù)自由度有關(guān)。若越小，則T分布曲線就越平坦。若分布曲線中間部分越平坦，則多對(duì)應(yīng)兩側(cè)的尾部的曲線就會(huì)凸起的越高。這就存在兩種特殊的情況，一種情況為時(shí)，T分布曲線為柯西分布曲線。另外一種情況為時(shí)，T分布曲線為高斯分布曲線。T分布變異恰好融合了柯西分布變異和高斯分布變異的特點(diǎn)，通過不斷改變自由度參數(shù)的值可以獲得不同變異幅度。

3.2 ? 基于T分布的蟻群算法

基本蟻群算法是對(duì)螞蟻的生物學(xué)原理進(jìn)行模擬后的一種人工智能優(yōu)化算法?；鞠伻核惴ǜ鶕?jù)信息素遺留的多少來判定選擇的路徑，路徑上遺留的信息素越多，則該路徑被選擇的概率就越大。

基本蟻群算法易陷入局部最優(yōu)、尋優(yōu)精度低等缺陷，為了克服上述缺陷，將T分布引入信息素更新中。由于T分布具有較好的擾動(dòng)作用，使得群體多樣性增加，因此能夠提高算法的收斂速度，且不受局部最優(yōu)的限制，增加尋得全局最優(yōu)解概率。

為了提高收斂速度，可事先確定一個(gè)閾值，以避免螞蟻周游一次后，較差解所帶來的無效搜索。同時(shí)，為避免蟻群算法陷入局部最小，在調(diào)整信息素時(shí)，引入T分布，用以跳出局部最小點(diǎn)。改進(jìn)后的各條路徑上的信息素調(diào)整為

其中，表示信息素?fù)]發(fā)程度，;表示所有螞蟻在節(jié)點(diǎn)與節(jié)點(diǎn)間的信息素濃度的總和;表示第只螞蟻在節(jié)點(diǎn)和節(jié)點(diǎn)之間路徑上釋放的信息素濃度;為螞蟻循環(huán)一次釋放的信息素總量，的大小對(duì)算法的收斂速度有影響;為第只螞蟻?zhàn)哌^的路徑長度;為T分布變量。

3.3 ? 求解步驟

步驟1 參數(shù)初始化，包括、、及等蟻群算法參數(shù)以及T分布變異的特征參數(shù)。

步驟2 令，為迭代次數(shù)，將只螞蟻隨機(jī)放在座城市。

步驟3 根據(jù)式（9）計(jì)算螞蟻的轉(zhuǎn)移概率，選擇并移動(dòng)到下一個(gè)城市，同時(shí)將加入到中。

其中，為信息素重要程度因子，反映螞蟻間的協(xié)作能力;為啟發(fā)函數(shù)重要程度因子，反映螞蟻對(duì)于啟發(fā)信息的重視程度;為啟發(fā)函數(shù)表示螞蟻從節(jié)點(diǎn)轉(zhuǎn)移到節(jié)點(diǎn)的期望，，表示兩點(diǎn)間的距離，為螞蟻待訪問的節(jié)點(diǎn)集合。

步驟4 是否滿。若為否，回到步驟3，否則，繼續(xù)步驟4。

步驟5 按式（6）—式（8）進(jìn)行T分布信息素的全局更新。

步驟6 判斷是否，若為是，重復(fù)步驟3—步驟6，否則，結(jié)束迭代，輸出最優(yōu)解。

4 ? 實(shí)驗(yàn)仿真（Experimental simulation）

為了驗(yàn)證算法的有效性，利用TSPLIB標(biāo)準(zhǔn)庫中的berlin52、eil76及RAT99三個(gè)測試集進(jìn)行算法性能測試[16]。設(shè)置最大迭代次數(shù)，信息素重要程度因子，啟發(fā)函數(shù)重要程度因子，信息素全局揮發(fā)因子，信息素釋放總量。表1為在重復(fù)實(shí)驗(yàn)30次的情況下，ACO算法及T-ACO算法在三個(gè)測試集所獲得最優(yōu)解、最差解和平均值。表2為ACO算法及T-ACO算法在三個(gè)測試集所獲得成功率、平均收斂代數(shù)及標(biāo)準(zhǔn)差。

從上述測試可以看出：在尋優(yōu)能力方面，T-ACO算法在最優(yōu)解、最差解及平均值都優(yōu)于ACO。在收斂速度方面，T-ACO的平均收斂代數(shù)少于ACO。在穩(wěn)定性方面，T-ACO標(biāo)準(zhǔn)差小于ACO。由此可以看出，T-ACO算法相對(duì)于ACO算法更有效。

5 ? 結(jié)論（Conclusion）

為了彌補(bǔ)基本蟻群算法的不足，將T分布引入到蟻群算法中，提出改進(jìn)的蟻群算法（T-ACO）。利用改進(jìn)的蟻群算法求解旅行商問題，并將其結(jié)果與基本蟻群算法進(jìn)行了對(duì)比對(duì)比發(fā)現(xiàn)，改進(jìn)的蟻群算法在求解旅行商問題上比基本蟻群算法更具有優(yōu)越性，具有更好的收斂性和更高的收斂精度。本文的研究仍存在一些不足，解決旅行商問題時(shí)，使用的對(duì)比算法較少，這是后續(xù)研究需要加入的部分。

參考文獻(xiàn)（References）

[1] 王凌.智能優(yōu)化算法及其應(yīng)用[M].北京：清華出版社，2001：

218-222.

[2] 李軍民，林淑飛，高讓禮.用混合遺傳算法求解多目標(biāo)問題TSP問題[J].西安科技大學(xué)學(xué)報(bào)，2006，26（4）：515-518.

[3] HE Qing，WU Yi-Le，XU Tong-Wei.Application of improved genetic simulated annealing algorithm in TSP optimization[J].Control and Decision，2018（2）：219-225.

[4]王宏斌，劉娜.基于優(yōu)先權(quán)編碼的改進(jìn)禁忌搜索算法求解TSP問題[J].物流科技，2017，40（6）：29-32.

[5] 施泰龍，鄭悠，王蔚，等.引入外來種群的禁忌遺傳混合算法求解TSP問題[J].寧波工程學(xué)院學(xué)報(bào)，2017，29（3）：20-25.

[6] 許凱波，魯海燕，程畢蕓，等.求解TSP的改進(jìn)信息素二次更新與局部優(yōu)化蟻群算法[J].計(jì)算機(jī)應(yīng)用，2017，37（6）：1686-1691.

[7] 張勇，高鑫鑫，王昱潔.基于SFLA-GA混合算法求解時(shí)間最優(yōu)的旅行商問題[J].電子與信息學(xué)報(bào)，2018，40（2）：363-370.

[8] 裴皓晨，婁淵勝，葉楓，等.一種求解旅行商問題的改進(jìn)混合粒子群算法[J].計(jì)算機(jī)與數(shù)字工程，2018，46（2）：218-235.

[9] Cavdar B，Sokol J.A distribution-free TSP tour length estimation model for random graphs[J].European Journal of Operational Research，2015，243（2）：588-598.

[10] 王賽一，王成山.遺傳禁忌混合算法及其在電網(wǎng)規(guī)劃中的應(yīng)用[J].電力系統(tǒng)自動(dòng)化，2004，28（20）：43-46.

[11] 沐士光.遺傳算法在網(wǎng)絡(luò)優(yōu)化問題中的研究與應(yīng)用[J].計(jì)算機(jī)仿真，2010，27（5）：128-131.

[12] 鐘石泉，杜綱.基于核心路徑禁忌算法的開放式車輛路徑問題研究[J].計(jì)算機(jī)集成制造系統(tǒng)，2007，13（4）：827-832.

[13] 王華東，李巍.粒子群算法的物流配送路徑優(yōu)化研究[J].計(jì)算機(jī)仿真，2012，29（5）：243-246.

[14] 鄧義成，任聲策，殷旅江.基于改進(jìn)果蠅算法的旅行商問題[J].蘭州理工大學(xué)學(xué)報(bào)，2016，42（4）：109-113.

[15] 茆詩松.概率論與數(shù)理統(tǒng)計(jì)教程[M].北京：高等教育出版社，2004：22-28.

[16]TSPLIB[EB/OL].http：//comopt.ifi.uni-heidelberg.de/software/TSPLIB95/，2016-12-10.

作者簡介：

費(fèi) ? 騰（1983-），女，博士，副教授.研究領(lǐng)域：智能計(jì)算與群智能算法.

趙 ? 斌（1983-），男，本科，講師.研究領(lǐng)域：算法研究.

黃俊東（1999-），男，本科生.研究領(lǐng)域：自動(dòng)化設(shè)計(jì).

劉澤田（1999-），男，本科生.研究領(lǐng)域：智能算法.