指針網絡改進遺傳算法求解旅行商問題

陳思遠，林丕源，黃沛杰

華南農業大學 數學與信息學院，廣州510642

1 引言

遺傳算法屬于演化算法，是最優化算法的一種。遺傳算法模擬自然界物種進化，適者生存的規律，通過模擬物種進化生成新種群過程中，基因交叉互換，變異等過程生成新的個體[1]?；騼灹嫉膫€體會被保留，延續至下一代，不斷改進種群整體的基因。從理論上，隨著種群迭代，子代基因會優于父代基因。然而，實際上并非如此，因為子代基因受種群基因質量影響，質量差的種群容易生成適應度次的子代，會對算法的性能和尋優速度造成影響[2]。這種影響可以通過對種群的擇優構造來避免。

遺傳算法在大規模最優化問題中，能取得最優值或者次優值。然而遺傳算法本身也存著諸多缺陷，在處理規模較大的最優化問題，如旅行商問題（Traveling Salesman Problem，TSP），算法容易陷入局部最優、收斂速度慢等問題。遺傳算法相比精確算法，其求解過程是隨機性的，通過隨機的選中基因進行互換和變異。交叉和變異算子是影響遺傳算法搜索過程的兩大重要因素[3]。目前，學者們在改進遺傳算法搜索算子過程中提出了許方案，像自適應遺傳算子[4]、改進變異算子[5]等。

種群初始化是遺傳算法的第一個階段，也是影響遺傳算法性能的另一重要因素。初始種群影響著算法的收斂速度和算法的尋優空間，是遺傳算法性能的決定因素之一[6]。傳統的遺傳算法常使用隨機策略生成初始種群集合，然而隨機初始策略帶來算法的不穩定性，導致種群適應度底下，搜索速度慢，容易陷入局部最優等缺點，嚴重影響算法后期優化搜索算子的應用。如何優化遺傳算法的初始種群階段，提供高質量多樣性的種群個體是學者研究改善遺傳算法的方向之一。

本文提出一種基于指針網絡改進遺傳算法初始種群模型，通過改進指針網絡生成高適應度種群，并結合基于漢明距離改進輪盤賭策略對種群進行改造，并將改進模型應用于求解旅行商問題中。

2 基礎問題的描述

2.1 TSP問題

2.2 遺傳算法

遺傳算法通過模擬生物基因交叉變異等過程來生成目標問題新的解集，直到尋得最優解。傳統遺傳算法主要求解步驟如下所示。

（1）種群初始化：初始種群的生產是遺傳算法的前備工作。初始種群產生許多解決方案，方案個數取決于種群規模大小。初始種群的規模和質量會對遺傳算法的搜索空間和搜索速度產生很大的影響。傳統遺傳算法主要使用隨機策略來生成種群來完成初始化，然而隨機算法帶來的不確定性會給遺傳算法搜索尋優空間帶來很大影響。

（2）選擇最優子代：遺傳算法模擬自然界優勝劣汰的規則。對于當下的存在的種群。算法會對大的種群進行劃分N個子種群。在每個子種群中選取適應度高的子代進行保留，淘汰適應度低的子代。以保證種群質量。

（3）交叉和變異：交叉和變異算法是遺傳算法的種群的部分。交叉算子為遺傳算法帶來新的基因組合，擴大搜索范圍。以一定概率Pc和Pm進行交叉和變異操作。其中個體c的交叉概率為體c的適應值，Pm亦然。

（4）重復（2）和（3）過程直至算法收斂。

遺傳算法雖然在求解城市規模較小的問題時具有較快的尋優速度，但在城市點集規模較大的TSP 問題時，早熟、后期收斂慢等缺陷愈加明顯，影響算法性能[9]。其中，影響遺傳算法的主要因素為交叉變異概率和初始化種群。

2.3 指針網絡

指針網絡是由Vinyals 等人[10]提出的一種能從離散的輸入序列中學習到輸出序列條件概率的神經網絡，它是sequence to sequence（簡稱seq2seq）網絡模型的一個變種[11]，能有效用于學習到中低維度的組合優化問題，并能高準確度預測出問題的解。指針網絡的原理是將輸入映射為一系列按概率指向輸入序列元素的指針[10]，如圖1所示，xn和yn代表輸入網絡數據。

圖1 指針網絡模型

圖1中，白色的RNN用于處理輸入序列以產生編碼向量，其中編碼向量用于使用概率連規則生成輸出序列和另一個灰色的RNN。指針網絡在原本的seq2seq模型的基礎上的修改，并不是通過加權所有的結果得到輸出，而是直接將softmax的結果值作為輸出的條件概率，可以用公式表示為：

