《智能控制理論和方法》課件第9章

第9章粒子群算法及其在智能控制中的應(yīng)用9.1引言9.2基本粒子群算法9.3粒子群算法的分析9.4幾種改進(jìn)的粒子群算法9.5粒子群算法在智能控制中的應(yīng)用

9.1引言

CraigReynolds在1986年提出一個(gè)仿真鳥(niǎo)群體飛行行為的模型Boid(bird-oid)[1]，并設(shè)定鳥(niǎo)群的飛行行為遵循以下規(guī)則:

(1)碰撞的避免，即個(gè)體應(yīng)避免和附近的同伴碰撞;

(2)速度的匹配，即個(gè)體必須同附近個(gè)體的速度保持一致;

(3)向中心聚集，即個(gè)體必須飛向鄰域的中心。該模型較成功地模擬了真實(shí)鳥(niǎo)群聚集飛行的行為。之后，Heppner在Boid模型的基礎(chǔ)上，又加入了棲息地的仿真條件，即鳥(niǎo)群的活動(dòng)范圍不會(huì)越出棲息地。這兩個(gè)鳥(niǎo)群飛行模型都只使用一些較為基本的規(guī)則(比如個(gè)體之間的速度匹配)來(lái)指導(dǎo)鳥(niǎo)個(gè)體的飛行，并沒(méi)有誰(shuí)對(duì)群體進(jìn)行集中的控制，即整個(gè)群體組織起來(lái)(鳥(niǎo)群一起飛行)，卻沒(méi)有一個(gè)組織者；整個(gè)群體中的個(gè)體被協(xié)調(diào)起來(lái)(鳥(niǎo)群集體在藍(lán)天整齊劃一、任意翱翔)，卻沒(méi)有一個(gè)協(xié)調(diào)者。實(shí)際上，這就是一種群體智能模型。進(jìn)一步的研究發(fā)現(xiàn)，鳥(niǎo)在搜尋食物的過(guò)程中，群體中每個(gè)鳥(niǎo)個(gè)體能得益于群體中所有其他成員的發(fā)現(xiàn)和先前的經(jīng)歷。當(dāng)食物地點(diǎn)不可預(yù)測(cè)，且零星分布時(shí)，這種協(xié)作帶來(lái)優(yōu)勢(shì)是非常明顯的，遠(yuǎn)遠(yuǎn)大于鳥(niǎo)個(gè)體間對(duì)食物競(jìng)爭(zhēng)帶來(lái)的劣勢(shì)。這種協(xié)作的本質(zhì)是生物群體中存在著一種社會(huì)信息共享機(jī)制，它為群體的某種目標(biāo)(如鳥(niǎo)的覓食)提供了一種優(yōu)勢(shì)。

在以上研究的基礎(chǔ)上，1995年，Kennedy和Eberhart模擬鳥(niǎo)群覓食行為，提出了一種新穎而有效的群體智能優(yōu)化算法，稱為粒子群優(yōu)化算法(PSO，ParticleSwarmOptimization)[2,3]。

9.2基本粒子群算法

9.2.1基本粒子群算法的原理

設(shè)想有這樣一個(gè)場(chǎng)景：一群鳥(niǎo)在某一個(gè)區(qū)域里隨機(jī)搜尋食物。在這個(gè)區(qū)域里，只存在一處食物源，而所有的鳥(niǎo)都不知道食物的具體位置，但是每只鳥(niǎo)知道自己當(dāng)前的位置離食物源有多遠(yuǎn)，也知道哪一只鳥(niǎo)距離食物源最近。在這樣的情況下，鳥(niǎo)群找到食物的最優(yōu)策略是什么呢?最簡(jiǎn)單有效的方法就是搜尋目前離食物源最近的那只鳥(niǎo)的周?chē)鷧^(qū)域。PSO就是從這種搜尋食物的場(chǎng)景中得到啟示，并用于解決優(yōu)化問(wèn)題。PSO的形象圖示見(jiàn)圖9.1。在PSO算法中，每個(gè)優(yōu)化問(wèn)題的潛在解都類似搜索空間中的一只鳥(niǎo)，稱其為“粒子”。粒子們追隨當(dāng)前群體中的最優(yōu)粒子，在解空間中不斷進(jìn)行搜索以尋找最優(yōu)解。PSO算法首先初始化一群隨機(jī)粒子(隨機(jī)解集)，通過(guò)不斷迭代，且在每一次迭代中，粒子通過(guò)跟蹤兩個(gè)極值來(lái)更新自己；第一個(gè)極值是粒子本身截至目前所找到的最優(yōu)解，這個(gè)解稱為個(gè)體極值pb(pbest)；另一個(gè)極值是整個(gè)粒子群迄今為止所找到的最優(yōu)解，稱為全局極值gb(gbest)，最終找到最優(yōu)解。圖9.1PSO的形象圖示9.2.2基本粒子群算法

