蟬鳴優化算法在組合優化問題中的應用

沈秋玲 胡甜 馬婷 李社蕾

【摘 要】文獻（1）提出了蟬鳴優化（CSO）算法，利用CSO、PSO和DE對9個高維Benchmark函數的仿真，得到了非常好的優化結果，該算法尚未在組合優化問題中應用，本文利用CSO算法對旅行商問題（TSP），這一典型的組合優化問題，進行優化，建立了CSO算法解決TSP問題的模型，并利用MATLAB進行仿真。實驗結果表明，CSO也是一種非常適于求解組合最優化問題的進化算法。

【關鍵詞】蟬鳴優化算法;組合優化;旅行商問題;水平集

中圖分類號：TP391.4文獻標識碼： A文章編號： 2095-2457（2019）04-0099-002

DOI：10.19694/j.cnki.issn2095-2457.2019.04.038

Application of cicada song optimization algorithm in combinatorial optimization problems

SHEN Qiu-ling HU Tian MA Ting LI She-lei

（College of Information & Inteligence Engineering ?Sanya University，Sanya Hainan 572022，China）

【Abstract】The literature（1）proposed a CSO algorithm and uses CSO， PSO， and DE to simulate 9 high-dimensional Benchmark functions. The result of the optimization is very good. The algorithm has not yet been applied to combinatorial optimization problems. The CSO algorithm optimizes the traveling salesman problem（TSP）， a typical combinatorial optimization problem， established a CSO algorithm to solve the TSP problem model， and used MATLAB to simulate. The experimental results shown that CSO is a kind of evolutionary algorithm very suitable to solve combination optimization problems.

【Key words】Cicada optimization algorithm; Combination optimization; Traveling salesman problem; Level set

0 引言

TSP（traveling salesman problem）的歷史很久，是一個經典的組合優化問題[2-5]，問題表述為[6-9]：假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。很多高效的算法被用于嘗試求解TSP。遺傳算法、蟻群算法、模擬退火算法、粒子群算法和神經網絡等仿自然算法在求解TSP問題上都獲得不錯的結果。隨著旅游業和物流業快速發展，高效、低成本、低能耗成了各個物流企業追求的目標，更加合理的配送路線能明顯地為物流公司增大利潤;如何有效地節省出行費用和時間一直都是游客、旅行社、物流企業探索和研究的內容。出行路線的選擇其實是旅行最優商問題（TSP），是一個組合優化問題。因此，旅行商問題（TSP）有著廣泛的應用領域和巨大的發展空間。

2014年，賀毅朝[2]等人提出了借鑒秋蟬鳴叫中表現出的某種同步化以及蟬的生活習性提出了一種新的仿生優化算法： 蟬鳴優化（CSO），從秋蟬的求偶歌，使用5種信號構成一種音樂節律的現象得到啟發， 提出了一種基于5種不同進化方式的進化算子： 五音進化算子（Five Timbre Evolution Operator ，FTEO），對9個高維Benchmark函數進行仿真計算，在求解數值優化問題性較好，在求解組合優化問題方面尚未進行研究，雖然近年來不斷涌現了許多基于仿生學的優化算法，常見的有粒子群算法、遺傳算法、蟻群算法人工魚等算法。在解決組合問題過程中都得到了很好的優化結果，但是對于某一特定的優化問題，不同的優化算法的優化效果存在一定的差異，因此對于不同的優化問題，設計更適于求解的優化算法是有一定的研究價值的，本文嘗試將CSO算法應用在組合優化問題的求解中，選取旅行商問題（TSP），這一典型的組合優化問題，進行優化，建立了CSO算法解決TSP問題的模型。

1 基于CSO算法的TSP問題數學模型

假設有一個G=（V，E），其中V是頂點集，E是邊集，設D=（dij），是由頂點i和頂點j之間的距離所組成的距離矩陣，TSP問題就是求解一條經過所有頂點且每個頂點只通過一次的具有最短距離的回路。

對于TSP問題，L為問題的最優解，用CSO算法求解該問題，其控制參數如下：種群大小POPSIZE，最大迭代次數NC，城市數目NumCity，距離矩陣D，城市列表W，best_route為最優路徑，inindividual_cso為種群矩陣，大小為POPSIZE*NumCity，rand（5）為{1，2，3，4，5}中的一個隨機數，則FTEO定義如下：

其中，1≤i≤POPSIZE，p1≠p2≠p3≠i，A為（0，1）的隨機數。FTEO算子可能會使群體中產生一些不滿足問題的約束條件或者無意義的巡回路線，為克服這一缺點，采用Grefenstettet 編碼法，任意種群中的個體都對應這一條有實際意義的巡回路線，是的概算子有意義，然后對其解碼得到實際巡回路徑。

設閾值threshold的個體的生命周期，種群inindividual_cso的第i個體的生存因子為sp（i），初始sp（i）=0; 1≤i≤POPSIZE，每當產生新一代種群后，如果當前的最短路徑L_generation>L，則sp（i）= sp（i）+1，否則sp（i）不變。對于種群inindividual_cso中的個體inindividual_cso（i），如果其生存因子sp（i）>threshod，則用一個隨機產生的新個體替換inindividual_cso（i）。

2 仿真結果分析

為了驗證CSO的可行性與有效性，使用硬件環境為Intel（R）Core（TM）i3-2100 CPU@3.10GHz 3.09GHz，3.01GB內存硬件，操作系統為windows XP操作系統， 利用Matlab2012a軟件，進行仿真并與蟻群算法和遺傳算法進行對比，實驗結果表明，CSO算法的優化結果由于遺傳算法，和蟻群算法的優化結果相近，但種群的收斂性不如遺傳算法。

3 結論

本文利用CSO算法對旅行商問題（TSP），這一典型的組合優化問題，進行優化，建立了CSO算法解決TSP問題的模型，利用該算法模擬仿真求解——30個城市的TSP問題，并用MATLAB實現了該算法，仿真實驗結果驗證了CSO結果組合優化問題的可行性和有效性，為解決組合優化問題提供一種方案。優化結果有待進一步改進，下一步考慮將CSO優化算法應用到其他組合優化問題上，研究CSO求解其他組合優化問題的方法，并逐步改進其性能。

【參考文獻】

[1]賀毅朝，李寧，李文斌.蟬鳴優化：一種新的仿生進化算法[J].計算機科學，2014，41（06）：235-238+249.

[2]鄭明，卓慕瑰.四點三線遺傳算法求解旅行商問題[J].計算機工程與應用，2017，53（14）：148-154.

[3]梁旗軍，舒堅，樊鑫，劉琳嵐.一種基于遺傳算法的TSP建模方法[J].計算機工程，2011，37（05）：68-70.

[4]代桂平，王勇，侯亞榮.基于遺傳算法的TSP問題求解算法及其系統[J].微計算機信息，2010，26（04）：15-16+19.

[5]Bergeron J，Nightingai A.Verification methodology manualfor System Verilog [M].New York：Springer-Ver1ag，2006.

[6]葉歡，經亞枝.Grefenstette編碼法的MATLAB實現[J].中國測試技術，2004（02）：58-60.

[7]溫清芳.遺傳算法求解TSP問題的MATLAB實現[J].韶關學院學報，2007（06）：18-22.

[8]袁汪凰，游曉明，劉升，朱艷.求解TSP問題的自適應模擬退火蟻群算法[J].計算機應用與軟件，2018，35（02）：261-266.

[9]陳海英，李淑玉.TSP問題的蟻群算法模型及仿真研究[J].科技通報，2012，28（12）：72-75.