混合伊藤算法求解多尺度著色旅行商問題

韓舒寧，徐敏，董學士*，林青，沈凡凡

（1.青島大學計算機科學技術學院，青島 266071；2.長江航道規(guī)劃設計研究院，武漢 430040；3.南京審計大學信息工程學院，南京 211815）

0 引言

目前關于著色旅行商問題（Colored Traveling Salesman Problem，CTSP）的研究主要包括：利用遺傳算法（Genetic Algorithm，GA）、貪心法遺傳算法（Genetic Algorithm with Greedy initialization，GAG）、爬山法遺傳算法（Hill Climbing Genetic Algorithm，HCGA）和模擬退火遺傳算法（Simulated Annealing Genetic Algorithm，SAGA）等來求解CTSP［1-2］，而且還對CTSP 進行了擴展，提出了連續(xù)著色旅行商問題（Serial Colored Traveling Salesman Problem，SCTSP）［3］；將離散伊藤算法（Discrete IT? algorithm，DIT?）用于求解小尺度CTSP（即CTSP 城市數(shù)小于等于101）［4］；探討了伊藤算法（IT? algorithm）的收斂性與收斂速度，并將其應用于求解旅行商問題（Traveling Salesman Problem，TSP）［5］；利用基于伊藤過程的混合算法求解著色瓶頸旅行商問題［6］，并將混合遺傳算法和伊藤算法應用于求解多平衡旅行商問題［7］；結合均勻設計（Uniform Design，UD）與混沌理論［8］來對蟻群（Ant Colony Optimization，ACO）算法的參數(shù)進行優(yōu)化；探討了基于UD 的GA 與ACO 算法求解TSP 參數(shù)優(yōu)化［9］；設計了一種基于多任務學習的ACO 求解CTSP［10］；將CTSP 擴展到大規(guī)模，并應用一種改進的蜂群算法求解大尺度CTSP［11］；給出了一種基于伊藤過程的遺傳算法以解決大尺度的著色平衡TSP［12］；提出了一種變量鄰近搜索的混合遺傳算法求解多尺度多瓶頸TSP［13］；應用一種基于種群的增量學習算法求解一類連續(xù)CTSP，并設計了一種變量鄰近搜索算法解決CTSP 變種問題［14］；應用三角網(wǎng)可變鄰域搜索方法求解大規(guī)模一般CTSP（general CTSP）［16］等。

伊藤算法是由董文永等［5］首次提出的一種群體智能算法，可用伊藤隨機積分的方法建立該算法的動力學方程，而漂移和波動操作是全局優(yōu)化的關鍵點。由于伊藤算法在求解組合優(yōu)化問題具備一定的優(yōu)勢，因此本文結合CTSP 的特點，設計了一種基于UD 融合IT? 和ACO 的混合伊藤算法（Hybrid IT? Algorithm with Uniform Design，UDHIT?）來求解該問題，并將研究問題的尺度擴展到大尺度，即CTSP 的城市數(shù)目大于101。本文主要工作如下：用粒子來表示CTSP 的解，一定量的粒子可以構成粒子系統(tǒng)，并應用伊藤隨機積分的方法建立算法的動力學方程，每個粒子的運動包括漂移和波動兩種。為了使伊藤算法能夠求解組合優(yōu)化問題，UDHIT? 首先借鑒ACO 的思想構建產(chǎn)生CTSP 的可行解的概率生成模型，然后采用伊藤算法的漂移和波動算子來更新，如此循環(huán)，直到找到滿意的解為止。實驗結果表明，UDHIT?求解CTSP 的最優(yōu)解和平均解要優(yōu)于對比算法。

1 混合伊藤算法求解CTSP

1.1 基于圖的概率生成模型

混合伊藤算法UDHIT? 采用城市數(shù)排列為編碼方法［4］。對于組合優(yōu)化問題，使用ACO 的基于圖的概率生成模型來構建一個可行解的方法已被證實是可行的，因此，UDHIT?使用該方法來構建一個CTSP 的訪問序列。例如一個CTSP實例，每條i到j的邊有兩個影響因素：一個是活動強度，由τ（i，j）決定；另一個是距離，由d（i，j）表示。從起始點開始去生成一個可行解，ACO 概率選擇公式如下所示：

其中：η（i，j）表示距離d（i，j）的倒數(shù)；tabu表示禁忌表，用來存儲已被訪問的城市；α是在選擇概率中控制邊權重的參數(shù)，β為控制可見度的參數(shù)。用ACO 的思想構建CTSP 可行解的步驟［4］如下所示：

