一種有效的多峰函數優化算法

收稿日期：2007-11-20；修回日期：2008-06-30

基金項目：國家“十五”科技攻關課題資助項目（2001BA605A09）

作者簡介：李莉（1971-），遼寧沈陽人，博士研究生，主要研究方向為群智能、粒子群優化算法、數據挖掘(uplily@hotmail.com)；李洪奇(1960-)，男，遼寧昌圖人，教授，博導，主要研究方向為智能信息處理、資源軟件工程等；謝紹龍（1985-），男，碩士研究生，主要研究方向為地球信息處理與評價、粒子群優化算法*

（中國石油大學 a.計算機科學與技術系; b.資源信息學院，北京 102249)

摘 要：針對小生境粒子群優化技術中小生境半徑等參數選取問題，提出了一種新穎的小生境方法，無須小生境半徑等任何參數。通過監視粒子正切函數值的變化，判斷各個粒子是否屬于同一座山峰，使其追蹤所在山峰的最優粒子飛行，進而搜索到每一座山峰極值。算法實現簡單，不僅克服了小生境使用中需要參數的弊端，而且解決了粒子群算法只能找到一個解的不足。最后通過對多峰值函數的仿真實驗，驗證了算法可以準確地找到所有山峰。

關鍵詞：粒子群算法；多峰值函數；小生境技術；Sobol序列

中圖分類號：TP18

文獻標志碼：A

文章編號：1001-3695(2008)10-2973-04

Effective optimization algorithm for multimodal functions

LI Lia， LI Hong-qia， XIE Shao-longb

(a. Dept. of Computer Science Technology， b. School of Resource Information， China University of Petroleum， Beijing 102249， China)

Abstract:This paper proposed a novel niche technique to solve the problem of parameters’ selection. Any parameters were unnecessary in this method. Through monitoring the changes of tangent value， particles were judged whether there were in the same hill and they would follow the best particle which was in the same hill with them. Each local best solution could be found in this way. The algorithm is easy to realize. So it not only can conquer the shortcoming the limitation of parameters but also only one solution can be found in particle swarm optimization algorithm. The typical numerical simulation results show that the improved algorithm is fairly effective.

Key words：particle swarm optimization(PSO); multimodal functions; niching technique; Sobol sequence

0 引言

多峰值函數的優化問題在實踐中大量存在，是函數優化問題的一個重要方面。例如神經元的結構及權重優化、模糊系統結構和參數優化等，歸根到底都是多峰值函數的優化問題。多峰值函數有多個極值點，使得尋優極易陷入到局部區域中。因此研究快速有效的優化算法具有重要意義。粒子群算法[1，2](PSO)是一種模擬鳥群覓食行為而設計的群智能優化算法，由于其實現簡單易于理解，得到了廣泛的應用。然而，標準PSO（standard PSO，SPSO）算法只能找到一個極值點，對于多峰值函數優化問題，SPSO算法顯得無能為力。小生境方法[3]可以有效地維持種群多樣性，是解決多峰值函數優化的有力工具。但是小生境方法中參數半徑選取不當，將極大影響小生境方法使用的效果。因此本文提出了一種新穎的粒子群（novel PSO，NPSO）算法，可以精確地定位所有的山峰極值，從而找到全局最優解。NPSO不僅克服了傳統小生境算法中參數選擇的問題，而且克服了SPSO只能找到一個極值點的不足。

1 SPSO算法的實現原理

標準粒子群優化（SPSO）算法通過粒子群中個體的合作與競爭來實現優化問題的求解。種群中的每個個體稱做粒子，每個粒子代表待優化問題的一個可能解。

SPSO算法首先初始化一群隨機粒子（初始解），然后進化（迭代）找到最優解。每個粒子通過跟蹤兩個極值來更新自己，一個極值是粒子本身找到的最優解，這個位置被稱為個體極值；另一個極值是鄰居粒子所找到的最優位置，通常被稱為gbest。SPSO算法的數學描述如下：

