求解排列組合問題的解空間動態縮減策略

李章洪，梁曉磊，田夢丹，周文峰

（武漢科技大學汽車與交通工程學院，武漢430065）（*通信作者電子郵箱liangxiaolei@wust.edu.cn）

0 引言

排列組合優化問題是一類NP-hard 問題，此類問題規模的擴大將導致解空間呈指數式增長，對求解算法具有極高的要求。典型的問題有旅行商問題（Travel Salesmen Problem，TSP）、車輛路徑調度問題（Vehicle Routing Problem，VRP）、船舶配載（Stowage Optimization，SO）問題等。現代智能優化算法是解決排列組合優化問題的主要方法，目前主要集中于對蟻群優化（Ant Colony Optimization，ACO）算法、模擬退火（Simulated Annealing，SA）算法、遺傳算法（Genetic Algorithm，GA）、免疫算法（Immune Algorithm，IA）等啟發式算法及其改進等方面，其思路主要以算法自身機制調整及多種算法混合進行算法性能提升。例如：針對TSP，為了避免傳統遺傳算法容易陷入局部最優解的缺點，于瑩瑩等［1］引入貪婪算法對種群進行初始化；何慶等［2］將模擬退火算法和遺傳算法進行了有效的組合；胡云清［3］提出了一種混沌模擬退火算法來求解VRP，提高了問題的求解速度。針對傳統蟻群算法求解速度慢、容易陷入局部最優解的問題，周永權等［4］對蟻群算法信息素的更新規則做出了改變；吳新杰等［5］通過改進基本的蛙跳算法，增大了搜索空間，在一定程度上防止了TSP容易早熟的缺陷；王艷等［6］引入對數遞減的慣性權重來影響螢火蟲的位置，并結合遺傳算法中的選擇、交叉、變異等概念對螢火蟲算法進行改進；為了增強煙花算法求解TSP的穩定性、提高收斂速度，蔡延光等［7］提出了一種混沌煙花算法。上述為此類問題的研究提供了較好的思路和解決方法，但集中于算法自身搜索機制的改進，對算法搜索行為和問題特征的融合分析較少，當問題規模急劇增加時仍然面臨著解空間過大、個體有效搜索緩慢、群體搜索停滯等問題。而通過群體搜索過程中解的分析，可知群體迭代搜索中解具有一定的重疊相似性，如可以利用這一特點進行解空間的縮減，將會大幅度降低群體搜索成本，提高搜索效率。本文正是通過對排列組合優化問題解自身特點的研究，提出了一種解空間動態縮減（Solution Space Dynamic Compression，SSDC）的個體編碼策略，并將這種新的編碼策略應用于TSP和VRP進行求解。

1 具有解空間動態縮減的改進算法構建

1.1 典型排列組合優化問題模型

排列組合是組合學最基本的概念。排列就是指從給定個數的元素中取出指定個數的元素進行排序；組合則是指從給定個數的元素中僅僅取出指定個數的元素，不考慮排序。排列組合的中心問題是研究給定要求的排列和組合可能出現的情況總數。排列組合優化是指從可能出現的情況中尋找到最優或者近優的解。旅行商問題（TSP）是排列組合問題中的典型問題，不失一般性，本文主要以旅行商問題進行問題分析。TSP 是一類典型的排列組合優化問題，是指商人從起點出發，然后遍歷剩下的全部城市，最后回到起點，要求從中找到一條距離最短的路徑。TSP的數學模型如下：

其中：n為城市的個數，Dij為城市i到j的距離，xij為從i到j路徑長。

1.2 解空間動態縮減策略

以TSP 為例，通過對排列組合問題求解過程中多個可行解個體表達的分析，比較其結構時會發現，部分排列片段具有重復出現的現象。通過對TSP、VRP 等問題解的圖像觀察，這些重復出現的排列大概率是特征較優的路段，也就是對求解結果比較有利的路段。馮志雨等［8］通過聚類的方法，將TSP分割成較小的簇來對問題進行求解；饒衛振等［9］提出了距離矩陣方差最小法來對TSP 的距離矩陣進行改進；程畢蕓等［10-12］在蟻群算法的基礎上提出了一種二次更新信息素的策略以提高最優解子路徑被選擇的概率，在粒子群算法的基礎上給路徑設置合理的優秀系數，以提高短邊被選擇的概率。在以上研究的啟示下，本文對重復出現的排列段進行保留，只允許重復排列的起止點參加新的排序。通過這樣的處理方法在一定程度上減小了排列組合優化問題的規模，縮小了群體搜索的可行空間，提升了個體在有限空間內的搜索效率，能更大概率地獲得更優解。具體的構建過程如圖1所示。