在基本PSO算法中，首先初始化一群粒子。設(shè)有N個(gè)粒子，每個(gè)粒子定義為D維空間中的一個(gè)點(diǎn)，第i個(gè)粒子pi在D維空間中的位置記為Xi=(xi1,xi2,…,xiD),i=1,2,…,N，粒子pi的飛翔速度記為Vi，Vi=(vi1,vi2,…,viD),i=1,2,…,N。粒子pi從誕生到目前為止(第k次迭代后)，搜索到最好位置稱其為粒子pi的個(gè)體極值，表示為pbki=(pbki1,pbki2,…,pbkiD)。在整個(gè)粒子群中，某粒子是迄今為止(第k次迭代后)所有粒子搜索到的最好位置，稱其為全局極值，表示為gbk=(gbk1,gbk2,…,gbkD)，則PSO算法進(jìn)行優(yōu)化迭代中，第i個(gè)粒子pi按照下面公式來(lái)更新自己的速度和位置:(9.1)(9.2)其中，i=1,2,…,N,是粒子群體中第i個(gè)粒子pi的序號(hào)；k=1,2,…,m,為PSO算法的第k次迭代；d=1,2,…,D,為解空間的第d維；vkid表示第k次迭代后粒子pi速度的第d維分量值；xkid表示第k次迭代后粒子pi在D維空間中位置的第d維分量值；pbkid表示截至第k次迭代后，粒子pi歷史上最好位置的第d維分量值；gbkd表示截至第k次迭代后，全體粒子歷史上處于最好位置的粒子的第d維分量值；r1,r2是介于[0,1]之間的隨機(jī)數(shù)；c1,c2是學(xué)習(xí)因子，是非負(fù)常數(shù)，分別調(diào)節(jié)向PBki和GBk方向飛行的步長(zhǎng)，學(xué)習(xí)因子使粒子具有自我總結(jié)和向群體中優(yōu)秀粒子學(xué)習(xí)的能力，合適的學(xué)習(xí)因子可以加快算法的收斂且不易陷入局部最優(yōu)；xid∈[－xmaxd,xmaxd],根據(jù)實(shí)際問(wèn)題將解空間限制在一定的范圍；vid∈[－vmaxd,vmaxd],根據(jù)實(shí)際問(wèn)題將粒子的飛行速度設(shè)定在一定的范圍。

vmaxd=ρxmaxd

(9.3)

基本粒子群算法流程見(jiàn)圖9.2。圖9.2基本粒子群算法流程基本粒子群算法流程描述如下:

(1)初始化一群共N個(gè)粒子，給每個(gè)粒子隨機(jī)賦予初始位置(從初始位置開(kāi)始，不斷迭代最終可以尋找到全體粒子中最好的位置)和初始速度，并將i初始化為1，將k初始化為0;

(2)計(jì)算粒子pi的適應(yīng)度；

(3)當(dāng)粒子pi在第k(k≥1)次迭代時(shí)發(fā)現(xiàn)了一個(gè)好于它以前所經(jīng)歷的最好位置時(shí)，將此坐標(biāo)記入PBki，如果這個(gè)位置也是群體中迄今為止搜索到的最優(yōu)位置，則將此坐標(biāo)記入GBk;

(4)將PBki與粒子pi當(dāng)前位置向量之差隨機(jī)加入到下一代速度向量中，同時(shí)，將GBk與粒子pi當(dāng)前位置向量之差隨機(jī)加入到下一代速度向量中，并根據(jù)式(9.1)和式(9.2)更新粒子pi的速度和位置；

(5)粒子群中如果還有粒子的速度和位置沒(méi)有更新，則置i=i+1，轉(zhuǎn)(2),否則轉(zhuǎn)(6);

(6)檢查結(jié)束條件，如果算法達(dá)到設(shè)定的迭代次數(shù)或滿足尋優(yōu)誤差，則算法結(jié)束，否則置i=1，k=k+1，返回(2)繼續(xù)進(jìn)行搜索。

其中，(3)和(4)這兩項(xiàng)對(duì)粒子的調(diào)整，將使粒子圍繞全局最優(yōu)和個(gè)體最優(yōu)兩個(gè)極值附近展開(kāi)搜索。9.2.3帶慣性權(quán)重的粒子群算法