設在一個n維的搜索空間中，由m個粒子組成的種群X={x1，x2，…，xm}。其中：第i個粒子位置為xi={xi1，xi2，…，xin}T，速度為vi={vi1，vi2，…，vin}T。該粒子迄今為止搜索到的最好位置，記為pi={pi1，pi2，…，pin}T，其所在鄰域內的所有粒子迄今為止搜索到的最好位置為pg={pg1，pg2，…，pgn}T，粒子i的速度和位置更新公式分別為vt+1id=ωvtid+c1R1(ptid-xtid)+c2R2(ptgd-xtid)(1)

xt+1id=xtid+vt+1id(2)其中：d=1，2，…，n，i=1，2，…，m（n為搜索空間維數，即待優化的變量個數；m為種群規模）；t為當前進化代數；c1、c2表示正的加速常數（acceleration constants）；R1、R2表示[0，1]之間的均勻分布隨機數;ω為慣性權重，它決定了粒子先前速度對當前速度的影響程度。

如果粒子的鄰域包含整個群體，則上述算法為全局模式的粒子群算法g-PSO；否則為局部模式的粒子群算法l-PSO。

2 小生境技術用于優化算法

生物學上，有共同特性的組織被稱為物種（species），而物種賴以生存的資源環境，稱之為小生境（niches）。小生境技術最早是由Cavicchio在1970年提出的基于預選機制[4]（preselection）的小生境實現方法。1975年DeJong一般化了Cavicchio的基于預選機制，在其博士論文中提出了基于排擠機制[5]（Crowding）的小生境實現方法，并指出這兩種方法均可在群體中形成小生境的進化環境，有效地維持群體的多樣性。1992年Mahfoud指出在實際應用中，這兩種方法并不能成功地維持種群多樣性。真實情況是這兩種方法所采用的隨機替代技術將產生大量的基因漂移，而使算法收斂于局部最優解。通過對Crowding算法的修改，Mahfoud提出了確定性排擠機制[6]（deternimistic crowding， DC）的小生境實現方法。1987年Goldberg等人提出了基于共享機制[7]（fitness sharing）的小生境實現方法（簡稱FSGA）。1993年，Beasley等人提出的sequential ni-ching[8]，其基本思想如下：找到一個峰值，然后將其削平，使得下次尋找時可以搜索到其他山峰，如此反復，直到找到所有的山峰。Yin等人[9]將MacQueen’s K-mean聚類算法引入FSGA。1996年Petrowski提出將群體內資源只提供給境內最優個體的clearing機制的小生境方法[10]。

Brits等人將小生境技術引入PSO算法中，提出小生境粒子群算法[11]（niche particle swarm optimization，NichePSO），以保持粒子群的多樣性，在多峰值函數優化問題中顯示了比較好的性能。但NichePSO算法的小生境產生依賴于參數μ和δ，分別表示判斷子群合并與產生的閾值，不同的參數會導致不同的計算結果。

綜上所述，小生境方法均需要輸入參數。其中，最重要的參數就是小生境半徑。不合適的小生境半徑將使得小生境算法的執行效果很差，而小生境半徑的選取依賴于對特定問題的一定先驗知識。因此這種應用狀況不僅影響了小生境技術的使用效果，還極大地限制了小生境技術的推廣應用。為此本文對小生境方法進行了改進，提出了一種新穎的粒子群算法（NPSO）：在程序運行中，無須嚴格界定小生境區間，既避免了參數小生境半徑的設置，無須任何先驗知識，又克服了SPSO只能找到一個解的不足。

3 NPSO的實現原理

31 NichePSO

在NichePSO算法中，如果粒子i的適應度值在連續幾代進化過程中變化很小，則以該粒子為中心，以與它最近的粒子之間的距離為半徑的拓撲領域內的粒子形成了一個小生境粒子群。具體算法如下：

a)初始化主粒子群。

b)主粒子群以l-PSO方式更新。

c)更新主粒子群中每個粒子的適應度值。

d)對每個小生境子粒子群，執行:子粒子群以GCPSO[12]方式進化一代；更新子粒子群中每個粒子的適應度值；更新小生境半徑。

