多模態(tài)函數(shù)聚類(lèi)后再創(chuàng)種群的并行搜索佳點(diǎn)集螢火蟲(chóng)算法

，，，

(1.浙江理工大學(xué)信息學(xué)院，杭州 310018；2.合肥工業(yè)大學(xué)管理學(xué)院，合肥 230009)

多模態(tài)函數(shù)聚類(lèi)后再創(chuàng)種群的并行搜索佳點(diǎn)集螢火蟲(chóng)算法

方賢1，鐵治欣1，李敬明2，高雄1

(1.浙江理工大學(xué)信息學(xué)院，杭州 310018；2.合肥工業(yè)大學(xué)管理學(xué)院，合肥 230009)

螢火蟲(chóng)算法在求解多模態(tài)函數(shù)時(shí)，隨著峰值個(gè)數(shù)的增加，往往需要更大的種群規(guī)模才能得到較為理想的結(jié)果，而且初始種群是否均勻分布對(duì)結(jié)果也有很大影響。針對(duì)螢火蟲(chóng)算法的這些不足，提出了一種多模態(tài)函數(shù)的聚類(lèi)后再創(chuàng)種群的并行搜索佳點(diǎn)集螢火蟲(chóng)算法。該算法首先以數(shù)論佳點(diǎn)集的思想將螢火蟲(chóng)均勻分布于搜索空間中，在粗糙搜索完成后，通過(guò)密度聚類(lèi)算法進(jìn)行捕峰操作，重新構(gòu)造等同于峰值點(diǎn)數(shù)的各個(gè)平行空間；然后在各空間中繼續(xù)加入少量佳點(diǎn)集生成的螢火蟲(chóng)并行精細(xì)搜索，最終可獲得各個(gè)平行空間的局部最優(yōu)解以及整個(gè)空間的全局最優(yōu)解。與其他算法在12個(gè)典型多模態(tài)函數(shù)中的測(cè)試結(jié)果進(jìn)行對(duì)比，該算法總體上縮小了種群規(guī)模，加快了收斂速度，搜索精度更高，時(shí)間成本更低，穩(wěn)定性能更好。

螢火蟲(chóng)算法；多模態(tài)函數(shù)；佳點(diǎn)集；密度聚類(lèi)算法；并行搜索

0 引 言

在工程技術(shù)、科學(xué)計(jì)算、經(jīng)濟(jì)管理等領(lǐng)域中，絕大多數(shù)實(shí)際問(wèn)題可以通過(guò)構(gòu)建模型歸結(jié)為函數(shù)優(yōu)化問(wèn)題。其中，一些函數(shù)由于自身維數(shù)高、峰值點(diǎn)多、震蕩嚴(yán)重等因素造成性態(tài)差。采用傳統(tǒng)的算法，如DFP變尺度算法、Powell方向加速法等，往往難以或無(wú)法找到全局最優(yōu)解。近年來(lái)隨著智能計(jì)算學(xué)科的發(fā)展，一些仿生算法應(yīng)運(yùn)而生，如粒子群算法(particle swarm optimization，PSO)、遺傳算法(genetic algorithm，GA)、蟻群算法(ant clony optimization，ACO)、蜂群算法(artificial bee colony algorithm，ABC)、魚(yú)群算法(artificial fish swarm algorithm，AFSA)等。這些基本群智能算法可以較好地滿足全局搜索需求，但在算法性能上仍有很大程度的提升空間。

多模態(tài)函數(shù)優(yōu)化問(wèn)題(multi-modal function optimization problems)，又稱(chēng)多峰值函數(shù)優(yōu)化問(wèn)題，在函數(shù)優(yōu)化問(wèn)題中最為常見(jiàn)。它指的是具有多個(gè)峰值點(diǎn)的函數(shù)，因存在較多的峰值點(diǎn)，很容易使得算法尋優(yōu)陷入局部最優(yōu)而無(wú)法找出全局最優(yōu)。將一些基本算法的改進(jìn)措施應(yīng)用于多模態(tài)函數(shù)的全局尋優(yōu)上可以取得更好的效果，例如：Kennedy[1]在基本PSO算法基礎(chǔ)上提出一種基于聚類(lèi)技術(shù)改進(jìn)的PSO算法，使用K-means算法將主群分割為K個(gè)子群，通過(guò)各子群中粒子的全局最優(yōu)位置與歷史最優(yōu)位置的質(zhì)心交換來(lái)更新主群的相關(guān)參數(shù)。Shelokar等[2]將ACO算法與PSO算法結(jié)合，采用簡(jiǎn)單的信息素將蟻群與粒子群相關(guān)聯(lián)，當(dāng)粒子更新時(shí)，與之關(guān)聯(lián)的螞蟻也會(huì)更新。Agrawal等[3]將Fletcher-Reeves共軛梯度的思想用于搜索PSO算法中的粒子訪問(wèn)區(qū)域，可以使粒子移動(dòng)到更具尋優(yōu)潛力的區(qū)域。Fan等[4]提出一種最小消除逃逸函數(shù)方法，該方法主要由最小消除函數(shù)和最小逃逸函數(shù)兩個(gè)子函數(shù)實(shí)現(xiàn)功能，前者用于減少局部最優(yōu)解的個(gè)數(shù)，后者在此基礎(chǔ)上將當(dāng)前最小解作為唯一的全局最大值。Zhou等[5]對(duì)基本ABC算法進(jìn)行了多方面改進(jìn)，首先通過(guò)動(dòng)態(tài)調(diào)整蜂群的規(guī)模較好地適應(yīng)不同的目標(biāo)函數(shù)，其次加入了平衡搜索機(jī)制用于加快算法收斂速度，此外通過(guò)半徑估算及最佳精英策略的嵌入分別增強(qiáng)了不規(guī)則分布的蜜蜂搜索最優(yōu)解能力，消除無(wú)關(guān)的局部最優(yōu)解能力。

