一種基于禁忌策略的混合優化算法

印 溪,許 斌,亓 晉

(1.南京郵電大學 自動化學院，江蘇 南京 210003; 2.南京郵電大學 物聯網學院，江蘇 南京 210003)

一種基于禁忌策略的混合優化算法

印 溪1,許 斌2,亓 晉2

(1.南京郵電大學 自動化學院，江蘇 南京 210003; 2.南京郵電大學 物聯網學院，江蘇 南京 210003)

為了提升綜合學習粒子群算法(Comprehensive Learning Particle Swarm Optimization，CLPSO)的后期收斂能力，提出一種基于禁忌策略的混合優化算法，記為CLPSO+Tabu(CMA-ES)。算法以禁忌搜索算法為后續搜索操作，對綜合學習粒子群算法進行改進。同時將協方差矩陣自適應進化策略(Covariance Matrix Adaptation Evolution Strategy，CMA-ES)引入禁忌搜索算法，以高斯分布為基礎，以CMA-ES策略引導鄰域結構的分布，構造新型自適應鄰域結構，指導禁忌搜索算法中候選解的選取，從而解決綜合學習粒子群算法在收斂精度低的問題，極大改善了求解效果。針對26個標準測試函數的實驗結果表明，與CLPSO相比，CLPSO+Tabu(CMA-ES)算法在絕大多數函數上具有更好的收斂效果。針對其中6個優化問題，CLPSO+Tabu(CMA-ES)更是有至少一個數量級的改進。

綜合學習粒子群算法；禁忌搜索；高斯分布；參數自適應；協方差矩陣自適應進化策略

0 引 言

D維無約束優化問題可以表達為：minf(x),x∈Rn。對于非線性、高維、非凸、病態等函數優化問題，傳統算法通常不能很好地利用目標函數的梯度信息或者次梯度信息進行優化。而群智能優化算法[1]是通過轉移概率在解空間內進行選擇和搜索，故而具有全局搜索能力強、收斂快、搜索效率高、魯棒性好等優點，為解決管理科學、計算機科學、控制工程等領域的優化問題提供了新的求解途徑[2]。目前群智能優化算法已成為最優化方法中的研究熱點[3]。

群智能優化算法是一種通過模擬動物集體行為來求解優化問題的智能算法。與傳統算法相比，該算法的實現較簡單，對要解決的問題是否連續以及問題的規模均無要求，并且具有廣泛的適應性和魯棒性[1]。

綜合學習粒子群算法自提出以來，很多專家在增強CLPSO性能以及擴展CLPSO應用等方面進行了相應的研究與工作。Liang和Suganthan提出了自適應CLPSO，其中，粒子的學習概率隨著過去幾代取得的最大改進的差值而自適應改變，同時將歷史改進方向加入到粒子速度的更新中。HasanzadehM在CLPSO的基礎上引入自動學習機，對CLPSO的算法性能、魯棒性以及收斂速度都有提升。

雖然有了眾多的改進和融合，CLPSO的性能也得到了相應提升，但目前其只在解決一部分多峰問題上有較好的效果[4]，而在單峰問題以及一部分多峰問題上效果較差，算法后期的收斂速度慢，求解精度不足[5]。

基于綜合學習粒子群算法，文中提出一種融入禁忌算法的搜索方法。算法中以綜合學習粒子群算法作為全局搜索算法，以禁忌算法作為局部搜索算法。由于禁忌搜索需要較好的初始解，才能得到較好的局部搜索能力，因此，以綜合學習粒子群算法的結果作為禁忌搜索的初始解，以CMA-ES策略控制高斯分布的參數變化，以高斯分布作為自適應鄰域結構，選取候選解。針對26個特性各異的函數的實驗表明，與CLPSO相比，文中算法在解決函數優化問題上有一定的優勢，尤其是在優化旋轉函數上較顯著。

1 相關工作

1.1 CLPSO

Liang J J[6]基于經典PSO提出了基于綜合學習策略粒子群優化算法-CLPSO。CLPSO使用一種新穎的學習方法，利用所有其他的粒子歷史最優信息來更新粒子的速度，使得算法中的粒子多樣性得以保持，從而一定程度上避免了過早收斂。

CLPSO的速度和位置更新公式為：

(1)

(2)