e)如果符合合并條件，合并小生境。

f)將進入小生境半徑范圍的粒子從主粒子群中吸收進小生境子粒子群。

g)搜尋主粒子群中的成熟粒子并以此粒子為中心產生新的小生境子粒子群。

h)重復b)，直到滿足算法停止條件。

NichePSO算法實現過程需要輸入參數μ和δ。μ是判斷子群合并的閾值，即當兩個子群的距離小于μ時，合并這兩個子群；δ是子群產生的閾值。因此算法的實現效果依賴于參數μ和δ的選擇。不同的參數會導致不同的計算結果。

32 NPSO的實現思想

在SPSO中，所有粒子追隨當前所發現的最優粒子飛行，雖然加快了算法收斂的速度，但同時降低了種群的多樣性，導致算法出現早熟收斂；此外，如果當前的這個最優解位于局部極值區域中，則算法極易陷入局部極值。尤其是在多峰值優化問題中，不同山峰的粒子相互影響而無法找到全局最佳值，如圖1(a)所示，A、B、C點追隨當前的最優粒子D飛行，極有可能陷入到局部極值中，最終導致尋優失敗。在多峰值優化問題中，如果可以找到所有可能的山峰，并將其鎖定為一個個獨立的小生境環境，使得位于小生境中的粒子追隨所在山峰的最優粒子飛行，那么就可以避免受到其他山峰粒子的干擾，找到所在山峰的峰值，最后從所有的極值中挑選出全局最優解。因此，利用小生境技術將搜索空間分割成一個個獨立的小生境區間，不僅可以有效地維持種群的多樣性，還可以避免處于不同山峰上的粒子在飛行時的相互干擾，因此小生境技術是解決多峰值函數優化問題的一個有力工具。但小生境方法很強地依賴于小生境半徑的選擇，不合適的小生境半徑會使小生境應用效果很差。在尋優過程中，如果可以判斷兩個點是否位于同一個山峰，那么就可以避免小生境半徑的選擇。為此本文設計了Same_hill函數判斷兩個點是否位于同一座山峰。具體做法如下：在兩點A、B兩點間任意插入n個點，考察這n個點的正切函數值tan α=Δy/Δx，如果tan α的值出現由負變正，則意味著在這兩點之間有波谷存在，那么A、B應該位于不同的山峰，函數返回1，否則返回0。例如在圖1中考察A、D兩點，在A、D間任意插入n個點，與A點位于同一側山峰的點的正切函數值小于零，與D點同側的點的正切函數值大于零，即A、D兩點之間的正切函數值發生了由負變正的變化，意味著在這兩點之間有山谷存在，那么A、D兩點分別屬于不同的山峰。這個判斷條件不僅適應于一元函數，對于多元函數仍然適用。因此本方法具有很好的通用性。

Same_hill函數的偽碼如圖1（b）所示。

33 INPSO的具體實現

INPSO的實現過程如下所示：

a)均勻初始化整個粒子群，使粒子均勻遍布整個搜索空間。

b)對整個種群按照適應度好壞降序排序。

c)調用Same_hill函數，標志每個小生境，以及每個小生境到目前為止所發現的最好個體g[i]，i是小生境標號，表示所發現的第i個山峰；將每個粒子分配到相應的小生境中。

d)在每個小生境中，讓粒子追隨所在小生境的最優粒子g[i]飛行，速度按照式（3）進行更新：vi+1id=ωvtid+c1R1(g[i]-xtid)（3）

e)計算更新后的粒子適應度值。

f)判斷每一個新產生的粒子與g[i]是否屬于同一座山峰，是則說明新粒子屬于g[i]所在的山峰，并進一步判斷新粒子是否優于所在小生境的最佳個體g[i]，是則用新粒子更新g[i]，否則g[i]保持不變。

g)判斷是否滿足終止條件，若不滿足，轉d);否則輸出結果，程序結束。

