印 溪,許 斌,亓 晉

(1.南京郵電大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210003; 2.南京郵電大學(xué) 物聯(lián)網(wǎng)學(xué)院，江蘇 南京 210003)

一種基于禁忌策略的混合優(yōu)化算法

印 溪1,許 斌2,亓 晉2

(1.南京郵電大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210003; 2.南京郵電大學(xué) 物聯(lián)網(wǎng)學(xué)院，江蘇 南京 210003)

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

綜合學(xué)習(xí)粒子群算法；禁忌搜索；高斯分布；參數(shù)自適應(yīng)；協(xié)方差矩陣自適應(yīng)進(jìn)化策略

0 引 言

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

群智能優(yōu)化算法是一種通過模擬動(dòng)物集體行為來求解優(yōu)化問題的智能算法。與傳統(tǒng)算法相比，該算法的實(shí)現(xiàn)較簡單，對(duì)要解決的問題是否連續(xù)以及問題的規(guī)模均無要求，并且具有廣泛的適應(yīng)性和魯棒性[1]。

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

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

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

1 相關(guān)工作

1.1 CLPSO

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

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

(1)

(2)

每個(gè)粒子均產(chǎn)生[0，1]內(nèi)的均勻隨機(jī)數(shù)，若產(chǎn)生的隨機(jī)數(shù)大于設(shè)定的學(xué)習(xí)概率Pc，則設(shè)定學(xué)習(xí)對(duì)象為pbest，即粒子本身的歷史最優(yōu)位置；若產(chǎn)生的隨機(jī)數(shù)小于設(shè)定的學(xué)習(xí)概率，則按錦標(biāo)賽選擇策略(tournamentselectionprocedure)從種群內(nèi)隨機(jī)選取的兩個(gè)個(gè)體中選出較優(yōu)的歷史最優(yōu)位置作為學(xué)習(xí)對(duì)象。

為上述學(xué)習(xí)對(duì)象選擇過程中設(shè)定一個(gè)更新間隔代數(shù)(refreshinggap)m，即粒子的適應(yīng)度值經(jīng)過m次迭代都不再改進(jìn)后，重新分配學(xué)習(xí)對(duì)象，否則，保持上次選擇的學(xué)習(xí)對(duì)象不變。該策略可以使粒子向優(yōu)秀的對(duì)象學(xué)習(xí)，而不會(huì)在較差的對(duì)象上浪費(fèi)時(shí)間[7]。

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

1.2 Tabu

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

簡單TS算法的基本思想：首先，給定問題的一個(gè)初始解，同時(shí)，選擇一種鄰域結(jié)構(gòu)。然后，在初始解的鄰域中隨機(jī)確定一些候選解。此時(shí)，如果最優(yōu)候選解對(duì)應(yīng)的適應(yīng)度值優(yōu)于“best so far”狀態(tài)，則用該最優(yōu)候選解代替初始解和“best so far”狀態(tài)，同時(shí)將其加入禁忌表，并修改禁忌表中對(duì)象的禁忌時(shí)間；如果最優(yōu)候選解對(duì)應(yīng)的適應(yīng)度值并不優(yōu)于“best so far”狀態(tài)，則新的初始解在候選解中的非禁忌的最優(yōu)狀態(tài)中選出，即忽略其與初始解的優(yōu)劣關(guān)系，并將其加入禁忌表，同時(shí)修改禁忌表中對(duì)象的禁忌時(shí)間。如上述般重復(fù)迭代搜索過程，當(dāng)滿足停止準(zhǔn)則時(shí)，才可停止。

文中應(yīng)用的藐視準(zhǔn)則是基于適應(yīng)度值準(zhǔn)則中的全局形式。采用的終止準(zhǔn)則:給定每次運(yùn)行后總循環(huán)的次數(shù)，即最大迭代步數(shù)。

2 算法描述

2.1 鄰域結(jié)構(gòu)

禁忌搜索的性能基本依賴于所選取的鄰域結(jié)構(gòu)和所給定的初始解。文中的初始解由CLPSO提供。選取不同的鄰域結(jié)構(gòu)將得到不同的禁忌算法，而鄰域結(jié)構(gòu)的設(shè)計(jì)通常與問題有關(guān)。

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

高斯分布的概率密度函數(shù)為：

(3)

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

