改進(jìn)型混沌粒子群算法求解函數(shù)均值問(wèn)題

王曉敏,劉宏偉,李石妍

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

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

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

1 算法優(yōu)化

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

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

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

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

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

1.2 混沌與混沌序列

混沌是被提出用以分析對(duì)初始設(shè)置非常敏感的動(dòng)態(tài)系統(tǒng)的一種理論工具。它是由Lorenz在1972年提出的。混沌序列有非常良好的非線(xiàn)性性質(zhì),比如對(duì)初始值敏感,對(duì)可行域的遍歷等。這些性質(zhì)有利于分析和應(yīng)用于具有多極值的復(fù)雜系統(tǒng)。

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

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

1.3 初始分布對(duì)搜索過(guò)程的影響

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

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

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

1.4 粒子的作用域

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

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

1.5 求解過(guò)程

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

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

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

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

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

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

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

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

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

步驟8:確定局部均值。

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

步驟9:確定整體均值。

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

2 算例分析

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

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

表1 三個(gè)測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果Tab.1 Experimental results of three test function

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

3 結(jié)論

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

2）該算法將有限作用域的機(jī)制和混沌序列引入到速度更新過(guò)程中,增加了種群多樣性,提高了粒子對(duì)可行域的開(kāi)發(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]周書(shū)敬,薄濤,史三元.混合算法在輕鋼結(jié)構(gòu)優(yōu)化設(shè)計(jì)中的應(yīng)用[J].河北工程大學(xué)學(xué)報(bào):自然科學(xué)版,2011,28（2）:71-74.

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

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

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

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