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

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

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

0 引言

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

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

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

1 TSP描述

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

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

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

2 改進(jìn)遺傳算法求解TSP

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

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

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

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

2.1 聚類分區(qū)操作

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

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

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

2.2 遺傳操作

對(duì)于分區(qū)完成的城市的路徑進(jìn)行編碼，直接采用城市在路徑中的位置來(lái)構(gòu)造用于優(yōu)化的狀態(tài)。例如四分區(qū)時(shí)：第一分區(qū)有24個(gè)城市，路徑為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é)果，一個(gè)個(gè)體由該分區(qū)城市數(shù)目隨機(jī)產(chǎn)生，隨機(jī)生成N個(gè)個(gè)體作為初始群體popm[14]，隨機(jī)選擇一個(gè)種群，由于隨機(jī)性較強(qiáng)，因而也較公正。

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

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

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

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

2）計(jì)算出每個(gè)個(gè)體被遺傳到下一代群體中的概率：

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

5）若r

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

父?jìng)€(gè)體1：1 4 7 2 5 8 3 6 9；

父?jìng)€(gè)體2：2 5 8 3 6 9 1 4 7；

交叉點(diǎn)的位置選為：2 5 8。

子個(gè)體1：1 4 8 3 6 8 3 6 7；

子個(gè)體2：2 5 7 2 5 9 1 4 9。

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

算法流程如圖1所示。

圖1 算法流程圖

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

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

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

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

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

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

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

圖2 分區(qū)擬合圖

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

4 結(jié)論

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