分區(qū)協(xié)作遺傳算法及其在大規(guī)模TSP問題中的應(yīng)用

邢凱，肖灑，賴菲，王鐵廣，方賽銀，李明

（西南林業(yè)大學(xué)機械與交通學(xué)院，昆明 650224）

0 引言

旅行商問題（Traveling Salesman Problem,TSP）屬于NP難的組合優(yōu)化問題，經(jīng)典的規(guī)劃算法在有限的時間內(nèi)無法得到優(yōu)化解，故采用群集智能優(yōu)化算法來解決此問題，諸如遺傳算法[1]、蟻群算法[2]、模擬退火算法[3]等。

遺傳算法本身具有較強的魯棒性，并且適用于求解各種復(fù)雜的優(yōu)化問題，能夠在理想的時間內(nèi)求出全局最優(yōu)解。Ahmed[4]對交叉算子深入研究，提出了一種新的順序建設(shè)性交叉算子，能夠高效精確地解決TSP問題。Liu[5]針對變異操作提出增強突變的改進，將交叉操作中隨機選擇用異構(gòu)配對選擇代替，最終在解決TSP問題時其效果明顯優(yōu)于傳統(tǒng)GA算法。胡士娟等[6]提出將蟻群算法（Ant Clony Optimization, ACO）的反饋機制和GA算法的全局搜索能力相結(jié)合，并且通過TSP實例驗證了其算法比ACO算法和傳統(tǒng)GA算法具有更好的尋優(yōu)能力。Deep 和Adane[7]對于順序交叉算子，提出了一種改進的樹形結(jié)構(gòu)，有效地提高了傳統(tǒng)GA算的效率。Kumar等[8]將TSP不同交叉算子進行比較分析，實驗結(jié)果表明部分映射的交叉給出了最短的路徑。葛耀寶[9]提出一種基于染色體擇優(yōu)選擇的策略，大幅度地減少了算法早熟情況。Ma[10]在2-opt選擇策略和GA算法框架的基礎(chǔ)上，提出了一種新的混合遺傳算法，仿真試驗結(jié)果表明了該算法的有效性。對于小規(guī)模的路徑優(yōu)化問題，可以通過上述啟發(fā)式GA算法獲得最優(yōu)解，然而對于大規(guī)模的路徑優(yōu)化問題，傳統(tǒng)GA算法局限性就凸顯出來了，不僅收斂速度慢，而且容易早熟收斂陷入局部最優(yōu)化。

為此，本文提出一種分區(qū)協(xié)作遺傳算法（Subpartition Cooperation Genetic Algorithm，SCGA），提高GA算法在求解大規(guī)模路徑優(yōu)化問題時的全局收斂能力。首先，基于距離聚類的方法將城市集劃分為規(guī)模相當(dāng)?shù)姆謪^(qū)，并通過傳統(tǒng)GA算法獲取分區(qū)不閉合的分區(qū)最優(yōu)路徑；其次根據(jù)分區(qū)之間的距離按照就近原則確定每個分區(qū)的首尾城市，根據(jù)各分區(qū)之間距離順序連接各個分區(qū)路徑獲得全局最優(yōu)路徑；最后，從TSPLIB標(biāo)準(zhǔn)測試集選取若干實例進行試驗，驗證SCGA算法的可行性與有效性。

1 TSP描述

TSP問題是一個NP難問題[11-12]，可以描述為給定一系列城市坐標(biāo)集, 一個旅行商從起點城市出發(fā), 去往各個城市推銷他的商品，如何經(jīng)過各個城市一次并回到出發(fā)點的路徑規(guī)劃問題。其問題的解可以被描述為各個城市出現(xiàn)一次且僅出現(xiàn)一次構(gòu)成的排列方案, 該排列方案代表著旅行商將第一個城市作為出發(fā)點, 依次按排列順序?qū)Τ鞘羞M行訪問, 最后再回到第一個城市的路徑規(guī)劃方案。TSP問題的最優(yōu)解就是旅行商所經(jīng)歷過的最短路徑。

