【正文】 %Pg 為全局最優(yōu) for i=2:N if fitness(x(i,:),D)fitness(pg,D) pg=x(i,:)。 y(i,:)=x(i,:)。 %賦初始值 %初始化種群的個(gè)體 (可以在這里限定位置和速度的范圍 ) for i=1:N for j=1:D x(i,j)=100*randn。 %全體極值需要擾動(dòng)的停止步數(shù) 闕值 t0=0。 %設(shè)置精度 (在已知最小值時(shí)候用 ) T0=3。 %搜索空間維數(shù)（未知數(shù)個(gè)數(shù)） N=15。 MaxDT=1000。 %學(xué)習(xí)因子 2 wini=。 %給定初始化條件 c1=2。 實(shí)驗(yàn)名稱 迭代次數(shù) 平均值 最小值 最大值 Sphere 函數(shù) bPSO 95 45 180 sPSO 15 10 30 tPSO 75 40 140 tsPSO 14 10 16 Rosenbrock 函數(shù) bPSO 350 250 600 sPSO 17 7 30 tPSO 240 100 400 tsPSO 15 7 30 Rastrigin 函數(shù) bPSO 410 100 700 sPSO 22 12 40 tPSO 220 400 140 tsPSO 18 9 40 clc。這表明，帶極值擾動(dòng)的 sPSO 算法 具有非常高的優(yōu)化性能和實(shí)用性。 同樣比較 bPSO 和 tPSO 實(shí)驗(yàn)可以看出： tPSO 總體上比 bPSO 的優(yōu)化效果好一些。 固定收斂精度下的迭代次數(shù) 4 個(gè)實(shí)驗(yàn)在適應(yīng)度值為 610 的 收斂精度下經(jīng)過 20 次獨(dú)立運(yùn)行后的最大迭代次數(shù)、最小迭代次數(shù)、平均迭代次數(shù)見表 1。 實(shí)驗(yàn)結(jié)果及 分析 固定進(jìn)化迭代次數(shù)的收斂速度和精度 bPSO、 sPSO、 tPSO、 tsPSO 用三個(gè)測試函數(shù)進(jìn)行 測試，固定進(jìn)化迭代次數(shù)為 150次，（ 1）（ 2）（ 3）分別選用 Sphere 函數(shù)、 Rosenbrock 函數(shù)、 Rastrigin 函數(shù)作為測試函數(shù)，（ a）（ b）（ c）（ d）分別為用各個(gè)測試函數(shù)的 bPSO 算法、 sPSO 算法 、 tPSO 算法、 tsPSO算法的適應(yīng)度的對(duì)數(shù)值進(jìn)化曲線（注：為了方便進(jìn)化曲線的顯示和觀察，對(duì)函數(shù)的適應(yīng)度以 10 為底的對(duì)數(shù)；同時(shí)，為了避免縱坐標(biāo)范圍貴大，對(duì)函數(shù)的適應(yīng)度均加上 610 作為截止值） 觀察改進(jìn)優(yōu)化粒子群優(yōu)化算法的效果。 具體參數(shù)設(shè)置為： 種群規(guī)模設(shè)為 m=15，粒子的維數(shù)為Dim=30，最大迭代步數(shù)為 150； max 1v ? ； 122cc??； 0 3。 實(shí)驗(yàn)選用 Sphere、 Rosenbrock、 Rastrigin 函數(shù) 三種基準(zhǔn)函數(shù)。優(yōu)化算法很容易在通往全局 最優(yōu)點(diǎn)的路徑上陷入一個(gè)局部最優(yōu)點(diǎn)。 搜索空間 100 100ix? ? ? 。函數(shù)的 3D 圖形如圖 所示 。 搜索空間 100 100ix? ? ? 。該函數(shù)在原理最優(yōu)點(diǎn)區(qū)域的適應(yīng)值地形很簡單，但靠近最優(yōu)的區(qū)域?yàn)橄憬稜睢?函數(shù)的 3D 圖形如圖 所。 搜索空間 100 100ix? ? ? 。因此 ,tsPSO 是 sPSO 的推廣 ， sPSO 是 tsPSO 的特例。以上兩種策略結(jié)合，得到帶 極值擾動(dòng)的簡化粒子群算法（ tsPSO）。 帶極值擾動(dòng)的簡化粒子群優(yōu)化算法 sPSO 去掉了 PSO 進(jìn)化方程的粒子速度項(xiàng)而使原來的二階微分方程簡化為一階微分方程，僅由粒子位置控制進(jìn)化過程，避免了由粒子速度項(xiàng)引起的粒子發(fā)散而導(dǎo)致后期收斂變慢和精度低問題。需要說明的是 , 0, gTT的取值大小決定了極值擾動(dòng)算子生效的延遲長短 ,一般取值范圍為 3～ 0, gTT等于進(jìn)化世代數(shù)時(shí) ,式 ()退化為式 ()。 00 003001,( 0 ,1)tT tTr tTU? ??? ? ??和00 004001,( 0 ,1)tT tTr tTU? ??? ? ?? 表示帶條件的均勻隨機(jī)函數(shù)。 ggtTtT ggp r p p r p????， 其中 : 0,gtt分別表示個(gè)體極值和全局極值進(jìn)化停滯步數(shù) 。文獻(xiàn) [18]的改進(jìn)方法屬于第 2 種情況 ,以適應(yīng)度方差作為觸發(fā)條件 ,并以很小概率 [,]改變 gp 。*p ,經(jīng)歷新的搜索路徑和領(lǐng)域 ,因此發(fā)現(xiàn)更優(yōu)解的概率較大。gp ,使所有粒子飛向新的位置 39。(2)調(diào)整個(gè)體極值和全局極值為 39。 文獻(xiàn) [17]通過嚴(yán)格的數(shù)學(xué)推導(dǎo) ,得到式 (): 1 1 2 201 1 2 2 1 1 2 2( ) *l im gtc r c rx t p p pc r c r c r c r?? ? ? ??? () 由于 1r ， 2r 服從均勻分布 ,故 bPSO系統(tǒng)的平均行為可 通過其期望值進(jìn)行觀察 ,故式 ()可以變?yōu)? 1 0 2 012( ) * ( 1 )l img gtc p c px t p p pcc ?????? ? ? ? ?? () 由式 ()和定理 2可知 :在 bPSO和 sPSO中 ,粒子將聚集到由自身極值 0p 和群體全局極值 gp 決定的極值之上 ,如果所有粒子在向 *p 靠近過程中沒有找到優(yōu)于 gp 的位置 ,則進(jìn)化過程將處于停滯狀態(tài) ,粒子逐漸聚集到 *p 。 bPSO 收斂于局部極值的原因分析 實(shí)驗(yàn)發(fā)現(xiàn) :當(dāng) bPSO 處于進(jìn)化停滯時(shí) ,粒子群中的粒子都會(huì)出現(xiàn)“聚集”現(xiàn)象 ,直至突破進(jìn)化停滯局面 ,粒子才會(huì)“飛散”開去。這些改進(jìn)策略都不同程度地提高了收斂速度和精度 ,但都不是從 bPSO 收斂于局部極值的根本原因上采取改進(jìn)策略。這主 要是粒子群難以擺脫局部極值的原因 ,也是 bPSO 的美中不足。 帶極值擾動(dòng)的粒子群優(yōu)化算法 bPSO 在優(yōu)化前期中收斂速度很快。 由于 1r ， 2r 服從均勻 分布，故 sPSO 系統(tǒng)的 平均行為可通過其期望值進(jìn)行觀察，即 11 1 1() 1 0 2cxE c r c dx???? ， 22 2 2() 1 0 2cxE c r c dx???? ； 故 1 1 0 2 2 1 0 21 1 2 2 1 2( ) * 2l imggtc r p c r p c p c px t p c r c r c c??? ? ? ?????? ? ? ?? ? ? ? ?。 證明：式（ ）的微分方程解為 ()() tx t Ce ?? ??????? ?，要使 ()limt xt??收斂，則( 1) 1()limtxtxt??? ?，解得 0 ????。 采用第 ,式 (8)可以變形為一階微分方程 : ( 1 ) ( ) ( )x t x t? ? ??? ? ? ? () 由式 ()和式 ()的比較可知 :改寫后的 sPSO 進(jìn)化方程不僅沒有粒子速度參數(shù) ,而且方程也由二階降到了一階 ,簡化了分析和控制粒子的進(jìn)化過程。第 2 項(xiàng)為“認(rèn)知 (cognition)”部分 ,表示粒子對(duì)自身的思考 。 本定理的重要性在于說明 bPSO 算法可以沒有粒子速度的概念 ,避免了人為確定參數(shù)max, max[]vv? 而影響粒子的收斂速度和 收斂精度。再令 1 0 21 1 1 2 2 2 1 2 12, , , gppr c r c ??? ? ? ? ? ? ???? ? ? ? ? ?。故不失一般性 ,證明過程可以簡化到一維進(jìn)行 ,下標(biāo) d可以省略。 證明 :文獻(xiàn) [16]已經(jīng)證明 ,約束粒子速度范圍 max, max[]idv v v?? 與添加約束因子 ? 是等價(jià)的 ,因此 ,可以只考慮由式 ()與式 ()組成的聯(lián)合進(jìn)化方程。另外 ,從式()～ 式 ()來看 ,位置與速度直接進(jìn)行加法運(yùn)算 ,而沒有粒子運(yùn)動(dòng)時(shí)間概念 ,這也不符合現(xiàn)實(shí)生活中的運(yùn)動(dòng)規(guī)律： x=vt。 仔細(xì)分析 bPSO 的生物模型和進(jìn)化迭代方程式 ()和方程式 ()可以發(fā)現(xiàn) :在 PSO 中 ,粒子速度概念不是必需的。慣性權(quán)重 ? 使 PSO 算法的性能得到很大提高。這種條件下，粒子群將收縮到當(dāng)前全局最好位置，更像一個(gè)局部算法。這樣使得 PSO 在開始時(shí)搜索較大的區(qū)域，較大地定位最優(yōu)解的大致位置，隨 著權(quán)重的減小，粒子速度減慢，開始精細(xì)的局部搜索。目前，采用較多的慣性權(quán)重是 Shi 建議的線性遞減權(quán)值 (1inearly decreasing weight，簡稱 LDW)策略，即 ( ) ( ) ( ) /ini e nd e ndt w w M ax D T t M ax D T w? ? ? ? ? （ 25） 其中， MaxDT 為最大迭代數(shù)， iniw 為初始慣性權(quán)值， endw 為進(jìn)化到最大代數(shù)時(shí)的慣性權(quán)值。 初始時(shí)， Shi 將慣性權(quán)重取值為常數(shù)，但后來的試驗(yàn)發(fā)現(xiàn)，動(dòng)態(tài)慣性權(quán)重能夠獲得比定值更好的尋優(yōu)結(jié)果。控制其取值大小可調(diào)節(jié) PSO 算法的全局與局部尋優(yōu)能力。 標(biāo)準(zhǔn)粒子群算法 （ bPSO） 為了更好的控制算法的尋優(yōu)能力， Shi 和 Eberhart 在記憶部分引入具有慣性權(quán)重，于是公式 (2． 1)和 (2． 2)可以修改成為以下兩個(gè)新的公式 ： id 1 1v ( 1 ) ( ) ( )idt t v t c r?? ? ? id id 2 2 gd id（ p x ( t ) ） + c r（ p x ( t ) ） （ 23） id id( 1 ) v ( 1 )x t t? ? ?idx (t) + （ 24） 很多學(xué)者將上述兩式稱為 bPSO 算法。 （ 7） 迭代終止條件：迭代終止條件的設(shè)定需要根據(jù)具體的問題兼顧算法的優(yōu)化質(zhì)量和搜索效率等多方面性能。 （ 6） 粒子空間的初始化：這是由具體問題決定的。不過在文獻(xiàn)中也其他的取值，但是一般 1c 等于 2c ，并且范圍在 [0,4]之間。此時(shí)，由于粒子只能搜索有限的區(qū)域，故很難找到好解。由于個(gè)體之間沒有交互，一個(gè)規(guī)模為 m 的群體等價(jià)于 m 個(gè)獨(dú)立的粒子運(yùn)行，因而得到最優(yōu)解的概率非常小。其收斂速度比標(biāo)準(zhǔn)算法更快，但碰到復(fù)雜問題，比標(biāo)準(zhǔn)算法更容易陷入局部極點(diǎn)。 如果 1 0c? ，則粒子自身沒有認(rèn)知能力，只有群體的經(jīng)驗(yàn)，即“只有社會(huì) (socialonly)”模型 。 1c 和 2c 分別調(diào)節(jié)粒子向個(gè)體最優(yōu)和群體最優(yōu)方向飛行的最大步長，決定粒子個(gè)體經(jīng)驗(yàn)和群體經(jīng)驗(yàn)對(duì)粒子自身運(yùn)行軌跡的影響，反映粒子群體之間的信息交流。 假設(shè)在搜 索空間中，第 i 個(gè)粒子的第 D 維速度經(jīng)過公式 （ 21） 更新后為 iDv ，如果 max max[ , ]iDv v v?? ， iDv將被限定為 maxv? 。如果 maxv 較大，粒子的探索能力強(qiáng)，但是容易飛過優(yōu)秀的搜索空間，錯(cuò)過最優(yōu)解；如果 maxv較小，粒子的開發(fā)能力強(qiáng)，但是容易陷入局部最優(yōu)，可能使粒子無法移動(dòng)足夠遠(yuǎn)的距離跳出局部最優(yōu)，從而不能到達(dá)解空間中的最佳位置。粒子的維數(shù)是根據(jù)具體問題的解空間的維數(shù)來確定的。然而，群體過大將導(dǎo)致計(jì)算時(shí)間大幅增加，并且當(dāng)群體數(shù)目增長至一定水平時(shí)，再增加粒子數(shù)目將不再有顯著的作用。 通常，粒子種群的數(shù)目是根據(jù)具體問題而設(shè)定的，一般設(shè)置在 10 到 50 之間。對(duì)于不同的優(yōu)化問題，在取得最優(yōu)結(jié)果時(shí)參數(shù)的設(shè)置往往是不完全相同的。 下面演示一下這個(gè)算法運(yùn)行一次的大概過程： 圖 初始化粒子 圖 粒子位置第 1 次更新 圖 粒子位置第 2 次更新 圖 粒子位置第 21 次更新 圖 粒子位置第 30 次更新 最后所有的結(jié) 果都集中在最大值的地方 。 （ 3） 計(jì)算兩個(gè)點(diǎn)函數(shù)值就是粒子群算法中的適應(yīng)值，計(jì)算用的函數(shù)就是粒子群算法中的適應(yīng)度函數(shù)。這個(gè)過程與 粒子群算法作為對(duì)照如下： （ 1） 這兩個(gè)點(diǎn)就是粒子群算法中的粒子。下面這些點(diǎn)就會(huì)按照一定的公式更改自己的位置，到達(dá)新位置后，再計(jì)算這兩個(gè)點(diǎn)的值，然后再按照一定的公式更新自己的位置。該函數(shù)的圖形如下： 圖 函數(shù) 1 cos 3 xy x e?? ? ? 在 [0,4]區(qū)間上的曲線 當(dāng) x=，達(dá)到最大值 y=。 基本粒子群優(yōu)化算法的流程圖 如 圖 21： 圖 21 基本粒子群優(yōu)化算法流程圖 粒子群算法的具體表述 PSO 算法 過程我們轉(zhuǎn)化為一個(gè)數(shù)學(xué)問題。公式 ()中的第一部分起到了平衡全局和局部搜索能力的作用：第二部分使粒子擁有的局部搜索能力，能更好的開發(fā)解空間；第三部分體現(xiàn)了粒子間的信息共享，使粒子能在空間更廣闊的探索；只有在這三個(gè)部分的共同作用下粒子才能有效的搜索到最好