混合算法求解多目標平衡旅行商問題

董學士 董文永 王豫峰

(武漢大學計算機學院 武漢 430072) (dxs_cs@163.com)

混合算法求解多目標平衡旅行商問題

董學士 董文永 王豫峰

(武漢大學計算機學院 武漢 430072) (dxs_cs@163.com)

平衡旅行商問題(balanced traveling salesman problem, BTSP)是旅行商問題(traveling salesman problem, TSP)的變化模型，是另一種組合優化問題，可在汽輪機(gas turbine engines, GTE)等的優化問題中得到應用，但BTSP模型只能對含單個旅行商一個任務的優化問題建模，不能同時對含多個旅行商多任務的問題進行建模和優化.基于此，首次提出了一種多目標平衡旅行商問題(multi-objective balanced traveling salesman problem, MBTSP)模型,可建模含多個旅行商多任務的優化問題，具體可應用在含多個目標或個體的實際問題，例如含多個GTE的優化.相關文獻的研究已證實，伊藤算法和遺傳算法(genetic algorithm, GA)在求解組合優化問題中具有較好的性能，因此，應用混合伊藤算法(hybrid ITO algorithm, HITO)和混合遺傳算法來求解MBTSP問題.HITO通過蟻群算法(ant colony optimization, ACO)來產生基于圖的概率生成模型，再用伊藤算法的漂移和波動算子對該圖模型進行更新,從而得到MBTSP的最優解.對于混合遺傳算法，第一個用貪心法對遺傳算法進行改進，命名為貪心法遺傳算法(genetic algorithm with greedy initialization, GAG)，第二個用爬山算法優化遺傳算法，稱之為爬山法遺傳算法(genetic algorithm by hill-climbing, GAHC)，最后一個為模擬退火遺傳算法(genetic algorithm with simulated annealing, GASA).為了有效驗證該算法，使用小尺度到大尺度的不同規模MBTSP問題的數據進行實驗，結果表明：混合算法在求解MBTSP問題是有效的，并表現出不同的特點.

混合伊藤算法；混合遺傳算法；平衡旅行商問題；多目標平衡旅行商問題；蟻群算法

平衡旅行商問題(balanced traveling salesman problem, BTSP)是TSP的變化模型，可應用在汽輪機的優化等問題.但是BTSP模型只能對含一個旅行商單個任務的問題建模，沒法同時對含多個旅行商有多個單獨任務的問題進行建模和優化，基于此，本文提出了多目標的平衡旅行商問題(multi-objective balanced traveling salesman problem, MBTSP)，該模型可應用于含多個旅行商多任務的優化問題.相關文獻研究已證實伊藤算法和遺傳算法在求解組合優化問題上具有一定的優勢[1-2]，因此，本文將混合的伊藤算法(hybrid ITO algorithm, HITO)和遺傳算法(genetic algorithm, GA)應用到求解MBTSP問題，通過3種不同尺度的實驗表明各種算法在求解該問題上是有效的，并表現出不同的特點.

著色旅行商問題(colored traveling salesman problem, CTSP)[1-4]是近年被提出的一個問題，國內外在這方面的研究文獻較少，李俊等人[1,3]首次提出了CTSP，并將遺傳算法、貪心初始化的遺傳算法(genetic algorithm with greedy initialization, GAG)、爬山算法遺傳算法(genetic algorithm by hill-climbing, GAHC)、模擬退火遺傳算法(genetic algorithm with simulated annealing, GASA)應用在求解該問題中.CTSP是TSP和MTSP一種擴展模型，一定條件下它可以轉化成TSP和MTSP問題[1]；董文永等人將伊藤算法應用于求解CTSP問題[2].CTSP可在一定條件下(共享城市只含有起始點)轉換成多個單一的TSP[1]，然后改變目標函數可轉化為MBTSP.Ahmed將一種混合的遺傳算法應用于求解瓶頸旅行商問題(bottleneck traveling salesman problem)[5]；Plante等人給出可將瓶頸TSP和BTSP應用在汽輪機的導向葉片組的優化問題，其中，BTSP可應用于最小化平均噴嘴流的區域的最大平方差和最小平方差的差值[6]；另外，文獻[7-8]對BTSP的模型和應用做了更詳細的介紹.此外，利用混合算法或策略求解優化問題的工作包括：文獻[9]給出了混合策略在演化算法求解優化問題有效性的理論支持；文獻[10]將一種混合算法應用在求解有實際限制的車輛路徑問題；文獻[11-12]分別提出了一種混合算法用于求解多目標優化問題和最小權重支配集問題.

