最大最小目標(biāo)的多旅行商問題求解①

袁 志

(廣州大學(xué) 華軟軟件學(xué)院, 廣州 510990)

1 概述

多旅行問題(Multiple Traveling Salesmen Problem,MTSP)是TSP的擴(kuò)展. 給定一個(gè)中心城市和n個(gè)訪問城市, 將訪問城市分配給m個(gè)旅行商, 每個(gè)旅行商從中心城市出發(fā)巡游若干訪問城市后回到中心城市, 要求所有旅行商經(jīng)過的總路程(total)盡量小且其中最長環(huán)路的長度(max)盡量小. 事實(shí)上, 無法保證total和max兩個(gè)目標(biāo)同時(shí)達(dá)到最小, 本文尋求最小化max, 稱之為MinMax-MTSP. 這一類問題的算法可應(yīng)用在工作均衡調(diào)度, 印刷機(jī)調(diào)度、衛(wèi)星測量系統(tǒng)設(shè)計(jì)、機(jī)器人應(yīng)急響應(yīng)[1–3]等領(lǐng)域.

城市集合C ={c0,c1,c2,…,cn}, c0表示中心城市, c1,c2,…,cn表示訪問城市. 距離矩陣D={di,j}, di,j為ci到cj的距離. 每條環(huán)路用城市號序列來編碼, 例如cycle =(0,1,2)表示 c0→c1→c2→c0. 圖1顯示了 n=10, m=3 的MinMax-MTSP的一個(gè)解(非最優(yōu)解), 其中的3條環(huán)路分別是(0,1,2), (0,5,4,3)和(0,6,7,8,9,10), 解表示為S=(0,1,2,0,5,3,4,0,6,7,8,9,10). MinMax-MTSP求解目標(biāo)是尋找S的最佳序, 使max最小.

將進(jìn)化算法與局部搜索算法結(jié)合來求解MTSP是近年來的主要方法. 一類是遺傳算法, Carter[4]提出了一種雙基因編碼(城市基因和組基因)的遺傳算法, 并提出了12個(gè)測試?yán)? Brown[5]提出一種分組遺傳算法.Yuan[6]在分組遺傳算法中引入了一種新的交叉算子(TCX), 提出了3個(gè)新的測試?yán)? Singh[7]改進(jìn)了分組遺傳算法(GGA-SS), 用組的rk值(rk=路徑長度/城市數(shù))衡量一個(gè)組屬于最優(yōu)解的可能性, rk值較大的組優(yōu)先保留在子代中, 其余一些零散的城市用貪心算法插入到各個(gè)組, 使用2-opt局部搜索算子進(jìn)行組內(nèi)優(yōu)化.另一類是群體智能算法, Liu[8]用蟻群算法求解MTSP;VENKATESH[9]提出了兩種蜂群算法(ABCFC、ABCVC) 和一種雜草入侵算法 (IWO), 同樣用2-opt進(jìn)行組內(nèi)優(yōu)化.

圖1 3個(gè)旅行商10個(gè)訪問城市的一個(gè)解

以上算法的一致性在于: 使用局部搜索算法來快速加速尋優(yōu)過程, 使用群體進(jìn)化算法不斷累計(jì)優(yōu)化結(jié)果. 這些算法采用2-opt作為局部搜索算子, 而且僅將2-opt作用于單條環(huán)路的優(yōu)化. 實(shí)際上, 在MTSP中, 可以將局部搜索從單條環(huán)路的優(yōu)化擴(kuò)展為兩條環(huán)路的重組優(yōu)化, 加速算法的尋優(yōu)過程(第2節(jié)討論). 這些算法主要依賴個(gè)體之間交換信息來完成迭代優(yōu)化, 很少考慮到局部搜索算子自身的特點(diǎn), 在進(jìn)化算法中根據(jù)局部搜索算子自身的特點(diǎn), 設(shè)計(jì)新的進(jìn)化機(jī)制, 是本文關(guān)注的另一個(gè)重要內(nèi)容(在第3節(jié)討論).

