多模態(tài)優(yōu)化粒子群算法的研究

黃 琨

多模態(tài)優(yōu)化粒子群算法的研究

黃 琨1,2

（1.廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004；2.廣西農(nóng)業(yè)職業(yè)技術(shù)學(xué)院，廣西 南寧 530007）

基本粒子群算法直接用于求解多模態(tài)函數(shù)優(yōu)化問題會(huì)存在不少問題，文章詳述了這些可能出現(xiàn)的問題并分析了引起這些問題的原因，然后針對這些不足提出2項(xiàng)改進(jìn)措施。這2項(xiàng)措施主要是為了在理論上保證找到所有極值點(diǎn)。最后通過對4個(gè)不同規(guī)模，不同特征的多模態(tài)函數(shù)進(jìn)行測試，實(shí)驗(yàn)結(jié)果證明這2項(xiàng)措施是有效的。

多模態(tài)；粒子群算法；遷徙

粒子群算法［1］最開始是J. Kennedy和R. C. Eberhart等為了圖形化、形象化的模擬鳥群似乎沒有規(guī)律、飛行軌跡難以預(yù)測的捕食昆蟲的活動(dòng)而設(shè)計(jì)的演化計(jì)算算法。由粒子群算法的位置以及速度更新原理可知［2］，該算法簡單明了，收斂迅速而且精度也高，是非線性連續(xù)問題的有效求解方法。粒子群算法常用于神經(jīng)網(wǎng)絡(luò)的訓(xùn)練，模擬簡化的大腦模型，這要求它必須快速而高效。目前運(yùn)用較多的領(lǐng)域還有計(jì)算機(jī)視覺、計(jì)算機(jī)輔助設(shè)計(jì)等等。我們在工作、學(xué)習(xí)和日常生活中碰到的許多問題都可能是多模態(tài)問題，而目前運(yùn)用粒子群算法解決多模態(tài)問題的研究并不多，粒子群算法由于本身的設(shè)計(jì)特性，在求解多模態(tài)問題時(shí)常常會(huì)遇到一些困難，比如難以找出所有極值點(diǎn)。本文將會(huì)對這些問題進(jìn)行分析，并提出一些改進(jìn)措施，最后通過實(shí)驗(yàn)測試驗(yàn)證措施的有效性。

1　問題提出

筆者從公式（1）和（2）可以看出，粒子位置的更新變化會(huì)受到粒子自己曾經(jīng)發(fā)現(xiàn)的最佳位置和所有粒子曾經(jīng)發(fā)現(xiàn)的最佳位置的影響，至于受影響的程度，跟學(xué)習(xí)因子C1和C2有關(guān)，除此之外還與權(quán)重因子、加速度有關(guān)。如果一個(gè)粒子的適應(yīng)度是以粒子的函數(shù)值作為直接或者間接的參考的話，那么我們推測，在多峰尋優(yōu)問題中，采用這種適應(yīng)度評價(jià)策略的粒子群算法極有可能無法符合多峰尋優(yōu)的要求，無法發(fā)現(xiàn)所有的極值點(diǎn)，容易陷入局部極值區(qū)域而無法跳出。經(jīng)過對多個(gè)不同特性的多峰函數(shù)的測試，筆者發(fā)現(xiàn)這一猜想是正確的。針對這一問題，在保證粒子群算法執(zhí)行原理不變的情況下，筆者需要找到一種新的適應(yīng)度評價(jià)策略。

粒子算法在執(zhí)行時(shí)，除了粒子本身會(huì)記錄一個(gè)自身曾經(jīng)發(fā)現(xiàn)的最佳位置之外，算法本身也會(huì)記錄一個(gè)所有粒子所發(fā)現(xiàn)的最佳位置。對于多峰函數(shù)極值點(diǎn)存在多個(gè)的情況，采用基本粒子群算法的只記錄當(dāng)前最佳位置的方法行不通，我們需要尋求新的解決方案。

2　多峰函數(shù)優(yōu)化的改進(jìn)思想