用公式(9.1)迭代計(jì)算vk+1id時(shí)，若僅考慮粒子先前的速度vkid，即vk+!id=vkid,d=1,2,…,D，則粒子將以當(dāng)前的速度飛行，直至達(dá)到解空間的邊界。顯然，這樣將很難找到最優(yōu)解。若僅考慮反映粒子自身到目前為止最好位置信息和整個(gè)粒子群迄今為止最好位置信息對(duì)vk+1id的影響，即那么當(dāng)粒子自身到達(dá)目前為止最好位置，且是整個(gè)粒子群迄今為止最好位置時(shí)，粒子將不再飛行，直到粒子群出現(xiàn)一個(gè)新的最好點(diǎn)代替此粒子。于是，每個(gè)粒子始終都將向它自身最好位置和群體最好位置方向飛去。此時(shí)，粒子群算法的搜索空間隨著進(jìn)化而收縮。在這種情況下，PSO算法更多地顯示其局部的搜索能力。為了改善基本PSO算法的搜索性能，我們必須在一次尋優(yōu)過(guò)程中，平衡全局搜索和局部搜索的作用。為此，我們?cè)谒俣冗M(jìn)化方程中引入慣性權(quán)重系數(shù)w，即(9.4)式中，w稱為慣性權(quán)重系數(shù)。稱式(9.2)與式(9.4)構(gòu)成的方程組為標(biāo)準(zhǔn)PSO算法(也稱其為帶慣性權(quán)重的PSO算法)?；綪SO算法是標(biāo)準(zhǔn)PSO算法中慣性權(quán)重系數(shù)w=1的特殊情況。慣性權(quán)重系數(shù)w的不同取值使粒子保持不同運(yùn)動(dòng)慣性，使其有擴(kuò)展搜索空間的趨勢(shì)，有能力探索新的區(qū)域。如果w較大，則速度vkid的影響也較大，能夠快速搜索以前所未達(dá)到的區(qū)域，整個(gè)算法的全局搜索能力加強(qiáng);若w較小，則速度vkid的影響也較小，主要在當(dāng)前解附近搜索，局部搜索能力加強(qiáng)。顯然，理想的情況是算法開(kāi)始階段應(yīng)設(shè)定較大的w取值，能夠使PSO算法在開(kāi)始時(shí)探索較大的區(qū)域，較快地定位最優(yōu)解的大致位置，隨后逐漸減小w取值，使粒子速度減慢，以便精細(xì)地進(jìn)行局部搜索(這里，w類似于模擬退火中的溫度參數(shù))。顯見(jiàn)，對(duì)w進(jìn)行合適的動(dòng)態(tài)設(shè)定，可加快PSO算法收斂速度，提高PSO算法的性能。為此，常用公式(9.5)，自適應(yīng)地改變慣性權(quán)重系數(shù)：(9.5)其中，wmax為最大慣性權(quán)重，wmin為最小慣性權(quán)重，k為當(dāng)前迭代次數(shù)，kmax為設(shè)定的最大迭代次數(shù)。這樣的設(shè)定，將慣性權(quán)重看做迭代次數(shù)的函數(shù)，使w線性度減小。值得注意的是，線性遞減慣性權(quán)值w只對(duì)某些問(wèn)題有效。9.2.4帶收縮因子的粒子群算法

Clerc采用收縮因子的方法[4，5]可以保證PSO算法收斂。收縮因子ξ是關(guān)于參數(shù)c1和c2的函數(shù)，定義為(9.6)(9.7)帶收縮因子的PSO算法的速度迭代定義為在Clerc的收縮因子方法中，通常φ取值為4.1，從而使收縮因子ξ大致等于0.729。分析公式(9.7)知收縮因子ξ的作用是用來(lái)控制與約束粒子的飛行速度，同時(shí)增強(qiáng)算法的局部搜索能力。

9.3粒子群算法的分析

9.3.1標(biāo)準(zhǔn)PSO算法分析

下面參考并部分引用文獻(xiàn)[16]，對(duì)粒子群算法的收斂性進(jìn)行分析。標(biāo)準(zhǔn)的PSO算法進(jìn)化方程中，雖然xid和vid是D維變量，但各維之間相互獨(dú)立。故此，對(duì)標(biāo)準(zhǔn)的PSO算法的分析[6~9]可以將其簡(jiǎn)化到一維進(jìn)行。我們把方程(9.2)和(9.4)簡(jiǎn)化為一維后，就有(9.8)(9.9)令φ1=c1r1，φ2=c2r2，φ=φ1+φ2，代入上兩式并進(jìn)行整理，可得(9.10)(9.11)對(duì)公式(9.10)和(9.11)進(jìn)一步整理可得公式(9.12)為標(biāo)準(zhǔn)的離散時(shí)間線性系統(tǒng)方程。所以，標(biāo)準(zhǔn)PSO算法可表述為線性時(shí)間離散系統(tǒng)。依據(jù)線性離散時(shí)間系統(tǒng)穩(wěn)定判據(jù)，粒子的狀態(tài)取決于矩陣G特征值，即當(dāng)k→∞,vki和xki趨于某一定值時(shí)，系統(tǒng)穩(wěn)定的充分必要條件是G的全部特征值λ1、λ2的幅值均小于1。下面給出標(biāo)準(zhǔn)PSO收斂性分析，G的特征值為式(9.13)的解:

λ2－(w+1－φ)λ+w=0

(9.13)

式(9.13)的解為(9.14)

(1)當(dāng)(w+1－φ)2≥4w時(shí)，λ1、λ2為實(shí)數(shù)，且此時(shí)(9.15)其中,