本文設(shè)計(jì)了一個(gè)新的局部搜索算子reverse/ move(轉(zhuǎn)置/移動(dòng)), 該算子既能進(jìn)行一條環(huán)路的優(yōu)化, 也能重組優(yōu)化兩條環(huán)路, 即便在一條環(huán)路上進(jìn)行優(yōu)化, 其能力也明顯好于2-opt; 在分析reverse/move算子特點(diǎn)的基礎(chǔ)上, 提出了“搜索-選優(yōu)-變異-搜索”策略, 設(shè)計(jì)了競爭搜索算法(Competitive Search Algorithm, CSA), 在文獻(xiàn)[4]和文獻(xiàn)[6]的15個(gè)測試?yán)线M(jìn)行實(shí)驗(yàn), 與文獻(xiàn)[6–9]進(jìn)行比較, CSA在計(jì)算結(jié)果上有明顯的改進(jìn).

2 局部搜索算子reverse/move

為了指導(dǎo)搜索過程, 需要對解有合適的評價(jià)方法.MinMax-MTSP的目標(biāo)是最小化max, 但注意到, 將目標(biāo)改為優(yōu)先最小化max, 其次最小化total, 有助于最小化max. 因?yàn)楹笳咭竺恳粭l環(huán)路自身次序最優(yōu), 在大多數(shù)情況下, 這有利于最小化max.

以圖1為例, 算法運(yùn)行到當(dāng)前步驟, (0,6,7,8,9,10)是最長環(huán)路, 次序已經(jīng)是最優(yōu); (0,5,3,4)是另外一條稍短的環(huán)路, 次序不是最優(yōu). 此時(shí)對(0,5,3,4)進(jìn)行優(yōu)化得到(0,3,4,5), 然后從(0,6,7,8,9,10)中移動(dòng)“6”到(0,3,4,5)可以得到(0,3,4,5,6), 這是一條新的最長環(huán)路,而且比前一條最長環(huán)路更短.

因此, 將解的適應(yīng)值設(shè)計(jì)為一個(gè)二元組(max,total), 規(guī)定: 解 S1優(yōu)于解 S2, 當(dāng)且僅當(dāng) (max1＜max2) 或(max1=max2且 total1＜total2).

本文局部搜索算子通過依次檢查S中的每一個(gè)位置來完成. 下文中, 將被檢查位置上的城市標(biāo)記為c1,它在S中的后一個(gè)城市標(biāo)記為c3, c1的鄰域N(c1)中的城市的標(biāo)記為c2, c4和c5分別是c2在S中的后一個(gè)城市和前一個(gè)城市. 按照Lin-kernighan算法的建議,N(c1)取離c1最近的6個(gè)城市.

我們的局部搜索方法是: 依次檢查S的每一個(gè)位置, 對于該位置上的城市c1, 對N(c1)中每一個(gè)c2, 做兩種嘗試: 先嘗試轉(zhuǎn)置c2與c3之間(包含c2與c3)的次序, 得到 S′, 如果 S′優(yōu)于 S, 則用 S′代替 S; 否則嘗試將c2移動(dòng)到 c1和 c3之間, 得到 S′, 如果 S′優(yōu)于 S, 則用S′代替S. S包含n+m個(gè)位置, 如果連續(xù)檢查n+m個(gè)位置都無法優(yōu)化 S, 算子停止. 轉(zhuǎn)置和移動(dòng)合稱“reverse/move”.

c2和c3可能位于S中的同一環(huán)路, 也可能位于兩條不同的環(huán)路, 以下分別進(jìn)行討論.

當(dāng)c2和c3在同一環(huán)路中, 轉(zhuǎn)置c2和c3之間的次序?qū)h除兩條邊并新增兩條邊, 效果如圖2(a), 例如:cycle=(0,1,2,3,4,5,6), c2=1, c3=5, reverse(cycle)=(0,5,4,3,2,1,6); 移動(dòng)c2將刪除三條邊并新增三條邊, 效果如圖2(b), 例如: cycle=(0,1,2,3,4,5,6), c2=1,c3=5, move(cycle)=(0,2,3,4,1,5,6).

當(dāng)c2和c3屬于分屬兩條環(huán)路. 轉(zhuǎn)置c2和c3之間的次序, 將對兩條環(huán)路進(jìn)行重組, 效果如圖3(a), 例如:S=(0,1,2,0,5,3,4,0,6,7,8,9,10), c2=1, c3=7,reverse(S)=(0,7,6,0,4,3,5,0,2,1,8,9,10). 移動(dòng) c2, 相當(dāng)于將c2從一條環(huán)路中移除, 插入到另一條環(huán)路, 效果如圖3(b), 例如: S=(0,1,2,0,5,3,4,0,6,7,8,9,10), c2=1, c3=7,move(s)=(0,2,0,5,3,4,0,6,1,7,8,9,10).

