改進快速單親遺傳算法解均衡多旅行商問題

朱紅瑞 譚代倫*

（西華師范大學(xué)數(shù)學(xué)與信息學(xué)院，四川南充 637000）

多旅行商問題（Multiple Traveling Salesman Problem,MTSP）是經(jīng)典旅行商問題（TSP）的一類重要擴展［1］，它是指有多個旅行商從某個指定的起點出發(fā)，去訪問給定的一組城市，要求每個城市只被一個旅行商訪問，且只訪問一次，求使得總成本最低的最佳行走方案，其中成本可以是路程、時間等。MTSP問題有很多實際應(yīng)用場景，比如印刷機的調(diào)度［2］、印刷前廣告的調(diào)度［3］、銀行工作人員的調(diào)度［4］、校車的路線［5］、衛(wèi)星測量系統(tǒng)的設(shè)計［6］等現(xiàn)實問題。隨著快遞和外賣配送行業(yè)的不斷發(fā)展，需要最小化各旅行商的最長路線，使其承擔(dān)的工作任務(wù)盡量均衡，避免資源的浪費，所以，均衡多旅行商問題（Balanced Multiple Travelling Sales?man Problem,BMTSP）也逐漸得到廣泛的關(guān)注與研究，如何快速且有效地解決該問題仍然具有很高的實際應(yīng)用價值。

在求解多旅商問題時，大多數(shù)研究者常常只達到了總路程最短的目標，目前，在總路程最短的基礎(chǔ)上使得每個旅行商的路程均衡的相關(guān)研究成果還不算豐富。劉偉民［7］以最小化各旅行商最長路線這一負載均衡為優(yōu)化目標，提出了一種結(jié)合構(gòu)造機制和局域搜索的改進蟻群算法，提高了算法性能，得到更優(yōu)結(jié)果。文卡塔斯（Venkatesh）和辛格（Singh）［8］通過借鑒不同的生物智能，分別提出了不同程度上改進的蜂群算法和雜草入侵算法，并且在多數(shù)實例上得到了較優(yōu)的計算結(jié)果。胡士娟［9］在遺傳算法中利用繁殖機制來產(chǎn)生種群并進行遺傳操作；同時提出一種混合局部優(yōu)化算子來求解平衡的MTSP 問題，提高了算法的搜索效率和收斂精度。

在上述群智能算法中，由于遺傳算法（GA）具有通用性高、魯棒性強、求解性能穩(wěn)定等優(yōu)點，被廣泛應(yīng)用于求解MTSP 問題［10］，但為了避免不可行解的出現(xiàn)，常采用更復(fù)雜的部分映射交叉、順序交叉、循環(huán)交叉［11］等特殊的交叉算子，導(dǎo)致遺傳過程復(fù)雜，計算效率不高。而單親遺傳算法（PGA）取消了交叉算子，代之以僅在一條染色體上操作的基因重組等遺傳算子，即通過單親繁殖來產(chǎn)生后代，遺傳操作得以簡化，避免了“早熟”問題［12］，提高了計算效率。李茂軍［13］等在2001 年也研究證明單親遺傳算法的基因重組算子隱含了交叉算子的功能。隨著單親遺傳算法受到越來越多的關(guān)注，許多學(xué)者也將其應(yīng)用于更多的實際生活中解決相關(guān)的組合優(yōu)化問題［14-16］。

基于以上分析，本文提出一種改進的快速單親遺傳算法（Improved Fast Partheno-Genetic Algo?rithm,IFPGA）來求解BMTSP 問題，將已經(jīng)被實驗證明求解TSP問題有效的基因移位、倒序、交換等變異算子與單親遺傳策略相結(jié)合，增強種群尋優(yōu)能力，同時引入最近鄰點的局部優(yōu)化策略，以加快種群的收斂。

1 BMTSP問題及數(shù)學(xué)模型

一般地，均衡多旅行商問題（BMTSP）可以描述為：有m 個旅行商，從某個指定起點出發(fā)，需要去訪問給定的n 個城市并回到起點（城市之間的距離已知），每一個城市必須且只被一個旅行商訪問一次，求使得路程最長的旅行商回路盡量短的均衡最佳行走路線。