其中v和W1、W2是模型可訓練的參數，向量uij為輸入元素的指針，softmax 將uij歸一化為輸入序列在輸出元素中的分布。p(Ci|C1,C2,…,Ci-1,P;θ)則代表從輸入元素被選中作為輸出元素的條件概率。

2.4 種群初始化改進方案

傳統遺傳算法在種群初始化中，一般使用隨機策略。而隨機策略自身存在諸多缺陷，如種群個體質量偏低、無法保證種群多樣性等，這也導致傳統遺傳算法會出現早熟陷入局部最優等缺陷。近年來，學者們從各種組合優化方案中探討對初始種群的優化改進，有以下幾種主流改進方案。

2.4.1 近領域搜索策略

近領域搜索，也叫最鄰近初始化（Nearest Neighbor，NN）[12]，是貪婪初始化（Greedy）的一種。NN 從隨機城市出發，每次都從剩余城市中選擇與當前所在城市距離最近的城市作為下一個城市，重復過程直到走完范圍內所有城市?？捎霉奖硎緸椋?/p>

其中Tt為當前路徑長度，Dcicr表示當前城市Ci與剩余城市集合Cr之間的距離。

2.4.2K-means搜索策略

K-means是基于K中心點聚類的初始化方案[13]，算法過程可描述為，在有n個觀測點集中尋找K個中心點，最小化觀測點與其最近中心點的平均距離。其具體步驟如下：

（1）基于K-means 聚類將N個城市集合分成K組，其中，

（2）GA 初始化過程中，從K組聚類中心集合中獲得局部最優子路徑，再將K個局部最優子路徑整合為全局最優路徑。

（3）將上一步驟獲得的最優路徑里面的局部最優子路徑斷開，首尾交換，并記錄新路徑的長度。如果行路徑大于當前最優路徑，則替換當最優路徑。

（4）重復（3），直到所有子路徑交換完成，則完成K-means初始化步驟。

2.4.3 線性規劃策略

線性回歸初始化是一種基于線性回歸（Linear Regression，LR）[14]，將TSP城市劃分為幾個子區域，然后，在子區域中，反復迭代求使得子區域路徑最短，最后合并得到初始化路徑集合的過程。算法的思想基于回歸和連續分區，通過把大問題轉化為局部最優問題。設LR 平面劃分線為y=a+bx，其中，x是解釋性或者獨立變量，y是非獨立變量a和b是代表線性域的常量，其中：

LR的求解方式類似于K-means，都是基于一定的基線將初始種群進行劃分成小的區域模塊，再在小區域中進行局部求解。其缺點也和K-means 一樣，受到LR 回歸劃分的影響大，容易陷入局部最優等。

3 指針網絡改進初始種群模型

本文引入深度學習網絡——指針網絡來優化初始種群的構造。指針網絡是基于seq2seq 網絡模型改造，能準確學習到組合優化問題的組合規則，在TSP 問題中，指針網絡能在中低規模的TSP模擬數據中獲得高準確度結果。本文提出基于指針網絡的遺傳算法初始化方案，以此改善遺傳算法的初始種群構造，提高整體算法性能。

3.1 指針網絡改進遺傳算法流程

初始種群的本文引入基于指針網絡改進遺傳算法模型，即PNGA。模型通過指針網絡來改進初始種群總體質量，并以改進優化策略組合優化新種群結構，保證種群的質量與多樣性。

PNGA模型具體流程步驟如下所示：

（1）基于指針網絡生成高質量初始種群。

（2）將指針網絡初始種群與隨機初始種群以最優個體保留策略保留雙方優良個體，形成新初始種群。

（3）將（2）中剩余個體，以基于漢明距離改進輪盤賭策略，加入到新種群中。

（4）結合自適應遺傳算子，提高算法迭代效率。

PNGA模型的流程圖如圖2所示。

圖2 PNGA流程圖

3.2 改進初始種群構造策略

種群整體素質不僅受個體質量影響，還取決于種群整體個體的基因多樣性組成。在保證種群有高質量個體的同時，為了優化種群個體組成，PNGA 模型以兩種構造方案相結合。

設GA 種群規模上限為Psize，GA 隨機初始化得到種群為S，指針網絡解集為T，目標初始種群為G。為了優化目標種群G質量與多樣性，模型使用的兩種構造策略如下。

3.2.1 最優子代融合策略

（1）首先，生成Psize大小的初始種群S和指針網絡解集T。

（2）對S和T分別計算集合中個體的適應度。