很多實(shí)際問(wèn)題不僅要求尋找全局最優(yōu)解，同時(shí)還需要找到眾多有意義的局部最優(yōu)解，以便工程師進(jìn)行多方面考量與決策。因此，對(duì)于多模態(tài)函數(shù)優(yōu)化問(wèn)題，在搜索到其全局最優(yōu)解的同時(shí)獲得局部最優(yōu)解既具有挑戰(zhàn)難度，更具有實(shí)際價(jià)值。螢火蟲(chóng)群優(yōu)化(glowworm swarm optimization，GSO)算法具有操作簡(jiǎn)單易實(shí)現(xiàn)、算法流程清晰、全局與局部性能協(xié)調(diào)、參數(shù)設(shè)置較少、魯棒性強(qiáng)等優(yōu)點(diǎn)，尤其在可視化方面表現(xiàn)優(yōu)異，能直觀地顯現(xiàn)出螢火蟲(chóng)在多模態(tài)函數(shù)極值點(diǎn)附近的聚簇狀況，并快速獲取局部最優(yōu)解以及整個(gè)空間的全局最優(yōu)解。GSO以其卓越的特性而廣泛運(yùn)用于多模態(tài)函數(shù)優(yōu)化中，如：Zhang等[6]提出了自適應(yīng)步長(zhǎng)的V-GSO算法和自探索行為的E-GSO算法，并列舉3個(gè)多模態(tài)函數(shù)驗(yàn)證GSO算法可以通過(guò)動(dòng)態(tài)線性或非線性遞減步長(zhǎng)兩種途徑提升性能，此外為每只螢火蟲(chóng)設(shè)置閾值和適應(yīng)度值，通過(guò)兩者關(guān)系來(lái)判斷是否存在鄰居進(jìn)而考慮是否采用螺旋搜索可改善GSO的自適應(yīng)性。Zhou等[7]提出了一種混合的HGSO算法，該算法將AFSA算法中魚(yú)群的覓食行為引入到GSO算法中，采用雙種群的協(xié)同進(jìn)化機(jī)制，同時(shí)加入模擬退火算法的局部搜索策略以克服早熟收斂缺陷。雖然以上各種改進(jìn)的策略在收斂速度和計(jì)算精度上較傳統(tǒng)GSO有較大的提高，但GSO算法在多模態(tài)函數(shù)優(yōu)化中仍存在以下兩方面問(wèn)題未得到妥善地處理[8-9]：一方面，螢火蟲(chóng)的初始種群隨機(jī)分布，算法穩(wěn)定性能無(wú)法得到提升，不適合的分布還會(huì)導(dǎo)致算法收斂速度慢、搜索精度低；另一方面，隨著多模態(tài)函數(shù)峰值點(diǎn)個(gè)數(shù)的增加，較少的螢火蟲(chóng)種群往往難以捕捉到所有的峰值，即便可以成功捕獲所有峰值，也很難將搜索到的各個(gè)峰值點(diǎn)的誤差降到合理的范圍內(nèi)。為克服以上不足，本文提出一種針對(duì)多模態(tài)函數(shù)的聚類(lèi)后再創(chuàng)種群的并行搜索佳點(diǎn)集螢火蟲(chóng)算法(parallel search good-point set GSO，PGSGSO)，并通過(guò)在12個(gè)基準(zhǔn)測(cè)試函數(shù)上的仿真實(shí)驗(yàn)驗(yàn)證了所提算法的可行性與有效性。