如圖1 是對一個TSP 進行求解生成的兩條路徑d1和d2。兩條路徑中路段1-2-3-4 是重復出現的排列，第一步將重復出現的排列1-2-3-4 記錄到m中（方便之后將整條路徑還原）；第二步將城市2、3 從原城市集合中剔除；第三步對重復路段的起止點1-4 的距離設為0（為保證再一次求解過程中路段1-4能被選擇）；第四步利用剩余城市的坐標和路段1-4 之間的特殊距離0 生成新的距離矩陣；最后運用常規智能算法在新矩陣下進行繼續求解。

圖1 解空間動態縮減策略Fig.1 Solution space dynamic compression strategy

本策略的編碼和解碼設計是針對結果特征，通過采用整數規則基于常規智能算法所求得路徑對原問題的距離矩陣進行漸進式調整，以此達到空間縮減的目的，并未對常規智能算法搜索機制進行改變。因此在采用相同編碼規則下，本策略可以應用于多種智能算法對類似問題進行求解，具有較好的適用性。

1.3 算法流程

本文改進算法流程如圖2所示，具體的步驟如下：

圖2 改進算法流程Fig.2 Flowchart of the improved algorithm

步驟1 參數初始化，即設置相應算法所需要的參數。

步驟2 利用式（5）計算TSP的距離矩陣D1。式中：n為城市個數，a、b為城市坐標。

步驟3 利用智能算法g求解得到路徑dn（g代指一種群智能算法，n為路徑編號）。

步驟4 如果n不大于2，返回步驟3。

步驟5 將矩陣D1按照解空間動態縮減策略轉換為D2。

步驟6 利用智能算法g對D2進行求解，生成路徑d3。

步驟7 對d3利用m中記錄的重復排列進行還原，還原為原始城市個數的路徑d4。

步驟8 利用式（1）計算路徑d1、d2、d4的長度，將最短的路徑記為d1。

步驟9 判斷是否達到終止條件，若達到則輸出結果；若未達到則返回步驟3。

2 仿真實驗與結果分析

2.1 改進算法效果驗證

為了驗證改進方法的有效性，本文分別對蟻群優化（ACO）算法、模擬退火（SA）算法、免疫算法（IA）改編為解空間動態縮減蟻群優化（Solution Space Dynamic Compression Ant Colony Optimization，SSDCACO）算法、解空間動態縮減模擬退火（Solution Space Dynamic Compression Simulated Annealing，SSDCSA）算法、解空間動態縮減免疫算法（Solution Space Dynamic Compression Immune Algorithm，SSDCIA）并用標準測試函數庫TSPLIB 里面的5 個測試算例dantzig42、st70、eil101、pr144 和bier127 進行算法測試。蟻群算法的參數組合為：種群規模m=18，啟發因子α=1，期望啟發因子β=5，信息素揮發系數ρ=0.5，信息素強度Q=10，最大迭代次數Nmax=100；模擬退火算法的參數組合為：初始溫度t0=120，最后溫度t=1，溫度衰減系數a=0.99，Markov鏈長度=5 000；免疫算法的參數組合為：群體規模NP=200，交叉概率Pc=0.5，變異概率Pm=0.1，克隆個數Ncl=10，最大免疫代數G=1 000。所有算法采用Matlab 2018a 實現，基于i5 CPU 2.50 GHz 處理器，4 GB RAM，操作系統為64 位Windows 10 系統平臺進行測試。實驗中針對單個算例，每個測試算法獨立運行10 次，實驗結果從平均值、最優值、最差值、方差及提升率進行統計學分析。

