求解旅行商問題的分布式演化算法

韓 珂，楊俊鵬

(1.華北水利水電大學(xué)，河南 鄭州 450045;2.中原工學(xué)院，河南 鄭州 450007)

旅行商問題(Traveling Salesman Problem，TSP)是一類典型的NP 安全問題，也是數(shù)學(xué)領(lǐng)域的著名問題之一.該問題假設(shè)有一個旅行商人要拜訪N 個城市，他從A 城出發(fā)，選擇所要走的路徑，要求N 個城市只能拜訪一次，而且最后返回A 城.他可以有很多種走法，但是為了省時省力，他要選擇一條最短的路徑，TSP 問題就是用來求得的路徑之路程為所有路徑之中的最小值［1］.TSP 問題的術(shù)語描述:即尋找一條最短的遍歷N 個城市的路徑.用演化算法求解TSP 問題一直是學(xué)術(shù)界研究的熱點，演化算法最引人注目的的特性是它的本質(zhì)并行性［2］，對于規(guī)模較大的TSP 問題研究采用并行演化算法求解顯得尤為重要.

目前的求解TSP 問題的演化算法普遍使用雜交算子為主算子，變異算子作為輔助算子，但是雜交算子涉及到群體中個體間信息的交換，而這可能增加處理機(jī)間的通信開銷，所以屬于不太適合并行計算的算子.其次，分布在各個處理機(jī)上進(jìn)行演化的個體，在每演化了一萬多代后，才進(jìn)行一次處理機(jī)間的通信，這樣就使通信開銷在并行計算時間上所占的比例大大減少.最后，算法的串行計算部分所占的比例很小，當(dāng)并行演化一萬多代后，才收集所有的個體進(jìn)行一次演化和淘汰操作.

筆者研究了一種并行計算演化算法來求解TSP問題.算法采用變異算子對每個個體進(jìn)行獨立的遺傳操作，大大提高了算法的并行程度.該算法結(jié)構(gòu)簡單，采用主–從分布式并行模式，大量的演化操作由從進(jìn)程完成，主進(jìn)程只完成任務(wù)的分發(fā)和少量的遺傳操作.算法選用通用的 TSPLIB 中的實例KROB150(這里KROB150 是設(shè)計實例為了驗證算法的可靠性)和文獻(xiàn)［3］中提到的中國CHN144 城市實例進(jìn)行算法測試.對于實例KROB150，TSPLIB提供最短路徑值為26 130(整數(shù)運算所得的結(jié)果)，文獻(xiàn)［4］給出的最優(yōu)路徑值為26 127.357 9(浮點運算所得的結(jié)果)，筆者提出的算法所得的結(jié)果為:整數(shù)運算所得的結(jié)果為26 130，浮點運算所得的結(jié)果為26 127.357 888 739 3.對于CHN144 實例，文獻(xiàn)［3］和［4］給出的最優(yōu)路徑值都為30 354.3(浮點運算所得的結(jié)果)，本算法所得的結(jié)果:浮點運算所得的結(jié)果為30 353.860 996 523 6，整數(shù)運算所得的結(jié)果為30 347.通過本算法得到的實際浮點運算值比參考文獻(xiàn)［4］提出的值更優(yōu).

1 求解TSP 問題的并行演化算法

1.1 算法采用的變異操作

在算法上，設(shè)計的編碼方式用普通路徑來表達(dá)，一個染色體表示一次旅行.這種變異操作編碼方式的特點是:變異算子的設(shè)計相對容易，計算個體的適應(yīng)值無需解碼.

由于引入了染色體編碼，常規(guī)的變異算法在編碼串中的異位發(fā)生突變情況下不再適用，所以這里需要采用基于位置的變異和基于次序的變異.首先考慮基于位置的變異，對個體編碼串中隨機(jī)選取的子串以逆轉(zhuǎn)概率逆向排序后產(chǎn)生新的個體，這種倒位變異算子符合本編碼模型的設(shè)計需求.其次是次序的變異，相對于位置的變異，只改變子串的一個位置利用插入的手段產(chǎn)生新個體，這樣的插入變異算子設(shè)計更簡單，同時也符合模型的變異算法.

倒位變異算子，是指在個體編碼串中隨即選取2 城市，使第1 個城市的右城市與第2 個城市之間的編碼倒序排列，從而產(chǎn)生1 個新的個體.在父體中隨機(jī)選擇兩個截斷點，然后將兩點間的城市反序，倒位算子是對染色體的邊改動最少的變異(只變化了2 條邊).

插入變異算子，是在父體中隨機(jī)選擇1 個城市，然后將這個城市隨機(jī)插入到父體中的某個位置，該算子只變化了3 條邊.