1 基本GSO算法

基本GSO算法最初是由印度學(xué)者Krishnanand和Ghose[10-11]于2005年提出的一種新穎的群智能優(yōu)化算法。此后，隨著國(guó)內(nèi)外廣大學(xué)者們的研究深入[12-16]，該算法逐漸展露出其獨(dú)特的多模態(tài)尋優(yōu)性能，展現(xiàn)出良好的研究與應(yīng)用前景。通過(guò)觀察自然界中一種常見(jiàn)的現(xiàn)象可以發(fā)現(xiàn)：夜晚螢火蟲(chóng)利用熒光亮度與外界交互，求偶或覓食。在感知范圍內(nèi)，每只螢火蟲(chóng)憑借自身的亮度吸引其它亮度更弱的螢火蟲(chóng)向它聚集，同時(shí)也受到亮度更強(qiáng)的螢火蟲(chóng)的吸引。GSO算法受這種自然機(jī)理的啟發(fā)設(shè)計(jì)。它的數(shù)學(xué)描述為：若干只螢火蟲(chóng)個(gè)體i(i=1,2,…,n)被隨機(jī)分布于目標(biāo)函數(shù)f定義的范圍空間D中，每只螢火蟲(chóng)代表了優(yōu)化問(wèn)題的一個(gè)潛在解，這些螢火蟲(chóng)各自擁有所在位置對(duì)應(yīng)于目標(biāo)函數(shù)的評(píng)價(jià)值，稱(chēng)為適應(yīng)度值。愈亮的螢火蟲(chóng)其適應(yīng)度值愈優(yōu)，吸引其它螢火蟲(chóng)向自己移動(dòng)的能力也愈強(qiáng)。同時(shí)，它們還擁有相同的感知半徑與決策半徑，處于感知范圍內(nèi)的亮度更弱的螢火蟲(chóng)，稱(chēng)為鄰居。迭代過(guò)程中，決策半徑與熒光素值動(dòng)態(tài)更新。其中決策半徑受鄰居數(shù)目的影響，兩者成反比例關(guān)系；熒光素值受揮發(fā)系數(shù)及增強(qiáng)系數(shù)的影響。迭代完成后，大多數(shù)螢火蟲(chóng)會(huì)聚集到相對(duì)更優(yōu)的適應(yīng)度值的位置，獲得尋優(yōu)結(jié)果。GSO算法主要涉及以下公式：

a) 熒光素更新公式為

li(t)=(1-ρ)li(t-1)+γJ(xi(t))

(1)

式中：ρ為熒光素值揮發(fā)系數(shù)，γ為熒光素值增強(qiáng)系數(shù)，li(t)為第t次迭代時(shí)螢火蟲(chóng)i的熒光素值，xi(t)為第t次迭代時(shí)螢火蟲(chóng)i的位置，J(xi(t))為第t次迭代時(shí)的目標(biāo)函數(shù)值。

b) 位置更新公式為

(2)

式中：s為螢火蟲(chóng)位移的步長(zhǎng)。

c) 鄰居集合公式為

(3)

d) 路徑概率選擇公式為

(4)

式中：pij(t)為第i只螢火蟲(chóng)轉(zhuǎn)向鄰居中其他螢火蟲(chóng)的轉(zhuǎn)移概率。

e) 決策域更新公式為

(5)

2 聚類(lèi)后再創(chuàng)種群的并行搜索佳點(diǎn)集螢火蟲(chóng)算法

2.1 佳點(diǎn)集理論

張鈸等[18]更進(jìn)一步地研究得出以下結(jié)論：

a) 在近似積分的運(yùn)用中，佳點(diǎn)集所產(chǎn)生的誤差的階只依賴于樣本個(gè)數(shù)，并不隨著樣本空間維數(shù)的遞增而變大。這為高維空間的研究提供了一個(gè)潛在的理論基礎(chǔ)。

b) 對(duì)于任意未知分布的對(duì)象，隨機(jī)產(chǎn)生n個(gè)空間中的點(diǎn)所得出的偏差通常為Φ(n)=O(n-1/2(loglogn)1/2)，使用佳點(diǎn)集分布所得到的偏差僅為Φ(n)=O(n-1+ε)。相比較隨機(jī)方法，佳點(diǎn)集的偏差降到了平方根級(jí)別。

2.2 密度聚類(lèi)算法