文中Tabu算法將初始解設(shè)為位置參數(shù)μ，使得候選解在初始解的3σ范圍內(nèi)，且離初始解越近，取到的機(jī)率就越大，即以初始解為中心，在其周邊3σ范圍內(nèi)進(jìn)行候選解的選取。σ的大小意味著候選解可能的取值范圍。為控制σ的大小，引入?yún)f(xié)方差矩陣自適應(yīng)進(jìn)化策略，隨著進(jìn)化代數(shù)的推進(jìn)，自適應(yīng)地改變?chǔ)业娜≈?，從而影響候選解選取的范圍。

2.2 CMA-ES

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

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

σ的步長控制函數(shù)為：

(4)

其中，pσ為進(jìn)化路徑，其更新公式為：

(5)

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

(6)

協(xié)方差矩陣自適應(yīng)進(jìn)化策略結(jié)合了進(jìn)化策略方法的全局性和協(xié)方差矩陣的可引導(dǎo)性，對(duì)于解決非凸非線性優(yōu)化函數(shù)問題有非常好的適應(yīng)能力。

2.3 基于CMA-ES的CLPSO算法

為了進(jìn)一步增強(qiáng)CLPSO的局部搜索能力，提高解精度，引入禁忌搜索算法。以CMA-ES策略引導(dǎo)高斯鄰域結(jié)構(gòu)的變化，自適應(yīng)地產(chǎn)生較好的鄰域解，從而獲得更精確的解。

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

第一步：初始化。

(1)對(duì)種群中每個(gè)個(gè)體的位置進(jìn)行隨機(jī)初始化；

(2)計(jì)算初始化后個(gè)體的適應(yīng)度值，將最優(yōu)值存儲(chǔ)于pbestval，將最優(yōu)解存儲(chǔ)于pbest；

(3)對(duì)種群中每個(gè)個(gè)體的速度進(jìn)行隨機(jī)初始化。

第二步：用錦標(biāo)賽的方式挑選學(xué)習(xí)對(duì)象。

在種群中隨機(jī)挑選兩個(gè)粒子進(jìn)行比賽，根據(jù)兩個(gè)粒子pbest的適應(yīng)度值的大小判斷輸贏，適應(yīng)度值優(yōu)的一方獲勝。若其值相同，則隨機(jī)選取。利用較好的那個(gè)粒子的pbest作為更新的標(biāo)本，如果一個(gè)粒子的所有標(biāo)本都是自身pbest，就隨機(jī)抽取其中一維來學(xué)習(xí)其他粒子的pbest。

第三步：更新。

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

第四步：停止CLPSO。

當(dāng)函數(shù)評(píng)估次數(shù)達(dá)到預(yù)設(shè)值，停止CLPSO的進(jìn)化，將最后一代的最優(yōu)解作為初始解。

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

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

①更新協(xié)方差矩陣Cg，更新進(jìn)化路徑pσ。

②計(jì)算鄰域大小。

(2)選出候選解中最優(yōu)解作為“bestsofar”狀態(tài)。

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

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

第六步：停止禁忌搜索。

當(dāng)“bestsofar”狀態(tài)連續(xù)50次未進(jìn)化，則停止搜索，輸出最后一代的“bestsofar”狀態(tài)。

第七步：迭代次數(shù)加1，跳回第一步重新開始，當(dāng)達(dá)到最大迭代次數(shù)停止進(jìn)化并輸出最優(yōu)的“bestsofar”狀態(tài)。

經(jīng)過實(shí)驗(yàn)驗(yàn)證，該算法在優(yōu)化旋轉(zhuǎn)函數(shù)上優(yōu)勢顯著，由于禁忌算法的加入，CLPSO+Tabu(CMA-ES)算法在單峰問題中較經(jīng)典CLPSO效果更優(yōu)秀，而在非離散問題和病態(tài)問題上，效果也有一定程度的改進(jìn)。

3 實(shí) 驗(yàn)

3.1 測試函數(shù)

利用26個(gè)具有不同特性的測試函數(shù)來對(duì)算法進(jìn)行測試,測試函數(shù)詳見文獻(xiàn)[11]。

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

3.2 參數(shù)取值

3.2.1 禁忌表及禁忌長度

在不考慮藐視準(zhǔn)則的情況下，禁忌長度是禁忌對(duì)象不能被選取的最大次數(shù)，只有當(dāng)其禁忌時(shí)間為0時(shí)才可以被解禁。禁忌長度小，則相應(yīng)算法的計(jì)算量和存儲(chǔ)量?。坏?，禁忌長度過小，將造成循環(huán)搜索。文中禁忌長度取為7[12]。

3.2.2 學(xué)習(xí)概率Pc