基于圖論知識，BMTSP 問題中所有旅行商訪問全部城市構(gòu)成一個圖，記為

其中V為頂點集，v0為旅行商共同的起點、v1,…,vn為要訪問的n個城市；E為邊集，eij為城市vi到城市的邊，記為。

則均衡多旅行商問題（BMTSP）的數(shù)學(xué)模型可表示為：

式（1）表示使個m旅行商的回路最大最小化；式（2）和式（3）表示m個旅行商都從指定的起點城市出發(fā)并回到起點，使得旅行路徑成為閉回路；式（4）表示每個城市只被一個旅行商訪問且只訪問一次；式（5）用于約束每一個旅行商不產(chǎn)生子回路［17］；式（6）表示每一個旅行商至少訪問D個城市，其中D為工作量均衡控制常量。

2 改進快速單親遺傳算法設(shè)計

本文IFPGA算法著重對單親遺傳策略進行了改進，并引入了最近鄰點局部優(yōu)化策略，使算法的收斂速度和求解精度得到了明顯提升。下面簡要說明IFPGA算法的各個步驟。

2.1 基因編碼方案

基因編碼方案是遺傳算法的基礎(chǔ)，決定了種群個體染色體基因的結(jié)構(gòu)和表現(xiàn)形式，對遺傳交叉與變異操作都有重要影響。

遺傳算法求解旅行商問題（TSP）普遍采用以城市序號構(gòu)成的路徑節(jié)點序列編碼。對多旅行商問題（MTSP），還需要將路徑節(jié)點序列編碼拆分為多個片段，以對應(yīng)于多個旅行商各自的訪問路徑。拆分方法一般是隨機生成多個斷點。為此，本文算法也采用路徑節(jié)點序列編碼和斷點相結(jié)合的兩段式染色體編碼。

染色體的第一部分稱為路由編碼段，是所訪問的n個城市v1,…,vn的任意隨機序列；第二部分稱為斷點編碼段，其作用是將路由編碼段隨機劃分為m個片段。這m個片段即是m個旅行商各自需要訪問的城市序列，每個片段包含的城市數(shù)應(yīng)不少于常量D，使得每個旅行商所訪問的城市數(shù)大致相等，以體現(xiàn)工作量的均衡性。如圖1所示，表示3個旅行商需要訪問8個城市的兩段式編碼。

圖1 兩段式染色體編碼示例

記旅行商的起點城市為0，則第一個旅行商的訪問回路為（0-5-2-0），第二個旅行商的訪問回路為（0-4-7-1-0），第三個旅行商的訪問回路為（0-8-3-6-0）。

2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用來評估種群個體在遺傳進化過程中對生存環(huán)境的適應(yīng)程度。適應(yīng)度較高的個體，將獲得更多的繁殖機會，遺傳到下一代的概率較大，而適應(yīng)度較低的個體，其繁殖機會相對較少，遺傳到下一代的概率就相對小一些。

根據(jù)BMTSP問題的數(shù)學(xué)模型，其目標函數(shù)是使路程最長的旅行商回路最小化，為此本文算法的適應(yīng)度函數(shù)取m個旅行商路程長度的最大者。設(shè)m個旅行商各自所訪問的城市數(shù)（除起點城市外）分別為n1,n2,…,nm，第k個旅行商所訪問的城市編碼序列記為{0,1,2,…,nk}（0 是起點城市的編號），則適應(yīng)度函數(shù)的計算公式為：

由適應(yīng)度函數(shù)可知，當(dāng)適應(yīng)度值越小，意味著路程最長的旅行商回路越短，那么個體更優(yōu)。

2.3 快速單親變異策略

單親遺傳算法取消了交叉操作，因此如何基于父代個體進行單親變異，是算法設(shè)計的關(guān)鍵。遺傳算法求解TSP 問題時，被廣泛采用的變異算子有“基因換位、倒序、左移、右移”等，其尋優(yōu)能力較強。為此，本文算法將這四種變異算子與隨機插入思想相結(jié)合，形成以下4 種新的快速單親變異算子：

a.基因換位，隨機產(chǎn)生兩個基因點，將這兩個基因點的基因進行交換，再將介于這兩個基因點之間的基因片段剪切插入到染色體的另一個隨機點位置；