根據存在的問題和實際需求，本文提出了一種含多個旅行商多單獨任務的問題模型MBTSP，并首次將混合伊藤算法和遺傳算法應用其中.HITO采用ACO來生成基于圖的概率生成模型，然后應用伊藤算法的波動和漂移算子對該圖模型進行動態的更新來求得問題的最優解.混合遺傳算法應用貪心算法、爬山算法和模擬退火算法對基本的遺傳算法進行優化，通過不同尺度的實驗和分析表明，混合算法在求解問題上表現出不同的特點，GAHC在求解MBTSP問題的求解質量表現較好，在多數實例情況下，要好于其他對比算法，GASA和HITO在該方面也表現較優，HITO是ACO與伊藤算法的混合算法，在求解質量方面要好于ACO.

1 多目標平衡旅行商問題

1.1MBTSP問題

多目標平衡旅行商問題MBTSP含有m個旅行者和n個城市，m，n∈Z={1,2,3,…},m

城市數據集V被分成m個非空集.另一個數據集Vi,?i∈Zm={1,2,3,…,m}表示只有旅行者i才能訪問.定點depot表示站點或起始點，是旅行者i開始和結束的地方.

變量xijk(i≠j,i,j∈V,k∈Zm)為第k個旅行者是否經過城市i到j，變量uik(i∈V,k∈Zm)為第k個旅行者從起點到城市i的城市數目.

MBTSP的目標就是在G中尋找m個Hamilton回路，并使得所有旅行回路中的最大邊與最小邊的差最小，其中所有的城市只能被訪問一次.

MBTSP的目標函數為

Minf=maxedge(i,j)m-minedge(i,j)m，
i,j=0,1,2,…,n-1.

(1)

MBTSP限制條件為

(2)

式(2)為旅行者開始和結束于該起始點；

j≠i,i∈V{0}，

(3)

式(3)代表在每個問題中，除了起始點之外，每個城市只能被訪問一次.

1.2MBTSP與CTSP

MBTSP與CTSP的相同點是都為TSP的變化模型，都有多個旅行商，屬于NP難問題，都可對實際的優化問題進行建模，每個問題都有獨享城市，并且每個城市只能被訪問一次，MBTSP中的獨享城市與CTSP的獨享城市有相同的訪問規則和限制條件.不同點是：MBTSP與CTSP的目標函數不同,前者是使所有旅行回路的最大邊與最小邊的差值最小，而后者是使所有旅行回路的總的旅行距離最小.但是，CTSP在一定條件下，可轉化為MBTSP，當CTSP的共享城市為0，即只含一個起始點，CTSP會變成多個單一的TSP[1].然后改變多個單一TSP問題的目標函數，即最小化所有旅行回路的最大邊與最小邊的差，即可將CTSP轉化為MBTSP問題.

1.3MBTSP相關應用

文獻[6-8]已給出BTSP可在汽輪機GTE的噴嘴導葉片組(nozzel guide vane assembly problem, NGVAP)等優化問題得到應用，并可用于建模資源均勻分配的實際問題.但BTSP模型不能同時對含多個旅行者有多個任務的優化問題進行建模和優化，譬如含多個GTE的優化，本文提出的模型MBTSP可用來建模該類問題.MBTSP中的多目標可指多個旅行者和車輛等，本文給出了該問題的另外一類應用實例.例如有多個人或車輛需要對某個地區的資源或物資進行均勻的分配，該地區根據目標或個體(人或車輛)的數量被分成若干區域，每個個體將單獨負責一個區域，對該區域的資源進行均勻分配，一個區域包涵若干地點，一個地點被訪問之后，無需再次訪問，該問題有多個個體及其單獨的任務，其目標是完成任務并使資源均勻分配在整個地區.實例問題中的個體、任務和目標與MBTSP中的旅行商、任務和目標相匹配，因此該類問題可用MBTSP進行建模和優化.

2 混合算法求解MBTSP

2.1混合伊藤算法求解MBTSP

伊藤算法[13-17]是由武漢大學董文永等人提出，該算法用粒子來表示問題的解，其全局優化的關鍵點是漂移和波動算子.

2.1.1 概率生成公式

混合算法采用ACO路徑選擇策略來生成MBTSP解的構造方案[16-17]：

(4)

其中，α和β為控制參數，η(i,j)表示經驗能見度，也是距離的倒數；tabuk為禁忌表，在此表示已被旅行者走過的城市.

2.1.2 設計伊藤算法算子

1) 微粒半徑

在求解過程中需要對粒子解的適應度值排序，然后計算粒子半徑[16-17]：

(5)

式(5)中粒子的適應度值均勻地分布在粒子半徑界限值rmax和rmin之間.

2) 環境溫度

