分區協作遺傳算法及其在大規模TSP問題中的應用

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

（西南林業大學機械與交通學院，昆明 650224）

0 引言

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

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

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

1 TSP描述

TSP問題是一個NP難問題[11-12]，可以描述為給定一系列城市坐標集, 一個旅行商從起點城市出發, 去往各個城市推銷他的商品，如何經過各個城市一次并回到出發點的路徑規劃問題。其問題的解可以被描述為各個城市出現一次且僅出現一次構成的排列方案, 該排列方案代表著旅行商將第一個城市作為出發點, 依次按排列順序對城市進行訪問, 最后再回到第一個城市的路徑規劃方案。TSP問題的最優解就是旅行商所經歷過的最短路徑。

TSP的數學模型描述如下：

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

2 改進遺傳算法求解TSP

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

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

在優化操作后期，將已經劃分好的分區按照順時針或逆時針的順序，相鄰兩分區內的起始點與終點有優先的選擇權，以此來提高算法的精確性。

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

2.1 聚類分區操作

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

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

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

2.2 遺傳操作

對于分區完成的城市的路徑進行編碼，直接采用城市在路徑中的位置來構造用于優化的狀態。例如四分區時：第一分區有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）。

優質的初始種群往往能夠得到理想的遺傳算法結果，一個個體由該分區城市數目隨機產生，隨機生成N個個體作為初始群體popm[14]，隨機選擇一個種群，由于隨機性較強，因而也較公正。

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

式中：f為適應度；d為兩城市之間距離。

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

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

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

4）在[0，1]區間內產生一個均勻分布的偽隨機數r。

5）若r

交叉操作是產生新個體的操作之一，優良的交叉方式可以在一定程度上提高種群的多樣性。為提高算法的搜索效率，本文采用多點交叉的方式[15]，對于多點交叉，m個交叉位置Ki可以隨機無重復地選擇，在交叉點之間的變量間續地相互交換，產生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。

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

算法流程如圖1所示。

圖1 算法流程圖

3 大規模TSP仿真試驗

仿真環境為Win10系統下的Matlab2016a，系統主要硬件為：CUP主頻為2.7 GHz，內存為12 GB。

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

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

表1 算法分區對比

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

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

圖2 分區擬合圖

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

4 結論

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