混合算法求解多目標(biāo)平衡旅行商問題

董學(xué)士 董文永 王豫峰

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

混合算法求解多目標(biāo)平衡旅行商問題

董學(xué)士 董文永 王豫峰

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

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

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

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

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

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

1 多目標(biāo)平衡旅行商問題

1.1MBTSP問題

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

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

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

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

MBTSP的目標(biāo)函數(shù)為

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

(1)

MBTSP限制條件為

(2)

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

j≠i,i∈V{0}，

(3)

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

1.2MBTSP與CTSP

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

1.3MBTSP相關(guān)應(yīng)用

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

2 混合算法求解MBTSP

2.1混合伊藤算法求解MBTSP

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

2.1.1 概率生成公式

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

(4)

其中，α和β為控制參數(shù)，η(i,j)表示經(jīng)驗?zāi)芤姸龋彩蔷嚯x的倒數(shù)；tabuk為禁忌表，在此表示已被旅行者走過的城市.

2.1.2 設(shè)計伊藤算法算子

1) 微粒半徑

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

(5)

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

2) 環(huán)境溫度

算法環(huán)境溫度的更新公式：

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

(6)

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

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

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

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

(7)

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

信息素更新[17]

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

(8)

ρ為信息素?fù)]發(fā)因子，1≤i≤n,1≤j≤n.

增強信息濃度：

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

(9)

其中，δ表示運動能力.

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

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

(10)

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

(11)

其中，σ?表示粒子和最優(yōu)粒子都未經(jīng)過的路徑.

2.1.3 算法設(shè)計步驟

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

算法1.Optimumsolution←HITO /*HITO求解問題的最優(yōu)解*/

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

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

③ 讀取MBTSP數(shù)據(jù)集;

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

⑤ 初始化粒子群M;

⑥ whilenoUpdateTimes

⑦ 根據(jù)適應(yīng)值fitness對所有粒子進行排序;

⑧currentBestSolution←particles[0]; /*首個粒子為當(dāng)前最優(yōu)解*/

⑨ ifallBestSolution.fitness

⑩noUpdateTimes←0; /*將未更新次數(shù)設(shè)置為0*/

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

2.2混合遺傳算法

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

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

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

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

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

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

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

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

3 實驗與分析

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

Table 1 The Experiment Data for MBTSP表1 MBTSP的實驗數(shù)據(jù)

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

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

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

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

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

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

圖5和圖6表示算法求解MBTSP的求解時間對比情況，圖中橫軸表示不同實例的序號，對應(yīng)表1中的實例，縱軸表示平均求解時間.該2圖是由表2和表3的時間數(shù)據(jù)生成.從圖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的最優(yōu)路線圖

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的求解質(zhì)量對比圖

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

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]給出的最優(yōu)解方差PDbest和平均解方差PDav，對6種不同算法求解MBTSP問題進行顯著性分析.PDbest計算方法為算法當(dāng)前最優(yōu)解減去已知最優(yōu)解，然后除以已知最優(yōu)解，再乘以100；PDav計算方法是算法當(dāng)前平均最優(yōu)解減去已知平均最優(yōu)解，然后除以已知平均最優(yōu)解，再乘以100[20].

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

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

表2和表3中，當(dāng)前最優(yōu)解為算法求解MBTSP的最優(yōu)解，對應(yīng)著表中相應(yīng)算法的最優(yōu)解，已知最優(yōu)解為6種算法求解該問題的最優(yōu)解的最優(yōu)值，即6種算法求得最優(yōu)解的最小值，表中GAHC最優(yōu)解的最優(yōu)值出現(xiàn)的次數(shù)最多；當(dāng)前平均最優(yōu)解是算法求解該問題的平均最優(yōu)解，已知最優(yōu)解為6種算法中求得的最好的平均最優(yōu)解，表中6種算法中GAHC在該方面結(jié)果最好.在以上數(shù)據(jù)的基礎(chǔ)上，通過計算可求得6種不同算法求解MBTSP的方差.

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

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

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

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

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

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

4 結(jié)語與展望

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

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

[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)(董文永, 張文生, 于瑞國. 求解組合優(yōu)化問題伊藤算法的收斂性和期望收斂速度分析[J]. 計算機學(xué)報, 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)(易云飛, 蔡永樂, 董文永, 等. 求解帶用戶滿意度的多目標(biāo)實時車輛路徑問題的改進伊藤算法[J]. 電子學(xué)報, 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

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

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

TP301