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

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

9.1引言

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

(1)碰撞的避免，即個體應避免和附近的同伴碰撞;

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

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

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

9.2基本粒子群算法

9.2.1基本粒子群算法的原理

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

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

vmaxd=ρxmaxd

(9.3)

基本粒子群算法流程見圖9.2。圖9.2基本粒子群算法流程基本粒子群算法流程描述如下:

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

(2)計算粒子pi的適應度；

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

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

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

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

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

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

9.3粒子群算法的分析

9.3.1標準PSO算法分析

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

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

(9.13)

式(9.13)的解為(9.14)

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

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

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

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

r1=r2=r3=r4=0.5

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

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

下面方程的解：

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

對上式的根進行分析，可以得到結(jié)論：當

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

或

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

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

9.4幾種改進的粒子群算法

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

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

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

對基于連續(xù)空間DPSO算法的研究取得了很多進展，其中Kennedy和Eberhart于1997提出了二進制PSO算法[9](PBSO，BinaryPSO)，并建立了不同于基本PSO算法的新計算模式。在BPSO中，粒子位置的每一維xid定義為1或者0，但對速度vid而言，則不作這種限制。通過粒子的速度來更新粒子位置時，根據(jù)粒子速度值大小，按概率來選擇粒子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算法，需要針對具體問題，構(gòu)建相應的粒子表達方式，并重新定義粒子更新公式(9.1)和(9.2)。Clerc針對旅行商問題(TSP，TravelingSalesmanProblem)所提出的TSP-DPSO算法[10，13]，具有典型性。在TSP-DPSO算法中，用所有城市的一個序列來表示粒子的一個位置，這個序列也表示了TSP問題的一個解。如n個城市的TSP-DPSO算法中某粒子pi的一個位置為pis=(aij),j=1,2,…,n,aij為某城市，從左向右表示訪問城市的順序。例如，對于5個城市，某粒子的一個位置為pis=(24513)，從左至右第1位置上的元素是城市2，第2位置上的元素是城市4，第3位置上的元素是城市5，第4位置上的元素是城市1，第5位置上的元素是城市3。這個序列表示從城市2出發(fā)去城市4，再去城市5，后去城市1，最后去城市3，然后返回城市2。全體城市所有可能的序列就構(gòu)成了問題搜索空間。粒子位置的更新就意味粒子pi從所有城市的一種序列變化到另一種序列。而這種更新是由粒子的飛翔引起的。基于此，速度定義為：粒子為達到目標狀態(tài)(城市序列對應路徑的路程最短)需要對其當前序列中的多個位置上的元素執(zhí)行交換操作。為此，引入了交換子和交換序列概念。一個交換子s=Swappi(k,l)定義為：交換子s作用在粒子pi上，使pi的位置(序列)中位置k上元素和位置l上元素相互交換。例如，5個城市TSP的一個粒子p1當前的位置(序列)為(12345)，對其施加一個交換子s=Swapp1(2,4)后，p1新的位置(序列)變?yōu)?14325)。在這里，交換子的作用可看做粒子的飛翔速度，它改變p1的位置。

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

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

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

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

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

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

(1)初始化粒子群體為

P={p1,p2,…,pN}

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

通過計算兩個粒子個體的距離，確定小生境子粒子群sji,i=1,2,…,k，共k個子粒子群，為子粒子群

的元素個數(shù)。

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

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

9.5粒子群算法在智能控制中的應用

9.5.1用PSO算法求解TSP的應用

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

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

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

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

交換序列及操作兩個或兩個以上交換子的有序序列就是交換序列，記作SS。例如交換子s1，s2，…，sl構(gòu)成一個交換序列SS=(s1,s2,…,sl)，在這里交換子的順序是有意義的。交換序列SS作用于一個TSP的解p0，就意味著這個交換序列中的交換子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)生相同的新解,所有有相同效果的交換序列的集合稱為交換序列的等價集。在交換序列的等價集中，擁有最少交換子的交換序列稱為該等價集的基本交換序列。

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

例如，兩個交換子s1(2,4)和s2(3,5)，作用在p=(12345)，結(jié)果為p′=(14523)，顯然，交換序列s′=(s1,s2)等價于s1和s2的合并。“粒子”速度更新基本PSO算法中的速度算式(9.1)已不適合TSP問題，重新構(gòu)造粒子速度更新算式為

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

(9.25)

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

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

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

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

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

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

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

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

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

xik+1=xki+vk+1i

(9.26)

⑤如果所計算的xik+1即當前粒子是一個更好的解，則更新pbki。

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

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

(1)TSP問題20個城市及對應坐標為：

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) 具體仿真實驗結(jié)果如表9.1。

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

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

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

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

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

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

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

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

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

(9.27)

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

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

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