表1中理論最優值來源于TSPLIB 提供的最優值，原算法的值來源于每次改進算法原始矩陣下出現的最優值，提升率為改進算法相較于原算法平均值優化的程度。從表1中可以看出，算法SSDCACO、SA、SSDCSA 獲得了比測試算例dantzig42理論最優值更好的解，SSDCSA在其他算例的測試結果也已接近理論最優值。總體上，運用本文提出的解空間動態縮減策略的三種改進算法無論是求解TSP效果比較好的模擬退火（SA）算法還是效果一般的免疫算法（IA）得到的最優值、最差值和平均值均要優于原算法，可見本文提出的解空間動態縮減策略的優越性。

表1 仿真實驗結果Tab.1 Simulation results

由于改進方法的步驟較原有的算法復雜，迭代次數和運算時間也明顯增加。為了證明是改進方法使TSP 得到優化，本文做了進一步的比較分析，將dantzig42 問題運用原蟻群算法（ACO）和改進蟻群算法（SSDCACO）在相同迭代次數下進行結果比較。收斂曲線和優化路徑如圖3、圖4所示。

圖3中改進蟻群算法的收斂圖像分為了五個階段：

第一階段 應用蟻群算法（ACO）對距離矩陣D1進行搜索，得到路徑d1。

第二階段 應用蟻群算法（ACO）對距離矩陣D1進行搜索，得到路徑d2。

第三階段 在路徑d1和d2的基礎上使用解空間動態縮減策略將原始距離矩陣D1轉換為D2，然后采用蟻群算法（ACO）進行搜索，得到路徑d3。

第四階段和第五階段 對第二階段和第三階段的重復。

圖3中第三階段和第五階段應用解空間動態縮減策略后路徑值均優于蟻群算法單獨搜索，說明了應用解空間動態縮減策略的改進算法優于原算法；第五階段的路徑值優于第三階段，說明了解空間動態縮減策略能在一次求解過程中多次運用；圖3中還可以看出，在總迭代次數相同的情況下，改進算法的路徑搜索結果優于原算法，說明了解空間動態縮減策略的有效性。

圖3 改進前后蟻群算法收斂曲線Fig.3 Convergence curves of initial and improved ant colony optimizations

圖4 優化路徑Fig.4 Optimized path

2.2 重復排列長度對算法的影響

為了研究重復排列長度對解空間動態縮減策略有效性的影響，本文在編碼時對最小重復排列長度做了區分，分別為2城市、3 城市、4 城市、5 城市，并在測試算例eil101、bier127 運用改進的蟻群算法做實驗，實驗結果如表2所示。

表2 最小重復排列長度對比實驗結果Tab.2 Experimental results of minimum repeat permutation length

從表2中可以看出隨著最小重復排列的長度增加，應用解空間動態縮減策略的改進蟻群算法對原算法的提升率逐步減小，方差呈增加的趨勢，說明了不同長度的重復排列對算法優化均具有一定作用，并且當最小重復排列的長度增加時，使得改進算法的結果偶然性增大，算法的穩定性變差。

2.3 VRP算例驗證

為了證明本文提出的方法同樣適用于其他的排列組合優化問題，本文將解空間動態縮減策略應用于模擬退火算法（SA）對車輛路徑優化問題（VRP）進行求解。算例來源于The VRP Web 里的測試算例A-n64-k9 和A-n80-k10。測試算法獨立運行10次，仿真實驗數據統計結果如表3所示。

表3 VRP仿真實驗結果Tab.3 Simulation results of VRP

從表3 結果中可以看出，基于本文提出新編碼方式的改進算法作用于車輛路徑優化問題與作用于TSP具有相同的效果，在最優值和平均值等方面均優于原算法，這也說明了本文提出解空間動態縮減策略對多種排列組合優化問題起作用，具有一定的通用性。

3 結語

本文針對一般群智能算法對大規模排列組合優化問題求解精度不高及時間過長的不足，提出了一種解空間動態縮減策略，逐步減小算法的搜索空間。在該解空間動態縮減策略中，基于在群智能算法兩次求解，分析并融合解中重復片段，而后對剩余孤立片段再次求解，從而逐步減小群體搜索規模、節約算法搜索成本。通過將該策略用于多種群智能算法求解TSP 和VRP，得到的解均要優于原算法，表明解空間動態縮減策略適用于此類排列組合優化問題。本文所提算法在常規TSP 和VRP 等無約束或弱約束問題取得了較好的效果，對于復雜約束問題如帶時間窗的VRP、柔性車間調度問題的應用將是今后研究的一個重點。