算法環境溫度的更新公式：

T(t)=ρT(t-1)，

(6)

其中，T(t)為t時刻的溫度，ρ為溫度下降的速率.

3) 漂移和波動算子的設計

本文用ACO的信息素濃度進行漂移和波動操作:1)漂移算子是指用吸引元來吸引當前粒子，從而增強其信息素濃度；2)因隨機擾動可以產生了波動，因此可以選取路徑增強其濃度；3)路徑信息素的揮發可使其濃度的大小均衡[16-17].

布朗運動中，微粒半徑和環境溫度控制粒子的運動能力，本文運動能力為[17]

(7)

其中，δ表示運動能力，λ為控制半徑運動能力的參數.

信息素更新[17]

τ(i,j)=(1-ρ)×τ(i,j)，

(8)

ρ為信息素揮發因子，1≤i≤n,1≤j≤n.

增強信息濃度：

τ(i,j)=τ(i,j)+δ,e(i,j)∈σ′，

(9)

其中，δ表示運動能力.

增強隨機路徑之上的濃度：

τ(i,j)=τ(i,j)+δ, ife(i,j)∈σ?∩rand()<ρ，

(10)

其中，ρ為選擇隨機路徑的概率，可調整波動強度的參數，rand()表示隨機產生0～1的函數.更新公式如下：

(11)

其中，σ?表示粒子和最優粒子都未經過的路徑.

2.1.3 算法設計步驟

混合伊藤算法的設計步驟如算法1所示[2].

算法1.Optimumsolution←HITO /*HITO求解問題的最優解*/

①MAX_NO_UPDATE_TIME;GEN; /*初始化*/

②α=4.7;β=3.8;p=0.55;T=1 000;Tlength=2; /*初始化參數*/

③ 讀取MBTSP數據集;

④ 初始化所有路徑的活動強度;

⑤ 初始化粒子群M;

⑥ whilenoUpdateTimes

⑦ 根據適應值fitness對所有粒子進行排序;

⑧currentBestSolution←particles[0]; /*首個粒子為當前最優解*/

⑨ ifallBestSolution.fitness

⑩noUpdateTimes←0; /*將未更新次數設置為0*/

算法1中MAX_NO_UPDATE_TIME表示最大未更新迭代次數，指算法在一定迭代次數后仍未求得更好解則終止，GEN為最大迭代次數.步驟①②是初始化階段，需對種群大小、終止條件、算法參數等進行初始化；步驟③～⑤讀取案例數據和產生初始的種群；下一步是算法的迭代過程，在此將執行漂移和波動，并找最優解，其中步驟⑦ 根據適應度對粒子進行分類，步驟⑧～表示找到當前最優解和更新最優解未變的次數；步驟～為更新算法的主操作，包括粒子半徑、環境溫度、漂移和波動強度等；最后，步驟～漂移和波動所有的粒子，構建新的解.算法1最大未更新迭代次數為停機條件的代碼，用最大迭代次數做終止條件時，將步驟⑥～的最大未更新迭代次數的地方對應的替換為迭代次數即可.

2.2混合遺傳算法

本文所用混合遺傳算法包括貪心法遺傳算法GAG、模擬退火遺傳算法GASA、爬山法遺傳算法GAHC[1].這3種混合算法以及遺傳算法均采用雙染色體編碼的方法來表示問題的解，其中一個染色體表示城市集合;另一個染色體為旅行者[1].混合遺傳算法都采用交叉算子和變異算子對城市染色體進行交叉和變異操作，通過該方式可以產生問題的最優解.在求解過程中適應度值可用來表示問題的解.

從圖1中可看出，3種混合的遺傳算法求解MBTSP的步驟比較相似，首先是編碼和產生初始種群，然后計算適應度值，并選擇最優個體a，之后運用貪心法、爬山法或模擬退火法進行優化，并產生個體b，如果b的適應度值大于a的適應度值，則將b替換a，如果滿足終止條件，輸出結果，否則，執行選擇、交叉和變異操作.

Fig. 1 The steps of GAG,GAHC and GASA for MBTSP圖1 GAG，GAHC和GASA求解MBTSP的步驟[1]

下面主要介紹GAG和GASA的步驟或原理，GAHC的具體介紹可參考CTSP文獻[1].

1) 貪心法遺傳算法GAG[1].在每個步驟中，由一個貪心算法做出的決策應該不能取得一個全局的最優解而只是一個局部的最優解.但是，因為它避免了去尋找最優解的一些可能的開銷，所以它能快速地得到一個滿意的解.在遺傳算法的第1步，我們使用它隨機產生初始種群的個體.一個高質量的初始種群，能加速遺傳算法的種群演化，快速獲得一個滿意的解，我們把這種改進的算法叫做貪心初始化的遺傳算法GAG.對于MBTSP問題，一個城市訪問需要滿足一個鄰近度，也就是，當前城市的旅行者選擇下一個最靠近它的城市，通過重新排列順序可優化一個解.GAG初始種群的產生過程為：