圖2 一條環(huán)路中的轉(zhuǎn)置/移動(dòng)

圖3 跨兩條環(huán)路的轉(zhuǎn)置/移動(dòng)

我們在經(jīng)典TSP的公開測試數(shù)據(jù)TSPLIB上比較reverse/move與2-opt. 經(jīng)典TSP問題相當(dāng)于m=1的MTSP問題, 其上的測試結(jié)果能夠反映局部搜索算子的尋優(yōu)能力. 對每個(gè)測試?yán)? 分別產(chǎn)生800個(gè)隨機(jī)的初始解, 然后各用reverse/move與2-opt兩種局部搜索進(jìn)行優(yōu)化, 得到800個(gè)最終解. 從兩個(gè)方面進(jìn)行比較: 1)環(huán)路長度(length)的平均值, 2) 檢查位置數(shù)(checkedpoints)的平均值, 結(jié)果如表1.

表1 reverse/move與2-opt的搜索能力比較

表1顯示, 對每一個(gè)測試?yán)? 兩種局部搜索算法在停止時(shí), reverse/move檢查的位置數(shù)略大于2-opt, 與此同時(shí), 在搜索的結(jié)果上, reverse/move的明顯好于2-opt.

3 競爭搜索算法

當(dāng)reverse/move算子停止搜索時(shí), 對所得到的解S, 選擇其中一個(gè)片段, 轉(zhuǎn)置其次序, 然后再執(zhí)行reverse/move, 可能得到更優(yōu)的解. 以圖4為例, 圖4(a)是reverse/move得到的一個(gè)解, 圖4(b)是一次轉(zhuǎn)置的結(jié)果, 圖4(c)和圖4(d)是再次執(zhí)行reverse/move的中間過程和結(jié)果.

圖4 轉(zhuǎn)置一個(gè)片段后再次執(zhí)行reverse/move

用一對城市號(cstart,cend)來標(biāo)記S中的一個(gè)片段,這樣的對共有(n+m)×(n+m-1)/2個(gè), 構(gòu)成S的候選對集. 用隨機(jī)方式來選擇一對城市, 轉(zhuǎn)置其所標(biāo)記的片段,然后再次執(zhí)行reverse/move, 可能有三種結(jié)果: 1) 得到更好的解, 2) 恢復(fù)到轉(zhuǎn)置之前的解, 3) 得到變差的解.每選出一對城市, 就從S的候選對集中將其刪除, 直到候選對集為空.

根據(jù)reverse/move的以上特點(diǎn), 我們提出一種群體迭代策略: “搜索-選優(yōu)-變異-搜索”, 用圖5 說明. 圖5中的橫坐標(biāo)是解空間, 縱坐標(biāo)是解的適應(yīng)值. 如果一組解經(jīng)過局部搜索得到相同的局部最優(yōu)解, 則將這組解集中在一個(gè)區(qū)域, 該區(qū)域中適應(yīng)值最小的解就是該區(qū)域的局部最優(yōu)解. 選擇最好的若干個(gè)局部最優(yōu)解, 對其進(jìn)行變異(隨機(jī)的片段轉(zhuǎn)置), 得到的一部分新的解將到達(dá)新的區(qū)域, 經(jīng)再次搜索得到新的局部最優(yōu)解. 如此迭代, 逐步提高局部最優(yōu)解的質(zhì)量, 直至最好的若干個(gè)局部最優(yōu)解的候選對集全部為空.

圖5 多個(gè)解經(jīng)過局部搜索得到相同的局部最優(yōu)解

基于這一策略, 我們設(shè)計(jì)了競爭搜索算法(CSA),如算法1.

算法1. CSA算法1) 設(shè)定種群規(guī)模p和選擇比例θ(θ建議取0.2), 隨機(jī)生成p個(gè)初始解, 對每個(gè)解執(zhí)行reverse/move.2) 對所有解按適應(yīng)值從小到大排序, 保留θ×p個(gè)排名靠前且互異的解.3) 對保留的解, 從其候選對集中隨機(jī)選(1–θ)/θ個(gè)城市對, 并從候選對集中刪除這些對; 對保留解, 分別轉(zhuǎn)置這些片段產(chǎn)生新的解.4) 在新的解上執(zhí)行reverse/move, 然后加入種群.5) 循環(huán)執(zhí)行2)到4), 直至所有保留解的候選集為空.6) 輸出群體中的最優(yōu)解.