每個粒子均產生[0，1]內的均勻隨機數，若產生的隨機數大于設定的學習概率Pc，則設定學習對象為pbest，即粒子本身的歷史最優位置；若產生的隨機數小于設定的學習概率，則按錦標賽選擇策略(tournamentselectionprocedure)從種群內隨機選取的兩個個體中選出較優的歷史最優位置作為學習對象。

為上述學習對象選擇過程中設定一個更新間隔代數(refreshinggap)m，即粒子的適應度值經過m次迭代都不再改進后，重新分配學習對象，否則，保持上次選擇的學習對象不變。該策略可以使粒子向優秀的對象學習，而不會在較差的對象上浪費時間[7]。

CLPSO的每個粒子的每一維都可以隨機地向自身或其他粒子學習。該策略使得粒子群中的粒子保持了較好的多樣性，從而避免了過早收斂的現象。其在解決多峰問題上具有較好的性能，但在單峰問題上效果卻不夠好。而現實中，問題的適應度景觀形態通常未知，將CLPSO與局部搜索算法結合起來就能有效解決單峰問題[8]。

1.2 Tabu

禁忌搜索算法[9](Tabu Search)是一種現代啟發式算法，由美國科羅拉多大學教授Fred Glover提出，是一種用來跳出局部最優解的搜索方法。

簡單TS算法的基本思想：首先，給定問題的一個初始解，同時，選擇一種鄰域結構。然后，在初始解的鄰域中隨機確定一些候選解。此時，如果最優候選解對應的適應度值優于“best so far”狀態，則用該最優候選解代替初始解和“best so far”狀態，同時將其加入禁忌表，并修改禁忌表中對象的禁忌時間；如果最優候選解對應的適應度值并不優于“best so far”狀態，則新的初始解在候選解中的非禁忌的最優狀態中選出，即忽略其與初始解的優劣關系，并將其加入禁忌表，同時修改禁忌表中對象的禁忌時間。如上述般重復迭代搜索過程，當滿足停止準則時，才可停止。

文中應用的藐視準則是基于適應度值準則中的全局形式。采用的終止準則:給定每次運行后總循環的次數，即最大迭代步數。

2 算法描述

2.1 鄰域結構

禁忌搜索的性能基本依賴于所選取的鄰域結構和所給定的初始解。文中的初始解由CLPSO提供。選取不同的鄰域結構將得到不同的禁忌算法，而鄰域結構的設計通常與問題有關。

采用高斯分布(Gaussian distribution)，又稱正態分布(Normal distribution)，高斯分布有兩個參數：位置參數μ，意味著高斯曲線的中心位置；尺度參數σ，意味著高斯曲線的陡峭程度。

高斯分布的概率密度函數為：

(3)

3σ原則意味著，正態曲線下變量取值在(μ-3σ，μ+3σ)中的概率為99.7%。

文中Tabu算法將初始解設為位置參數μ，使得候選解在初始解的3σ范圍內，且離初始解越近，取到的機率就越大，即以初始解為中心，在其周邊3σ范圍內進行候選解的選取。σ的大小意味著候選解可能的取值范圍。為控制σ的大小，引入協方差矩陣自適應進化策略，隨著進化代數的推進，自適應地改變σ的取值，從而影響候選解選取的范圍。

2.2 CMA-ES

協方差矩陣自適應進化策略[10](Covariance Matrix Adaptation Evolution Strategy，CMA-ES)由Hansen和Ostermeier提出，是一種新型的基于生物進化的優化算法。該進化策略適用于解決隨機的、不可導的非線性或非凸連續優化問題。進化方法大多基于生物進化，重復作用的變異(包括重組和突變)以及選擇。在CMA-ES中，新的候選解是根據多元正態分布來選擇的。重組相當于為分布選擇一個新的平均值。突變則相當于增加了一個隨機變量，增加了一個平均值為0的擾動。協方差矩陣記錄的是兩個變量的相關性，而CMA是更新這個協方差矩陣的一種方法。由于CMA-ES具有旋轉不變性，其在解決旋轉函數和病態函數時特別有效。CMA-ES策略的核心是動態自適應地調整變量建的協方差矩陣，使得種群逐步收斂于全局最優解。