步驟1.確定當前初始種群的個體數量是否等于集合數量N，如果等于，則退出；

步驟2.隨機產生一個城市序列，隨機賦值獨享城市到指定的旅行者，結果序列命名為個體a；

步驟3.通過最短距離的方法來記錄a的城市序列，最小化開銷和獲得個體a′；

步驟4.檢測在種群中是否存在a′，如果存在返回步驟2，否則，將其插入到種群，并返回到步驟1.

2) 模擬退火遺傳算法GASA[1].是一種元啟發式算法，在大的搜索空間中，它適合于全局優化問題，該問題定位于給定函數的全局最優解的好的鄰近值.尤其在搜索過程中，根據Metropolis準則，它不僅接受一個好的解還接受一個差的解.它能跳出局部最優解的區域和保證它的收斂性能，模擬退火被用來改進上述GAG問題的收斂性.MBTSP的解和最優解類似于每個粒子的狀態和模擬退火中的最低的能量狀態.MBTSP的目標函數到最短路徑和模擬退火的能量函數相對應.通過設置合適的初始化溫度和按照某些設計的冷卻規劃，能解決MBTSP問題.

3 實驗與分析

本文的實驗是用Java平臺開發，運行環境為AMD AthlonTMⅡ X4 640 3.01 GHz處理器和3.25 GB內存.本文使用混合算法求解該問題，算法參數的選取依據大量的實驗，即該參數組合使算法求解問題的求解結果較好，混合伊藤算法和蟻群算法參數設置情況為：種群m=30，α和β分別為4.7與3.8，隨機選擇概率p=0.55，初始溫度T=1 000；混合遺傳算法與遺傳算法的參數與CTSP論文[1]對應的算法相同.實驗所有算法的最大未更新迭代次數設置為60，最大迭代次數為2 000.文獻[18-19]對算法對比的停機條件或終止條件做了介紹，并指出相同的適應函數評價次數也難以做到公平的比較.本文算法的停機條件相同，用兩種方式的停機條件分別做實驗，可使對比更全面，第1種終止條件是所有算法執行相同的最大迭代次數，第2種是執行相同的最大未更新迭代次數.表1為在3種不同尺度下不同算法求解MBTSP實驗所用數據.

Table 1 The Experiment Data for MBTSP表1 MBTSP的實驗數據

表1中n表示MBTSP的城市數量，m表示旅行者的數目，e表示共享的城市數量，s表示MBTSP起始點數.其中n的取值為21～665，m的取值在2～33.表1的數據是根據原始的TSP數據，按照MBTSP數據要求制作而成.

圖2表示當n=51和m=5時，以相同最大未更新迭代次數為終止條件的6種算法求解MBTSP的最優路線圖.該實例運行30次，分別求得6種算法求解MBTSP的最優解、最差解、平均求解質量(平均解)和求解時間.圖2中，6種算法求解MBTSP問題的具體情況為：1)GA.最優解24.12，最差解34.20，平均求解質量29.31，求解時間0.10；2)GAG.最優解21.92，最差解35.79，平均解29.78，求解時間0.10；3)GAHC.最優解18.00，最差解31.75，平均解26.45，求解時間0.13；4)GASA.最優解24.09，最差解31.57，平均解28.07，求解時間1.33；5)ACO.最優解51.03，最差解56.52， 平均解51.93，求解時間0.31；6)HITO.最優解19.69，最差解29.05，平均解23.21，求解時間0.73.從該實例的數據對比可看出，GAHC的最優解在6種算法中表現最好，HITO 求解該實例的平均解要好于GAHC和GASA 等算法，在6種算法中最優，SAGA求解所用時間最長，其次是HITO.

表2為不同尺度下，GA,GAG,GAHC求解MBTSP的實驗數據對比，其中GAG,GAHC來自CTSP的論文[1].求解質量或求解精度的單位km，求解時間單位s，n為城市數量，取值在21～665，m表示旅行者數，取值在2～33，最優(Best)、最差(Worst)、均值(Average)分別為算法運行30次的最優解、最差解和平均解，時間(Time)為算法運行30次的平均時間.從表2可以看出，3種算法之中，GAHC在3種尺度下的最優解、平均解最好，但GA和GAG的求解所用時間要少于GAHC.圖3和圖4是用表2和表3六種算法求解MBTSP的平均解的數據生成對比圖，通過圖中的曲線可以看出不同實例下平均解的大小.圖3～4為6種算法求解MBTSP的求解質量或求解精度數據對比圖.