b.基因倒序，隨機產(chǎn)生兩個基因點，將這兩個基因點內(nèi)的基因片段按位倒序，再將倒序后的基因片段剪切插入到染色體的另一個隨機點位置；

c.基因左移，隨機產(chǎn)生兩個基因點，將這兩個基因點內(nèi)的基因片段按位循環(huán)左移一次，再將改變后的基因片段剪切插入到染色體的另一個隨機點位置；

d.基因右移，隨機產(chǎn)生兩個基因點，將這兩個基因點內(nèi)的基因片段按位循環(huán)右移一次，再將改變后的基因片段剪切插入到染色體的另一個隨機點位置。

對單個染色體隨機執(zhí)行其中之一的變異算子來進行變異操作。通過上述4種變異算子的單親繁殖與變異，較大幅度增加了種群多樣性，提升了種群全局尋優(yōu)能力，也加快了進化速度。將變異片段剪切后進行隨機插入，有利于迭代后期防止陷入局部最優(yōu)。

2.4 選擇策略

在遺傳算法中，選擇策略的作用是從種群中挑選出基因優(yōu)良的個體，淘汰掉弱勢個體，從而實現(xiàn)仿生學(xué)的“優(yōu)勝劣汰、適者生存”機制。常用的選擇策略包括輪盤賭策略、錦標賽策略、精英選擇策略，以及一些演變和改進的新型選擇策略，它們往往各有針對性，適用于不同的情形。

在本文算法中，通過執(zhí)行快速單親變異策略后，種群個體得到快速繁殖，種群多樣性得到較大的豐富和提高，為此采用一種改進的精英選擇策略，其方法是將父代種群和子代種群合并，再按個體適應(yīng)度排序，最后選擇適應(yīng)度最好的前N個精英個體（N為種群規(guī)模），構(gòu)成下一代種群。

精英選擇策略只選擇種群中的最優(yōu)良個體，因此它可以大幅加快收斂速度，但是如果種群遺傳進化的多樣性不夠，則該策略將導(dǎo)致算法早熟而陷入局部最優(yōu)。

2.5 最近鄰點局部優(yōu)化策略

通過執(zhí)行2.3節(jié)的快速單親變異策略，種群規(guī)模得到快速擴大，全局尋優(yōu)能力得到增強，但是在局部尋優(yōu)能力上還有所欠缺，特別是在迭代的中后期，個體已經(jīng)進化比較充分，如何進一步提高求解精度、逼近理論最優(yōu)解，還可以設(shè)計新的輔助策略。

局部尋優(yōu)能力的增強，意味著需要對旅行商路徑中部分不優(yōu)的節(jié)點序列進行調(diào)整，對此貪心思想［18］是一種常見的處理方法，即對旅行商路徑的某部分節(jié)點序列，按一定的貪心規(guī)則進行重新排序，使旅行商的整個路徑長度更短，對應(yīng)個體的適應(yīng)度更優(yōu)。

為此，本文算法給出基于最近鄰點的局部優(yōu)化策略，其處理步驟如下：

Step1：對種群的每一個體，查找路徑最大旅行商所對應(yīng)的染色體，記為R；

Step2：對染色體R，隨機生成兩個基因點I1和，將從I1到I2所包含的基因片段記為；

Step3：對基因片段S，從基因 1Ir開始，在右側(cè)節(jié)點集合中查找它的最近鄰點（距離最近的節(jié)點），將其交換到該基因的后面；重復(fù)本操作，直到S中全部基因被處理完；

Step4：重新計算該個體的適應(yīng)度，若比之前的適應(yīng)度更優(yōu)，則保持對基因片段S的局部優(yōu)化，否則還原基因片段S；

Step5：返回Step1 處理下一個個體，直到種群個體全部處理完畢。

在Step4中，借鑒了自然界生物個體的競爭排斥思想［19］，對局部優(yōu)化前后的個體按適應(yīng)度優(yōu)劣進行競爭，把適應(yīng)度差的個體排斥掉，保留適應(yīng)度優(yōu)的個體，以此增強個體的局部尋優(yōu)能力。