步驟a)實現了粒子的初始化。為了沒有遺漏的搜索到所有山峰，初始粒子一定要均勻遍布整個搜索空間。因此本文采用了Sobol序列[13]產生初始粒子，使粒子遍布整個搜索空間，保證在每一座山峰都有粒子分布。

粒子飛行后，有可能會飛出原來的山峰（小生境區間），這樣其個體極值信息對新的小生境區間沒有任何意義，所以速度更新公式中除掉了個體認知部分，即粒子本身到目前為止所發現的最好位置；此外，為避免粒子在飛行時受到不同山峰的影響，將速度更新公式中的全局極值修改為所在山峰的最好極值g[i]，使得粒子追隨所在山峰的最優粒子，保證算法搜索到所在山峰的極值。因此在d)中，粒子的速度更新公式如式（3）所示。

4 實例驗證

為驗證算法，本文作了下面兩組測試實驗，實驗目的分別是：a）測試算法是否可以搜尋到多峰函數的所有山峰；b）全局最優解的精度。

測試中，參數設置如下：插入點n=100，最大進化代數取50次，慣性權值為ω=0729，加速常數為c1=1494 45。為驗證算法的準確性，取30次獨立實驗的平均值作為最后的實驗結果。

41 測試一

為驗證算法是否可以搜尋到所有山峰，本文選用下面幾個經典函數進行了測試：

a)f1(x)=x sin(10πx)+20，x∈(-1，2)。函數具有17個局部極大值，這些山峰間隔相等，但高度不等，全局最大值[14]為f(1.850 549)=3.850 274。

b)f2(x)=∑5i=1i cos[(i+1)x+i]。其中:x∈(-10，10)函數具有19個局部極大值，當x=-7.083 5，-0.800 3，5.482 9時，函數有3個全局最大值：14.508 008。

c)f3(x，y)=x²+y²-cos(18x)-cos(18y)。 其中:x∈(-1，1)函數有50個局部極小值，全局最小值為f(0，0)=-2。這個函數的山峰非常密集，全局最優解很難尋找。

測試中，函數f1與f2的初始種群規模為100，函數f3的初始種群規模為2 000，其他測試參數如上面所述。圖2~7給出了三個測試函數進化到不同代數時的粒子分布圖。

圖2~5中，星星表示粒子，圓點表示到目前為止粒子找到的所在山峰的最佳值。函數1的運行結果如圖2、3所示。圖2是初始化粒子的分布圖，從圖中可以看到，利用Sobol序列產生初始化粒子可以使粒子均勻分布整個空間，遍布每一座山峰，這樣才有可能沒有遺漏地搜尋到每一座山峰。圖3是函數1進化到50代時粒子的分布圖：基本上所有的粒子都爬到了峰頂。采用本文提出的算法，將粒子劃分在不同的山峰上，粒子追隨所在山峰的最優粒子飛行，避免不同山峰的粒子相互影響，找到每一座山峰的極值。

圖4~7分別是函數2與函數3的運行效果。從二維函數的運行結果圖6、7可以看出，本算法也取得了很好的效果。因此，本算法對多元函數仍然適用。

42 測試二

為檢驗算法精度，本文選用下列四個函數，并將本文所得的測試結果與NichePSO[12]方法的測試結果進行了對比。f4(x)=sin6(5πx)，x∈[0，1]

f5(x)=(e-2long(2)×(（x-0.1）/0.8)²)sin6(5πx)，x∈[0，1]

f6(x)=sin6(5π(x3/4-0.05))，x∈[0，1]

f7(x)=(e-2long(2)×(（x-0.08）/0.854)²)sin6(5π(x3/4-0.05))，x∈[0，1]

函數F4~F7的性質如表1所示。表中第一列給出了函數名稱，第二列local表示局部極值的個數，第三列global表示全局極值的個數，第四列best solution表示全局最優解。

表1 函數F4~F7的性質functionlocalglobalbest solutionfunctionlocalglobalbest solutionF4051.00F6051.00F54１1.00F7411.00

