改進蜂群算法的旅行商問題仿真

蘇曉勤，孫鶴旭，潘旭華

（1.河北工業(yè)大學 控制科學與工程學院，天津 300130；2.天津商業(yè)大學 信息工程學院，天津 300130）

0 引 言

旅行商問題（traveling salesman problem，TSP）由Dantzig等人于1959年提出，已被證明是NP難題的組合優(yōu)化問題，很多文獻中應(yīng)用啟發(fā)式算法求解，希望可以在短時間內(nèi)獲得更好的結(jié)果。多種優(yōu)化算法用來求解TSP問題其中王忠英、白艷萍等［1］應(yīng)用蟻群算法，Ilie、Badica［2］在分布式架構(gòu)中提出分布式的蟻群優(yōu)化算法，Kim和Cho［3］結(jié)合局部搜索的混合算法，另外還有文獻使用了模擬退火算法［4］、遺傳算法［5］，但都面臨易陷入局部最優(yōu)問題且算法的收斂性有待提高。蜂群算法是近幾年新興的優(yōu)化算法，借助各個角色的分工合作與轉(zhuǎn)換能有效改善優(yōu)化問題。Whitfield［6］指出蜜蜂通過搖擺舞把食物源相關(guān)的方向和距離以及食物源好壞等信息傳遞給蜂巢中的其它蜜蜂。Karaboga［7］提 出了 人 工 蜂 群 算 法（artificial bee colony，ABC），并把ABC算法應(yīng)用到解決TSP問題中［8］，其中跟隨蜂的概率指定為固定值。Li－Pei Wong在文獻［9］中利用“首選路徑”的蜂群算法求解TSP 問題。胡中華、趙敏［10］利用ABC算法對TSP 問題進行求解。但上述文獻都未考慮TSP問題求解的復雜度問題，求解大規(guī)模TSP問題時收斂慢、效果下降明顯。

本文模擬蜂群覓食原理，應(yīng)用改進的蜂群算法求解TSP問題，覓食尋優(yōu)過程中蜜蜂動態(tài)轉(zhuǎn)變角色；采用改進的局部搜索策略解決大規(guī)模基準測試問題，有效降低了TSP問題的復雜度。改進算法和傳統(tǒng)算法對不同規(guī)?；鶞蕟栴}進行了分析對比，結(jié)果表明改進算法能有效地跳出局部最優(yōu)，快速的收斂于最優(yōu)解。

1 TSP問題

旅行商問題中一個商人必須訪問n個城市。假設(shè)商人知道這一系列城市之間的距離（花費），規(guī)定商人必須訪問每個城市有且僅有一次，最終回到他最初出發(fā)的城市，求出商人往返的最小距離或者花費。TSP 問題是用來確定哈密頓圖中最小花費，被歸類為NP難題的離散優(yōu)化問題。

用城市間距離表示最小花費，城市間距離用式（1）表示，TSP問題路徑長度f 由式（2）表示

2 改進蜂群算法

許多有趣的群體行為可以在一些動物諸如蜜蜂，螞蟻，魚等身上觀察到。他們高度協(xié)調(diào)的覓食和聚集行為反映了這一現(xiàn)象。這些個體相對與整個系統(tǒng)來說，所能處理的問題是極其有限的，但是當把這些局部行為相結(jié)合時，將產(chǎn)生全局性的影響。

覓食過程中，蜜蜂記住形狀、顏色和氣味等食物特征，逐步形成自己的搜索經(jīng)驗［11］。在蜂巢附近搜索食物源的蜜蜂，通過搖擺舞把食物源的信息帶回蜂巢，招募更多的蜜蜂進行采蜜。基于此共享信息，遺棄質(zhì)量較差的食物源，調(diào)整搜索策略使得蜜蜂移動到質(zhì)量好的精英食物源上，最終聚集于精英食物源。基于這個自然現(xiàn)象的啟發(fā)，模擬蜜蜂覓食行為求解尋優(yōu)問題。

2.1 蜂群的基本概念

蜂巢內(nèi)共有三種蜜蜂：引領(lǐng)蜂，跟隨蜂，偵查蜂；每種角色的蜜蜂分擔不同的工作，相互協(xié)作，角色之間根據(jù)收益比在一定條件下進行相互轉(zhuǎn)換。每個食物源代表一個解決方案，對應(yīng)于TSP問題中的一條路徑；食物源花蜜的收益就代表問題解的質(zhì)量，對應(yīng)于TSP 問題中路徑質(zhì)量，即路徑長度的倒數(shù)。對于每個食物源來說，有若干個參數(shù)與之相關(guān)：食物源的花蜜（解決方案），花蜜的收益（解決方案的質(zhì)量），花蜜的數(shù)量。