聚類(lèi)算法是數(shù)據(jù)挖掘領(lǐng)域重要的技術(shù)，其思路是按照事物內(nèi)在屬性將對(duì)象聚集成若干類(lèi)，要求同一類(lèi)間相似性盡可能高，而不同類(lèi)間相似性盡可能低。它是一種無(wú)導(dǎo)師指導(dǎo)的學(xué)習(xí)方法，主要應(yīng)用在模式識(shí)別、推薦系統(tǒng)、圖像處理等方向。根據(jù)具體實(shí)現(xiàn)方法的不同可將聚類(lèi)算法分為五種：劃分法聚類(lèi)、層次法聚類(lèi)、基于模型的聚類(lèi)、網(wǎng)格法聚類(lèi)以及密度聚類(lèi)。其中，密度聚類(lèi)算法區(qū)別于另外幾種方法很重要的一點(diǎn)，在于該方法是以數(shù)據(jù)在空間中分布的稠密程度為原則進(jìn)行聚類(lèi)，因此無(wú)需預(yù)先設(shè)置簇的數(shù)量，尤其適用于搜尋未知多模態(tài)函數(shù)的峰值數(shù)。

DBSCAN(density-based spatial clustering of applications with noise)算法是密度聚類(lèi)算法中最為典型的一種，其基本思想是：從數(shù)據(jù)集中的任意對(duì)象出發(fā)，查找該對(duì)象在半徑Eps條件下密度可達(dá)的所有對(duì)象，若所發(fā)現(xiàn)的對(duì)象不少于最小密度閾值MinPts，則稱(chēng)該對(duì)象為核心對(duì)象，若所發(fā)現(xiàn)的對(duì)象少于最小密度閾值MinPts，則稱(chēng)該對(duì)象為邊界點(diǎn)，此時(shí)邊界點(diǎn)會(huì)被暫時(shí)標(biāo)記為噪聲點(diǎn)。采用廣度優(yōu)先搜索循環(huán)執(zhí)行，最終由一個(gè)核心對(duì)象與其密度可達(dá)的所有對(duì)象構(gòu)成一個(gè)聚類(lèi)。

2.3 改進(jìn)的螢火蟲(chóng)算法

本文所提的PGSGSO算法從以下兩個(gè)方面對(duì)基本GSO算法進(jìn)行改進(jìn)。首先，在基本GSO算法的初始種群構(gòu)造方面，使用數(shù)論佳點(diǎn)集均勻化的思想設(shè)計(jì)螢火蟲(chóng)個(gè)體的均勻分布，使得盡可能少的螢火蟲(chóng)能全面地表征整個(gè)空間所有潛在解的分布。換言之，如果產(chǎn)生隨機(jī)初始種群，就很難遍歷解空間中的各種狀況，只有將整個(gè)解空間中最能表征潛在解分布的若干個(gè)體作為初始解集合，才能更為有效地解決實(shí)際問(wèn)題。因此，佳點(diǎn)集均勻化設(shè)計(jì)可以很好地解決這個(gè)問(wèn)題。其次，在針對(duì)多模態(tài)函數(shù)捕峰操作方面，考慮到僅用少量的螢火蟲(chóng)難以準(zhǔn)確地捕捉到復(fù)雜函數(shù)的各個(gè)峰值點(diǎn)，而使用大量的螢火蟲(chóng)無(wú)疑會(huì)增加算法的復(fù)雜度，加大時(shí)間開(kāi)銷(xiāo)。本文借助密度聚類(lèi)函數(shù)在GSO算法迭代完成后，對(duì)散落在空間中的所有螢火蟲(chóng)進(jìn)行聚類(lèi)，然后分別將每個(gè)類(lèi)中的螢火蟲(chóng)的坐標(biāo)以各個(gè)坐標(biāo)軸對(duì)應(yīng)的最大最小值為邊界，構(gòu)建出等同于峰值點(diǎn)數(shù)的各個(gè)平行空間。通過(guò)在各個(gè)平行空間中繼續(xù)加入少量的佳點(diǎn)集策略生成的螢火蟲(chóng)進(jìn)行精細(xì)搜索，可以達(dá)到并行搜索的效果，以此權(quán)衡效率與成本之間的矛盾。

PGSGSO算法的基本步驟如下：

a) 初始化基本GSO算法相關(guān)參數(shù)，包括：搜索空間維數(shù)d，種群規(guī)模n，熒光素值l0，熒光素值揮發(fā)系數(shù)ρ，熒光素值增強(qiáng)系數(shù)γ，感知半徑rs，感知半徑變化系數(shù)β，鄰居個(gè)數(shù)閾值nt，移動(dòng)步長(zhǎng)s等，設(shè)置迭代計(jì)數(shù)器初值為t0=1，終值為tmax。

b) 利用佳點(diǎn)集方法在搜索空間中設(shè)計(jì)螢火蟲(chóng)種群的均勻分布，空間中的坐標(biāo)對(duì)應(yīng)為螢火蟲(chóng)種群的初始位置，選取典型多模態(tài)函數(shù)作為評(píng)價(jià)適應(yīng)度值函數(shù)。