算法在這2 個變異算子的基礎(chǔ)上設(shè)計了一個新的變異算子——組合變異算子.假設(shè)父體是S，組合變異算子操作步驟如下.

第1 步:從S 中任選2 個城市i 和j.

第2 步:假如將包含i 和j 在內(nèi)的i 和j 間的所有城市反序后，使S 的適應(yīng)值增加了，則將i 和j 間的城市做反序處理，同時修改S 的適應(yīng)值.

第3 步:在S 中隨即選擇某個城市i，再在S 中任意選擇另外1 個城市j.

第4 步:如果將i 放到j(luò) 的前面能使S 的適應(yīng)值增加，則將該i 放到j(luò) 的前面，同時修改S 的適應(yīng)值.

從以上操作過程可以看到，組合變異算子的特點如下.

1)該算子作用后，所得后代的適應(yīng)值大于等于其父體的適應(yīng)值，是一種無退化的變異.

2)當(dāng)?shù)? 步和第4 步中的條件都不滿足時，有可能對父體沒有改變.

3)該算子操作完后，所得后代的適應(yīng)值也同時計算出來了.

算法將組合變異算子作為主搜索算子，用于局部區(qū)域的搜索.將一般的插入變異算子作為從變異算子，用于搜索方向向其他區(qū)域的遷移，跟組合變異算子一樣，本算法讓插入變異算子在變異的同時，修改個體的適應(yīng)值.

1.2 求解TSP 的串行演化算法

PROCEDURETSP_GA

begin

optimal_indi :=M 中最佳的個體;

i:=0;gen:=0;

if gen＜=KS do

begin

if i＜=RG

begin

對M 中的每一個個體使用組合變異算子進(jìn)行變異;

i:=i+1;

end

else

begin

if M 中最佳個體好于optimal_indi

optimal_indi:=M 中最佳的個體;

S:={從M 中選擇的N－1 個個體};

M:=S+{個體optimal_indi};

對M 中的每一個個體使用插入變異算子進(jìn)行變異;

i:=0;

gen:=gen+1;

end;

end;

end;

算法中的參數(shù)為每一輪使用組合變異算子進(jìn)行變異的代數(shù)，為輪換次數(shù)，為群體規(guī)模.

1.3 并行演化算法

開始;

向PVM 提出登記;

創(chuàng)建從進(jìn)程;

初始化群體M;

計算M 中個體的適應(yīng)值;

optimal_indi:=M 中最佳的個體;

設(shè)gen:=0;

if gen＜=KS then

begin

將M 中所有的個體傳給每個從進(jìn)程;

然后等待接收所有從進(jìn)程發(fā)來的新個體;

M:={接收到的N 個新個體};

if M 中最佳個體好于optimal_indi

將M 中最佳的個體賦予optimal_indi;

S:={從M 中選擇的N－1 個個體};

M:=S+{個體optimal_indi};

gen:=gen+1;

end;

將進(jìn)程終止條件發(fā)布給各從進(jìn)程;

退出PVM;

end;

開始m 個從進(jìn)程:

begin

返回并向PVM 登記;

repeat

按序號接收主進(jìn)程傳來的個體;

S:={接收到的個體};i:=0;

if i＜=RG then

begin

對S 中的每一個個體使用組合變異算子進(jìn)行變異;

i:=i+1;

end;

將S 中的個體依次傳遞給主進(jìn)程;

滿足終止條件(gen＜=KS);

退出PVM.

2 算法說明與分析

本算法與傳統(tǒng)的全局單種群主－從模式(主程序存儲整個種群)有所不同，采用“主－ 從編程模式”，即1 個主進(jìn)程控制并協(xié)調(diào)多個從進(jìn)程.由從程序來評估個體的適應(yīng)值，個體的適應(yīng)值評估是并行的，適應(yīng)值的評估在程序中花費時間最長.

算法中使用了KS，N，RG 3 個參數(shù):參數(shù)KS 用來控制整個算法的終止.算法經(jīng)過反復(fù)執(zhí)行輪的過程，經(jīng)過KS 輪的操作后，最終找到最優(yōu)解.這里的“輪”是指讓群體進(jìn)化指定的數(shù)，通過競賽選擇機(jī)制淘汰較差的個體，再對剩余的每一個個體進(jìn)行一次插入變異，這個過程稱為1 輪.參數(shù)N 用來表示群體的規(guī)模.參數(shù)RG 用來表示每一輪中使用組合變異算子演化.

從求解TSP 問題的算法看出，變異后的個體適應(yīng)值只需在原適應(yīng)值的基礎(chǔ)上稍作計算，變異算子最多改動一個個體的3 條邊，所以花費在這里的計算時間較短.但是一旦求解問題的規(guī)模N 增加，染色體的長度增加，倒位和插入所移動的城市的總數(shù)將增加，遺傳操作花費時間將快速增長.由于上述原因，算法在設(shè)計時，將大部分遺傳操作放到從程序中執(zhí)行，遺傳操作和個體的評估并行執(zhí)行，當(dāng)從進(jìn)程執(zhí)行后，才執(zhí)行RG 個體的遺傳操作并計算適應(yīng)值.