算法1 ACO 構建CTSP 可行解。

1.2 UDHIT?設計

設計UDHIT? 共有五個部分，包括粒子半徑、環(huán)境溫度、活動強度、漂移算子和波動算子。該算法具體設計如下：

1）粒子半徑。式（2）指適應度值與粒子半徑的關系，適應度值越好，粒子半徑會越大，活動強度會越弱。

其中：x表示當前種群的一個粒子，f（x）代表適應度值，g（x）表示單調(diào)函數(shù)。N個當前種群的粒子根據(jù)適應度值的等級按照從最好到最差的順序分類，結果用x1，x2，…，xN來表示。粒子半徑由下列公式［6-7］計算：

其中：rmax和rmin分別表示最大和最小的半徑，所有的半徑被均勻分布在rmax和rmin之間。如果是缺省值，rmax設置為1，rmin設為0。

2）環(huán)境溫度。環(huán)境溫度可以用下面的方法來計算：

其中：Ti表示第i個規(guī)劃時間的溫度；ρ表示退火系數(shù)，它能控制溫度降低的速度，缺省值的情況下ρ=0.9。

3）活動強度。根據(jù)愛因斯坦的大分子運動和粒子熱力學運動定律，粒子活動強度與粒子半徑成反比，與溫度成正比，因此當前種群的粒子xi的活動強度δi可由式（5）［6-7］來計算：

其中ri表示粒子xi的半徑。

4）漂移和波動算子。漂移可以吸引粒子向最優(yōu)粒子（吸引元）移動，在求解過程中，可增加被最優(yōu)粒子所訪問的路徑信息素濃度；波動是一種受環(huán)境影響的隨機分布，在環(huán)境中，它隨機選擇一些路徑來增加信息素濃度。所有路徑信息濃度將會蒸發(fā)以保持整個信息素濃度的平衡。具體設計步驟如下所示：

a）所有路徑的活動強度τ將蒸發(fā)，其中，ρ是揮發(fā)因子。

b）所有的粒子按照適應度值來分類，最小的設置為最好，因此，第一個粒子是當前最好的粒子，其他的粒子會向它漂移。

c）按照上面的a）與b）順序，更新每個粒子的解。

漂移算子可通過式（7）更新當前路徑和最優(yōu)解路徑上的活動強度τ。其中：σ表示當前解，使活動強度δi等于信息素增量δ；σ′表示當前最好的粒子，或當前最好解。

UDHIT? 波動算子如式（8）所示，以求解CTSP 為例，城市之間路徑的活動強度用τ表示，當前粒子漂移強度為δ，σ″代表未被訪問的路徑，漂移強度（信息素增量）等于活動強度δi，rand（）為隨機函數(shù)，可產(chǎn)生一個［0，1）的隨機數(shù)，p為選擇隨機路徑的概率。

1.3 UDHIT?的步驟

UDHIT? 有漂移和波動兩個操作，漂移運動表示每個粒子向自己的吸引元運動，漂移強度函數(shù)依賴于它的適應度值、半徑和環(huán)境溫度。波動強度函數(shù)依賴于粒子半徑、適應度值和環(huán)境溫度。UDHIT? 的設計流程如下：

算法2 UDHIT? 算法求解CTSP。

2 實驗與結果分析

本文實驗所用數(shù)據(jù)一部分來自于文獻［1］，表1 中城市數(shù)量n從21～101 的數(shù)據(jù)即可以直接從該文中下載；另一部分數(shù)據(jù)，也就是城市數(shù)量大于101 的數(shù)據(jù)，是根據(jù)CTSP 的要求，由最原始的TSP 數(shù)據(jù)制作而成，該原始數(shù)據(jù)的名稱為TSPLIB，可由http：//people.sc.fsu.edu/～jburkardt/datasets/tsp/tsp.html 下載。

表1 實驗采用的CTSP實例Tab.1 Examples of CTSP in experiments