對于不同的多峰尋優(yōu)問題， 其極值點(diǎn)可能有多個(gè)，并且對應(yīng)的目標(biāo)函數(shù)值有可能是不同的。本文研究如何利用粒子群算法找到規(guī)定區(qū)域內(nèi)的某種極值，比如要么找的是峰值，要么找谷值。有些多峰函數(shù)的一些點(diǎn)，盡管同是極值，但是其函數(shù)值有可能是不同的，當(dāng)存在某個(gè)極值點(diǎn)比別的極值點(diǎn)的函數(shù)值都大或者都小時(shí)，粒子在搜索時(shí)極可能都朝這個(gè)點(diǎn)移動(dòng)，這會(huì)導(dǎo)致算法無法找到別的極值點(diǎn)。針對多峰函數(shù)的多極值以及極值點(diǎn)的特征［3］，只需要判別哪些是極值點(diǎn)，哪些是非極值點(diǎn)，只要是極值點(diǎn)，都是最佳的位置點(diǎn)。本文改進(jìn)粒子群算法的適應(yīng)度評估策略參考了文獻(xiàn)［4］中遺傳算法適應(yīng)度值的設(shè)計(jì)思想，并針對粒子群算法做了相應(yīng)改進(jìn)，其設(shè)計(jì)思想是：

筆者假設(shè)粒子的位置坐標(biāo)是X=（x1，x2，…，xm），這是一個(gè)m維坐標(biāo)。筆者用F（x）表示多峰函數(shù)某個(gè)位置對應(yīng)的函數(shù)值。由數(shù)學(xué)知識，知道極值點(diǎn)出現(xiàn)在函數(shù)的駐點(diǎn)，駐點(diǎn)是導(dǎo)數(shù)為零的點(diǎn)，駐點(diǎn)有一個(gè)特征，那就是它對應(yīng)的函數(shù)值要比它周邊鄰域的點(diǎn)的函數(shù)值都要大或者都要小，比周邊鄰域更大的點(diǎn)，稱它為峰點(diǎn)，反之，則稱為谷點(diǎn)。

由數(shù)學(xué)中偏導(dǎo)數(shù)Fitnessi的理論知識，駐點(diǎn)的偏導(dǎo)數(shù)是0，而且越是鄰近駐點(diǎn)的點(diǎn)，其各個(gè)自變量的偏導(dǎo)數(shù)越趨于0，那么公式（4）中，F(xiàn)itnessi的值越趨于1，而離駐點(diǎn)遠(yuǎn)的點(diǎn)，其偏導(dǎo)數(shù)的絕對值通常都比較大，F(xiàn)itnessi也就會(huì)比較小。由于我們設(shè)置了一個(gè)隨機(jī)因子，這個(gè)因子能放大靠近駐點(diǎn)的點(diǎn)之間的差異。這種適應(yīng)度評價(jià)方法忽視了不同極值點(diǎn)之間的函數(shù)差異，對所有極值點(diǎn)一視同仁，這在理論上為粒子群算法找出所有極值點(diǎn)提供了保證。

在上文介紹的粒子群算法基本原理中，粒子更新位置受粒子自己發(fā)現(xiàn)的sj，i（t）和群體中的gj，i（t）的影響。在多峰尋優(yōu)問題中，極值點(diǎn)有多個(gè)，那么需要處理好gj，i（t）與多個(gè)極值點(diǎn)之間的關(guān)系。根據(jù)基本粒子群的原理，gj，i（t）只有一個(gè)，而多峰尋優(yōu)問題則存在多個(gè)最優(yōu)值的問題。對于這個(gè)問題，本文的處理策略是將尋找到的符合一定條件的不同優(yōu)良粒子通過一個(gè)庫存儲(chǔ)這些粒子的相關(guān)信息，也就是說gj，i（t）可能不是一個(gè)粒子，而可能是多個(gè)。在參考gj，i（t）執(zhí)行于粒子位置更新時(shí)，我們隨機(jī)抽取一個(gè)新粒子執(zhí)行更新，粒子更新后，如果發(fā)現(xiàn)同屬一個(gè)坡或者一個(gè)谷的粒子更加優(yōu)越時(shí)，則替換自身，接著才與整個(gè)群體優(yōu)良庫中的粒子執(zhí)行比較替換，其原則依舊是同坡、同谷更優(yōu)秀的則替換，否則不做修改。2個(gè)粒子是否同峰、同谷，主要依據(jù)粒子間的歐氏距離判定。

