王克甫，薛 鵬，黃全振，2，李恒宇

（1.河南工程學院 電氣信息工程學院，河南 鄭州451191；2.上海大學 機電工程與自動化學院，上海200072）

0 引 言

TSP作為一類經(jīng)典的NP 難組合優(yōu)化問題，在車輛調(diào)度、物流配送、管道鋪設、電路板布局等領域得到廣泛應用，國內(nèi)外學者對此已開展大量的研究工作，并提出一些求解算法，總的可歸為兩方面：精確算法和啟發(fā)式算法。然而，TSP解空間隨問題規(guī)模呈指數(shù)級增長，對于大規(guī)模問題，傳統(tǒng)精確算法很難在可接受的時間內(nèi)找到最優(yōu)解。比如：分支－切割法［1］，動態(tài)規(guī)劃法［2］等；而啟發(fā)式算法本身具有一定的智能性，它們可依靠自身的這些特性，對解空間進行啟發(fā)式搜索。與精確算法相比，在同等條件下它們就可以獲得較為滿意的解。啟發(fā)式算法一般有：蟻群算法［3，4］，遺傳算法［5］，人工蜂群算法［6］，粒子群算法［7－8］等。在這樣的背景下，啟發(fā)式算法越來越得到廣大學者的關注。

鑒于果蠅算法 （Fruit fly algorithm，F(xiàn)FA）在求解連續(xù)優(yōu)化問題中表現(xiàn)出的良好性能［9］，本文對其求解TSP 組合優(yōu)化問題進行了探索性的嘗試，并針對它易陷入局部最優(yōu)及收斂速度慢等問題，提出基于局部最優(yōu)區(qū)域半徑的啟發(fā)式變異策略以及覓食步長自適應調(diào)整策略。最后，在對其全局收斂性進行證明的同時，也通過國際標準實例庫TSPLIB驗證了它的有效性。

1 果蠅算法

中國臺灣學者潘文超受果蠅覓食行為的啟發(fā)，于2011年6月提出了基于群體智能的果蠅算法［9］，并在連續(xù)優(yōu)化問題領域得到應用［10－12］。其原理為：群體中的果蠅在覓食過程中利用相對發(fā)達的嗅覺朝食物氣味濃度最高的區(qū)域飛行，并在飛近食物過程中利用視覺發(fā)現(xiàn)覓食能力最高的果蠅，并向該果蠅飛行，以快速覓到食物。覓食行為如圖1所示。

圖1 果蠅覓食行為

然而，目前FFA 算法還未應用于TSP等離散組合優(yōu)化問題。固定的覓食步長影響了收斂速度。群體覓食行為的趨同性降低了種群的多樣性，易于陷入局部最優(yōu)。針對這些不足，對覓食步長進行了改進，提出步長自適應調(diào)整策略，以提高收斂速度；同時，提出局部最優(yōu)半徑的概念，并提出啟發(fā)式變異算子，使處于局部最優(yōu)半徑中的部分個體進行啟發(fā)式變異，在保護最優(yōu)解的同時，提高種群多樣性，改善優(yōu)化性能。

2 果蠅算法改進

定義1 不同于連續(xù)優(yōu)化問題，對于采用城市序號編碼的離散TSP問題，不重復遍歷所有城市的一個序列為一條染色體，序列中的任一城市為一個基因位，對染色體中任兩個基因位進行一次2－opt操作的行為，稱為一步覓食。

定義2 在進行2－opt過程中，任選染色體中的2個基因的行為，稱為覓食方向選擇。

定義3 對于TSP問題，假如第i個果蠅的當前位置為C（i）＝（ci1，ci2，…，cin），cij（j∈｛1，2，…n｝）表示一個城市的編號，則第i個果蠅位置處食物的濃度可表示為式 （1）

式中：dj，j＋1——城市cij與城市cij＋1之間的距離。

2.1 步長自適應設計