(2)當(dāng)(w+1－φ)2<4w時(shí)，λ1、λ2為復(fù)數(shù)，且此時(shí)其中,(3)當(dāng)(w+1－φ)2=4w時(shí)，且此時(shí)其中,9.3.2PSO算法在二維空間的收斂分析

PSO算法在二維空間域中，第i個(gè)粒子pi第k+1步迭代的狀態(tài)向量表示為[xk+1i2,vk+1i2]T，把這個(gè)狀態(tài)向量在二維上分別分解，對(duì)粒子pi位置分解為：xk+1i(x方向位移)與yk+1i(y方向位移)；速度可分解為：uk+1i(x方向速度)和vk+1i(y方向速度)。于是，PSO算法在二維空間域中，第i個(gè)粒子pi的第k+1步迭代的狀態(tài)向量可寫(xiě)為[xk+1i,yk+1i,uk+!i,vk+1i]T。加入慣性權(quán)重改進(jìn)后的標(biāo)準(zhǔn)PSO算法，可得各方向的方程為其中，ξ,ζ為標(biāo)準(zhǔn)PSO算法中的權(quán)重系數(shù);c1,c2,d1,d2為加速常數(shù);r1,r2,r3,r4為隨機(jī)數(shù);pxki為x方向的粒子pi最優(yōu)值;gxk為x方向全局最優(yōu)值;pyki為y方向的粒子pi最優(yōu)值;gyk為y方向的全局最優(yōu)值。

為了便于分析PSO算法在二維域內(nèi)的收斂，對(duì)隨機(jī)參數(shù)r1,r2,r3,r4取下面的值：

r1=r2=r3=r4=0.5

并令則方程組可簡(jiǎn)化表示為寫(xiě)成向量形式為其中A為根據(jù)動(dòng)態(tài)系統(tǒng)理論，粒子的時(shí)間行為依賴于動(dòng)態(tài)矩陣A的特征值。對(duì)于給定的均衡點(diǎn)而言，均衡點(diǎn)穩(wěn)定的必要充分條件是矩陣A的四個(gè)特征值小于1。只有在這個(gè)條件下，粒子才最終達(dá)到均衡點(diǎn)，粒子群算法才會(huì)收斂。

矩陣A的特征值λ1、λ2、λ3、λ4(實(shí)數(shù)或者復(fù)數(shù))是

下面方程的解：

[λ2－(ξ－c+1)λ+ξ][λ2－(ζ－d+1)λ+ζ]=0

對(duì)上式的根進(jìn)行分析，可以得到結(jié)論：當(dāng)

ξ<1,c>0,2ξ－c+2>0

或

ξ<1,d>0,2ζ－d+2>0時(shí)，對(duì)于給定的任何初始位置和速度，只要算法的參數(shù)在這個(gè)區(qū)域內(nèi)選定，粒子都會(huì)最終收斂于由式子所決定的均衡點(diǎn)。

同理，可采用類似的思想方法，研究PSO算法在多維空間域內(nèi)的收斂性。

9.4幾種改進(jìn)的粒子群算法

9.4.1離散粒子群優(yōu)化算法

為了用PSO算法求解大量的離散組合優(yōu)化問(wèn)題，主要有兩條完全不同的技術(shù)路線：一種是以基本的PSO算法為基礎(chǔ)，針對(duì)具體問(wèn)題，將離散問(wèn)題空間映射到連續(xù)粒子運(yùn)動(dòng)空間，并適當(dāng)修改基本PSO算法，對(duì)位置的表示采用離散形式，但在計(jì)算上仍保留基本PSO算法速度更新中的連續(xù)運(yùn)算規(guī)則；另一種是針對(duì)離散優(yōu)化問(wèn)題，基于基本PSO算法搜尋求解更新的基本機(jī)理，在基本PSO算法的基本思想和算法框架下，重新定義粒子群離散表示方式以及操作算子，在位置的表示上采用離散形式。在計(jì)算上，以離散空間特有的對(duì)矢量的位操作，取代傳統(tǒng)向量計(jì)算。但從信息的交流機(jī)制上看，仍保留了基本PSO算法特有的信息交換機(jī)制。這兩種方法的區(qū)別在于：前者將實(shí)際離散空間中的優(yōu)化問(wèn)題映射到粒子連續(xù)運(yùn)動(dòng)空間后，在連續(xù)空間中使用經(jīng)典的PSO算法求解，稱其為基于連續(xù)空間的DPSO(DiscreteParticleSwarmOptimization)；后者則是將PSO算法機(jī)理引入到離散空間，在離散空間中進(jìn)行計(jì)算和求解，稱其為基于離散空間的DPSO。

1.基于連續(xù)空間的DPSO優(yōu)化算法