圖3橫軸表示不同實例的序號，對應表1中的實例，縱軸表示平均求解質量或精度，該數據為表中的均值(平均解).從圖3可以看出GAHC的求解質量最優，GASA和HITO也表現出較好的性能，ACO在6種算法中的求解質量最差.圖4表示6種算法求解MBTSP的求解質量或求解精度實驗結果對比圖.

圖4中，橫軸表示不同實例的序號，對應表1中的實例，縱軸表示平均求解質量.從圖4可以看出，ACO的解的質量最差，GAHC的求解質量最好.

表3表示GASA,ACO和HITO求解MBTSP的實驗對比，Best,Worst,Average,Time分別表示算法運行30次的最優解、最差解、平均解和平均求解時間.

圖5和圖6表示算法求解MBTSP的求解時間對比情況，圖中橫軸表示不同實例的序號，對應表1中的實例，縱軸表示平均求解時間.該2圖是由表2和表3的時間數據生成.從圖5～6中可以看出，在3種不同尺度下，GASA和HITO所用時間較長，GAG和GA所用時間最短，GAHC求解時間較短.從表2～3和圖5～6中可以看出，4種混合算法之中，GAHC和GAG所用求解時間較短，要好于其他的對比混合算法GASA和HITO，HITO所用時間要長于ACO.

Fig. 2 Solving optimum routes of the case with n=51 and m=5 using GA,GAG,GAHC,GASA,ACO and HITO圖2 n=51,m=5時GA,GAG,GAHC,GASA,ACO和HITO求解MBTSP的最優路線圖

ScaleInstancenmGAGAGGAHCBest∕kmWorst∕kmAverage∕kmTime∕sBest∕kmWorst∕kmAverage∕kmTime∕sBest∕kmWorst∕kmAverage∕kmTime∕sSmall12125．9210．267．860．475．9210．267．610．475．9210．267．480．58231211．5318．4514．690．5410．9316．7214．310．5511．3815．0013．180．87331311．6620．0815．020．6311．6619．6815．500．6111．5820．5114．720．90441212．7017．9414．940．6713．0118．4315．630．6810．3413．7512．401．23541315．6121．4918．500．7214．6321．0718．050．7314．6319．4716．111．35641420．4726．1223．130．8319．3425．6622．530．8419．3425．2221．791．42751318．4027．1922．610．8518．9726．1222．150．8415．1222．7318．151．73Medium851418．0027．9422．970．9018．0029．1222．530．9015．5925．8820．531．82951519．3831．2325．930．9620．4331．7525．330．9718．0029．9823．761．881076324．6328．6226．791．1523．8330．4525．971．1511．9216．4715．012．831176426．6832．0429．641．2126．6834．0529．751．2217．2520．9319．483．151276521．8327．7825．051．2919．5528．2224．341．2616．2420．3618．153．301376632．8338．0035．381．3330．9537．3334．581．3129．0034．3931．343．4314101425．9431．8227．801．5525．9431．0527．671．5814．1722．2618．144．55Large15101534．0041．1737．741．5732．1439．9737．301．5820．0327．2221．114．6116101631．4436．8533．861．5931．4136．6333．801．6519．5423．4521．274．9817101728．3435．0431．241．7727．1434．9230．221．7623．1432．8226．645．211820699210．0010108．009782．133．769438．0010718．009860．803．728003．0011214．008641．1318．2219431129700．0011390．0010674．0010．129837．0011451．0010684．209．758892．0010191．009632．3675．0620547149457．0010924．0010073．7013．689367．0010793．0010100．4613．296685．008516．006998．10129．23216122311268．0012961．0012095．3616．9911215．0012844．0011960．3317．569154．0011070．009795．80194．62226653314402．0015281．0014847．1021．5914379．0015479．0014858．9320．8914127．0014825．0014590．56270．19

Fig. 3 The solving solution quality comparison of the algorithms for MBTSP圖3 算法求解MBTSP的求解質量對比圖

Fig. 4 The solving solution quality comparison of the algorithms for MBTSP圖4 算法求解MBTSP的求解質量對比圖

