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

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

0 引言

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

1 具有解空間動態(tài)縮減的改進(jìn)算法構(gòu)建

1.1 典型排列組合優(yōu)化問題模型

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

其中：n為城市的個數(shù)，Dij為城市i到j(luò)的距離，xij為從i到j(luò)路徑長。

1.2 解空間動態(tài)縮減策略

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

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

圖1 解空間動態(tài)縮減策略Fig.1 Solution space dynamic compression strategy

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

1.3 算法流程

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

圖2 改進(jìn)算法流程Fig.2 Flowchart of the improved algorithm

步驟1 參數(shù)初始化，即設(shè)置相應(yīng)算法所需要的參數(shù)。

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

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

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

步驟5 將矩陣D1按照解空間動態(tài)縮減策略轉(zhuǎn)換為D2。

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

步驟7 對d3利用m中記錄的重復(fù)排列進(jìn)行還原，還原為原始城市個數(shù)的路徑d4。

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

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

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

2.1 改進(jìn)算法效果驗證

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

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

表1 仿真實驗結(jié)果Tab.1 Simulation results

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

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

第一階段 應(yīng)用蟻群算法（ACO）對距離矩陣D1進(jìn)行搜索，得到路徑d1。

第二階段 應(yīng)用蟻群算法（ACO）對距離矩陣D1進(jìn)行搜索，得到路徑d2。

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

第四階段和第五階段 對第二階段和第三階段的重復(fù)。

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

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

圖4 優(yōu)化路徑Fig.4 Optimized path

2.2 重復(fù)排列長度對算法的影響

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

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

從表2中可以看出隨著最小重復(fù)排列的長度增加，應(yīng)用解空間動態(tài)縮減策略的改進(jìn)蟻群算法對原算法的提升率逐步減小，方差呈增加的趨勢，說明了不同長度的重復(fù)排列對算法優(yōu)化均具有一定作用，并且當(dāng)最小重復(fù)排列的長度增加時，使得改進(jìn)算法的結(jié)果偶然性增大，算法的穩(wěn)定性變差。

2.3 VRP算例驗證

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

表3 VRP仿真實驗結(jié)果Tab.3 Simulation results of VRP

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

3 結(jié)語

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