沈秋玲 胡甜 馬婷 李社蕾

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

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

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

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

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

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

對于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}中的一個(gè)隨機(jī)數(shù)，則FTEO定義如下：

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

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

2 仿真結(jié)果分析

為了驗(yàn)證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軟件，進(jìn)行仿真并與蟻群算法和遺傳算法進(jìn)行對比，實(shí)驗(yàn)結(jié)果表明，CSO算法的優(yōu)化結(jié)果由于遺傳算法，和蟻群算法的優(yōu)化結(jié)果相近，但種群的收斂性不如遺傳算法。

3 結(jié)論

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

【參考文獻(xiàn)】

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

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

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

[4]代桂平，王勇，侯亞榮.基于遺傳算法的TSP問題求解算法及其系統(tǒng)[J].微計(jì)算機(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實(shí)現(xiàn)[J].中國測試技術(shù)，2004（02）：58-60.

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

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

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