ScaleInstancenmGASAACOHITOBest∕kmWorst∕kmAverage∕kmTime∕sAverage∕kmTime∕sBest∕kmWorst∕kmAverage∕kmTime∕sSmall12125．926．986．069．1522．902．385．538．397．653．74231212．0215．1914．0412．4241．594．9313．2814．0413．407．68331312．5314．6513．8613．3243．944．2916．1418．7817．786．60441214．8217．6216．5317．1248．928．4216．6318．6417．1713．48541314．9118．7317．7818．2959．517．2019．6225．6221．8410．80641420．5222．9721．5319．3143．646．6520．3521．9120．769．84751322．0625．1323．6921．6159．7210．7522．9426．3925．2316．26Medium851420．3025．0723．6422．8755．189．9321．4024．1623．3714．44951522．2327．0125．0624．0651．889．5718．6121．6220．3313．681076323．7327．8926．4833．9859．5122．6423．9328．9027．8834．931176427．2131．5929．8435．7053．7620．5027．4130．3229．0530．861276523．6026．8125．5036．6155．5719．3024．0628．1725．8428．561376634．4436．9836．0037．9954．8618．6631．0039．2937．0927．3114101427．0129．9128．6843．6955．7234．3623．4227．2225．3753．80Large15101536．1439．0537．8445．8168．4432．2529．7836．4833．1848．7216101633．0534．9833．9947．7961．0130．6831．0336．6634．0246．1217101730．7434．8132．8749．6159．0530．1030．7236．5933．4644．551820697642．008921．008153．33113．1719126．00110．2010093．0012300．0011425．00172．0719431129184．0010535．009934．03267．6717664．00435．089877．0013940．0011367．36659．0320547147237．007591．007458．93379．6618556．00668．278192．0012971．0011270．301018．3121612238933．0011261．009744．53505．8418553．00803．2612081．0014368．0013566．131173．01226653314342．0015333．0014766．93667．1219113．00953．6215015．0016008．0015826．101346．53

Fig. 5 The time comparison of the algorithms for MBTSP圖5 算法求解MBTSP的求解時間對比

Fig. 6 The time comparison of the algorithms for MBTSP圖6 算法求解MBTSP的求解時間對比

為了充分驗證算法的有效性，本文運用求解TSP問題的文獻[20]給出的最優解方差PDbest和平均解方差PDav，對6種不同算法求解MBTSP問題進行顯著性分析.PDbest計算方法為算法當前最優解減去已知最優解，然后除以已知最優解，再乘以100；PDav計算方法是算法當前平均最優解減去已知平均最優解，然后除以已知平均最優解，再乘以100[20].

表4表示用最大未更新迭代次數為停機條件的GA,GAG,GAHC,GASA,ACO和HITO求解MBTSP的實驗結果對比數據.

本文選擇表2和表3的最優解和平均解的數據做方差分析，GA,GAG,GAHC,GASA,ACO和HITO求解MBTSP的方差數據，計算結果如表5所示.

表2和表3中，當前最優解為算法求解MBTSP的最優解，對應著表中相應算法的最優解，已知最優解為6種算法求解該問題的最優解的最優值，即6種算法求得最優解的最小值，表中GAHC最優解的最優值出現的次數最多；當前平均最優解是算法求解該問題的平均最優解，已知最優解為6種算法中求得的最好的平均最優解，表中6種算法中GAHC在該方面結果最好.在以上數據的基礎上，通過計算可求得6種不同算法求解MBTSP的方差.

表4表示用最大未更新迭代次數為停機條件的6種不同算法求解MBTSP問題的實驗對比數據，表中Average為算法運行30次的平均求解質量(平均解)，Time為算法運行30的平均求解時間.從表4中3種尺度的實驗數據對比可看出，在6種算法中，GAHC最好均值出現的次數最多，其次是GASA和HITO，HITO求解質量要好于ACO.從求解時間來看，GA,GAG和ACO求解該問題的運行時間較短.

Table 4 Experiment Data of Algorithms for MBTSP with Same Maximum No-update Iterations as Stopping Condition表4 相同最大未更新迭代次數為停機條件的算法求解MBTSP的實驗數據

Table 5 Experiment Deviation Data of Algorithms for MBTSP with Same Maximum Iterations as Stopping Condition表5 相同最大迭代次數為停機條件的算法求解MBTSP的實驗方差數據 km

表5表示GA,GAG,GAHC,GASA,ACO和HITO求解MBTSP的方差數據，表中Best為最優解方差PDbest，Average為平均解方差PDav，表中分別對小尺度、中尺度和大尺度不同算法求解該問題的方差數據求平均值，最后又給出3種尺度的方差數據總的平均值.從表5可以看出，GAHC的平均PDbest與PDav值最小，GA,GAG,GAHC的該平均值相差不大，HITO求解該問題的平均PDbest與PDav值小于ACO.