定義4 對于C（i）＝（ci1，ci2，…，cin）、C（j）＝（cj1，cj2，…，cjn）2個果蠅，則這2個果蠅之間的解空間距離定義為C（i）與C（j）相同位置處不同基因位的對數(shù)。比如：C（1）＝ （1，2，3，4，5，6，7，8）、C（2）＝ （4，8，3，6，1，7，2，5）。則C（1）與C（2）之間的解空間距離為7。則為C（i）與C（j）之間的解空間距離可定義為

由于果蠅算法采用固定步長進行覓食，如果步長設置過大，則較容易進行全局搜索，但卻帶來求解精度的降低；然而，步長設置過小，在求解精度提高的同時，會造成搜索效率的降低。為使精度與效率達到一種平衡，需對步長進行自適應調(diào)整。鑒于所有果蠅從當前食物濃度最大處進行覓食的情況，為避免不必要的重復搜索，因而覓食的步長不應超出上代果蠅群體中距離食物濃度最大處果蠅的最短距離。同時，為兼顧到全局尋優(yōu)，對每個果蠅的步長調(diào)整為

其中，C（i），i∈｛1，2，…，Popsize｝＆＆i≠j）為非食物濃度最大處的果蠅，C（j）為食物濃度最大處的果蠅。rand（）為0、1之間的隨機數(shù)。

2.2 參考局部最優(yōu)區(qū)域半徑的變異算子設計

果蠅算法的覓食策略較為單一，難免會進入局部最優(yōu)。為此，提出一種考慮局部最優(yōu)區(qū)域半徑的變異方法。通常，在某個區(qū)域中如果存在多個局部最優(yōu)值，會進入局部最優(yōu)。因而，結合本文定義的解空間距離概念，把距離當前最優(yōu)解小于等于半徑R 的區(qū)域定義為局部最優(yōu)區(qū)域。變異策略為：從局部最優(yōu)區(qū)域中隨機選擇R 個果蠅以概率pm（i）（i∈｛1，2，…，R｝）進行變異，對選中的果蠅則隨機選擇R 個連續(xù)的基因位進行倒序。假設Smax為局部最優(yōu)區(qū)域中當前距離最優(yōu)解的最大值，則被選擇到的R 個果蠅的變異概率為

其中，i∈｛1，2，…，R｝，C（j）為食物濃度最大處的果蠅。

2.3 改進果蠅算法描述

步驟1 隨機初始化Popsize 只果蠅的位置；

步驟2 依據(jù)式 （1）對Popsize 只果蠅進行食物濃度判定；

步驟3 找出食物濃度最大處的果蠅，并記錄其濃度值fitness（C（j））及位置C（j）；

步驟4 按本文定義的覓食方向及覓食方式并按式 （5）進行自適應覓食

步驟5 保留食物濃度最大處的果蠅，如果當前代食物濃度最大值fitness（C（m））優(yōu)于Smellbest，則更新

其中，Positionbest及Smellbest初始值為任一隨機位置及其對應的濃度值。

步驟6 如果達到設定的迭代次數(shù)，則輸出最優(yōu)解；否則，轉(zhuǎn)步驟7；

步驟7 按本文定義的變異策略進行自適應變異，轉(zhuǎn)步驟2。

3 全局收斂性分析

定義5 在TSP問題中，果蠅C（i）＝（ci1，ci2，…cin）通過覓食行為到達果蠅C（j）＝（cj1，cj2，…cjn）處，記為狀態(tài)變遷，序列（ci1，ci2，…cin）的全排列稱為TSP問題的狀態(tài)空間，也稱為解空間Η。

定義6 設C＊為TSP解空間Η中的最優(yōu)解，F(xiàn)（t）為覓食進行到第t代時的種群狀態(tài)，如果

則稱改進的果蠅算法以概率1收斂到全局最優(yōu)解。

定理改進的果蠅算法以概率1收斂到全局最優(yōu)解。