c) 按照式(1)更新所有螢火蟲(chóng)熒光素值。

d) 螢火蟲(chóng)個(gè)體按照式(2)進(jìn)行位置更新。其過(guò)程先按照式(3)計(jì)算鄰居集合，再按照式(4)計(jì)算移動(dòng)概率，以輪盤(pán)賭法作為選擇移動(dòng)對(duì)象的方法。

e) 按照式(5)對(duì)螢火蟲(chóng)動(dòng)態(tài)決策半徑進(jìn)行更新。

f) 判斷是否達(dá)到最大迭代次數(shù)，若是，轉(zhuǎn)向步驟g，否則，令t=t+1并轉(zhuǎn)向步驟c。

g) 使用密度聚類(lèi)算法將搜索空間中螢火蟲(chóng)個(gè)體聚集在等同于函數(shù)峰值數(shù)的若干區(qū)域內(nèi)，各區(qū)域空間螢火蟲(chóng)坐標(biāo)值排序后選擇最大最小坐標(biāo)固定平行空間界限。繼續(xù)投入少量佳點(diǎn)集生成的螢火蟲(chóng)于各平行空間并行搜索。

h) 重復(fù)執(zhí)行步驟c—e直至算法達(dá)到此階段最大迭代次數(shù)。

i) 輸出結(jié)果，算法終止。

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

3.1 測(cè)試函數(shù)

為了驗(yàn)證本文所提的PGSGSO算法在實(shí)際運(yùn)用中的有效性，采用Matlab R2013b平臺(tái)編寫(xiě)代碼，實(shí)驗(yàn)環(huán)境為：Intel 3.10 GHz CPU、64位Windows XP操作系統(tǒng)。選取了12個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)f1—f12對(duì)算法進(jìn)行仿真分析，它們均是定義在二維空間中的多模態(tài)函數(shù)，其中：f1—f5的極小峰值點(diǎn)個(gè)數(shù)小于等于50，相對(duì)簡(jiǎn)單；f6—f12均是極小峰值點(diǎn)個(gè)數(shù)遠(yuǎn)大于50的復(fù)雜多模態(tài)函數(shù)。f1、f9選自文獻(xiàn)[19]，f2選自文獻(xiàn)[3]，f3、f7選自文獻(xiàn)[20]，f4選自

文獻(xiàn)[21]，f5選自文獻(xiàn)[2]，f6、f10、f11選自文獻(xiàn)[22]，f8選自文獻(xiàn)[23]，f12選自文獻(xiàn)[4]。12個(gè)測(cè)試函數(shù)如下：