偵查蜂：探尋蜂巢周圍的食物源，并且獲取有關(guān)食物源的花蜜收益的信息，然后返回蜂巢，在舞蹈區(qū)通過蜜蜂獨特的搖擺舞傳達有關(guān)蜜源的信息。偵察蜂在算法陷入局部最優(yōu)時能有效的跳出進行新食物源的偵察，跳出條件是蜂群在一段時間內(nèi)沒有發(fā)現(xiàn)更好的食物源，算法中利用食物源的遍歷次數(shù)進行限定。

跟隨蜂：在蜂巢的跟隨蜂通過觀察舞蹈區(qū)內(nèi)有關(guān)蜜源的信息，依收益比決定是否跟隨跳舞的蜜蜂采蜜。根據(jù)引領(lǐng)蜂的收益比自適應(yīng)的決定跟隨比，跟隨蜂能加強引領(lǐng)蜂中的精英食物源的遍歷，凸顯引領(lǐng)蜂的精英作用，加速算法的收斂。

引領(lǐng)蜂：根據(jù)蜜蜂的收益比，決定引領(lǐng)角色。收益比高的蜜蜂，能招募更多的跟隨蜂，使得算法快速收斂于最優(yōu)。當食物源的花蜜被采集完畢時，引領(lǐng)蜂變?yōu)楦S蜂。

蜜蜂訪問食物源時，若此食物源的花蜜質(zhì)量優(yōu)于這只蜜蜂先前的花蜜質(zhì)量，則選擇此處為新的蜜源，并返回蜂巢和其他蜜蜂分享食物源的信息，否則將保持先前的位置。倘若食物源在限定的次數(shù)內(nèi)沒有進一步提高，遺棄食物源。

2.2 路徑選擇與角色轉(zhuǎn)換

蜂巢中最開始的蜜蜂都是偵察蜂，偵察蜂和跟隨蜂按轉(zhuǎn)移概率進行路徑選擇尋找食物源，轉(zhuǎn)移概率的計算見式（3）

偵察蜂選擇完路徑，按收益比進行角色轉(zhuǎn)換如式（5），收益比是偵察到的食物源質(zhì)量與整個蜂群的食物源質(zhì)量的比值，收益比越高意味著食物源質(zhì)量越好，它應(yīng)該招募更多的蜜蜂來采集蜂蜜

其中g(shù) 代表蜜蜂的總數(shù)，ibee 標識當前是哪只蜜蜂，fibee是當前第ibee 只蜜蜂的收益，與其經(jīng)歷的路徑長度成反比。動態(tài)轉(zhuǎn)變原則，見表1。

偵察蜂用來搜索新的食物源，每只偵察蜂對應(yīng)一個食物源，它代表解的多樣性，能幫助群峰跳出局部最優(yōu)，但是個數(shù)過大會破壞優(yōu)良路徑，不利于算法的收斂，過小會使得搜尋新食物源的能力變差，經(jīng)實驗驗證偵察蜂取蜂群總數(shù)的10%效果最好。

表1 動態(tài)轉(zhuǎn)變原則

表2 跟隨蜂的跟隨比

2.3 算法描述

所需參數(shù)：MaxCycle－最大迭代周期數(shù)，Cycle－迭代周期數(shù)，Cn為蜂群中所有蜜蜂數(shù)即城市個數(shù)，F(xiàn)ood＿Limit－允許訪問食物源的最大次數(shù)，超過該數(shù)就遺棄食物源。Vn－食物源的訪問次數(shù)，Best＿food－最好的食物源。

（1）GenerateInitRole（scout bee）／／算法開始蜂巢中的蜜蜂都是偵察蜂。

Scout＿bee（Cn）／／據(jù)式（4）計算路徑的適應(yīng)值ρij ，按式（3）計算Pij按概率選徑，對找到食物源的訪問次數(shù)Vn 進行累加。

Evaluate＿food（）／／對食物源的質(zhì)量進行評價，得到最優(yōu)食物源，計算收益比r見式（5）。

DChange＿role（）／／根據(jù)收益比r按表1動態(tài)轉(zhuǎn)換蜜蜂角色。

（2）滿足Cycle＜＝MaxCycle進入循環(huán)階段