3　改進(jìn)粒子群算法執(zhí)行流程

本文從2個(gè)方面對粒子群算法進(jìn)行了改進(jìn)，改進(jìn)的粒子群算法執(zhí)行流程有5點(diǎn)內(nèi)容，其具體內(nèi)容的描述如下：

（1）算法參數(shù)的設(shè)置：粒子數(shù)目SIZE，算法迭代停止次數(shù)Tmax，這與所研究問題的搜索空間大小有關(guān)；學(xué)習(xí)因子C1和C2、慣性權(quán)重因子W以及位置更新的加速度V的取值范圍。由于在具體的算法實(shí)現(xiàn)上，優(yōu)良粒子群體空間是自動(dòng)增長的，這里無需設(shè)置。

（2）初始化：根據(jù)第1步中設(shè)置后的參數(shù)建立粒子，通常就是指點(diǎn)的位置坐標(biāo)，并評價(jià)粒子的適應(yīng)度，然后進(jìn)行對比記錄sj，i（t）和gj，i（t）。

（3）粒子位置的更新：參考公式（6）、（7），根據(jù)粒子數(shù)目循環(huán)執(zhí)行，如果更新后的粒子同屬一個(gè)峰、或者一個(gè)谷而且更加優(yōu)越，則替換自身，并與優(yōu)良庫中的粒子執(zhí)行相似的比較。如果找到的粒子是不同峰或者不同谷的，則不對自身修改，而直接與優(yōu)良庫粒子執(zhí)行比較，如果是同峰或者同谷，如果比庫中的粒子更加優(yōu)秀，則替換。如果不同峰或者不同谷，達(dá)到了記錄要求，則將它加入庫中，否則不作修改。

（4）判斷：如果達(dá)到最大迭代次數(shù)Tmax，則停止算法的執(zhí)行，否則返回從第3步驟重復(fù)執(zhí)行。

（5）算法停止。

4　實(shí)驗(yàn)測試

算法的軟件運(yùn)行環(huán)境是matlab 2014a，硬件運(yùn)行環(huán)境是：Intel i5-4210U處理器、8GB內(nèi)存。

本節(jié)選取4個(gè)特征各異、尋優(yōu)難易程度各不相同的多峰值函數(shù)進(jìn)行算法性能的測試，主要檢驗(yàn)算法的2個(gè)指標(biāo)。（1）可否發(fā)現(xiàn)全部的極值點(diǎn)。極值點(diǎn)有峰值點(diǎn)和谷值點(diǎn)兩種類型，考慮到函數(shù)尋優(yōu)往往是求極小值，或者極大值，因此，在某一次的實(shí)驗(yàn)中，筆者只尋找極大值，或者極小值。（2）算法的可行、穩(wěn)定性。通過多次實(shí)驗(yàn)，觀察是不是每次實(shí)驗(yàn)都能找到所有極值點(diǎn)。這4個(gè)函數(shù)的實(shí)驗(yàn)參數(shù)設(shè)置是粒子數(shù)量SIZE=20，迭代搜索次數(shù)Tmax= 2000，學(xué)習(xí)因子C1、C2隨機(jī)取值于［0，2］之間，慣性權(quán)重因子W隨機(jī)取值于［0，1］之間，而加速度V的取值范圍與一致。

實(shí)驗(yàn)選取的標(biāo)準(zhǔn)測試函數(shù)有以下4個(gè)：

函數(shù)1：

函數(shù)4：

函數(shù)1、2、3來自文獻(xiàn)［5］，而函數(shù)4來自文獻(xiàn)［6］，表1是本文IMBF-PSO改進(jìn)粒子群算法對這四個(gè)標(biāo)準(zhǔn)測試函數(shù)的測試結(jié)果概覽，而表2是本文算法對這4個(gè)函數(shù)的測試結(jié)果與文獻(xiàn)［5］中的HABC算法、文獻(xiàn)［6］的Non-EA算法的測試結(jié)果對比。