（3）對S和T分別取適應度高的子集加入新解集G，以Sg和Tg表示。為了最大程度保留指針網絡解集T中個體的優勢，本文將和以特定比例加入，則新種群G的初步集合Gi組成如下：

3.2.2 基于漢明距離輪盤賭策略

在有優秀個體的情況下，為了優化種群多樣性。本文提出一種基于漢明距離的輪盤賭策略。

漢明距離是一種測量個體差異的方法，在信息學中，它表示兩個長度相等的字符串中，對應位置中不相同的個數[15]。以TSP 序列為例，TSP 序列a=[0，1，4，2，3，0]和b=[0，1，2，3，4，0]之間的漢明距離為3，因為序列a和b中第3、4、5位不相同。假設個體C2和C2的漢明距離為ρH(C1,C2)。

種群個體之間的漢明距離是種群多樣性的度量之一。為了計算種群之間的多樣性，必須計算出種群中每個個體之間的漢明距離。假設大小為N的初始種群，則種群平均漢明距離DH可以表示為：

4 仿真實驗及分析

為驗證PNGA初始化模型的有效性，實驗主要從兩方面進行比較：第一部分主要對比PNGA改進模型和主流初始化方案的在隨機數據集和TSPLIB 上的效果對比；第二部分主要對比PNGA與主流啟發式算法的求解準確度差異。實驗數據采用隨機模擬數據和TSPLIB上基于歐幾里德距離的對稱TSP城市數據。

4.1 實驗設置

實驗采用python 語言和tensorflow 框架，在Linux，內存8 GB，CPU 為i7-6700 環境下運行。指針網絡訓練集采用了隨機生成策略，以[0，1]×[0，1]范圍內生成的隨機數據作為城市坐標，城市數量為20～100 之間隨機生成。并用谷歌優化器（google optimization tools，or-tools）求解作為訓練標簽。GA 算法的初始種群大小為64。優化算子2-opt和片段交換swap次數為5。

4.2 PNGA與主流改進方案種群初始化系數對比

種群路徑圖是展示初始化路徑質量最為直觀的衡量方法之一，優秀的初始化路徑圖具有點與點之間連接緊湊，交叉路徑少，路徑間最長距離短等特點。為了和PNGA 進行對比，選取了研究進展中的NN、K-means、LR進行對比，具體對比實驗如下所示。

4.2.1 初始種群質量比較

本節主要從初始種群的結果對比和初始種群的質量對比討論不同初始化方案的優劣性。

種群路徑圖是展示初始化路徑質量最為直觀的衡量方法之一，優秀的初始化路徑圖具有點與點之間連接緊湊，交叉路徑少，路徑間最長距離短等特點。為了和PNGA 進行對比，本節選取了研究進展中的NN[12]、K-means[13]、LR[14]進行對比，初始化路徑圖如圖3所示。

圖3 為在50 個城市規模下，4 種不同初始化方案的初始化路徑對比圖。從圖中可以直觀的看出，NN 的路徑構成上，交叉點較多，長距離點存在，路徑構成較為不規則，初始化路徑的總體效果較差；K-means 相比NN，路徑圖中，交錯點較少，但仍然存在部分交錯。長距離點較少，因為交叉存在也導致長路徑明顯?？傮w路徑初始化效果優于NN。LR 在路徑圖構成上和K-means 類似，交錯點少，長距離路徑少，初始化路徑效果和K-means 相當。PNGA 相比K-means 和LR，具有更少的交叉點，長距離也明顯少于K-means和LR，總體初始化效果位于最優。從圖中分析，可以看出，PNGA 在n=50這樣的中低規模城市路徑中的初始化效果略優于K-means 和LR，總體上遠超NN，從初始化圖直觀效果上，處于初始化方案中效果最好的一個。

除了初始化路徑構成比較外，實驗還從種群的多樣性和平均個體值方面進行驗證。本文實驗與研究進展方法在平均路徑和種群多樣性上進行對比驗證。其中，參數AVGR代表在城市大小n恒定下，算法的平均初始化路徑均值，AVGR 越小，證明種群的平均個體質量越高，獲得的路徑越短，初始種群質量越高。CH代表種群個體的平均漢明距離均值，漢明距離是衡量集合中個體差異值的有效方法之一，CH越大，代表種群中個體間的差異大，種群多樣性更加豐富，能降低算法迭代過程中陷入局部最優的概率。實驗記錄PNGA 對比NN 和K-means 和LR，在20～100 個點TSP 模擬數據上進行種群初始化的結果，分別計算各自初始種群的CH 值和AVGR值，如表1所示。

圖3 4種方案初始路徑圖對比

