改進型混沌粒子群算法求解函數均值問題

王曉敏,劉宏偉,李石妍

（1.河北工程大學 機電工程學院,河北 邯鄲 056038;2.河北工程大學 文學院,河北 邯鄲 056038）

基于對鳥群捕食行為的仿生,Eberhart博士和Kennedy博士于1995年提出了粒子群優化（Particle Swarm Optimization,PSO）算法[1-2],該算法基于群體智能,是一種簡潔高效的隨機優化算法,但存在容易陷入局部最優、并且搜索精度不高的缺點。混沌是在非線性系統中普遍存在的現象,混沌運動具有對初值的高度敏感性、運動軌跡的遍歷性和隨機性等特點,它能在一定的范圍內按自身的規律遍歷每一個軌道,既不自我重復又不自我交叉。混沌算法和粒子群優化算法各有優缺點,混沌算法的全局搜索能力較強,而粒子群算法具有較強的局部搜索能力。近幾年來,很多學者把兩種算法的優點融合在一起,提出了多種混合算法:文獻[3]利用混沌運動隨機性、遍歷性和初值敏感性,提出了一種混沌粒子群優化算法并應用于多閾值圖像分割中;文獻[4]針對傳統的簡單粒子群算法易陷入局部最優的缺陷,提出了一種改進的混沌粒子群優化算法,該算法根據混沌算法遍歷性的特點,選擇合適的混沌映射提取基本粒子群初始種群,使粒子均勻分布在解空間,當基本粒子群陷入早熟時,混沌粒子群在最優解周圍的區域內進行混沌搜索,取代原來種群中的部分粒子,帶領種群跳出局部最優;文獻[5]針對基本粒子群優化算法易陷入局部極值和進化后期收斂速度緩慢的問題,提出基于Tent混沌序列的粒子群優化算法,應用Tent映射初始化均勻分布的粒群來提高初始解的質量,設定粒子群聚集程度的判定閾值,并引入局部變異機制和局部應用Tent映射重新初始化粒群的方法,增強算法跳出局部最優解的能力,有效避免計算的盲目性,從而加快算法的收斂速度。

但是融合混沌方法的混合型粒子群算法的求解精度尚不盡人意[6-7]。本文將有限作用域的機制引入到粒子群的尋優過程中,以有限作用域作為邊界,將粒子群體分成不同的兩部分:作用域內的粒子被用以提高搜索精度,作用域外的粒子被用以增加群體對可行域的開發程度。

1 算法優化

1.1 基本粒子群優化算法

在標準PSO算法中,假設在一個D維的問題空間中,包含m個粒子,每個粒子作為搜索空間中待優化問題的一個可行解,通過粒子之間的協作與競爭來尋找問題的最優解。在第 t次迭代中,第i個粒子的當前位置表示為xi（t）=（xi1（t）,xi2（t）,…xid（t））,當前速度表示為vi（t）=（vi1（t）,vi2（t）,…vid（t））。在每次迭代中,粒子個體搜索到的最佳位置用pbi（t）=（pbi1（t）,pbi2（t）,…pbid（t））表示,記作 pbest,稱為個體最優;群體中所有粒子搜索到的最佳位置用gb（t）=（gb1（t）,gb2（t）,…gbd（t））表示,記作 gbest,稱為全局最優。

優化問題的過程可看作粒子不斷更新的過程,每個粒子以當前速度、個體最優和全局最優來調整自己的飛行速度vid（t+1）和方向xid（t+1）,通過迭代n代,最終以第n代的全局最優值作為問題的解。

其中,i=1,2,…m;d=1,2,…D;r1,r2為（0,1）上的隨機數;常數c1,c2為學習因子,表示粒子受個體認知和社會認識的影響程度,調節向pbest和gbest方向飛行的最大移動步長,式（1）中的w×vid（t）部分稱為動量部分,表示粒子對當前自身運動狀態的信任程度,w稱為慣性權重（inertia weight）,使其依據自身速度進行慣性運動;c1×r1×（pbid（t）-xid（t））部分稱為個體認知（congnition）部分,代表粒子飛向自身的最佳位置;c2×r2×（gb（t）-xid（t））部分稱為社會（social）部分,表示粒子間的信息共享與相互協作,它引導粒子飛向群體中的最佳位置。這3個部分之間的相互平衡和制約決定了算法的主要搜索性能。

