陳思遠(yuǎn)，林丕源，黃沛杰

華南農(nóng)業(yè)大學(xué) 數(shù)學(xué)與信息學(xué)院，廣州510642

1 引言

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

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

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

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

2 基礎(chǔ)問題的描述

2.1 TSP問題

2.2 遺傳算法

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

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

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

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

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

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

2.3 指針網(wǎng)絡(luò)

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

圖1 指針網(wǎng)絡(luò)模型

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

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

2.4 種群初始化改進(jìn)方案

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

2.4.1 近領(lǐng)域搜索策略

近領(lǐng)域搜索，也叫最鄰近初始化（Nearest Neighbor，NN）[12]，是貪婪初始化（Greedy）的一種。NN 從隨機城市出發(fā)，每次都從剩余城市中選擇與當(dāng)前所在城市距離最近的城市作為下一個城市，重復(fù)過程直到走完范圍內(nèi)所有城市。可用公式表示為：

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

2.4.2K-means搜索策略

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

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

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

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

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

2.4.3 線性規(guī)劃策略

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

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

3 指針網(wǎng)絡(luò)改進(jìn)初始種群模型

本文引入深度學(xué)習(xí)網(wǎng)絡(luò)——指針網(wǎng)絡(luò)來優(yōu)化初始種群的構(gòu)造。指針網(wǎng)絡(luò)是基于seq2seq 網(wǎng)絡(luò)模型改造，能準(zhǔn)確學(xué)習(xí)到組合優(yōu)化問題的組合規(guī)則，在TSP 問題中，指針網(wǎng)絡(luò)能在中低規(guī)模的TSP模擬數(shù)據(jù)中獲得高準(zhǔn)確度結(jié)果。本文提出基于指針網(wǎng)絡(luò)的遺傳算法初始化方案，以此改善遺傳算法的初始種群構(gòu)造，提高整體算法性能。

3.1 指針網(wǎng)絡(luò)改進(jìn)遺傳算法流程

初始種群的本文引入基于指針網(wǎng)絡(luò)改進(jìn)遺傳算法模型，即PNGA。模型通過指針網(wǎng)絡(luò)來改進(jìn)初始種群總體質(zhì)量，并以改進(jìn)優(yōu)化策略組合優(yōu)化新種群結(jié)構(gòu)，保證種群的質(zhì)量與多樣性。

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

（1）基于指針網(wǎng)絡(luò)生成高質(zhì)量初始種群。

（2）將指針網(wǎng)絡(luò)初始種群與隨機初始種群以最優(yōu)個體保留策略保留雙方優(yōu)良個體，形成新初始種群。

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

（4）結(jié)合自適應(yīng)遺傳算子，提高算法迭代效率。

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

圖2 PNGA流程圖

3.2 改進(jìn)初始種群構(gòu)造策略

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

設(shè)GA 種群規(guī)模上限為Psize，GA 隨機初始化得到種群為S，指針網(wǎng)絡(luò)解集為T，目標(biāo)初始種群為G。為了優(yōu)化目標(biāo)種群G質(zhì)量與多樣性，模型使用的兩種構(gòu)造策略如下。

3.2.1 最優(yōu)子代融合策略

（1）首先，生成Psize大小的初始種群S和指針網(wǎng)絡(luò)解集T。

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

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

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

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

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

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

4 仿真實驗及分析

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

4.1 實驗設(shè)置

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

4.2 PNGA與主流改進(jìn)方案種群初始化系數(shù)對比

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

4.2.1 初始種群質(zhì)量比較

本節(jié)主要從初始種群的結(jié)果對比和初始種群的質(zhì)量對比討論不同初始化方案的優(yōu)劣性。

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

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

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

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

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

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

4.2.2 TSPLIB實例比較

基于表1 初始種群質(zhì)量對比，PNGA 和K-means[13]、LR[14]3 種初始化模型在TSPLIB 實例上進(jìn)行對比，詳見表2（表格中路徑值均經(jīng)過四舍五入取整處理）。其中，“BKS”表示TSPLIB 實例數(shù)據(jù)已知最優(yōu)解（Best Known Solution）。對PNGA 和K-means、LR 分別進(jìn)行了50 次求解，算法內(nèi)部最大迭代次數(shù)為100。“迭代次數(shù)”表示算法內(nèi)部收斂所需迭代次數(shù)。實驗記錄算法所得解的“最優(yōu)值”和“最差值”、50 次平均值“AVG”，并計算對應(yīng)PD值。PD值的計算公式如下：

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

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

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

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

圖4 eil51算法收斂曲線對比

圖5 rat99算法收斂曲線對比

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

4.2.3 PNGA與主流啟發(fā)式算法比較

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

表3 PNGA和主流啟發(fā)式算法最優(yōu)值對比

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

5 結(jié)束語

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