改進離散煙花算法求解旅行商問題的研究?

王思琦 高 尚 張 寧

（江蘇科技大學計算機學院 鎮江 212000）

1 引言

旅行商問題（Travelling Salesman Problem，TSP）是一種復雜的NP難題，近幾十年來，許多專家學者進行了大量的研究，為解決這一問題提出了許多群智能算法。這些算法簡單易操作，具有分布式計算機制、強魯棒性、良好擴展性以及廣泛的適應性等特點，為求解該類問題提供了新思路。典型的智能算法有模仿螞蟻集體覓食行為的蟻群算法（ACO），模擬鳥類捕食行為的粒子群算法（PSO），借鑒達爾文生物進化過程的遺傳算法（GA）等，它們不僅僅能夠解決路徑規劃問題，并被應用在多種領域。但其都有各自的局限性，例如GA需要對問題進行編碼解碼，對初始種群有一定的依賴性［1］；ACO初始信息素匱乏，收斂速度慢，易陷入局部最優［2］；PSO優化速度和精度較低，計算效果與算子復雜度成正比［3］。

離散煙花算法（discrete fireworks algorithm，DFWA）是北京大學譚營教授繼2010年開創性論文“Fireworks algorithm for optimization”［4］后提出的一種解決離散問題的群智能算法。針對煙花算法易陷入局部最優、火花之間缺少交流機制、選擇策略隨機性較大［5］等局限性，許多研究學者已經提出了相關改進策略。如：Zheng與Li［6等研究了煙花算法爆炸幅度的自適應策略，提出了動態搜索煙花算法和自適應煙花算法；Yu［7］等研究了煙花算法與差分演化算法的結合；Zhang［8］等提出生物地理學優化-煙花混合算法；Zhu［9］等提出引力搜索算子加強了火花之間的信息交流；徐煥芬等［10］提出雙種群煙花算法促使種群間的信息交換以提高精度等。應用領域主要包括多目標調度問題［11］、方向性特征距離度量、油料作物的施肥問題、圖像識別［12］、云計算［13］等。

隨著煙花算法的不斷改進，其在連續優化問題中已經表現出了出色的尋優能力，但離散煙花算法在路徑優化問題方面的研究還很缺乏。為此，以解決TSP問題為目的，針對離散煙花算法中的選擇策略，將每一代個體中最優解（適應度最小）保留，并且利用選擇參數動態調整種群的被選概率，將精英火花與動態選擇火花作為子代進行迭代搜索，以增強算法全局搜索能力，加快收斂速度，保證種群多樣性及算法精度。

2 離散煙花算法

與傳統煙花算法相比，離散煙花算法結構與其相似，由于其解不會超過定義域范圍，從而省略了映射這一步［14］，包括爆炸算子、變異算子和選擇策略。算法流程如圖1所示。

圖1 離散煙花算法流程圖

2.1 爆炸操作

考慮到離散的路徑規劃問題其解為一個不重復序列，因此爆炸操作被定義為單個個體中兩條邊或三條邊的交叉互換，從而產生新解，相當于2-opt操作和3-opt操作。把初始化的解帶入適應度函數中計算適應度值，并根據適應度大小來產生火花。每個煙花爆炸的火花個數的計算公式如下：

其中，Si為第i個煙花爆炸所產生的火花個數；Ymax是當前適應度最差即適應度值最大的個體的適應度；f(xi)為第i個個體的適應度值；m為最大火花數目；ε為避免分母為零的極小常數。

2.2 均勻變異操作

考慮到爆炸算子是對邊進行操作，均勻變異則定義為對點操作，目的是將個體中的一個點插入到兩個相鄰點中，以得出一個更優個體。例如，原個體為，要使ak插入到邊(ai，ai+1)中，先將子序列(ai+1，…，ak)反轉，再將子序列(ak-1，…，ai+1)反轉，使得原序列變化為(… ，ai，ak，ai+1，…，ak-1，ak+1，…) ，從而得出新個體。如圖2所示，經過變異后的新回路的路徑長度要明顯優于原回路。

圖2 均勻變異操作

2.3 選擇策略

選擇策略則是由精英選擇和輪盤賭策略相結合，保留最優解的同時加強局部搜索。每個個體被選中的概率可表示為

其中Lmin是最小適應度值，即最短路徑的長度；ε為防止除零情況的一個極小參數。

輪盤賭策略的出發點是適應度值越好，其被選中的概率越大，但其隨機性大并忽略了可能在下一代中爆炸變異出更好子代的差解，因此提出對選擇操作進行改進。

3 改進離散煙花算法

3.1 適應度函數

在TSP問題中，其解為一個無重復的序列，用向量x=(x1，x2，…，xn)表示，xi為路徑中第i個配送點，每個配送點必須且只能經過一次。因此待求問題L(x)可表示為

其中d(xi，xj)為第i個配送點和第j個配送點之間的距離。顯然，算法的優化目標是min(L(x))，并且滿足：

3.2 基于精英選擇和動態調整的選擇策略

