韓舒寧，徐敏，董學(xué)士*，林青，沈凡凡

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

0 引言

目前關(guān)于著色旅行商問題（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］，而且還對(duì)CTSP 進(jìn)行了擴(kuò)展，提出了連續(xù)著色旅行商問題（Serial Colored Traveling Salesman Problem，SCTSP）［3］；將離散伊藤算法（Discrete IT? algorithm，DIT?）用于求解小尺度CTSP（即CTSP 城市數(shù)小于等于101）［4］；探討了伊藤算法（IT? algorithm）的收斂性與收斂速度，并將其應(yīng)用于求解旅行商問題（Traveling Salesman Problem，TSP）［5］；利用基于伊藤過程的混合算法求解著色瓶頸旅行商問題［6］，并將混合遺傳算法和伊藤算法應(yīng)用于求解多平衡旅行商問題［7］；結(jié)合均勻設(shè)計(jì)（Uniform Design，UD）與混沌理論［8］來對(duì)蟻群（Ant Colony Optimization，ACO）算法的參數(shù)進(jìn)行優(yōu)化；探討了基于UD 的GA 與ACO 算法求解TSP 參數(shù)優(yōu)化［9］；設(shè)計(jì)了一種基于多任務(wù)學(xué)習(xí)的ACO 求解CTSP［10］；將CTSP 擴(kuò)展到大規(guī)模，并應(yīng)用一種改進(jìn)的蜂群算法求解大尺度CTSP［11］；給出了一種基于伊藤過程的遺傳算法以解決大尺度的著色平衡TSP［12］；提出了一種變量鄰近搜索的混合遺傳算法求解多尺度多瓶頸TSP［13］；應(yīng)用一種基于種群的增量學(xué)習(xí)算法求解一類連續(xù)CTSP，并設(shè)計(jì)了一種變量鄰近搜索算法解決CTSP 變種問題［14］；應(yīng)用三角網(wǎng)可變鄰域搜索方法求解大規(guī)模一般CTSP（general CTSP）［16］等。

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

1 混合伊藤算法求解CTSP

1.1 基于圖的概率生成模型

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

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

算法1 ACO 構(gòu)建CTSP 可行解。

1.2 UDHIT?設(shè)計(jì)

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

1）粒子半徑。式（2）指適應(yīng)度值與粒子半徑的關(guān)系，適應(yīng)度值越好，粒子半徑會(huì)越大，活動(dòng)強(qiáng)度會(huì)越弱。

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

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

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

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

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

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

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

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

b）所有的粒子按照適應(yīng)度值來分類，最小的設(shè)置為最好，因此，第一個(gè)粒子是當(dāng)前最好的粒子，其他的粒子會(huì)向它漂移。

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

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

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

1.3 UDHIT?的步驟

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

算法2 UDHIT? 算法求解CTSP。

2 實(shí)驗(yàn)與結(jié)果分析

本文實(shí)驗(yàn)所用數(shù)據(jù)一部分來自于文獻(xiàn)［1］，表1 中城市數(shù)量n從21～101 的數(shù)據(jù)即可以直接從該文中下載；另一部分?jǐn)?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 實(shí)驗(yàn)采用的CTSP實(shí)例Tab.1 Examples of CTSP in experiments

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

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

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

表2 參數(shù)組合的測(cè)試集實(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 的實(shí)驗(yàn)結(jié)果對(duì)比，表中最優(yōu)解和平均解分別表示算法運(yùn)行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ì)量?jī)?yōu)于GAG、HCGA、SAGA、ACO、HIT? 等對(duì)比算法；當(dāng)求解大尺度的CTSP 時(shí)，從求解質(zhì)量來看，UDHIT? 的效果最好，其次是DIT?、ACO 和SAGA。

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

3 結(jié)語(yǔ)

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

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