TSP的數(shù)學(xué)模型描述如下：

假設(shè)有n個城市，它們之間的距離矩陣為D=(dij)n×n，dij為城市i與城市j之間的距離(i≠j)；dij=M，M為足夠大的數(shù)。

2 改進遺傳算法求解TSP

本文設(shè)計一種距離聚類分區(qū)遺傳操作機制：受有限元分析思想的影響，將一個難以解決的大問題轉(zhuǎn)換成多個容易的小問題，在解決多個小問題的基礎(chǔ)上得到整個大問題的近似解；基于此思想，在進行一系列遺傳操作之前，將大規(guī)模城市群進行聚類分區(qū)優(yōu)化操作，每個分區(qū)選取一個中心城市，當(dāng)城市之間的“相近性”用歐氏距離來進行描述時，選擇準(zhǔn)則為各城市到其中心城市距離的平方和，可以表示為

式中：k為分區(qū)數(shù)目；Ci為第i中心城市；d（Ci，x）為城市x到中心城市Ci的距離。

在優(yōu)化操作后期，將已經(jīng)劃分好的分區(qū)按照順時針或逆時針的順序，相鄰兩分區(qū)內(nèi)的起始點與終點有優(yōu)先的選擇權(quán)，以此來提高算法的精確性。

在多個分區(qū)劃分完成并且排序后，分別對每個分區(qū)采用傳統(tǒng)GA算法得出分區(qū)相對最優(yōu)解作為分區(qū)的最短路徑，著重標(biāo)記起始點以及終點[13]；根據(jù)相鄰分區(qū)就近原則，選擇與該分區(qū)起始點或終點最近的鄰域內(nèi)起始點或終點，最后將多個分區(qū)的路徑按照相鄰分區(qū)最短距離拼接起來，作為整個大規(guī)模TSP問題的最短路徑。

2.1 聚類分區(qū)操作

對于大規(guī)模TSP，城市數(shù)目眾多，遺傳算法無法在短時間內(nèi)得到令人滿意的結(jié)果。本文采用聚類分區(qū)方法對大規(guī)模城市進行劃分，綜合考慮城市的布局、城市間距離以及城市的規(guī)模，將距離相近的城市劃為一個分區(qū)，城市之間的“相近性”用歐氏距離來進行描述，可以表示為

式中：dij為城市Ci與Cj的相近性；p為城市屬性的數(shù)量，本文中p取2（城市的橫縱坐標(biāo)）。

大規(guī)模城市總共被劃分為多個分區(qū)，此后解決大規(guī)模旅行商問題即在多個已劃分完成的分區(qū)上進行；對比分析將大規(guī)模旅行商問題分別劃分為多個分區(qū)時，哪種劃分方法所得旅行商最短路徑最適宜。

2.2 遺傳操作

對于分區(qū)完成的城市的路徑進行編碼，直接采用城市在路徑中的位置來構(gòu)造用于優(yōu)化的狀態(tài)。例如四分區(qū)時：第一分區(qū)有24個城市，路徑為5-4-18-1-22-7-9-24-8-19-6-14-21-2-15-3-23-10-11-20-12-17-13-16，路徑編碼為（5-4-18-1-22-7-9-24-8-19-6-14-21-2-15-3-23-10-11-20-12-17-13-16）。

優(yōu)質(zhì)的初始種群往往能夠得到理想的遺傳算法結(jié)果，一個個體由該分區(qū)城市數(shù)目隨機產(chǎn)生，隨機生成N個個體作為初始群體popm[14]，隨機選擇一個種群，由于隨機性較強，因而也較公正。

在進化搜索的過程中，遺傳算法基本不利用外部信息，僅將適應(yīng)度函數(shù)作為依據(jù)，利用種群中每個個體的適應(yīng)度值來進行搜索。TSP的目標(biāo)是路徑總長度為最短，路徑總長度的倒數(shù)就可以作為TSP的適應(yīng)度函數(shù)：