易陷入局部最優是離散煙花算法的不足之處，利用確定性選擇和隨機選擇相結合，通過選擇過程中加入動態參數［15］來使其跳出局部收斂，能夠加強離散煙花算法的全局搜索，保證種群多樣性，更有利于提高算法尋優能力。

傳統離散煙花算法中的精英選擇是將初始煙花和火花同時納入備選，其中最優解保留到下一次迭代中。改進后的精英選擇，將備選種群內的父代煙花剔除，只在子代火花種群中進行選擇。由于均勻變異操作只接受更優的解，因此一定程度上增大了選擇到優質種群的概率，其偽代碼如下。

考慮到被選概率依賴于適應度值的大小，而傳統離散煙花算法中選擇的子代個數為一個定值，并且式（2）中2次冪的形式使得優秀的個體更易被選中這樣不利于較差解被選入下一代進行爆炸變異操作，從而不利于算法進行全局搜索。受文獻［16］啟發，提出嘗試加入動態參數η和λ來調整選擇數量以及被選概率。

其中η為選擇子代數量，t為當前迭代次數，s為火花數目，C1和C2分別為增大因子和縮小因子。當本次平均適應度優于前一次平均適應度時減小選擇數目，反之增加選擇數目。

其中：

t為當前迭代次數。經實驗證明隨著迭代次數的增加，參數λ越來越小，對個體被選概率的干預增加，降低隨機性從而使算法跳出局部最優。

該策略通過C1和C2來調整子代的選擇數目，迭代前期適當增加子代數目，擴大搜索范圍，而參數λ使得適應度較小的個體更容易被選擇，在迭代的中后期最優解已經趨于穩定，則不需要過多的子代進行重復操作，而適當增加適應度較大的個體被選概率可以防止算法搜索過程中出現早熟。

改進后的選擇策略為

4 仿真實驗結果與分析

為驗證本文算法的優越性，利用Matlab R2016a軟件模擬34個地點進行實驗，將路徑距離之和作為適應度函數，并和遺傳算法、傳統離散煙花算法進行對比。實驗參數設定為34個配送地坐標如表1，遺傳算法種群大小為100，最大遺傳代數500，交叉概率0.9，變異概率0.05；離散煙花算法煙花數量為5，最大火花數目為50，最大迭代次數為500次；本文算法煙花數量為5，最大火花數目為50，最大迭代次數為500次，增大縮小因子為±0.2。將三種算法各運行30次。

表1 34個點坐標

圖3為改進算法運行的最優路徑結果。其最優路徑為5→17→18→20→19→12→24→21→16→7→27→6→1→3→28→30→8→2→29→9→32→31→14→23→15→33→13→26→22→11→25→4→10→34→5的回路，最優距離為15.6745。表2可見三種算法所尋找到的最優解差別不大，但遺傳算法所需要的平均迭代次數較多，與改進離散煙花算法相差甚遠，收斂速度較慢；傳統離散煙花算法平均最優解略高，收斂代數比改進后的算法多出40代左右，兩種算法所得方差較大，穩定性都略低于本文算法。

圖3 改進算法所得最優路徑

表2 算法對比實驗結果

將改進離散煙花算法與遺傳算法的優化過程對比，由圖4可見改進離散煙花算法在前期收斂速度相當快，能夠在前50代迅速下沉，尋優精度方面也明顯優于遺傳算法，說明精英選擇和動態參數的結合使得離散煙花算法的全局搜索能力增強的同時收斂速度加快，在解決TSP問題上的性能有較大提升。

圖4 改進算法和遺傳算法的優化過程

進一步驗證所提改進離散煙花算法的性能，在Matlab R2016a軟件上將該算法應用到TSP標準數據集中進行測試，并與GA、PSO和ACO各運行20次進行對比，選取的TSP標準數據集為Fri26、Bays29、Att48、Eil51。

由表3可知改進離散煙花算法在以上數據集中的性能均優于其他三個算法，更接近已知最優解，從數據集大小來看本文算法在小數據集上體現的性能更為優異，預測隨著數據集的增大其穩定性可能將會受到影響，因此選取數據集Eil101為下一個實驗對象，將本文算法與遺傳算法進行對比實驗，結果如下。

表3 算法實驗結果對比

由表4可知對于較大規模數據集，遺傳算法的尋優性能更為優異，改進離散煙花算法的最優解雖與遺傳算法仍有差距，但在算法穩定性上有明顯進步。圖5為改進離散煙花算法和遺傳算法的一次尋優過程對比，改進算法在迭代初期優于遺傳算法，收斂速度較快，優化比較穩定，但在600代以后尋優效率降低，曲線趨于平滑，從而導致最后尋優精度略低于遺傳算法。

表4 算法在數據集Eil101的實驗對比

圖5 兩種算法在數據集Eil101上的對比

5 結語

本文提出了一種改進的離散煙花算法，根據原算法易陷入局部最優而導致的早熟問題將選擇策略改進為基于精英選擇和動態參數相結合的策略，極大提升了算法的全局搜索性能，增加種群多樣性的同時保證算法的收斂速度。通過與GA、PSO、ACO和傳統離散煙花算法對TSP數據集的測試證明改進算法對小規模數據具有優良性能，大規模數據集以及不對稱TSP問題將是后續的研究方向。