黃 琨

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

黃 琨1,2

（1.廣西大學計算機與電子信息學院，廣西 南寧 530004；2.廣西農業(yè)職業(yè)技術學院，廣西 南寧 530007）

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

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

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

1　問題提出

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

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

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

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

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

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

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

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

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

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

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

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

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

（5）算法停止。

4　實驗測試

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

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

實驗選取的標準測試函數(shù)有以下4個：

函數(shù)1：

函數(shù)4：

函數(shù)1、2、3來自文獻［5］，而函數(shù)4來自文獻［6］，表1是本文IMBF-PSO改進粒子群算法對這四個標準測試函數(shù)的測試結果概覽，而表2是本文算法對這4個函數(shù)的測試結果與文獻［5］中的HABC算法、文獻［6］的Non-EA算法的測試結果對比。

表1　實驗測試結果總覽

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

表2　測試結果對比

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

5　結束語

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

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

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

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

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

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

［6］ 趙新超.基于非均勻變異的進化算法對高維多峰函數(shù)的收斂性分析［J］.系統(tǒng)科學與數(shù)學，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－），男，廣西都安人，廣西大學計算機與電子信息學院在職研究生，廣西農業(yè)職業(yè)技術學院助教，研究方向為計算機科學與技術。