上述局部優(yōu)化策略，只對每個個體中路徑最大的旅行商路徑進行基于最近鄰點的貪心局部優(yōu)化，既符合BMTSP問題對旅行商路徑最大最小化的目標要求，又對算法的計算量進行了合理的控制，使得算法具有較快的運算速度。

2.6 算法流程圖

根據(jù)單親遺傳算法的基本流程，本文設(shè)計的IFPGA 算法首先需要隨機生成初始種群，并設(shè)置算法所需的有關(guān)參數(shù)，如城市坐標，旅行商人數(shù)，算法最大迭代次數(shù)等；然后對每個初始個體進行快速單親變異操作繁殖后代，這樣可以保證種群的多樣性，擴大解空間的搜索范圍；計算父代與子代的適應(yīng)度值，利用精英策略選擇出優(yōu)良個體；對優(yōu)良個體進一步局部優(yōu)化，使每個旅行商所走路徑更短，從而得到最優(yōu)解。結(jié)合上述算法設(shè)計，算法具體流程圖如圖2所示。

圖2 改進快速單親遺傳算法流程

3 仿真實驗與結(jié)果分析

3.1 實驗準備

實驗環(huán)境為AMD A8-45000M CPU/8GB、操作系統(tǒng)為windows7、編程語言為matlab2019a。實驗數(shù)據(jù)從TSPLIB中選取3組算例共12種情形，包括eil51 算例的三種情形（m=3、5、10），kroA100 算例的四種情形（m=3、5、10、20），kroB150算例的五種情形（m=3、5、10、20、30），后續(xù)計算時式（8）中的常量D取所有旅行商近似均分全部城市節(jié)點。

為了檢驗IFPGA 算法的性能與有效性，下面從3 個方面進行實驗與分析。首先，分析IFPGA算法的求解性能，尤其是最近鄰點局部優(yōu)化策略和隨機插入操作對性能的提升效果；其次，驗證IFPGA 算法對所選取算例的求解能力；最后，將IFPGA算法與其他啟發(fā)式算法對所選取算例的求解結(jié)果進行比較。

3.2 IFPGA算法的求解性能分析

以算例kroB150為例，旅行商人數(shù)為m=10，種群規(guī)模為N=400、迭代次數(shù)為G=1 200。用IFPGA算法求解該算例，分別測試基于最近鄰點的局部優(yōu)化策略起作用和不起作用時的求解性能，繪制遺傳進化曲線如圖3所示。

圖3 最近鄰點局部優(yōu)化策略對算法性能的提升

從圖3 可以看到，IFPGA 算法的收斂速度非常快，當(dāng)?shù)?00 次左右就已經(jīng)快速下降。當(dāng)采用了最近鄰點的局部優(yōu)化策略時，遺傳進化效果得到明顯提升，求解精度更高。

為測試算法中單親遺傳算子與隨機插入思想的融合效果，仍按上述算例及參數(shù)分別作有隨機插入和無隨機插入的單親遺傳操作，繪制求解過程的遺傳進化曲線如圖4所示。

圖4 隨機插入操作對算法性能的提升

從圖4 可以看到，隨機插入操作對迭代的中后期具有持續(xù)改進的能力，進一步提升了算法在進化后期的局部尋優(yōu)能力，也能較好地避免陷入局部最優(yōu)。

3.3 IFPGA算法對算例的求解能力

對上述選取的3 個算例（Example）12 種旅行商人數(shù)（m）的情形，選取適當(dāng)?shù)乃惴▍?shù)：種群規(guī)模（N）、迭代次數(shù)（G）。將IFPGA算法在相同環(huán)境和參數(shù)下獨立運行30次，統(tǒng)計所求最優(yōu)解的最大值（Max）、最小值（Min）、均值（Mean）、標準差（Std）、平均耗時（Times），結(jié)果如表1所示。

表1 IFPGA對3個算例12種情形的求解結(jié)果

