王曉敏,劉宏偉,李石妍

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

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

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

1 算法優(yōu)化

1.1 基本粒子群優(yōu)化算法

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

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

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

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

1.2 混沌與混沌序列

混沌是被提出用以分析對初始設(shè)置非常敏感的動態(tài)系統(tǒng)的一種理論工具。它是由Lorenz在1972年提出的?；煦缧蛄杏蟹浅Ａ己玫姆蔷€性性質(zhì),比如對初始值敏感,對可行域的遍歷等。這些性質(zhì)有利于分析和應(yīng)用于具有多極值的復(fù)雜系統(tǒng)。

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

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

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

不適當(dāng)?shù)牧Ｗ映跏挤植紩?yán)重影響PSO的搜索效率。在PSO的搜索過程中,隨著迭代的進(jìn)行,粒子的搜索范圍會不斷地變小,如圖2所示。

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

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

1.4 粒子的作用域

有限作用域是指在函數(shù)值小到一定程度（設(shè)定的閾值）的粒子所組成的區(qū)域,在此區(qū)域中,可能存在函數(shù)值大于閾值的粒子。本文對有限作用域內(nèi)的粒子以式（1）更新速度,而對有限作用域外的粒子以其自身的最優(yōu)值作為目標(biāo)進(jìn)行更新,如式（4）所示。

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

1.5 求解過程

粒子群算法的每一步都根據(jù)前一步所獲得當(dāng)前最好的點與自身尋找的最好的點進(jìn)行該步的調(diào)整。通過此方式一步一步地調(diào)整,最后把問題的最優(yōu)值找出來?；谶@樣的思想,任何一個問題,只要其作為最優(yōu)的個體與作為局部最優(yōu)的個體是具有某種特性的,那么按粒子群算法的迭代方式,最終就可以把具有某種特性的解求出來。函數(shù)的均值,是具有某種特性的點,因此,可以利用粒子群算法進(jìn)行求解。

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

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

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

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

步驟4:以混沌序列代替隨機數(shù);

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

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

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

步驟8:確定局部均值。

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

步驟9:確定整體均值。

步驟10:若滿足終止條件,則返回當(dāng)前最優(yōu)粒子;否則,k=k+1,轉(zhuǎn)到步驟3。

2 算例分析

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

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

表1 三個測試函數(shù)的實驗結(jié)果Tab.1 Experimental results of three test function

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

3 結(jié)論

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

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

[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]周書敬,薄濤,史三元.混合算法在輕鋼結(jié)構(gòu)優(yōu)化設(shè)計中的應(yīng)用[J].河北工程大學(xué)學(xué)報:自然科學(xué)版,2011,28（2）:71-74.

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

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

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

[6]張勇,鞏敦衛(wèi),張婉秋.一種基于單純形法的改進(jìn)微粒群優(yōu)化算法及其收斂性分析[J].自動化學(xué)報,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.