1）Leader＿bee（）／／引領(lǐng)蜂招募跟隨蜂，訪問食物源，Vn 進行累加。

2）Onlooker＿bee（）／／跟隨蜂據(jù)跟隨比按表2隨引領(lǐng)蜂訪問食物源，Vn 進行累加。

3）Scout＿bee（）

4）Evaluate＿food（）

5）DChange＿role（）

Vn ＜＝Food＿Limit重復步驟1），否則遺棄當前食物源，迭代周期數(shù)Cycle累加。

（3）輸出最優(yōu)食物源Best＿food。

3 改進局部搜索策略的蜂群算法

用局部搜索策略優(yōu)化蜜蜂的解，可以加快算法的收斂度，針對一個蜜蜂所尋的食物源進行變換，將找到的質(zhì)量更好的解替換原食物源，否則拋棄新解。Marco Dorigo在文獻［13］中指出使用局部搜索策略可以大大減少循環(huán)次數(shù)，但是算法復雜度沒有下降。

蜂群算法的復雜度為O（迭代周期數(shù)＊蜜蜂數(shù)＊城市數(shù)＾2），設(shè)置蜜蜂個數(shù)與城市個數(shù)相同，所以算法的復雜度為O（迭代周期數(shù)＊城市數(shù)＾3）。使用局部搜索后，可以大大減少迭代的周期數(shù)，但即使迭代周期數(shù)忽略不計，算法仍是O（城市數(shù)＾3）的復雜度。

采用改進局部搜索策略可以降低問題的復雜度，TSP問題中最優(yōu)解的每個城市連接的都必定是附近的城市，即蜜蜂尋徑時，只需要嘗試附近的幾個城市而不用嘗試所有的城市。進行局部搜索時，不需要嘗試跟所有其他連接的城市是否能交換出更好的結(jié)果，只需要嘗試跟最靠近的若干個城市交換。把之前嘗試的N個城市，變?yōu)閲L試指定范圍n（n＜N），提速N／n 倍，所以新的算法復雜度跟N 無關(guān)，只是一個常數(shù)，所以算法復雜度降低了一個數(shù)量級，成為O（T＊N＾2）。

對蜂群算法的精英路徑進行改進的局部尋優(yōu)，可以有效的降低算法的復雜性。改進局部搜索策略的蜂群算法解決TSP問題（ILSBCO）的流程如圖1所示。

4 仿真結(jié)果

求解中國31個城市（Chn31）的最優(yōu)路徑，問題規(guī)模較小，不需局部搜索策略即可求得Chn31最優(yōu)路徑，參數(shù)設(shè)置為α＝1，β＝5，λ＝0.9，蜜蜂個數(shù)同城市個數(shù)，路徑最大訪問次數(shù)為10。在迭代到第50次即求得路徑最優(yōu)解，保留小數(shù)點后三位為15377.711，最優(yōu)路徑如圖2所示。

利用國際上通用的測試問題庫TSPLIB 中的幾個TSP問題作為測試對象，城市的個數(shù)從70到493，利用基本的蜂群算法和改進局部搜索的蜂群算法對求解結(jié)果進行了對比分析如表3所示，可以看出在求解規(guī)模增大時，蜂群算法的性能急速下降，而改進的蜂群算法的求解隨著規(guī)模增大也有不同程度的下降，但性能只是在很小的范圍內(nèi)下降。蜂群算法的參數(shù)設(shè)置為：最大迭代周期數(shù)設(shè)為1000，食物源的最大訪問次數(shù)設(shè)置為100，蜜蜂個數(shù)設(shè)置為城市數(shù)。參數(shù)的設(shè)置為：α＝1，β＝5，λ＝0.9，三種角色按表1和表2描述的概率進行分配，改進的局部搜索策略中最近城市的個數(shù)設(shè)置為10。

針對基準問題pr299.tsp的求解與文獻［15］中介紹的幾個優(yōu)化算法進行測試對比，性能分析顯示無論是尋優(yōu)時間還是最優(yōu)解的誤差以及平均解的誤差結(jié)果中，取得了更好效果，見表4。

結(jié)果說明改進的蜂群算法能有效的使問題的復雜度降低，對于大規(guī)模的基準問題能取得更好效果，盡管得到的結(jié)果和設(shè)置的參數(shù)有很大關(guān)系，但這些可以通過實驗求得。

表3 ILSBCO 與BCO 測試結(jié)果對比

表4 不同優(yōu)化方法測試Pr299的結(jié)果對比

5 結(jié)束語