表1 不同方案的初始種群比較

從CH 方面看，NN 的平均CH 值均比其他方法要低，NN 的初始化是基于貪婪策略而來的，這也導致了NN 初始化過程中種群的多樣性低，容易陷入局部最優而無法進行全面搜索。K-means的CH相比LR，略次于LR。K-means 受限于K中心點的選取，在種群組成上無法構成很多樣性豐富的初始種群。PNGA模型的CH優于LR 和K-means，在種群多樣性上，PNGA 的種群多樣性與其他算法對比均有絕對優勢。

4.2.2 TSPLIB實例比較

基于表1 初始種群質量對比，PNGA 和K-means[13]、LR[14]3 種初始化模型在TSPLIB 實例上進行對比，詳見表2（表格中路徑值均經過四舍五入取整處理）。其中，“BKS”表示TSPLIB 實例數據已知最優解（Best Known Solution）。對PNGA 和K-means、LR 分別進行了50 次求解，算法內部最大迭代次數為100?！暗螖怠北硎舅惴▋炔渴諗克璧螖?。實驗記錄算法所得解的“最優值”和“最差值”、50 次平均值“AVG”，并計算對應PD值。PD值的計算公式如下：

如表2，是K-means 和PNGA 算法在各項系數上的比較。在有優勢種群的環境下，對表1中數據進行分析比較，在迭代速度上，PNGA 相比K-means 模型，迭代次數上同比減少了15%左右的時間，相比LR，同比減少了10%的迭代時間。

最優值方面，PNGA 在最優值方面接近BKS，在最短路徑方法面，PNGA在規模較小的TSPLIB數據集上，均能取得最優值，在規模較大的數據中，PNGA 能部分接近最優，相比K-means，在不同規模數據集上，大約提升5%～15%左右，相比同等時間內，K-means 和LR 求解上和BKS相比，均有不小的誤差，其中，LR在BKS上的誤差相比K-means 的誤差大3%左右。此外，在最差值Worst 上，K-means 的最差值相比LR 和PNGA 高了5%～10%左右，絕對誤差上比較大。PNGA最差值波動上優于LR，最優值和最差值之差反饋于PD值。

表2 PNGA與K-means、LR在TSPLIB的實例比較

在方差PD值上，PNGA的PD值波動總體上較為平穩，隨著城市規模n的不斷增大，PNGA、K-means、LR均有較大的上升波動，PNGA 的PD 值波動和LR 較為接近，K-means 算法的PD 值波動較大，這和K-means 自身聚類中心點有關，會引起K-means 算法的不穩定性，相比基于深度學習改進的PNGA模型在求解過程中的PD值波動小，算法更加穩定。

圖4 eil51算法收斂曲線對比

圖5 rat99算法收斂曲線對比

如圖4 和圖5 分別為3 種算法在實例eil51 和rat99上的收斂曲線對比圖。從圖中可得，在不同規模的實例中，PNGA 的初始路徑值明顯優于K-means 和LR，PNGA 初始種群適應度相比其他算法更高。從總體的收斂速度上PNGA＞LR＞K-means，PNGA收斂速度更快，所需迭代次數更少，反映出PNGA 算法的尋優能力更強。從收斂曲線中分析可知，本文提出PNGA算法具有更好的尋優能力和尋優速度。

4.2.3 PNGA與主流啟發式算法比較

為了進一步研究PNGA 模型性能。本文將PNGA和研究進展中的主流啟發式算法在最優路值上進行了對比，如表3所示，其中SA-MMAS[19]和SOS-SA[17]是基于模擬退火算法，IMRGHPSO[18]是基于粒子群算法PSO。

表3 PNGA和主流啟發式算法最優值對比

從表3可以看出，PNGA在最優值上均優于IPCO和IMRGHPSO。除了kroA100略次于SA-MMAS外，平均結果略優于SA-MMAS。PNGA部分實例雖然沒有達到最優水平，但在結果上相對優于其他主流算法。實驗表明，PNGA 具有良好的性能和尋優效果，能有效用于求解TSP問題。

5 結束語

本文提出的深度指針網絡與改進遺傳算法相結合的模型，通過對TSP問題求解研究。指針網絡為遺傳算法提供的優秀初始種群，優化遺傳算法的運行能力，加快迭代過程。在TSPLIB公開數據集上的多組仿真實驗對比表明，指針網絡結合模型相求解質量和收斂速度方面均有顯著提高，比同類初始化方法更為優秀；與其他主流啟發式算法對比也占優，是求解TSP問題的有效改進方法。如何將指針結合更為復雜的組合優化問題是下一步研究的方向。