CSA算法與保留精英的遺傳算法相似, 其特異性在于: 用局部搜索reverse/move取代雜交操作; 用最優(yōu)且互異的若干個(gè)體作為父代個(gè)體, 取代概率性選擇; 用固定的小尺度變異(轉(zhuǎn)置一個(gè)片段)替代概率性變異.

4 實(shí)驗(yàn)

我們用文獻(xiàn)[4]的12個(gè)測試?yán)臀墨I(xiàn)[6]的3個(gè)測試?yán)鳛閷?shí)驗(yàn)數(shù)據(jù). 文獻(xiàn)[4] 的12個(gè)測試?yán)械某鞘袛?shù)據(jù)是二維平面坐標(biāo), 包括MTSP-51的3個(gè)問題(m=3,m=5,m=10), MTSP-100的4個(gè)問題(m=3,m=5,m=10,m=20)和MTSP-150的5個(gè)問題(m=3,m=5,m=10,m=20,m=30), 用第一個(gè)城市作為中心城市. 文獻(xiàn)[6]的3個(gè)測試?yán)械臄?shù)據(jù)是128個(gè)城市的經(jīng)緯度和距離矩陣, 包括sgb128(m=10,m=15,m=30), 用第一個(gè)城市作為出發(fā)城市.

我們在2.8 GHz, 2 Core, 4 G RAM的Windows 8.1系統(tǒng)上實(shí)現(xiàn)了CSA, 在實(shí)驗(yàn)中種群規(guī)模p設(shè)置為50. 表2給出了CSA在15個(gè)測試?yán)系玫降淖钚〉淖铋L環(huán)路長度(best max)、迭代次數(shù)(iterations)和計(jì)算時(shí)間(time).

表2 CSA算法的結(jié)果、迭代次數(shù)和時(shí)間

表2說明, CSA能在較短時(shí)間內(nèi)終止, 滿足實(shí)際應(yīng)用的需求.

對于文獻(xiàn)[4]的12個(gè)測試?yán)? CSA所得的best max與文獻(xiàn)[6–9]的結(jié)果比較如表3.

表3 幾種算法在文獻(xiàn)[4]測試?yán)系腷est max比較

由表3, 對文獻(xiàn)[4]的12個(gè)問題, 在所有算法中,CSA的結(jié)果都優(yōu)于或等于現(xiàn)有算法的最好結(jié)果, 其中兩個(gè)測試?yán)齅TSP-150 (m=3,m=5)的解展示在圖6中.

圖6 CSA在文獻(xiàn)[6]問題上的兩個(gè)解

對于文獻(xiàn)[6]的3個(gè)測試?yán)? CSA所得的best max與文獻(xiàn)[6–9]的結(jié)果比較如表4.

由表4, 對文獻(xiàn)[6]的3個(gè)測試?yán)? CSA的結(jié)果有大幅度改進(jìn). 由于文獻(xiàn)[6]提供的128城市的坐標(biāo)用經(jīng)緯度來表示, 在二維平面較難展示, 下面給出m=10,max=2748的解, 其中每一對括號包含的是一條環(huán)路.

表4 幾種算法在文獻(xiàn)[6]測試?yán)系腷est max比較

5 結(jié)論

為了求解最大最小目標(biāo)的多旅行商問題, 在對現(xiàn)有文獻(xiàn)進(jìn)行研究的基礎(chǔ)上, 提出了競爭搜索算法(CSA), 與近期文獻(xiàn)中的相比, 明顯提高了解的質(zhì)量. 局部搜索算子和變異算子是CSA算法中的兩個(gè)關(guān)鍵算子. 我們曾采用多種不同的變異算子, 包括: 隨機(jī)移動(dòng)一個(gè)城市、隨機(jī)轉(zhuǎn)置一個(gè)片段、隨機(jī)轉(zhuǎn)置兩個(gè)或多個(gè)片段以及這些操作的組合, 我們觀察到, 采用不同的變異算子, 在收斂速度和最終解質(zhì)量上有明顯差異, 其中,隨機(jī)轉(zhuǎn)置一個(gè)片段的變異方法明顯好于其他方法. 改進(jìn)變異方法, 可能進(jìn)一步提高CSA算法性能.