基于蜂群覓食行為，三種角色蜜蜂相互合作，引進集體智慧，改進蜂群算法求解TSP 問題。根據(jù)收益比值利用引領(lǐng)蜂保留精英解，并動態(tài)招募跟隨蜂保證算法的快速收斂，利用偵察蜂可以有效跳出局部最優(yōu)問題，有效提高TSP最優(yōu)解。針對大規(guī)?；鶞蕟栴}采用改進的局部搜索策略，降低求解問題的復雜度。改進蜂群算法與標準蜂群算法以及其它經(jīng)典算法對不同規(guī)模基準問題進行測試，仿真結(jié)果表明改進算法在更短時間內(nèi)找到最優(yōu)食物源。

［1］WANG Zhongying，BAI Yanping，YUE Lixia.An improved ant colony algorithm for solving TSP problems［J］.Mathematics In Practice and Theory，2012，42（4）：133－140（in Chinese）.［王忠英，白艷萍，岳利霞.經(jīng)過改進的求解TSP問題的蟻群算法［J］.數(shù)學的實踐與認識，2012，42（4）：133－140.］

［2］Ilie S，Badica C.Effectiveness of solving traveling salesman problem using ant colony optimization on distributed multi－agent middleware［C］／／Poland：Proceedings of the International Multiconference on Computer Science and Information Technology，2010：197－203.

［3］KIM Y，CHO S B.A hybrid cultural algorithm with local search for traveling salesman problem［C］／／Korea：Proceedings of Computational Intelligence in Robotics and Automation，2009：88－192.

［4］QIAO Yanping，ZHANG Jun.Traveling salesman problem solving based on an improved genetic simulated annealing algorithm［J］.Computer Simulation，2009，26（5）：205－208（in Chinese）.［喬彥平，張駿.基于一種改進遺傳模擬退火算法的TSP求解［J］.計算機仿真，2009，26（5）：205－208.］

［5］CHEN Minghua，ZHOU Benda.Solving traveling salesman problem using genetic algorithm based on Latin hypercube sampling［J］.College of Computer Mathematics Journal，2011，33（2）：138－144（in Chinese）.［陳明華，周本達.拉丁超立方體抽樣混合遺傳算法求解TSP 問題［J］.高等學校計算機數(shù)學學報，2011，33（2）：138－144.］

［6］Whitfield J.Animal behavior：The wisdom of the bees［J］.Nature，2010，467（7316）：658－659.

［7］Karaboga D.An artificial bee colony（ABC）algorithm for numeric function optimization［C］／／Indiana：Proceedings of IEEE Swarm Intelligence Symposium Indianapolis，2006：651－656.

［8］Karaboga D，Gorkemli B.A combinatorial artificial bee colony algorithm for traveling salesman［C］／／Istanbul：International Symposium on Innovations in Intelligent Systems and Applications，2011：50－53.

［9］WONG Lipei，Malcolm Yoke Hean Low.A bee colony optimi－zation algorithm for traveling salesman problem［C］／／Kuala Lumpur：Second Asia International Conference on Modeling ＆Simulation，2008：818－823.

［10］HU Zhonghua，ZHAO Min.Simulation on traveling salesman problem based on artificial bees colony algorithm［J］.Transactions of Beijing Institute of Technology，2009，29（11）：978－982（in Chinese）.［胡中華，趙敏.基于人工蜂群算法的TSP仿 真［J］.北 京 理 工 大 學 學 報，2009，29（11）：978－982.］

［11］LIU Yong，MA Liang.Bees algorithm for function optimization［J］.Control and Decision，2010，27（6）：886－890（in Chinese）.［劉勇，馬良.函數(shù)優(yōu)化的蜂群算法［J］.控制與決策，2012，27（6）：886－890.］

［12］CHONG C S，Malcolmlow Y H，Sivakumar A I.Using a bee colony algorithm for neighborhood search in job shop scheduling problems［C］／／USA：Proceeding of 21st European Conference on Modeling and Simulation，2007：1019－1025.

［13］Marvo Dorigo，Montes De Oca.Ant colony optimization［J］.Computational Intelligence Magazine，2006，1（4）：28－39.

［14］Bianchi L，Gambardella L.Ant colony optimization and local search based on exact and estimated objective values for the probabilistic traveling salesman problem［R］.Switzerland：IDSIA，2007：6－7.

［15］Albayrak M，Allahwerdi N.Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms［J］.Expert Systems with Applications，2011，38（3）：1313－1320.