下面分析一下算法的加速比.

設(shè)處理機(jī)的臺數(shù)為i.從以上算法可看出，算法每執(zhí)行1 輪，進(jìn)行1 次處理機(jī)通信，設(shè)這個通信時間為TC.串行算法執(zhí)行的每1 輪中，可設(shè)并行部分的計算時間為TP，串行部分的執(zhí)行時間為TS，因為在每1 輪中使用組合變異算子進(jìn)行RG 代演化后(可并行部分)，才進(jìn)行選擇操作和一代插入變異(需串行的部分)，所以可認(rèn)為TP=RG×TS.則進(jìn)行每一輪演化，采用串行計算所需的總時間為

采用并行計算所需的總時間為

則加速度比為

從上式看出，i 越大，λ 越大;RG 越大，λ 也越大.但RG 過大會影響解的質(zhì)量，因為RG 過大，在相同運算的時間內(nèi)，KS 會減少，進(jìn)行搜索方向遷移的次數(shù)會減少，就有可能發(fā)生過早收斂;RG 過小，在局部區(qū)域搜索的時間就會減少，使解的精度降低.在實例測試中，取RG=18 000.當(dāng)問題的規(guī)模增大(城市的個數(shù)增多)時，因為TP的增長幅度遠(yuǎn)大于TC，所以λ 也增大.

從以上分析可看出，該算法特別適合大規(guī)模的TSP 問題的并行演化計算，且機(jī)器越多越好，當(dāng)問題的規(guī)模相當(dāng)大時，甚至可以讓一臺處理機(jī)只處理一個個體.

3 算法測試

1)參數(shù)設(shè)定.算法測試所設(shè)定的參數(shù)為:RG=20 000，N=50;測試實例為選擇TSPLIB 中的150 個城市解決TSP 問題，命名為KROB150;選擇中國144個城市解決TSP 問題，命名為CHN144.

2)實驗情景.實驗主要模擬網(wǎng)絡(luò)環(huán)境，并行計算機(jī)的運作方式，將網(wǎng)絡(luò)中每臺計算機(jī)安裝PVW運算環(huán)境，同時使用6 臺計算機(jī)，每臺計算機(jī)只運行一個進(jìn)程.對每個問題進(jìn)行浮點運算和整數(shù)運算，每組20 次.計算數(shù)值見表1.

表1 算法求得最優(yōu)值

表1 中整數(shù)運算是指根據(jù)城市的原始坐標(biāo)值計算出來的所有的2 個城市間的距離值四舍五入取整運算.浮點運算是指保留小數(shù)位運算.

假定算法找到上表中的最優(yōu)解時終止，記錄算法運行的時間及最優(yōu)解的首達(dá)時間.串并行演化算法所用的時間對比見表2—3.

表2 CHN144 串并行演化時間對比 s

表3 KROB150 串并行演化時間對比 s

假設(shè)當(dāng)算法找到上述表格中的最優(yōu)解時停止.表2 和表3 的數(shù)據(jù)顯示，用串行演化算法的平均時間較長，是并行演化算法的平均時間的3 倍.讓串行演化算法和并行演化算法演化相同的輪數(shù)終止，串行演化算法的平均時間是并行演化算法的平均時間的2.89 倍，并行演化算法取得了較好的加速比.

4 結(jié)語

并行演化算法使用了較少的參數(shù)，只使用了變異算子，提出的組合變異算子具有很強(qiáng)的搜索能力;平均計算時間不到1 min，取得了較好的加速比;具備收斂速度快、解精度高等特點，實驗的結(jié)果都接近或優(yōu)于已知最優(yōu)解.

筆者將在此基礎(chǔ)上，進(jìn)一步研究算法中參數(shù)RG(每1 輪進(jìn)化的代數(shù))與問題的規(guī)模之間的關(guān)系，并對并行演化算法的計算效率做深入研究.

［1］Garey M R，Johnson D S.Computers and intractability［D］.San Francisc:Bell Telephone Laboratories，1979.

［2］Zbigniew Michalewicz.Genetic Algortihms+Data Structures=Evolution Programs［M］.Berlin Heidelberg:Springer-Verlag，1996.

［3］康立山，謝云，尤失勇.非數(shù)值并行運算法:模擬退火算法［M］.北京:科學(xué)出版社，1997

［4］吳斌，史忠植.一種基于蟻群算法的TSP 問題分段求解算法［J］.計算機(jī)學(xué)報，2001，24(12):1328－1333.