實驗計算機環(huán)境為：Intel Core i7-6700 CPU，3.40 GHz處理器和8 GB RAM。實驗對比算法DIT? 的參數(shù)設置［4］：種群M=30，α=5，β=3，隨機選擇概率p=0.3，初始溫度T=1 000，ACO 對應的參數(shù)設置與DIT? 相同。GA、GAG、HCGA和SAGA 的參數(shù)設置與文獻［1］中相同算法一致，算法參數(shù)設置情況為：種群大小=30，交叉概率=0.7，變異概率=0.1。SA 算法的初始溫度=100，總的冷卻時間=60，冷卻系數(shù)為0.9。HIT? 的參數(shù)隨機設置，UDHIT? 的參數(shù)設置通過UD方法得到。本文算法最大的未更新迭代次數(shù)為60，即算法終止條件。本實驗對比的GA、GAG、HCGA 和SAGA 均來自文獻［1］；DIT? 來自文獻［4］；ACO 來自文獻［9-10］；HIT? 是未采用UD 的混合伊藤算法。

為了有效驗證算法，本文實驗采用不同尺度的數(shù)據(jù)，CTSP 的實驗數(shù)據(jù)如表1 所示。

本文混合伊藤算法UDHIT? 的參數(shù)設置通過UD 獲得。UDHIT? 是一種基于ACO 的混合算法，其均勻設計參數(shù)選擇可參考ACO 實例［8］，算法均勻設計如表2 所示（括號內(nèi)值表示算法的參數(shù)組合數(shù)值）。表2 中，UDHIT? 共有15 種參數(shù)組合，采用這些參數(shù)設置，UDHIT? 求解101 個城市的CTSP的最優(yōu)解和平均求解質(zhì)量如表3 所示。從表3 可看出，第8種參數(shù)組合的UDHIT? 求解101 個城市CTSP 的最優(yōu)解和平均解最好，第3 種參數(shù)組合的伊藤算法求解101 個城市CTSP求解質(zhì)量最差，從而得出UDHIT? 的參數(shù)設置是種群M=30，α=4.48，β=4.77，隨機選擇概率p=0.448。

表2 參數(shù)組合的測試集實例Tab.2 Test set examples of parameters combination

表3 基于表2中15種參數(shù)組合的UDHIT? 求解101城市CTSP的最優(yōu)解與平均解 單位：kmTab.2 Optimal and average solutions of UDHIT? algorithm for 101-city CTSP on 15 parameters combinations from Tab.2 unit：km

表4～6分別為GA、GAG、HCGA、SAGA、ACO、HIT?、UDHIT? 等算法求解小、中、大尺度CTSP 的實驗結果對比，表中最優(yōu)解和平均解分別表示算法運行30 次的最優(yōu)解和平均解。

表4 各算法求解小尺度CTSP的最優(yōu)解與平均解 單位：kmTab.4 Optimal and average solutions of different algorithms for small scale CTSP unit：km

表5 各算法求解中尺度CTSP的最優(yōu)解與平均解 單位：kmTab.5 Optimal and average solutions of different algorithm for medium scale CTSP unit：km

表6 各算法求解大尺度CTSP的最優(yōu)解與平均解 單位：kmTab.6 Optimal and average solutions of different algorithm for large scale CTSP unit：km

從表4～6 可以看出，算法在求解CTSP 的求解精度相差不大，UDHIT? 的求解質(zhì)量優(yōu)于GAG、HCGA、SAGA、ACO、HIT? 等對比算法；當求解大尺度的CTSP 時，從求解質(zhì)量來看，UDHIT? 的效果最好，其次是DIT?、ACO 和SAGA。

UDHIT? 求解多尺度CTSP 的求解質(zhì)量不僅優(yōu)于對比文獻中的SAGA、HCGA、GAG、GA，也優(yōu)于DIT?、HIT?、ACO，表明基于均勻設計的混合伊藤算法UDHIT? 求解CTSP 是有效的。UDHIT? 是一種群體智能算法，運用均勻設計進行參數(shù)優(yōu)化，使用波動算子和漂移算子來完成解的更新，UDHIT?自身的特點使其有較強的自適應能力和全局搜索能力。

3 結語

針對傳統(tǒng)算法求解CTSP 容易陷入局部最優(yōu)等問題，本文給出了一種基于均勻設計的混合伊藤算法UDHIT? 求解CTSP，將模型的尺度從小尺度擴展到大尺度，通過實驗與分析表明，UDHIT? 求解多尺度CTSP 的求解質(zhì)量比SAGA、HCGA、GAG、DIT? 等算法有所改善。

后續(xù)的研究工作將集中在如下幾點：1）將UDHIT? 應用于其他組合優(yōu)化問題，進一步擴展其應用領域；2）分析該算法的作用機制，進一步從理論上探究該算法之所以比對比算法有效的原因；3）增強算法的參數(shù)自適應機制，進一步提高其求解問題的性能和效率［17-19］。