證明：通過對基本果蠅算法進行了步長自適應調(diào)整以及變異算子設計，改進果蠅算法的性能得到了提高。其核心思想為：所有果蠅從上一代中食物濃度最大的果蠅所在位置處進行覓食，具有引導向最優(yōu)方向覓食的能力。假如B ＝｛b（1），b（2），…，b（t），b（t＋1）｝表示從第1代到第t＋1代中每代的最優(yōu)解，則滿足

4 仿真實驗

為測試改進果蠅算法 （MFFA）的有效性，選用TSPLIB國際標準庫中的Eil51作為測試函數(shù)，與標準果蠅算法 （FFA）及文獻 ［14］中的改進的粒子群算法 （MPSO）進行了對比。種群規(guī)模Popsize 均為120，進化代數(shù)Gennum 均為500 代，IFFA 的局部最優(yōu)區(qū)域半徑R ＝15，MPSO 其他參數(shù)見文獻 ［14］。實驗環(huán)境：Windows XP 系統(tǒng)、G2030－3.0GHz CPU、4GRAM、VC＋＋2010。

從圖2看出，與FFA、MPSO 相比，MFFA 能快速收斂到最優(yōu)解，并且求解精度也得到很大程度的提高，說明本文采用的步長自適應調(diào)整及啟發(fā)式變異策略是可行的。圖3各代均值對比曲線顯示MFFA 有效避免了 “早熟”現(xiàn)象，使果蠅在進化后期依然保持較強的覓食能力，因而提高了求解效率。特別與FFA 相比，覓食能力有很大的提升，再次印證了MFFA 啟發(fā)式變異策略的可行性。

圖2 算法收斂曲線對比

圖3 算法各代均值對比

為測試MFFA 算法的適應能力，更好地檢測MFFA 算法的性能，選用了TSPLIB 國際標準庫中多個實例進行對比，同時，為排除隨機性，采用統(tǒng)計學原理進行比較。為此，參與對比的算法各單獨運行25次，結果見表1。在表1中TSPOPT 表示TSPLIB 的已知最優(yōu)解，BST 表示最優(yōu)解，AVG 表示平均解，DEV 表示平均解與已知最優(yōu)解的偏差，CPU（s）表示耗費CPU 的時間。

由表1可看出，3 個算法相比，MFFA 在所有測試實例中獲得的路徑都是最優(yōu)的。并且，通過對比不同規(guī)模實例中獲得的最優(yōu)路徑的情況，我們發(fā)現(xiàn)，當TSP 城市規(guī)模較小時，MFFA 基本上能得到TSPLIB 已知的最優(yōu)路徑；而當TSP城市規(guī)模較大時，MFFA 盡管不能取得TSPLIB已知的最優(yōu)路徑，但已與之相當接近。另外，從與已知最優(yōu)解的偏差這個角度來看，MFFA 依然是最小的，從中可以說明其具有較好的魯棒性。特別與FFA 相比，收斂速度與精度的改善非常顯著，這主要得益于兩方面：首先，果蠅能根據(jù)距離覓食能力最強果蠅的距離進行自適應調(diào)整覓食步長，有效縮短了尋覓到食物的時間，即提高了收斂速度，縮短了收斂時間；其次，基于局部最優(yōu)區(qū)域半徑的啟發(fā)式變異策略，在拓展了解空間的范圍的同時，也較好的保護了最優(yōu)解，不僅很好地解決了局部最優(yōu)的問題，而且對算法的尋優(yōu)方向也有一定的引導性，在一定程度上也為收斂效率的提高做出了貢獻。因而，從以上兩點的分析可以看出，本文提出MFFA 在求解效率與精度上都得到了很大程度的改善。

表1 3種算法求解TSP實例的結果對比

5 結束語