對(duì)基于連續(xù)空間DPSO算法的研究取得了很多進(jìn)展，其中Kennedy和Eberhart于1997提出了二進(jìn)制PSO算法[9](PBSO，BinaryPSO)，并建立了不同于基本PSO算法的新計(jì)算模式。在BPSO中，粒子位置的每一維xid定義為1或者0，但對(duì)速度vid而言，則不作這種限制。通過(guò)粒子的速度來(lái)更新粒子位置時(shí)，根據(jù)粒子速度值大小，按概率來(lái)選擇粒子pi在每一維d的位置上取1或0。vk+1id越大，xk+1id越有可能選1；相反，vk+1id值越小，xk+1id則越接近0。BPSO的粒子狀態(tài)更新公式為(9.18)(9.19)

2.基于離散空間的DPSO優(yōu)化算法

基于離散空間的DPSO算法，需要針對(duì)具體問(wèn)題，構(gòu)建相應(yīng)的粒子表達(dá)方式，并重新定義粒子更新公式(9.1)和(9.2)。Clerc針對(duì)旅行商問(wèn)題(TSP，TravelingSalesmanProblem)所提出的TSP-DPSO算法[10，13]，具有典型性。在TSP-DPSO算法中，用所有城市的一個(gè)序列來(lái)表示粒子的一個(gè)位置，這個(gè)序列也表示了TSP問(wèn)題的一個(gè)解。如n個(gè)城市的TSP-DPSO算法中某粒子pi的一個(gè)位置為pis=(aij),j=1,2,…,n,aij為某城市，從左向右表示訪問(wèn)城市的順序。例如，對(duì)于5個(gè)城市，某粒子的一個(gè)位置為pis=(24513)，從左至右第1位置上的元素是城市2，第2位置上的元素是城市4，第3位置上的元素是城市5，第4位置上的元素是城市1，第5位置上的元素是城市3。這個(gè)序列表示從城市2出發(fā)去城市4，再去城市5，后去城市1，最后去城市3，然后返回城市2。全體城市所有可能的序列就構(gòu)成了問(wèn)題搜索空間。粒子位置的更新就意味粒子pi從所有城市的一種序列變化到另一種序列。而這種更新是由粒子的飛翔引起的?；诖?，速度定義為：粒子為達(dá)到目標(biāo)狀態(tài)(城市序列對(duì)應(yīng)路徑的路程最短)需要對(duì)其當(dāng)前序列中的多個(gè)位置上的元素執(zhí)行交換操作。為此，引入了交換子和交換序列概念。一個(gè)交換子s=Swappi(k,l)定義為：交換子s作用在粒子pi上，使pi的位置(序列)中位置k上元素和位置l上元素相互交換。例如，5個(gè)城市TSP的一個(gè)粒子p1當(dāng)前的位置(序列)為(12345)，對(duì)其施加一個(gè)交換子s=Swapp1(2,4)后，p1新的位置(序列)變?yōu)?14325)。在這里，交換子的作用可看做粒子的飛翔速度，它改變p1的位置。

一組特定順序的交換子集合稱為一個(gè)交換序列ss=Swappi(s1,s2,…，sm)，它定義為：ss對(duì)粒子pi連續(xù)實(shí)施交換子s1,s2,…，sm。例如粒子p1，它當(dāng)前位置為(12345)，對(duì)其施加交換序列ss=Swapp1[(1,3),(2,3),(3,5),(4,5)]后，粒子p1的最新位置為(31524)。為此，需要重新定義基本粒子群算法中的運(yùn)算操作，重新定義后的粒子狀態(tài)更新公式為(9.20)(9.21)9.4.2小生境粒子群優(yōu)化算法

Brits等人將小生境[11](Niche)技術(shù)引入PSO算法，提出一種小生境粒子群算法[12](NPSO，NicheParticleSwarmOptimization)。小生境是來(lái)自于生物學(xué)的一個(gè)概念，是指特定環(huán)境下的一種生存環(huán)境，處于該生存環(huán)境的生物在其進(jìn)化過(guò)程中，一般總是與自己相同的物種生活在一起，共同繁衍后代。它們也都是在某一特定的地理區(qū)域中生存。引入小生境技術(shù)的NPSO算法保持了粒子群的多樣性，在多峰函數(shù)優(yōu)化問(wèn)題中顯示了比較好的性能。

Brits等人提出的小生境PSO算法，其最基本思想是，將生物學(xué)中處于分離狀態(tài)且在孤立的地理小生境中的不同物種之間不進(jìn)行競(jìng)爭(zhēng)或交配而獨(dú)立進(jìn)化這一概念移植到粒子群算法中，以便在迭代過(guò)程中保持粒子群的多樣性。小生境粒子群算法主要分為兩個(gè)階段,第一個(gè)階段基于小生境概念，根據(jù)粒子之間的距離(歐氏距離)找到每個(gè)粒子的小生境群體(稱其為子粒子群),然后在每個(gè)小生境群體中利用基本粒子群算法進(jìn)行速度和位置更新,其中子粒子群的最優(yōu)值僅在該小生境群體中起作用。對(duì)于更新(一次迭代)后的每個(gè)子粒子群,更新其最優(yōu)個(gè)體,并根據(jù)粒子間的距離,對(duì)進(jìn)入小生境的粒子進(jìn)行吸收，對(duì)符合合并條件的兩個(gè)小生境粒子群進(jìn)行合并。上述過(guò)程不斷迭代，直到滿足終止條件。在算法迭代運(yùn)行過(guò)程中，NPSO算法主要依賴于以下幾種操作:

(1)子粒子群sj的半徑rsj計(jì)算:(9.22)其中，psjg是子粒子群sj中最優(yōu)粒子，psji表示子粒子群sj中的任一非最優(yōu)粒子；

(2)當(dāng)粒子pi進(jìn)入子粒子群sj范圍內(nèi)時(shí)，子粒子群sj吸收粒子pi，即(3)當(dāng)兩個(gè)子粒子群sj1和sj2相交時(shí),即(9.23)(9.24)兩個(gè)子粒子群合并成一個(gè)新的子粒子群。

基于小生境的粒子群算法的具體步驟如下:

(1)初始化粒子群體為

P={p1,p2,…,pN}

(2)確定小生境子粒子群及每個(gè)子粒子群中的個(gè)體。

通過(guò)計(jì)算兩個(gè)粒子個(gè)體的距離，確定小生境子粒子群sji,i=1,2,…,k，共k個(gè)子粒子群，為子粒子群

的元素個(gè)數(shù)。

(3)按照基本PSO算法對(duì)每個(gè)小生境子粒子群進(jìn)行運(yùn)算,包括每個(gè)粒子的速度和位置更新、子粒子群半徑計(jì)算和更新、子粒子群的合并及每個(gè)子粒子群對(duì)符合條件粒子的吸收。

(4)計(jì)算每個(gè)子粒子群最優(yōu)的粒子，檢查是否達(dá)到優(yōu)化條件。如果達(dá)到誤差精度或所確定的迭代次數(shù)，算法結(jié)束；否則，轉(zhuǎn)(3)進(jìn)入下一次迭代。

9.5粒子群算法在智能控制中的應(yīng)用

9.5.1用PSO算法求解TSP的應(yīng)用

用PSO算法求解TSP問(wèn)題時(shí)，首先對(duì)PSO算法公式(9.1)、式(9.2)中最關(guān)鍵的兩點(diǎn),即①粒子的位置和粒子的速度,②粒子位置和速度的更新，要在TSP中有一個(gè)明確對(duì)應(yīng)的定義。對(duì)于TSP的一個(gè)解，是一條經(jīng)過(guò)各城市一次且僅一次的路線。顯然，可用所有城市的一個(gè)序列來(lái)表示TSP的一個(gè)可能的解，這個(gè)解可視為PSO算法中粒子的一個(gè)位置，故所有城市所有可能的序列就構(gòu)成了問(wèn)題搜索空間。粒子位置的更新就意味著將所有城市的一種序列變換到另一種序列，而這種更新是由粒子“飛翔”引起的，即粒子的速度可以看做是施加在粒子位置上的一種操作，這種操作可以使所有城市的一種序列發(fā)生變化。粒子速度的更新會(huì)引起粒子“飛翔”的變化，而這種變化最終還是引起粒子位置的變化?；谶@樣的粒子位置、位置變化、速度以及速度更新定義，下面參考并部分引用文獻(xiàn)[13]說(shuō)明用PSO算法解決TSP問(wèn)題。讓我們先表述幾個(gè)定義：

編碼對(duì)n個(gè)城市TSP的一個(gè)可能解進(jìn)行編碼，即每個(gè)城市用唯一的數(shù)i(i=1,2,…,n)表示，所有城市的一個(gè)序列就是一個(gè)編碼。例如設(shè)5個(gè)城市TSP問(wèn)題的一個(gè)解的編碼為p=(12345)，意為從城市1出發(fā)到城市2，再到城市3，…，最后經(jīng)城市5返回到城市1。

交換子及操作設(shè)n個(gè)城市TSP問(wèn)題的一個(gè)解pi={aij},i=1,2,…,n，交換子s(aik,ail)作用在pi就意味交換解pi對(duì)應(yīng)編碼中位置aik和位置ail上元素，這個(gè)操作可表示為pi′=pi+s，意思為T(mén)SP的一個(gè)解pi，經(jīng)交換子s操作后得一新解pi′，這里符號(hào)“+”表示交換子s施加在pi上。例如，對(duì)pi=(12345)，有一交換算子s(2,4)，則

p′=pi+s(2,4)=(12345)+s(2,4)=(14325)

交換序列及操作兩個(gè)或兩個(gè)以上交換子的有序序列就是交換序列，記作SS。例如交換子s1，s2，…，sl構(gòu)成一個(gè)交換序列SS=(s1,s2,…,sl)，在這里交換子的順序是有意義的。交換序列SS作用于一個(gè)TSP的解p0，就意味著這個(gè)交換序列中的交換子s1首先作用于該解p0上，得到p1，隨后交換子s2作用于p1，得到p2，…，最后交換子sl作用于pl－1，得到交換序列SS作用于p0結(jié)果即