minf2(x)=(1+(x1+x2+1)2(19-14(x1+x2)+

表1 實(shí)驗(yàn)使用的benchmark測(cè)試函數(shù)詳細(xì)信息

3.2 參數(shù)設(shè)置

實(shí)驗(yàn)參數(shù)設(shè)置如表2所示。對(duì)f1—f5函數(shù)，初始螢火蟲(chóng)的個(gè)數(shù)n設(shè)為50；對(duì)f6—f12函數(shù)，初始螢火蟲(chóng)的個(gè)數(shù)n設(shè)為200。

表2 PGSGSO算法實(shí)驗(yàn)參數(shù)

3.3 實(shí)驗(yàn)結(jié)果討論

以f1(x)為例說(shuō)明PGSGSO算法的實(shí)行過(guò)程。首先在定義域空間[-10,10]中均勻生成50只螢火蟲(chóng)，如圖1(a)所示。在20次粗糙搜索完成后得到圖1(b)所示結(jié)果，從圖1(b)可以清晰地看出螢火蟲(chóng)聚集成4個(gè)簇，即象征著搜索空間中的4個(gè)峰值點(diǎn)。在事先對(duì)極小峰值個(gè)數(shù)未知的情況下，采用DBSCAN算法進(jìn)行聚類(lèi)分析得到如圖1(c)所示結(jié)果。圖(c)中不同顏色的螢火蟲(chóng)積聚在一起代表不同的類(lèi)，可以驗(yàn)證此時(shí)成功捕獲出4個(gè)極小峰值，與實(shí)際峰值個(gè)數(shù)一致。然后對(duì)4個(gè)類(lèi)劃分平行空間，經(jīng)過(guò)先前20次迭代螢火蟲(chóng)已經(jīng)集中分布于各個(gè)峰值點(diǎn)附近，這時(shí)候需要在各個(gè)空間內(nèi)精確搜索，為此設(shè)計(jì)在這些空間中增添20只螢火蟲(chóng)，如圖1(d)所示。

圖1 PGSGSO對(duì)f1(x)的實(shí)行過(guò)程

PGSGSO算法的過(guò)程實(shí)質(zhì)上包括兩個(gè)階段：前期的全局粗糙搜索和后期的局部精細(xì)搜索。為合理地協(xié)調(diào)以上兩個(gè)階段，定義平衡因子φ，表示前期的粗糙搜索在整個(gè)搜索過(guò)程所占據(jù)的權(quán)重(0<φ<100%)?？紤]到φ的大小對(duì)于實(shí)驗(yàn)結(jié)果的重要性，在保持其他參數(shù)不變時(shí)，設(shè)置不同大小的φ獨(dú)立進(jìn)行20次實(shí)驗(yàn)，結(jié)果如圖2所示。本文選用φ=40%作為最終實(shí)驗(yàn)參數(shù)。

圖2 不同平衡因子與最優(yōu)解次數(shù)曲線圖

此外，在后期并行搜索中的過(guò)程中，由于劃分空間導(dǎo)致的空間數(shù)目增加而空間范圍縮小，步長(zhǎng)與決策半徑等變量需要進(jìn)行調(diào)整。采用等比例原則處理上述問(wèn)題：將空間的縮小以同等比例地應(yīng)用于這些變量。另外，限制搜索范圍，即各個(gè)空間之間互不干涉，保證并行搜索的可行性。

評(píng)價(jià)PGSGSO算法的改進(jìn)工作應(yīng)盡可能落實(shí)到全面而客觀，表3從捕峰能力、對(duì)全局最優(yōu)解所達(dá)到的精度、算法穩(wěn)定性能、消耗時(shí)長(zhǎng)等多方面綜合考慮。用PGSGSO算法、HGSO算法[7]、GSO-Powell算法[19]對(duì)12個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)各進(jìn)行20次實(shí)驗(yàn)，圖3是各種算法對(duì)測(cè)試函數(shù)的其中一次尋優(yōu)曲線。在捕峰能力的評(píng)價(jià)中，規(guī)定若平均捕峰個(gè)數(shù)與實(shí)際個(gè)數(shù)相差在2%范圍內(nèi)，則稱(chēng)捕峰“成功”，成功率為(Nm/Nc)×100%，其中Nm代表平均捕峰個(gè)數(shù)，Nc代表實(shí)際峰值個(gè)數(shù)。

表3 PGSGSO與其他算法性能對(duì)比

表3續(xù)

測(cè)試函數(shù)算法平均最優(yōu)值方差平均耗時(shí)/s捕峰成功率/%f2PGSGSO3.0000002583.4895×10-3213.52100HGSO3.0000058682.8627×10-733.12100GSO-Powell3.0000078435.1906×10-453.42100f3PGSGSO-1.0316285356.7426×10-2313.11100HGSO-1.0316285346.3556×10-736.5499.69GSO-Powell-1.0316285317.2425×10-1358.34100f4PGSGSO7.09023×10-68.3885×10-1216.28100HGSO3.93758×10-65.2853×10-438.3599.72GSO-Powell8.47588×10-63.8938×10-363.2899.16f5PGSGSO-1.9999990391.4993×10-1422.19100HGSO-1.9999983478.5831×10-556.3498.88GSO-Powell-1.9999948962.4362×10-263.5298.92f6PGSGSO3.25346×10-57.4493×10-1138.57100HGSO3.28755×10-54.6673×10-255.2192.21GSO-Powell4.35665×10-59.5683×10-677.3598.79f7PGSGSO-186.73093427.8482×10-1237.2399.69HGSO-186.73088472.9275×10-658.1498.48GSO-Powell-186.73053685.5362×10-474.5398.34f8PGSGSO-176.54179423.8371×10-1039.1199.74HGSO-176.54168373.5145×10-346.4198.32GSO-Powell-176.54025966.2358×10-379.2798.47f9PGSGSO8.28689×10-52.3923×10-939.3599.43HGSO9.47835×10-49.3433×10-553.3289.78GSO-Powell1.22544×10-48.5402×10-278.4298.83f10PGSGSO5.92375×10-66.4352×10-1239.2399.55HGSO8.28658×10-52.9057×10-547.3581.63GSO-Powell7.68675×10-45.3672×10-378.4379.64f11PGSGSO8.22819×10-55.3332×10-842.5297.28HGSO3.34376×10-43.0289×10-354.4678.23GSO-Powell7.05574×10-37.7735×10-272.2386.28f12PGSGSO-837.96588276.4425×10-837.3998.52HGSO-837.96381463.2975×10-256.2772.45GSO-Powell-837.39757323.9728×10-376.5988.86