從本節實驗數據與分析可看出，在求解小尺度到大尺度的MBTSP問題時，GAHC的求解精度或求解質量優于其他6種算法，GASA與HITO在該方面也表現較好，從求解時間來看，GA,GAG與ACO的時間較短.從表2～5數據可以看出，各種算法在求解MBTSP時，使用不同尺度的實例，會表現出不同的性能，GAHC在求解精度或求解質量方面表現最好，在6種算法中，最優求解質量出現的次數最多.GAHC,GASA和HITO是較優的元啟發式算法，在求解組合優化問題中，表現出較好的性能，本文通過實驗與數據分析可看出，GAHC在求解MBTSP中求解質量表現最好，其次是GASA和HITO.在求解MBTS問題的不同尺度的實例時，6種算法表現出不同的特點.

HITO是一種較新的群體智能算法，該算法是蟻群算法與伊藤算法的混合算法，與ACO相類似，都是運用螞蟻覓食的原理設計相關的概率圖模型，但HITO與ACO不同，它可以利用伊藤算法的波動與漂移操作來更新圖模型，從而進一步提升了求解問題的能力.從本文的求解結果可以看出，HITO在求解MBTSP的求解質量要好于ACO.GAHC是一種爬山算法和遺傳算法結合后的混合算法，在求解組合優化問題中也表現出較好的性能，從本文實驗可看出，該算法在求解MBTSP的求解質量表現最好.

4 結語與展望

本文提出了一種新的組合優化問題模型，可對含有多個旅行商的優化問題建模和優化，為了擴展該問題模型的應用領域，研究和設計先進的算法求解MBTSP問題有一定的意義，因此，本文將混合伊藤算法和遺傳算法應用于求解該問題，通過實驗驗證與分析表明，6種算法在求解MBTSP問題上是有效的，GAHC在求解該問題的求解質量要優于其他的對比算法，HITO求解質量要好于ACO.

未來的研究工作主要從3方面開展：1)開發和研究更先進的算法，來求解MBTSP問題，使其在求解質量和求解速度方面有所提高；2)研究更大規模的MBTSP，分析各種算法在求解更大規模該問題的性能和規律；3)探索和研究MBTSP其他的應用和相關的變化模型，使其可以建模更加復雜的優化問題，并有更多的應用領域.

[1] Li Jun, Zhou Mengchu, Sun Qirui, et al. Colored traveling salesman problem[J]. IEEE Trans on Cybernetics, 2015, 45(11): 2390-2401

[2] Dong Wenyong, Cai Yongle, Wang Yufeng, et al. Discrete ITO algorithm to the coloured travelling salesman problem[J]. International Journal of Wireless and Mobile Computing, 2016, 11(2): 157-165

[3] Li Jun, Sun Qirui, Zhou Mengchu, et al. A new multiple traveling salesman problem and its genetic algorithm-based solution[C] //Proc of the 2013 IEEE Int Conf on Systems Man and Cybernetics. Piscataway, NJ: IEEE, 2013: 1-6

[4] Meng Xianghu, Li Jun, Zhou Mengchu, et al. Population-based incremental learning algorithm for a serial colored traveling salesman problem[J]. IEEE Trans System, Man, Cybernetics: System, 2016, PP(99): 1-12

[5] Ahmed Z H. A hybrid genetic algorithm for the bottleneck traveling salesman problem[J]. ACM Trans on Embedded Computing Systems, 2013, 12(1): No.9

[6] Plante R D, Lowe T J and Chhandrasekaran R. The product matrix traveling salesman problem: An application and solution heuristic[J]. Operations Research, 1987, 35(5): 772-783

[7] John L R. The bottleneck traveling salesman problem and some variants[D]. Burnaby, BC: Master of Science of Simon Fraser University, Cannada, 2010, 21-23

[8] John L R, Abraham P P. The balanced traveling salesman problem[J]. Computer & Operations Research, 2011: 868-875

[9] Qian Chao, Tang Ke, Zhou Zhihua. Selection hyper-heuristics can provably be helpful in evolutionary multi-objective optimization[G] //LNCS 9921: Proc of the 14th Int Conf on Parallel Problem Solving from Nature. Berlin: Springer, 2016: 835-846

[10] Zhang Defu, Cai Sifan, Ye Furong, et al. A hybrid algorithm for a vehicle routing problem with realistic constraints[J]. Information Science, 2017, 394/395: 167-182

[11] Lin Qiuzhen, Chen Jianyong, Zhan Zhihui, et al. A hybrid evolutionary immune algorithm for multiobjective optimization problems[J]. IEEE Trans on Evolutionary Computation, 2016, 20(5): 711-729

[12] Lin Geng, Zhu Wenxing, Ali M M. An effective hybrid memetic algorithm for the minimum weight dominating set problem[J]. IEEE Trans on Evolutionary Computation, 2016, 20(5): 892-906