文中主要引入CMA-ES中的自適應迭代步長的方法，從而自適應地控制鄰域解的分布范圍以及取值概率，既保持了鄰域解的多樣性，同時也確保了解的精確度。

σ的步長控制函數為：

(4)

其中，pσ為進化路徑，其更新公式為：

(5)

Cg是第g代的協方差矩陣，其更新公式為：

(6)

協方差矩陣自適應進化策略結合了進化策略方法的全局性和協方差矩陣的可引導性，對于解決非凸非線性優化函數問題有非常好的適應能力。

2.3 基于CMA-ES的CLPSO算法

為了進一步增強CLPSO的局部搜索能力，提高解精度，引入禁忌搜索算法。以CMA-ES策略引導高斯鄰域結構的變化，自適應地產生較好的鄰域解，從而獲得更精確的解。

根據上述策略，文中提出CLPSO+Tabu(CMA-ES)，其算法的框架如下：

第一步：初始化。

(1)對種群中每個個體的位置進行隨機初始化；

(2)計算初始化后個體的適應度值，將最優值存儲于pbestval，將最優解存儲于pbest；

(3)對種群中每個個體的速度進行隨機初始化。

第二步：用錦標賽的方式挑選學習對象。

在種群中隨機挑選兩個粒子進行比賽，根據兩個粒子pbest的適應度值的大小判斷輸贏，適應度值優的一方獲勝。若其值相同，則隨機選取。利用較好的那個粒子的pbest作為更新的標本，如果一個粒子的所有標本都是自身pbest，就隨機抽取其中一維來學習其他粒子的pbest。

第三步：更新。

依據式(1)和(2)更新粒子的位置與速度，從新的粒子中選出最優解，更新pbest和pbestval。

第四步：停止CLPSO。

當函數評估次數達到預設值，停止CLPSO的進化，將最后一代的最優解作為初始解。

第五步：用禁忌搜索來更新粒子作為下一代種群。

(1)在CLPSO產生的初始解的鄰域中尋找候選解。

①更新協方差矩陣Cg，更新進化路徑pσ。

②計算鄰域大小。

(2)選出候選解中最優解作為“bestsofar”狀態。

(3)根據候選解是否滿足藐視規則，更新初始解、禁忌表、“bestsofar”狀態。

(4)判斷候選解對應的各對象的禁忌屬性，更新初始解和禁忌表。

第六步：停止禁忌搜索。

當“bestsofar”狀態連續50次未進化，則停止搜索，輸出最后一代的“bestsofar”狀態。

第七步：迭代次數加1，跳回第一步重新開始，當達到最大迭代次數停止進化并輸出最優的“bestsofar”狀態。

經過實驗驗證，該算法在優化旋轉函數上優勢顯著，由于禁忌算法的加入，CLPSO+Tabu(CMA-ES)算法在單峰問題中較經典CLPSO效果更優秀，而在非離散問題和病態問題上，效果也有一定程度的改進。

3 實 驗

3.1 測試函數

利用26個具有不同特性的測試函數來對算法進行測試,測試函數詳見文獻[11]。

其中，Ackley函數是由指數函數加適度放大的余弦波經過調制得到的多峰連續型實驗函數，存在多個局部極小值點；Sphere函數是單峰二次函數；Rosenbrock函數，又稱香蕉函數，非凸，為病態函數；Rastrigin函數是多峰函數，存在大量局部極小點；Griewank函數是多峰函數，存在大量局部極小點；Schwefel函數是一種典型的欺騙問題，具有許多虛假的局部最小值，算法極易陷入局部最優；diff pow為連續單峰函數；Quadric是一種徑向基函數，取值僅僅依賴于離原點距離的實值函數。

3.2 參數取值

3.2.1 禁忌表及禁忌長度

在不考慮藐視準則的情況下，禁忌長度是禁忌對象不能被選取的最大次數，只有當其禁忌時間為0時才可以被解禁。禁忌長度小，則相應算法的計算量和存儲量小；但是，禁忌長度過小，將造成循環搜索。文中禁忌長度取為7[12]。

3.2.2 學習概率Pc

學習概率的設置影響了每個粒子的學習能力。不同的學習概率對算法的探測和搜索能力有很大影響。研究[13]表明，學習概率為[14]：

(7)

其中，Lpmax和Lpmin分別對應學習概率的最大值和最小值，根據經驗，Lpmax=0.5，Lpmin=0.05；N為種群的粒子數。