學(xué)習(xí)概率的設(shè)置影響了每個(gè)粒子的學(xué)習(xí)能力。不同的學(xué)習(xí)概率對(duì)算法的探測和搜索能力有很大影響。研究[13]表明，學(xué)習(xí)概率為[14]：

(7)

其中，Lpmax和Lpmin分別對(duì)應(yīng)學(xué)習(xí)概率的最大值和最小值，根據(jù)經(jīng)驗(yàn)，Lpmax=0.5，Lpmin=0.05；N為種群的粒子數(shù)。

3.2.3 慣性權(quán)重w

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

(8)

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

3.2.4 更新間隔代數(shù)m

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

3.3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)設(shè)置測試函數(shù)的維數(shù)為30，設(shè)置最大函數(shù)評(píng)估次數(shù)為900 000，設(shè)置綜合學(xué)習(xí)粒子群算法中的粒子數(shù)為60，禁忌搜索中鄰域解的個(gè)數(shù)為100，禁忌表長度為60。對(duì)于所有的函數(shù)，每種算法均獨(dú)立運(yùn)行10次。

表1給出了CLPSO+Tabu(CMA-ES)、CLPSO在26個(gè)測試函數(shù)上10次運(yùn)行的平均最優(yōu)值及其標(biāo)準(zhǔn)差、適應(yīng)度函數(shù)評(píng)價(jià)次數(shù)及其標(biāo)準(zhǔn)差。

表1 運(yùn)行結(jié)果

部分函數(shù)的收斂過程如圖1所示。

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

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

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

文中算法由于采用了自適應(yīng)的高斯分布鄰域結(jié)構(gòu)，保持了解的多樣性和精確度，在大部分函數(shù)上均有改進(jìn)，而改進(jìn)的大多數(shù)為旋轉(zhuǎn)問題。因此，CLPSO+Tabu(CMA-ES)算法具有解決好旋轉(zhuǎn)問題、非離散問題和病態(tài)問題的能力。

4 結(jié)束語

文中以禁忌搜索算法為綜合學(xué)習(xí)粒子群算法的后續(xù)局部搜索操作，彌補(bǔ)了綜合學(xué)習(xí)粒子群算法后期收斂能力弱的缺點(diǎn)。禁忌搜索算法的性能和鄰域結(jié)構(gòu)以及禁忌表密切相關(guān)，針對(duì)禁忌搜索算法的鄰域結(jié)構(gòu)進(jìn)行改進(jìn)，以高斯分布作為鄰域結(jié)構(gòu)，并利用CMA-ES策略控制鄰域結(jié)構(gòu)的步長。通過在26個(gè)不同特性的函數(shù)上的實(shí)驗(yàn)，與經(jīng)典CLPSO算法相比，文中算法求解精度相對(duì)提高，很好地解決了綜合學(xué)習(xí)粒子群算法在后期收斂難的問題。

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

[2] 魏連偉.基于人工智能技術(shù)的地下水系統(tǒng)參數(shù)識(shí)別研究[D].天津:天津大學(xué),2003.

[3] 黃婉平.自適應(yīng)粒子群優(yōu)化算法及其應(yīng)用研究[D].杭州:浙江大學(xué),2006.

[4] 許 君,魯海燕,石桂娟.限制速度粒子群優(yōu)化和自適應(yīng)速度粒子群優(yōu)化在無約束優(yōu)化問題中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用,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] 許 駿,許曉東.一種群體智能融合算法及其在應(yīng)急設(shè)施選址的應(yīng)用[J].計(jì)算機(jī)工程與科學(xué),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].中國機(jī)械工程,2006,17(5):536-539.

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

[14] 蔡昭權(quán),黃 翰.自適應(yīng)變異綜合學(xué)習(xí)粒子群優(yōu)化算法[J].計(jì)算機(jī)工程,2009,35(7):170-171.

[15] 劉關(guān)俊.基于粒子群算法的移動(dòng)機(jī)器人路徑規(guī)劃研究[D].長沙:中南大學(xué),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

時(shí)間：2017-01-10

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

印 溪(1992-)，女，碩士研究生，研究方向?yàn)橹悄苡?jì)算與智能系統(tǒng)；許 斌，博士，講師，研究方向?yàn)橹悄苡?jì)算、云制造服務(wù)組合;亓?xí)x，博士，講師，研究方向?yàn)樾乱淮W(wǎng)絡(luò)、大數(shù)據(jù)管理與智能計(jì)算、云計(jì)算。

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