沈秋玲 胡甜 馬婷 李社蕾

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

【關(guān)鍵詞】蟬鳴優(yōu)化算法;組合優(yōu)化;旅行商問題;水平集

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

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

1 基于CSO算法的TSP問題數(shù)學模型

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

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

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

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

2 仿真結(jié)果分析

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

3 結(jié)論

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

【參考文獻】

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

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

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

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

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

[6]葉歡，經(jīng)亞枝.Grefenstette編碼法的MATLAB實現(xiàn)[J].中國測試技術(shù)，2004（02）：58-60.

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

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

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