[13] Dong Wenyong. The multi-objective ITO algorithms[C] //Proc of the 2nd Int Symp on Intelligence Computation and Applications (ISICA). Piscataway, NJ: IEEE, 2007: 21-23

[14] Dong Wenyong. Time series modeling based on ITO algorithm[C] //Proc of the 3rd Int Conf on Natural Computation. Piscataway, NJ: IEEE, 2007: 398-402

[15] Dong Wenyong, Lei M, Yu Ruiguo. BBOB-benchmarking: A new evolutionary algorithms inspired by ITO process for noiseless function tested[J]. Journal of Computational Information Systems, 2011: 2195-2203

[16] Dong Wenyong, Zhang Wensheng, Yu Ruiguo. Convergence and runtime analysis of ITO algorithm for one class of combinatorial optimization[J]. Chinese Journal of Computers, 2011, 34(4): 636-646 (in Chinese)(董文永, 張文生, 于瑞國. 求解組合優化問題伊藤算法的收斂性和期望收斂速度分析[J]. 計算機學報, 2011, 34(4): 636-646)

[17] Yi Yunfeng, Cai Yongle, Dong Wenyong, et al. Improved ITO for multiobjective real-time vehicle routing problem with customers satisfaction[J]. Acta Electronica Sinica, 2015, 43(10): 2053-2061 (in Chinese)(易云飛, 蔡永樂, 董文永, 等. 求解帶用戶滿意度的多目標實時車輛路徑問題的改進伊藤算法[J]. 電子學報, 2015, 43(10): 2053-2061)

[18] Engelbrecht A P. Fitness function evaluations: A fair stopping condition?[C] //Proc of IEEE Swarm Intelligence Symp on Swarm Intelligence. Piscataway, NJ: IEEE, 2014: 1-8

[19] Mernik M, Liu S H, Karaboga D, et al. On clarifying misconceptions when comparing variants of the artificial bee colony algorithm by offering a new implementation[J]. Information Science, 2015, 291: 115-127

[20] Zhang Hongguang, Zhou Jie. Dynamic multicale region search algorithm using vitality selection for traveling salesman problem[J]. Expert Systems with Applications, 2016, 60: 81-95

HybridAlgorithmsforMulti-ObjectiveBalancedTravelingSalesmanProblem

Dong Xueshi, Dong Wenyong, and Wang Yufeng

(ComputerSchool,WuhanUniversity,Wuhan430072)

Balanced traveling salesman problem (BTSP), a variant of traveling salesman problem (TSP), is another combination optimization problem, which can be applied in many fields such as the optimization problem for gas turbine engines (GTE). BTSP can only model optimization problems with the single traveling salesman and task, but can’t model and optimize the problem with multiple salesmen and tasks at the same time. Therefore, this paper firstly provides a multi-objective balanced traveling salesman problem (MBTSP) model, which can model the optimization problems with multiple salesmen and tasks. Specifically it can be applied to the real-world problems with multiple objectives or individuals, for example, the optimization for multiple GTE. Some literatures have proved that ITO algorithm and genetic algorithms can show better performance in solving combination optimization problems, therefore, the paper utilizes the hybrid ITO algorithm (HITO) and hybrid genetic algorithm (GA) to solve MBTSP. For HITO, it utilizes ant colony optimization (ACO) to produce a probabilistic generative model based on graph, and then uses the drift and volatility operators to update the model, and obtains optimum solution. For the hybrid GA, the first is improved by greedy method called GAG, the second GA is optimized by incorporating hill-climbing named GAHC, and the final one is GASA. In order to effectively test the algorithms, the paper makes extensive experiments using small scale to large scale MBTSP data. The experiments show that the algorithms are effective and reveal the different characteristics in solving MBTSP problem.

hybrid ITO (HITO) algorithm; hybrid genetic algorithms; balanced traveling salesman problem (BTSP); multi-objective balanced traveling salesman problem (MBTSP); ant colony optimization (ACO)

Dong Xueshi, born in 1985. PhD candidate in Computer School, Wuhan University. His main research interests include intelligent computing and simulation optimization.

Dong Wenyong, born in 1973. Professor in Computer School, Wuhan University. His main research interests include intelligent computing, system control and simulation optimization.

Wang Yufeng, born in 1982. PhD candidate in Computer School, Wuhan University. His main research interests include intelligent computing and simulation optimization.

2017-05-23；

：2017-06-25

國家自然科學基金項目(61672024,61170305) This work was supported by the National Natural Science Foundation of China (61672024, 61170305).

董文永(dwy@whu.edu.cn)

TP301