p′=p0+SS=p0+(s1,s2,…,sl)=((p0+s1)+s2)+…+sl

例如，交換序列SS=(s1(2,4),s2(3,5))，作用在p0=(12345)，結(jié)果為

p′={[(12345)+s1(2,4)]+s2(3,5)}=(14325)+s2(3,5)=(14523)不同的交換序列作用于同一解上可能產(chǎn)生相同的新解,所有有相同效果的交換序列的集合稱為交換序列的等價(jià)集。在交換序列的等價(jià)集中，擁有最少交換子的交換序列稱為該等價(jià)集的基本交換序列。

合并算子若干個(gè)交換子可以合并成一個(gè)新的交換序列，合并算子實(shí)現(xiàn)兩個(gè)或多個(gè)交換子的合并，合并算子用符號(hào)⊕表示。設(shè)兩個(gè)交換子s1和s2，按先后順序作用于解p上,得到新解p′，如果另外有一個(gè)交換序列s′作用于同一解p上，能夠得到相同的解p′，則可定義s′=s1⊕s2，稱s′等價(jià)s1和s2的合并。

例如，兩個(gè)交換子s1(2,4)和s2(3,5)，作用在p=(12345)，結(jié)果為p′=(14523)，顯然，交換序列s′=(s1,s2)等價(jià)于s1和s2的合并?！傲Ｗ印彼俣雀禄綪SO算法中的速度算式(9.1)已不適合TSP問(wèn)題，重新構(gòu)造粒子速度更新算式為

vk+1i=wvki⊕α(pbki－xki)⊕β(gbk－xki)

(9.25)

其中，α,β∈[0,1]為隨機(jī)數(shù)。α(pbki－xki)表示交換序列

(pbki－xki)以概率α起作用；同理，β(gbk－xki)表示交換序列(gbk－xki)以概率β起作用。由此可以看出，α的值越大，交換子(pbki－xki)起作用的概率就越大；同理，β的值越大，交換子(gbk－xki)起作的用概率就越大。根據(jù)以上定義，求解TSP的PSO算法步驟可描述如下：

(1)初始化粒子群，即給群體中的每個(gè)粒子賦一個(gè)隨機(jī)的初始解和一個(gè)隨機(jī)的交換序列。

(2)如果解滿足結(jié)束條件，則顯示求解結(jié)果并結(jié)束求解過(guò)程，否則繼續(xù)執(zhí)行(3)。

(3)根據(jù)粒子當(dāng)前位置xki，計(jì)算其下一個(gè)位置xk+1i，即新解，具體如下：

①尋找A，A=(pbki－xki)，A是一交換序列，表示A作用于xki得到pbki;

②尋找B,B=(gbk－xki),B是一交換序列，表示B作用于

xki得到gbk;③根據(jù)式(9.25)計(jì)算速度vik+1，得到的vik+1是一交換序列；

④根據(jù)式(9.26)計(jì)算新解xik+1，

xik+1=xki+vk+1i

(9.26)

⑤如果所計(jì)算的xik+1即當(dāng)前粒子是一個(gè)更好的解，則更新pbki。

(4)如果pbki比gbk更優(yōu)秀，用pbki代替gbk后轉(zhuǎn)步驟(2)。

根據(jù)上述DPSO算法，TSP問(wèn)題20個(gè)城市的仿真情況如下：

(1)TSP問(wèn)題20個(gè)城市及對(duì)應(yīng)坐標(biāo)為：

5.326,2.558;4.276,3.452;4.819,2.624;3.165,2.457;

0.915,3.921;4.637,6.026;1.524,2.261;3.447,2.111;

3.548,3.665;2.649,2.556;4.399,1.194;4.660,2.949;

1.479,4.440;5.036,0.244;2.830,3.140;1.072,3.454;

5.845,6.203;0.194,1.767;1.660,2.395;2.682,6.072

(2) 具體仿真實(shí)驗(yàn)結(jié)果如表9.1。

(3)當(dāng)α=0.5,β=0.7，粒子初始位置為取不同的編碼和初始交換序列時(shí)，解與收斂過(guò)程見(jiàn)圖9.3。

實(shí)驗(yàn)顯示，對(duì)應(yīng)粒子初始位置為不同的編碼且不同的初始交換序列，算法的收斂速度略有不同。當(dāng)算法找到好的粒子位置(解)，只有好的粒子位置對(duì)應(yīng)的路徑?jīng)]有交叉時(shí)，這些路徑才是較優(yōu)秀解。比如第2、4、5、6、8、10次實(shí)驗(yàn)。圖9.3采用DPSO算法解20個(gè)城市TSP問(wèn)題的仿真9.5.2在機(jī)器人控制領(lǐng)域的應(yīng)用