通常w在區間[0,1]中。不同的 c1,c2描述了粒子對可行域的開發程度,r1,r2是均勻分布在（0,1）之間的隨機數。vi在區間[vmin,vmax],當粒子的速度超過邊界時,設置其為邊界值,vmin,vmax按可行域大小進行設置。

1.2 混沌與混沌序列

混沌是被提出用以分析對初始設置非常敏感的動態系統的一種理論工具。它是由Lorenz在1972年提出的。混沌序列有非常良好的非線性性質,比如對初始值敏感,對可行域的遍歷等。這些性質有利于分析和應用于具有多極值的復雜系統。

Logistic是混沌理論中主要的映射。在確定初始值和映射參數后,序列便被確定。Logistic序列的表達式為

a=3.995,x0=0.640的Logistic序列和均勻分布的隨機數的對比分布圖如圖1所示。Logistic序列主要分布相對在[0,1/3）和（2/3,1]中。這與均勻分布的隨機函數相比,可以使粒子在初始分布時局有更大的覆蓋范圍。在粒子的速度更新過程中,更具多樣性。

1.3 初始分布對搜索過程的影響

不適當的粒子初始分布會嚴重影響PSO的搜索效率。在PSO的搜索過程中,隨著迭代的進行,粒子的搜索范圍會不斷地變小,如圖2所示。

在圖2中,4個子圖分別代表標準粒子群在搜索Rosenbrock函數時,不同迭代次數時的粒子分布。各個子圖中的不規則多邊形表示粒子群體有可能搜索到的可行域范圍,因為粒子的飛行速度在初始化過程中是隨機分布的,所以此范圍可能有擾動,但與多邊形相差不會很大。圖2中,陰影在不斷的縮小,最終聚集在最優值（1,1）點（對應于不同的測試函數,最優點不同）。這說明隨著迭代次數的增加,粒子更加注重在局部進行搜索,提高搜索精度,而基本放棄了對可行域的開發。

在每次的迭代過程中,算法均是基于如下的假定:最優點會在 Ci中,Ci為在第i次迭代過程中,包含所有粒子的最小圓,Rci為半徑,我們應用Rci來評判Ci的大小。Rci趨近于 0,既 pbest趨近于gbest,X趨近于gbest。其中存在的問題是gbest只是整個群體所搜索到的最優值。gbest也是其中一個粒子的Pbest,所以只要粒子的初始分布 C0沒包含優化問題的全局最優點,比如,當粒子的初始分布只限定在可行域的一部分,如果粒子只在一半的可行域中分布,粒子的作用域并沒有覆蓋最優值點（即最優點并不在圓中）,則PSO在搜索過程中很難再找到優化問題的全局最優點。所以在粒子群優化的改進過程中,在初始分布時,盡可能的擴大其作用域覆蓋范圍,或使在一定的迭代次數內,粒子的作用范圍不會收縮的很快,這有利于粒子對整個可行域的開發,并搜索到全局的最優解。

1.4 粒子的作用域

有限作用域是指在函數值小到一定程度（設定的閾值）的粒子所組成的區域,在此區域中,可能存在函數值大于閾值的粒子。本文對有限作用域內的粒子以式（1）更新速度,而對有限作用域外的粒子以其自身的最優值作為目標進行更新,如式（4）所示。

式（4）中,c3×r3×（pi-xi（k））代表粒子飛向自身的最好位置;c4×r4為粒子的搜索擾動,即之前的粒子在局部的隨機擾動,此項與粒子所在位置無關,只與粒子本身有關。粒子子群相當于在可行域中的隨機飛行,以廣度為目的繼續開發可行域。有限作用域是隨著迭代次數增加而不斷的減小的,這樣做的目的在于在迭代的后期,仍然存在粒子在開發可行域,而有限作用域內的粒子會更加專注于提高全局最優值的精度。

1.5 求解過程