圖3 12個(gè)函數(shù)的尋優(yōu)曲線

由表3和圖3可以看出，在捕峰能力方面，PGSGSO除了f11捕峰不“成功”外，其余均“成功”。而HGSO對(duì)f6、f9—f12捕峰均不“成功”，GSO-Powell對(duì)f10—f12捕峰均不“成功”。在全局解的精度方面，總體來(lái)看，PGSGSO稍優(yōu)于HGSO，GSO-Powell次之。在算法穩(wěn)定性能方面，觀察方差可以發(fā)現(xiàn)PGSGSO明顯更穩(wěn)定于另外兩種算法。在收斂速度方面，PGSGSO在尋優(yōu)過(guò)程中總是存在跳躍點(diǎn)，能迅速加快收斂速度，原因就在于采用了聚類(lèi)后再創(chuàng)佳點(diǎn)集種群操作。從圖3可以發(fā)現(xiàn)PGSGSO在對(duì)所有測(cè)試函數(shù)尋優(yōu)時(shí)，第1次迭代時(shí)的值相對(duì)來(lái)說(shuō)要好，原因是佳點(diǎn)集的均勻思想使得解分布更均勻，很容易遍布空間的各個(gè)角落。此外，本文PGSGSO算法采取了相對(duì)更少的種群規(guī)模與迭代次數(shù)，節(jié)省了時(shí)間開(kāi)銷(xiāo)。

4 結(jié) 語(yǔ)

GSO算法在多模態(tài)函數(shù)優(yōu)化中存在自身優(yōu)勢(shì)，但受到種群生成方式的隨機(jī)性和往往需要大規(guī)模的螢火蟲(chóng)種群才能得到較為滿意的尋優(yōu)結(jié)果這兩方面的制約，從而導(dǎo)致算法穩(wěn)定性能差、收斂速度慢、尋優(yōu)精度不高、時(shí)間花費(fèi)久。本文在GSO算法基礎(chǔ)上進(jìn)行改進(jìn)，提出一種針對(duì)多模態(tài)函數(shù)的聚類(lèi)后再創(chuàng)種群的PGSGSO算法，并通過(guò)實(shí)驗(yàn)驗(yàn)證該算法的有效性。與相關(guān)文獻(xiàn)所提的改進(jìn)方法相比，總體上來(lái)說(shuō)，PGSGSO算法使用更少的迭代次數(shù)，更少的種群規(guī)模即可達(dá)到更好的效果。但本文所有測(cè)試函數(shù)均為二維空間中的多模態(tài)函數(shù)，因此下一步將運(yùn)用PGSGSO算法對(duì)高維空間的多模態(tài)函數(shù)進(jìn)行研究。

[1] KENNEDY J. Stereotyping: improving particle swarm performance with cluster analysis[C]// Congress on Evolutionary Computation. IEEE,2000:1507-1512.

[2] SHELOKAR P S, SIARRY P, JAYARAMAN V K, et al. Particle swarm and ant colony algorithms hybridized for improved continuous optimization[J]. Applied Mathematics & Computation,2007,188(1):129-142.

[3] AGRAWAL S, SILAKARI S. FRPSO: Fletcher-Reeves based particle swarm optimization for multimodal function optimization[J]. Soft Computing,2014,18(11):2227-2243.

[4] FAN L, LIU X Y, JIA L P. A minimum-elimination-escape function method for multimodal optimization problems[C]//Tenth International Conference on Computational Intelligence and Security. IEEE,2014:312-316.

[5] ZHOU Z, XIE Y, PHAM D T, et al. Bees Algorithm for multimodal function optimisation[J]. Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science,2015,203-210(3):1989-1996.

[6] ZHANG Y L, MA X P, GU Y, et al. A modified glowworm swarm optimization for multimodal functions[C]// Control and Decision Conference. IEEE,2011:2070-2075.

[7] ZHOU Y Q, ZHOU G, ZHANG J L. A hybrid glowworm swarm optimization algorithm to solve constrained multimodal functions optimization[J]. Optimization,2015,64(4):1-24.

[8] 李敬明,倪志偉,許瑩,等.基于二進(jìn)制螢火蟲(chóng)算法的屬性選擇方法研究[J].系統(tǒng)科學(xué)與數(shù)學(xué),2017(2):407-424.

[9] 祝華正,何登旭.一種小規(guī)模多種群螢火蟲(chóng)群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(23):48-50.

[10] KRISHNANAND K N, GHOSE D. Detection of multiple source locations using a glowworm metaphor with applications to collective robotics[C]// Swarm Intelligence Symposium, 2005. Sis 2005. Proceedings. IEEE,2005:84-91.