1.路徑規(guī)劃問(wèn)題的描述與建模

對(duì)于移動(dòng)機(jī)器人，路徑規(guī)劃就是尋找它在環(huán)境中移動(dòng)時(shí)，所必須經(jīng)過(guò)的合適的點(diǎn)的集合。首先，在機(jī)器人運(yùn)動(dòng)空間建模時(shí)，作如下假定：

(1)移動(dòng)機(jī)器人在二維平面凸多邊形區(qū)域AS中移動(dòng)；

(2)視機(jī)器人為質(zhì)點(diǎn)機(jī)器人，將機(jī)器人尺寸大小轉(zhuǎn)換為對(duì)障礙物尺寸的適當(dāng)拓展；

(3)機(jī)器人移動(dòng)空間中，分布著有限個(gè)已知的靜態(tài)障礙物。

障礙物對(duì)機(jī)器人移動(dòng)阻擋的范圍，用障礙物在二維平面上的正投影區(qū)域來(lái)表征，即質(zhì)點(diǎn)機(jī)器人無(wú)法進(jìn)入也無(wú)法通過(guò)這個(gè)障礙的投影區(qū)域，換句話說(shuō)，這個(gè)障礙投影區(qū)域中的點(diǎn)都是障礙點(diǎn)。設(shè)s為機(jī)器人的出發(fā)點(diǎn)，g為終點(diǎn)。從s移動(dòng)到g，因障礙物的存在，機(jī)器人移動(dòng)的軌跡不可能是一個(gè)線段sg，機(jī)器人的路徑規(guī)劃就是要尋找一個(gè)點(diǎn)的集合p：

p={s,p1,p2,…,pn－1,g}

(9.27)

其中，出發(fā)點(diǎn)s可以視為p0，終點(diǎn)g可以視為pn，(p1,p2,…,pn-1)為二維平面上一個(gè)點(diǎn)的序列，即規(guī)劃目標(biāo)。對(duì)點(diǎn)pi(i=1,2,…,n－1)的要求是pi為非障礙點(diǎn)，pi(i=1,2,…,n－1)與相鄰點(diǎn)pi－1或pi+1的連線上不存在障礙點(diǎn)。機(jī)器人行走路徑L就是由pi到pi+1(i=0,2,…,n)的連線連接在一起而構(gòu)成的。路徑示意

圖見(jiàn)圖9.4。圖9.4機(jī)器人路徑示意圖對(duì)于一次機(jī)器人路徑規(guī)劃，假定已知障礙物位置、機(jī)器人出發(fā)點(diǎn)s和終點(diǎn)g。為使問(wèn)題簡(jiǎn)化，以過(guò)s、g兩點(diǎn)的直線為x軸，垂直于x軸且經(jīng)過(guò)s點(diǎn)的直線作為y軸。將線段sg進(jìn)行(n+1)等分，在每一個(gè)等分點(diǎn)處作x軸垂線，得到一簇平行直線(l1,l2,…,ln)，l0與y軸重合。在每一條直線li(i=1,2,…,n－1),上，確定一個(gè)點(diǎn)pi，pi不但為非障礙點(diǎn)，而且pi(i=1,2,…,n－1)與相鄰點(diǎn)直線li－1上點(diǎn)pi－1的連線上或與直線li+1上點(diǎn)pi+1的連線上，也不存在障礙點(diǎn)。這些點(diǎn)pi(i=1,2,…,n－1)就構(gòu)成目標(biāo)點(diǎn)序列(p0,p1,p2,…,pn)，其中p0、pn分別與

s、g重合。點(diǎn)pi(i=0,1,2,…,n)對(duì)應(yīng)的坐標(biāo)為(xpi,ypi)。pi(i=1,2,…,n－1)坐標(biāo)的最大—最小取值由機(jī)器人所移動(dòng)的二維平面凸多邊形區(qū)域AS邊界確定。對(duì)圖9.4所示的二維平面凸多邊形區(qū)域AS，機(jī)器人從s點(diǎn)出發(fā)，最終到達(dá)終點(diǎn)g對(duì)應(yīng)的機(jī)器人路徑規(guī)劃示意圖見(jiàn)圖9.5。圖9.5機(jī)器人路徑規(guī)劃示意圖機(jī)器人行走路徑L的長(zhǎng)度Ll為(9.28)其中，Lpipi+1表示平面上從pi點(diǎn)到pi+1點(diǎn)的距離，Lsg表示線段sg的長(zhǎng)度。顯見(jiàn)，機(jī)器人從s點(diǎn)出發(fā)，最終到達(dá)終點(diǎn)g的最終路徑規(guī)劃問(wèn)題本質(zhì)上是對(duì)公式(9.28)所示函數(shù)的優(yōu)化，即在ypi(i=1,2,…,n－1)的取值空間中尋找合適的ypi(i=1,2,…,n)，以使Ll最小。在這個(gè)模型描述中，障礙物的阻擋體現(xiàn)在對(duì)