3.2.3 慣性權重w

已有的研究工作[15]表明，較大的慣性權值有利于搜索時跳出局部極值點，而較小的慣性權值有利于算法收斂和提高搜索精度。因此提出慣性權重自適應動態調整的策略，在算法初始階段，使慣性權值較大，隨著算法的運行，其值又逐漸減小，即隨著CLPSO的進化，慣性權重應線性減小，從而達到算法探測能力和搜索能力的平衡。通常，慣性權重的值保持在0.1～0.9之間。慣性權重由式(8)表示。

(8)

其中，wmax是慣性權重的最大值；wmin是慣性權重的最小值。文中wmax=0.9，wmin=0.4。

3.2.4 更新間隔代數m

為學習對象選擇過程設定一個更新間隔代數(refreshinggap)m，即粒子的適應度值經過m次迭代都不再改進后，重新分配學習對象，否則，保持上次選擇的學習對象不變。研究[16]表明，m通常取7，效果較好。故文中更新間隔代數取7。

3.3 實驗結果及分析

實驗設置測試函數的維數為30，設置最大函數評估次數為900 000，設置綜合學習粒子群算法中的粒子數為60，禁忌搜索中鄰域解的個數為100，禁忌表長度為60。對于所有的函數，每種算法均獨立運行10次。

表1給出了CLPSO+Tabu(CMA-ES)、CLPSO在26個測試函數上10次運行的平均最優值及其標準差、適應度函數評價次數及其標準差。

表1 運行結果

部分函數的收斂過程如圖1所示。

由表1可以看出CLPSO+Tabu(CMA-ES)算法在26個函數上的最優值大多比經典CLPSO算法的結果更優。而在不同的函數上，該算法的優勢大小也不同。CLPSO+Tabu(CMA-ES)相比于經典CLPSO在函數F2、F5、F15、F17、F18、F19上有至少一個數量級的改進，在12個函數上有改進。由上述數據可以看出，CLPSO+Tabu(CMA-ES)算法在優化旋轉函數上的優勢較經典CLPSO更為顯著。

函數F1到F5是單峰問題。CLPSO+Tabu(CMA-ES)算法在函數F2、F5上比CLPSO算法有更優異的表現。函數F6到F11是離散多峰問題，局部最優值隨著維數的增大而增大。如表1所示，在這些函數中，CLPSO+Tabu(CMA-ES)算法的性能僅與經典CLPSO算法相持平。函數F12到F14是Rosenbrock函數和Rastrigin函數所衍射的函數問題。文中算法在這三個函數上只有些許改進甚至沒有改進。函數F15是由F2產生的問題，系統的高斯噪聲使得尋找全局最優值變得困難。在這個問題上，CLPSO+Tabu(CMA-ES)算法比經典CLPSO算法改進了至少一個數量級。函數F16到F26測試了算法解決非離散和病態問題的能力。F23、F24、F25是多峰問題。

圖1 CLPSO+Tabu(CMA-ES)和CLPSO在函數F2、F5、F15、F17、F18、F19上的收斂特性

文中算法由于采用了自適應的高斯分布鄰域結構，保持了解的多樣性和精確度，在大部分函數上均有改進，而改進的大多數為旋轉問題。因此，CLPSO+Tabu(CMA-ES)算法具有解決好旋轉問題、非離散問題和病態問題的能力。

4 結束語

文中以禁忌搜索算法為綜合學習粒子群算法的后續局部搜索操作，彌補了綜合學習粒子群算法后期收斂能力弱的缺點。禁忌搜索算法的性能和鄰域結構以及禁忌表密切相關，針對禁忌搜索算法的鄰域結構進行改進，以高斯分布作為鄰域結構，并利用CMA-ES策略控制鄰域結構的步長。通過在26個不同特性的函數上的實驗，與經典CLPSO算法相比，文中算法求解精度相對提高，很好地解決了綜合學習粒子群算法在后期收斂難的問題。

[1] 李雪梅,張素琴.基于仿生理論的幾種優化算法綜述[J].計算機應用研究,2009,26(6):2032-2034.

[2] 魏連偉.基于人工智能技術的地下水系統參數識別研究[D].天津:天津大學,2003.