從表1 可以看到，IFPGA 算法能以較小的種群規(guī)模和迭代次數(shù)在較少的時間內(nèi)求得最優(yōu)解。從求解穩(wěn)定性上，對3 個算例12 種情形所求得最優(yōu)解的最大值、最小值相對于均值都沒有出現(xiàn)明顯的偏離，標準差也較小，體現(xiàn)出算法較強的穩(wěn)定性。從求解的平均耗時上，表現(xiàn)出旅行商人數(shù)少則耗時多，反之則耗時少的特點。例如，對算例kroB150，IFPGA 算法的平均耗時（Times）與旅行商人數(shù)（m）的變化趨勢如圖5所示。

圖5 平均耗時－旅行商人數(shù)的變化關(guān)系

由于旅行商人數(shù)較少時，每個旅行商平均需要各自經(jīng)過的城市數(shù)就更多，路徑也更長，此時求解所花費的時間必然更多；隨著旅行商人數(shù)增多，每個旅行商需要各自經(jīng)過的城市數(shù)變少，此時IF?PGA 算法的求解性能明顯提升，特別是平均耗時（Times）有明顯下降。

記算法的平均耗時和旅行商人數(shù)分別為變量T,m，通過擬合可近似建立兩者的變化關(guān)系式為

利用式（8）可以對IFPGA 算法求解kroB150算例在不同旅行商人數(shù)時的平均耗時進行大致估計。對其他算例或?qū)嵗龜?shù)據(jù)，也可以類似獲得IF?PGA算法的平均耗時估計式，以此為算法的實用性進行更好的評估和控制。

3.4 IFPGA算法與其他算法的比較與分析

為進一步驗證IFPGA 算法的性能，本節(jié)將其與其他文獻中啟發(fā)式算法的求解結(jié)果進行比較。與經(jīng)典TSP不同，MTSP沒有開放的指定算例用于算法測試。為保持公平性，并且更有效地測試本文所設(shè)計算法的改進效果，因此選取一些已有的采用同個測試算例的改進遺傳算法和其他算法得到的實驗數(shù)據(jù)（均來自相關(guān)文獻）與之對比。參與比較的算法包括：利用兩部分染色體交叉算子的改進遺傳算法（TCX）［20］、穩(wěn)態(tài)分組遺傳算法（GGA-SS）［21］、入侵雜草優(yōu)化算法（IWO）［19］、融合雜草算法繁殖機制和局部優(yōu)化變異算子的改進遺傳算法（RLGA）［9］，結(jié)果如表2所示。

表2 幾種算法求解3個算例12種情形的結(jié)果比較

從表2 可以看到，與TCX、GGA-SS、IWO 和RLGA相比，IFPGA算法的求解結(jié)果都優(yōu)于其余幾種算法得到的結(jié)果。尤其是在算例kroB150中，當(dāng)旅行商人數(shù)m為3、5時，與其他幾種算法相比，求解精度的提高更為明顯，表明IFPGA 算法對較大規(guī)模BMTSP 問題在較少旅行商人數(shù)時具有比其余幾種算法更優(yōu)良的求解能力。當(dāng)旅行商人數(shù)較多時，雖然IFPGA算法的求解精度提升幅度不多，但是通過3.3 節(jié)的分析可知，其平均耗時下降很快，因此求解速度將會更快。

4 結(jié)語

針對均衡多旅行商問題（BMTSP），本文首先利用0-1變量添加了有工作量均衡要求的約束條件，完善了BMTSP 問題的數(shù)學(xué)模型，為后續(xù)在均衡條件下進行算法求解奠定了基礎(chǔ)；其次，基于遺傳算法的通用框架，提出了一種改進的快速單親遺傳算法，把加快速度的重點在于強化單親變異策略上，將常用的四種基因變異算子與隨機插入思想相結(jié)合，比較明顯地改善了父代個體變異為子代個體的多樣性，擴大了算法的搜索尋優(yōu)范圍；最后，受貪婪算法思想的啟發(fā)，在算法中單獨設(shè)置基于最近鄰點的局部優(yōu)化策略，以便對經(jīng)過精英優(yōu)選的子代個體再次進行局部改善，從而進一步增強種群個體的局部搜索尋優(yōu)能力。實驗仿真表明，本文的改進方法是可行且有效的。這些改進思路和方法對遺傳算法的進一步運用和發(fā)展有較好的推動作用，也對多旅行商問題的深入研究甚至實用化提供更多的手段，為生產(chǎn)實踐提供更多的決策分析依據(jù)。