粒子群算法的每一步都根據前一步所獲得當前最好的點與自身尋找的最好的點進行該步的調整。通過此方式一步一步地調整,最后把問題的最優值找出來。基于這樣的思想,任何一個問題,只要其作為最優的個體與作為局部最優的個體是具有某種特性的,那么按粒子群算法的迭代方式,最終就可以把具有某種特性的解求出來。函數的均值,是具有某種特性的點,因此,可以利用粒子群算法進行求解。

對于函數y=f（x）,x∈[a,b],利用粒子群算法求出其均值的關鍵是怎樣確定粒子群中的整體均值、局部均值。因為在均值未求出的情況下,很難確定哪個粒子更接近問題的均值。給出整體均值、局部均值的不同的算法將給出不同的粒子群求均值的算法。本文以最接近當前各粒子的適應度為整體均值、以一定的組合方式給出局部均值。

本文構造的利用粒子群算法求均值的基本過程如下:

步驟2:以Logistic序代替隨機數,初始化粒子群;

步驟3:更新有限作用域;

步驟4:以混沌序列代替隨機數;

步驟5:以一定的閾值把粒子分為兩類:有限作用域內的粒子集合和有限作用域外的粒子集合;

步驟6:用式（1）更新有限作用域內的粒子的速度;用式（4）更新有限作用域外的粒子的速度;

步驟7:用式（2）更新粒子的位置;

步驟8:確定局部均值。

其中rand（）是[0,1]之間的一個隨機數,比較 f（xi）,f（pid）,取其中離 qi最近的為新的f（pid）,從而得到局部均值點pid與局部均值f（pid）。

步驟9:確定整體均值。

步驟10:若滿足終止條件,則返回當前最優粒子;否則,k=k+1,轉到步驟3。

2 算例分析

為了驗證方法的有效性,分別取以下3種不同類型的函數進行測試:

算法初始種群都為100、迭代的代數都為100代;參數 ω,η1,η2分別取為:0.1,0.2,0.2;總共計算100次,每次得到一個平均值的結果,100個結果的平均值記為 af、最好值記為 of,標準差記為σ,精確值 p,結果列于表1。

表1 三個測試函數的實驗結果Tab.1 Experimental results of three test function

從以上的結果與演化曲線圖可以看出,本文方法能比較精確地求出函數在某一區間段上的平均值。這是由于本文對粒子群算法的局部極值與整體極值作出了合理的定義,使得粒子群算法能朝著函數的平均值進行運動,雖然有時會在平均值附近振蕩,但最終都能把平均值求出來。

3 結論

1）通過以混沌序列初始粒子分布,粒子以更大的概率分布靠近可行域的邊界并覆蓋最優值點,并提高粒子群體的多樣性。

2）該算法將有限作用域的機制和混沌序列引入到速度更新過程中,增加了種群多樣性,提高了粒子對可行域的開發程度。

[1]KENNEDY J,EBERHERT R.Particle swarm optimization[C/OL]//Proceedings IEEE International Conference on Neural Networks.[2011-01-22].http://ieeexplore.ieee.org/xpl/freeabs-all.jsp?arnumber=488968.

[2]周書敬,薄濤,史三元.混合算法在輕鋼結構優化設計中的應用[J].河北工程大學學報:自然科學版,2011,28（2）:71-74.

[3]蔣艷會,李峰.基于混沌粒子群算法的多閾值圖像分割[J].計算機工程與應用,2010,46（10）:175-177.

[4]劉玲,鐘偉民,錢鋒.改進的混沌粒子群優化算法[J].華東理工大學學報:自然科學版,2010,36（2）:267-272.

[5]田東平.基于Tent混沌序列的粒子群優化算法[J].計算機工程,2010,36（4）:180-183.

[6]張勇,鞏敦衛,張婉秋.一種基于單純形法的改進微粒群優化算法及其收斂性分析[J].自動化學報,2010,35（3）:289-298.

[7]CUI Z H,CAI X J,ZENG J C,et al.Apical-dominant particle swarm optimization[J].Progress in Natural Science,2011,18（2）:1577-1582.