[3] 黃婉平.自適應粒子群優化算法及其應用研究[D].杭州:浙江大學,2006.

[4] 許 君,魯海燕,石桂娟.限制速度粒子群優化和自適應速度粒子群優化在無約束優化問題中的應用[J].計算機應用,2015,35(3):668-674.

[5]KennedyJ.Particleswarmoptimization[M]//Encyclopediaofmachinelearning.Boston,MA:Springer,2010:760-766.

[6]LiangJJ,QinAK,SuganthanPN,etal.Comprehensivelearningparticleswarmoptimizerforglobaloptimizationofmultimodalfunctions[J].IEEETransactionsonEvolutionaryComputation,2006,10(3):281-295.

[7]LynnN,SuganthanPN.Comprehensivelearningparticleswa-rmoptimizerwithguidancevectorselection[C]//Proceedingsofthe2013IEEEsymposiumonswarmintelligence.Singapore:IEEE,2013:80-84.

[8] 許 駿,許曉東.一種群體智能融合算法及其在應急設施選址的應用[J].計算機工程與科學,2014,36(4):667-673.

[9]DewerraD,HertzA.Tabusearchtechnique-atutorialandanapplicationtoneuralnetworks[J].OperationsResearch,1989,11(3):131-141.

[10]OstermeierH.Adaptingarbitrarynormalmutationdistributionsinevolutionstrategies:thecovariancematrixadaptation[C]//Proceedingsofthe1996IEEEinternationalconferenceonevolutionarycomputation.Nagoya:IEEE,1996:312-317.

[11]WangY,LiB,WeiseT,etal.Self-adaptivelearningbasedparticleswarmoptimization[J].InformationSciences,2011,181(20):4515-4538.

[12] 潘全科,朱劍英.一類解決JobShop問題的禁忌搜索算法[J].中國機械工程,2006,17(5):536-539.

[13]LiangJJ,QinAK,SuganthanPN,etal.Evaluationofcomprehensivelearningparticleswarmoptimizer[J].LectureNotesinComputerScience,2004,3316:230-235.

[14] 蔡昭權,黃 翰.自適應變異綜合學習粒子群優化算法[J].計算機工程,2009,35(7):170-171.

[15] 劉關俊.基于粒子群算法的移動機器人路徑規劃研究[D].長沙:中南大學,2007.

[16]LiangJJ,SuganthanPN.Adaptivecomprehensivelearningparticleswarmoptimizerwithhistorylearning[C]//Simulatedevolutionandlearning.Berlin:Springer-Verlag,2006:213-220.

A Hybrid Optimization Algorithm Based on Tabu Strategy

YIN Xi1,XU Bin2,QI Jin2

(1.College of Automation,Nanjing University of Posts and Telecommunications,Nanjing 210003,China; 2.College of Things of Internet,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

In order to enhance the convergence ability of the Comprehensive Learning Particle Swarm Optimization (CLPSO) in the later stage,a hybrid optimization algorithm based on Tabu strategy is proposed and it is denoted by CLPSO+Tabu (CMA-ES).It improves CLPSO by taking Tabu strategy as the subsequent search operation.Moreover,the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) is introduced to the Tabu algorithm,which is based on Gaussian distribution.The CMA-ES guides the distribution of neighborhood structure to construct new adaptive neighborhood structure,then guides the selection of candidate solution,which can solve the problem of low convergence rate and improve the effect.The experimental result based on the 26 standard test functions shows that CLPSO+Tabu(CMA-ES) has better convergence effect than CLPSO.And it has improvement of at least one order of magnitude in six functions.

comprehensive learning particle swarm optimization;Tabu strategy;Gaussian distribution;parameter adaption;CMA-ES

2015-12-21

2016-05-12

時間：2017-01-10

國家自然科學基金資助項目(61401225);中國博士后科學基金資助項目(2015M571790)

印 溪(1992-)，女，碩士研究生，研究方向為智能計算與智能系統；許 斌，博士，講師，研究方向為智能計算、云制造服務組合;亓晉，博士，講師，研究方向為新一代網絡、大數據管理與智能計算、云計算。

http://www.cnki.net/kcms/detail/61.1450.TP.20170110.0941.012.html

TP301.6

A

1673-629X(2017)02-0046-05

10.3969/j.issn.1673-629X.2017.02.011