果蠅算法作為一種新穎的優(yōu)化算法，其在求解連續(xù)優(yōu)化問題上顯示出較好的性能。本文創(chuàng)新性地對果蠅算法進行了改進，并應用到離散組合優(yōu)化問題中的經(jīng)典NP 難TSP問題。結合TSPLIB 國際標準庫中的實例，與其他智能算法進行了對比測試。測試結果表明，改進后的果蠅算法不僅有效克服了易 “早熟”及收斂速度慢的問題，而且相對其他算法也表現(xiàn)出較好的性能。從這點看，本文采取的基于局部最優(yōu)區(qū)域半徑的啟發(fā)式變異策略及步長自適應調(diào)節(jié)策略是可行的，這也為改進的果蠅算法在相關組合優(yōu)化問題中的應用提供了一個很好的參考。

鑒于其在本文中TSP問題中表現(xiàn)出的良好性能，為了拓寬其應用領域。下一步準備在有約束的TSP問題中進行嘗試，有約束的TSP 也是一類經(jīng)典問題，對其進行研究，不僅可以擴大本文提出的改進果蠅的算法的應用的廣度，而且，也對相關帶約束的車輛路徑規(guī)劃、水管電網(wǎng)線及電路板走線等規(guī)劃問題的求解提供了一個很好的借鑒。

［1］Cordeaua JF，Dell’Amico M，Iori M.Branch－and－cut for the pickup and delivery traveling salesman problem with FIFO loading ［J］.Computers and Operations Research，2010，37（5）：970－980.

［2］Gromicho J，Hoorn JJV，Kok AL，et al.Restricted dynamic programming：A flexible framework for solving realistic VRPs ［J］.Computers and Operations Research，2012，39 （5）：902－909.

［3］WU Hao，NI Zhiwei，WANG Huiying.MapReduce－based ant colony optimization ［J］.Computer Integrated Manufacturing Systems，2012，18 （7）：1503－1509 （in Chinese）.［吳昊，倪志偉，王會穎.基于MapReduce的蟻群算法 ［J］.計算機集成制造系統(tǒng)，2012，18 （7）：1503－1509.］

［4］Tuba M，Jovanovic R.Improved ACO algorithm with pheromone correction strategy for the traveling salesman problem［J］.International Journal of Computers Communications and Control，2013，8 （3）：477－485.

［5］Nagata Y，Kobayashi S.A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem［J］.Informs Journal on Computing，2013，25 （2）：346－363.

［6］HU Zhonghua，ZHAO Min.Simulation on traveling salesman problem （TSP）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.］

［7］Marinakis Y，Marinaki M.A hybrid multi－swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem ［J］.Computers and Operations Research，2010，37 （3）：432－442.

［8］ZHANG Xumei，QIU Hanguang.Improved particle swarm optimization based on k－center and its application in traveling salesman problem ［J］.Computer Integrated Manufacturing Systems，2007，13 （1）：99－104 （in Chinese）. ［張旭梅，邱晗光.基于k－中心點法的改進粒子群算法在旅行商問題中的應用［J］.計算機集成制造系統(tǒng)，2007，13 （1）：99－104.］

［9］PAN WT.A new fruit fly optimization algorithm：Taking the financial distress model as an example ［J］.Knowledge－Based Systems，2012，26：69－74.

［10］WANG L，ZHENG XL，WANG SX.A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem ［J］.Knowledge－Based Systems，2013，48：17－23.

［11］SHENG W，BAO Y.Fruit fly optimization algorithm based fractional order fuzzy－PID controller for electronic throttle［J］.Nonlinear Dynamics，2013，73 （1－2）：611－619.

［12］LI HZ，GUO S，ZHAO HR.Annual electric load forecasting by a least squares support vector machine with a fruit fly optimization algorithm ［J］.Energies，2012，5 （11）：4430－4445.

［13］Lopez J，Dorronsoro JR.Simple proof of convergence of the SMO algorithm for different SVM variants ［J］.IEEE Transactions on Neural Networks and Learning Systems，2012，23（7）：1142－1147.

［14］Sedghi M，Aliakbar－Golkar M，Haghifam MR.Distribution network expansion considering distributed generation and storage units using modified PSO algorithm ［J］.International Journal of Electrical Power and Energy Systems，2013，52：221－230.