式中：f為適應(yīng)度；d為兩城市之間距離。

一般來說，個體被選中的可能性大小與其適應(yīng)度呈現(xiàn)出正相關(guān)的關(guān)系，適應(yīng)度較大（優(yōu)良）個體有較大的可能性被選中，而適應(yīng)度較小（低劣）的個體被選中的可能性相對來說就較小，本文采用最簡單的一種選擇方法——輪盤賭選擇法。具體操作如下。

1）計算出群體中每個個體的適應(yīng)f（w1，w2…，wn）。

2）計算出每個個體被遺傳到下一代群體中的概率：

4）在[0，1]區(qū)間內(nèi)產(chǎn)生一個均勻分布的偽隨機數(shù)r。

5）若r

交叉操作是產(chǎn)生新個體的操作之一，優(yōu)良的交叉方式可以在一定程度上提高種群的多樣性。為提高算法的搜索效率，本文采用多點交叉的方式[15]，對于多點交叉，m個交叉位置Ki可以隨機無重復(fù)地選擇，在交叉點之間的變量間續(xù)地相互交換，產(chǎn)生2個新的后代，但在第一位變量與第一個交叉點之間的一段不做交換，例如：

父個體1：1 4 7 2 5 8 3 6 9；

父個體2：2 5 8 3 6 9 1 4 7；

交叉點的位置選為：2 5 8。

子個體1：1 4 8 3 6 8 3 6 7；

子個體2：2 5 7 2 5 9 1 4 9。

變異操作本身是一種局部隨機搜索，與選擇、交叉算子結(jié)合在一起，確保了遺傳算法的有效性，使得遺傳算法具有局部的隨機搜索能力，可以加速向最優(yōu)解收斂；同時使得遺傳算法保持種群的多樣性，降低早熟收斂問題出現(xiàn)的可能性。本文采用倒置變異法，例如：假設(shè)當(dāng)前個體X為(1 3 7 4 8 0 5 9 6 2 )，如果當(dāng)前隨機概率值小于變異概率，則隨機選擇來自同一個體的2個點，然后倒置該2個點的中間部分，產(chǎn)生新的個體[16]。例如，假設(shè)隨機選擇個體X的2個點“7”和“9”，則倒置該2個點的中間部分，即將“4805”變?yōu)椤?084”，產(chǎn)生新的個體X為(1 3 7 5 0 8 4 9 6 2)。

算法流程如圖1所示。

圖1 算法流程圖

3 大規(guī)模TSP仿真試驗

仿真環(huán)境為Win10系統(tǒng)下的Matlab2016a，系統(tǒng)主要硬件為：CUP主頻為2.7 GHz，內(nèi)存為12 GB。

選取TSPLIB中若干實例進行試驗，試驗參數(shù)選取如下：初始種群大小為100；最大迭代次數(shù)為1000次；交叉概率為0.8；變異概率為0.1[17]。對多個分區(qū)分別采用普通遺傳算法處理，計算分區(qū)最優(yōu)路徑，將首尾城市按照就近原則選擇鄰域內(nèi)最近的首尾城市，領(lǐng)域的選擇順序按照順時針或者逆時針，獲取其全局最短路徑。在多個分區(qū)內(nèi)采用普通遺傳算法中，根據(jù)算法的隨機性，從中選出分區(qū)最短路徑。

為了驗證SCGA算法的性能，本文將大規(guī)模TSP問題劃分為多個分區(qū)，對每種劃分方式運用SCGA算法進行隨機計算10次處理，以10次試驗結(jié)果的平均值分析比較每種劃分方式的差異。傳統(tǒng)GA算法和SCGA算法所求最短距離如表1所示。

表1 算法分區(qū)對比