測試中，種群規模為20，其他參數如前面所述。表2記錄了本文算法NPSO與NichePSO的對比結果。全局最優解一欄給出了NPSO計算的全局最優解；偏離度給出了兩種算法最優解偏離標準值的大小，均采用標準方差計算；收斂率描述了兩種算法收斂到全局最優解的程度。從結果可以看到，NPSO的收斂率達到了100%，而NichePSO中，F5與F7的收斂率只有93%，此外，NPSO的偏離度比NichePSO小得多。

表2 函數F4~F7的測試結果函數全局最優解偏離度NPSONichePSO收斂率/%NPSONichePSOF41.000 0004.47E-092.20E-04 100100F51.000 0001.73E-076.43E-0210093F61.000 0006.08E-084.86E-05100100F71.000 0003.81E-086.68E-02100935 結束語

多峰值函數優化問題中，多峰值導致算法易陷入到局部極值。PSO算法只能找到一個解，因此PSO算法求解多峰值函數問題是人們關注的難題。小生境技術雖然是解決多峰值函數的有力工具，但小生境半徑等參數極大地限制了小生境技術的使用效果。為此，本文提出了一種新穎的方法，無須嚴格地界定小生境區間，而通過判斷兩個點是否屬于同一座山峰，克服小生境技術使用中需要小生境半徑的缺點。在進化過程中，使粒子追蹤所在山峰的最優粒子飛行，找到多峰函數的所有極值，克服了PSO算法只能找到一個解的缺點。通過仿真實驗，驗證了算法的高效有效性。

參考文獻：

[1]KENNEDY J， EBERHART R C. Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks. New York:IEEE， 1995:1942-1948.

[2]SHI Y， EBERHART R C. A modified particle swarm optimizer[C]//Proc of IEEE International Conference on Evolutionary Computation. Piscataway: IEEE， 1998: 67-73.

[3]MAHFOUD S W. Niching methods for genetic algorithms[D]. [S.l.]: Illinois Genetic Al-gorithm Laboratory， University of Illinois at

Urbana-Champaign，1995.

[4]CAVICCHIO D J. Adaptive search using simulated evolution [D]. Michigan， Arbor Illinois: University of Michigan， 1970.

[5]DeJONG K A. An analysis of the behavior of a class of genetic adaptive systems [D]. Michigan: University of Michigan，1975.

[6]MAHFOUD S W. Crowding and preselection revisited[M]//MANNER R， MANDERICK B. Parallel problem solving from nature. North-Holland: Elsevier， 1992:27-36.

[7]GOLDBERG D E，RICHARDSON J J. Genetic algorithms with sharing for multimodal function optimization[C]// Proc of the 2nd International Conference on Genetic Algorithms. 1987:41-49.

[8]BEASLEY D， BULL D R， MARTIN R R. A sequential niche technique for multimodal function optimization[J]. Evolutionary Computation， 1993，1(2):101-125.

[9]YIN X， GERMAY N. A fast genetic algorithm with sharing scheme using sharing scheme using cluster analysis methods in multimodal function optimization[C]//Proc of International Conference on Artificial Neural Networks and Genetic Algorithms. 1993:450-457.

[10]PETROWSKI A. A clearingprocedure as a niching method for genetic algorithms[C]//Proc of IEEE International Conference on Evolutio-nary Computation. Nagoya:[s.n.]， 1996:798-803.

[11]BRITS R， ENGELBRECHT A P，VAN DEN BERGH F. A niching particle swarm optimizer[C]// Proc of the 4th Asia-Pacific Conf on Simulated Evolution and Learning. 2002:692-696.

[12]BERGH F VAN DEN， ENGELBRECHT A P. A new locally convergent particle swarm optimizer[C]//Proc of IEEE Conference onSystem， Man and Cybernetics. 2002:96-101.

[13]PRESS W H， TEUKOLSKY S A， VETTERLING W T，et al. Nume-rical recipes in C: the art of scientific computing[M]. 2nd ed. Cambridge: Cambridge University Press， 1992.

[14]王小平，曹立明. 遺傳算法——理論、應用于軟件實現[M]. 西安：西安交通大學出版社，2002.