表1　實(shí)驗(yàn)測試結(jié)果總覽

由表1可以看出，在維度都是30維的情況下，算法均能在指定搜索次數(shù)內(nèi)找到所有指定精度的極值點(diǎn)，而搜索時(shí)間也相對較少，當(dāng)然了，時(shí)間運(yùn)行時(shí)間除了與算法本身有關(guān)之外，還與電腦的軟硬件條件有關(guān)，這里僅做參考。

表2　測試結(jié)果對比

由表2的實(shí)驗(yàn)結(jié)果來看，除了函數(shù)2在精度上比起文獻(xiàn)［5］的HABC算法略有不及之外，其余3個(gè)函數(shù)測試結(jié)果在穩(wěn)定性、精度都要稍微好一些。綜合上述實(shí)驗(yàn)測試結(jié)果分析，表明本文算法具有比較好的穩(wěn)定性以及尋優(yōu)精度，改進(jìn)措施能夠使算法達(dá)到多模態(tài)函數(shù)的優(yōu)化要求。

5　結(jié)束語

從論文對4個(gè)特征不同的多峰函數(shù)的測試結(jié)果來看，本文改進(jìn)了的粒子群算法在保持基本粒子群算法實(shí)現(xiàn)簡單、搜索收斂速度快，數(shù)值精度高的優(yōu)點(diǎn)之外，還克服了基本粒子群算法運(yùn)用于求解多模態(tài)問題時(shí)存在的無法找到多個(gè)極值的困難。這4個(gè)多峰函數(shù)均能在較高維數(shù)的情況下，找到所有極值。當(dāng)函數(shù)的維度逐步增高時(shí)，IMBF-PSO算法的搜索成功率可能會(huì)隨著尋優(yōu)函數(shù)極值點(diǎn)數(shù)量的增多和維度升高而下降，說明算法仍有一定的不足，需要進(jìn)一步的改進(jìn)。

［1］ 胡旺，李志蜀.一種更簡化而高效的粒子群優(yōu)化算法［J］.軟件學(xué)報(bào)，2007，18（4）：861-868.

［2］ 付榮，居鶴華.基于粒子群優(yōu)化的時(shí)間最優(yōu)機(jī)械臂軌跡規(guī)劃算法［J］.信息與控制，2011，40（6）：802-808.

［3］ 胡旺，李志蜀.一種更簡化而高效的粒子群優(yōu)化算法［J］.軟件學(xué)報(bào)，2007，18（4）：861-868.

［4］ 劉洪杰，王秀峰.多峰搜索的自適應(yīng)遺傳算法［J］.控制理論與應(yīng)用，2004，4（21）：303-310.

［5］ 林志毅，王玲玲.求解高維函數(shù)優(yōu)化問題的混合蜂群算法［J］.計(jì)算機(jī)科學(xué)，2013，3（40）：279-281.

［6］ 趙新超.基于非均勻變異的進(jìn)化算法對高維多峰函數(shù)的收斂性分析［J］.系統(tǒng)科學(xué)與數(shù)學(xué)，2010，30（2）：218-224.

The research of multimodal optimization PSO algorithm

There are some problems if basic PSO algorithm is used to solve multimodal function optimization problem directly. This article describes the possible problems and analyzes the causes， then puts forward 2 improved measures for these problems. The 2 measures are mainly to make certain to find all extreme points. Finally we take a test for four multimodal functions in different size and characteristics. The experimental results prove that the two measures are effective.

Uti-modal； PSO； migration

TP302

A

1008-1151（2016）02-0029-03

2016-01-10

黃琨（1985－），男，廣西都安人，廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院在職研究生，廣西農(nóng)業(yè)職業(yè)技術(shù)學(xué)院助教，研究方向?yàn)橛?jì)算機(jī)科學(xué)與技術(shù)。