由表1試驗結(jié)果可知，在迭代次數(shù)、交叉率、變異率等參數(shù)相同的情況下，分區(qū)GA算法對于大規(guī)模TSP問題的處理效果相較于傳統(tǒng)GA算法最優(yōu)解為原來的1/2以上；當(dāng)分區(qū)數(shù)目相同時，對于規(guī)模越大的TSP問題，SCGA算法的處理效果越好。但是獲得的最優(yōu)解并不是因為分區(qū)數(shù)目越多越好，當(dāng)分區(qū)數(shù)目過多時，獲取的最優(yōu)解并不是很理想；為解決此問題，選取Rat195TSP實例進行分區(qū)擬合，探究分區(qū)數(shù)與最優(yōu)解的函數(shù)關(guān)系。

選取Rat195TSP 實例問題進行分區(qū)擬合，對Rat195TSP實例進行2分區(qū)、4分區(qū)、8分區(qū)、10分區(qū)、12分區(qū)、14分區(qū)、16分區(qū)、18分區(qū)處理，對各分區(qū)所得最優(yōu)解進行擬合，擬合結(jié)果如圖2所示。

圖2 分區(qū)擬合圖

由擬合圖可知，對于Rat195TSP實例，分區(qū)數(shù)目與最優(yōu)解之間的函數(shù)關(guān)系式可以表達為y=-0.028x3+20x2-410x+5200，當(dāng)分區(qū)數(shù)目過多或是過少時，獲得的最優(yōu)解都不理想，分區(qū)數(shù)目過少時，單個分區(qū)內(nèi)城市數(shù)目過多，容易陷入局部最優(yōu)，造成早熟收斂現(xiàn)象，故不能獲得理想的最優(yōu)解；分區(qū)數(shù)目過多時，單個分區(qū)內(nèi)城市數(shù)目過少，可以較早地獲得分區(qū)最優(yōu)解，但分區(qū)之間的距離隨著分區(qū)的數(shù)目增加而增加，所以當(dāng)分區(qū)數(shù)目過多時也不能獲得理想的最優(yōu)解；當(dāng)分區(qū)數(shù)目為10時，Rat195TSP實例獲得最優(yōu)解，通過擬合結(jié)果可以看出，分區(qū)數(shù)與最優(yōu)解之間具有一定的多項式關(guān)系，能夠很好地反映出不同的分區(qū)數(shù)目之間仍存在一定差異，當(dāng)分區(qū)數(shù)目在8～12時，分區(qū)城市數(shù)目在17～26之間，此時的分區(qū)數(shù)目與分區(qū)城市數(shù)目相比于其他分區(qū)數(shù)目與分區(qū)城市數(shù)目達到一個“平衡點”，獲得的最優(yōu)解比其他分區(qū)數(shù)目時的效果更加令人滿意。

4 結(jié)論

傳統(tǒng)GA算法在解決大規(guī)模路徑優(yōu)化問題時存在著“早熟”、收斂速度慢等問題，規(guī)模越大傳統(tǒng)GA算法處理的性能也就越差，本文設(shè)計了一種改進遺傳算法用于解決大規(guī)模路徑優(yōu)化問題，將處理一個大規(guī)模路徑優(yōu)化問題轉(zhuǎn)化為處理多個小規(guī)模路徑優(yōu)化問題，可在一定程度上避免“早熟”現(xiàn)象的發(fā)生，加快收斂速度，使得算法性能得到較大的提升。仿真試驗結(jié)果表明，SCGA算法可以在一定程度上抑制“早熟”現(xiàn)象的發(fā)生，并且能夠較好地解決陷入局部最優(yōu)的問題，但是分區(qū)數(shù)目與最優(yōu)解之間存在一定的多項式關(guān)系，當(dāng)分區(qū)數(shù)目在8～12，可以獲得令人滿意的最優(yōu)解。本文提出的SCGA算法相較于傳統(tǒng)GA算法雖然性能上得到了較大的提升，但是對于路徑優(yōu)化問題分區(qū)間的銜接還有很大的研究空間，接下來會在以后的工作中進一步研究。