[11] KRISHNANAND K N, GHOSE D. Multimodal Function Optimization using a Glowworm Metaphor with Applications to Collective Robotics[C]// Indian International Conference on Artificial Intelligence, Pune, India, December. DBLP,2005:328-346.

[12] 黃正新,周永權(quán).自適應(yīng)步長(zhǎng)螢火蟲(chóng)群多模態(tài)函數(shù)優(yōu)化算法[J].計(jì)算機(jī)科學(xué),2011,38(7):220-224.

[13] ALJARAH I, LUDWIG S A. A MapReduce based glowworm swarm optimization approach for multimodal functions[C]// Swarm Intelligence. IEEE,2013:22-31.

[14] ZHOU Y Q, ZHOU G, ZHANG J. A hybrid glowworm swarm optimization algorithm for constrained engineering design problems[J]. Applied Mathematics & Information Sciences,2013,7(1):379-388.

[15] JAYAKUMAR D N, VENKATESH P. Glowworm swarm optimization algorithm with topsis for solving multiple objective environmental economic dispatch problem[J]. Applied Soft Computing,2014,23(5):375-386.

[16] LUDWIG S A. Improved glowworm swarm optimization algorithm applied to multi-level thresholding[C]// Evolutionary Computation. IEEE,2016:1533-1540.

[17] 華羅庚,王元.數(shù)論在近似分析中的應(yīng)用[M].北京:科學(xué)出版社,1978:83-86.

[18] 張鈸,張鈴.佳點(diǎn)集遺傳算法[J].計(jì)算機(jī)學(xué)報(bào),2001,24(9):917-922.

[19] 張軍麗,周永權(quán).一種用Powell方法局部?jī)?yōu)化的人工螢火蟲(chóng)算法[J].模式識(shí)別與人工智能,2011,24(5):680-684.

[20] CHENG S, SHI Y H, QIN Q D, et al. Population diversity maintenance in brain storm optimization algorithm[J]. Journal of Artificial Intelligence & Soft Computing Research,2015,4(2):83-97.

[21] 謝健,周永權(quán),陳歡.一種基于Lévy飛行軌跡的蝙蝠算法[J].模式識(shí)別與人工智能,2013,26(9):829-837.

[22] TUO S H, ZHANG J Y, YONG L Q, et al. A harmony search algorithm for high-dimensional multimodal optimization problems[J]. Digital Signal Processing,2015,46(C):151-163.

[23] AHRARI A, ATAI A A. Grenade explosion method-a novel tool for optimization of multimodal functions[J]. Applied Soft Computing,2010,10(4):1132-1140.

AParallelSearchGood-PointSetGlowwormSwarmOptimizationofRe-createdPopulationafterClusteringofMulti-ModalFunctions

FANGXian1，TIEZhixin1，LIJingming2，GAOXiong1

(1.School of Information Science and Technology, Zhejiang Sci-Tech University, Hangzhou 310018, China;2.School of Management, Hefei University of Technology, Hefei 230009, China)

In the event that the glowworm swarm optimization algorithm is used to solve multi-modal function, a larger population size is usually needed to obtain an ideal result as the number of peak values increases. In addition, the uniform distribution of the initial population also has a great influence on the results. In view of this, a parallel search good-point set glowworm swarm optimization based on re-created population after clustering of multi-modal functions (PGSGSO) is proposed in this paper. Firstly, the glowworms are evenly distributed in the search space based on the good-point set theory, and the function peaks are captured with density-based clustering algorithm after rough search is finished, to recreate parallel spaces with the same number of peak values; a small amount of glowworms are added into the spaces for fine search to obtain the locally optimal solution of the parallel spaces and the globally optimal solution of the whole space. The comparison with the test results of other algorithms in 12 typical multi-modal functions show that the proposed algorithm is superior in respect of population size, convergence speed, searching precision, time cost and stability.

glowworm swarm optimization; multi-modal function; good-point set; density clustering algorithm; parallel search

10.3969/j.issn.1673-3851.2017.11.015

2017-06-14 網(wǎng)絡(luò)出版日期： 2017-10-10

國(guó)家自然科學(xué)基金項(xiàng)目(61170110)；浙江省公益技術(shù)應(yīng)用研究項(xiàng)目(2014C31G2060072)；安徽省教育廳自然科學(xué)研究重點(diǎn)項(xiàng)目(KJ2016A308)

方 賢(1994-)，男，安徽滁州人，碩士研究生，主要從事智能計(jì)算、生物信息學(xué)方面的研究。

鐵治欣，E-mail：tiezx@zstu.edu.cn

TP391.9

A

1673- 3851 (2017) 06- 0843- 08

(責(zé)任編輯：康鋒)