【正文】 （ b） sPSO 算法 0 50 100 1506420246最優(yōu)個體適應(yīng)度進(jìn)化代數(shù)適應(yīng)度 （ b） tPSO 算法 （ d） tsPSO 算法 由（ 1）（ 2）（ 3）中的曲線（ a）和（ c）可以看出， sPSO 比 bPSO 在收斂精度上有了非常顯著的提高，說明了 sPSO 對應(yīng) 方程式（ ）的正確性和高效性；由曲線（ a）和曲線（ c）比較可以看出， tPSO 比 bPSO 在擺脫局部極值能力 、進(jìn)化后期收斂速度和收斂精度等方面具有顯著提高，說明了極值擾動算子具有很好的優(yōu)化性能；曲線（ d）具有最高的0 20 40 60 80 100 120 140642024最優(yōu)個體適應(yīng)度進(jìn)化代數(shù)適應(yīng)度0 20 40 60 80 100 120 140642024最優(yōu)個體適應(yīng)度進(jìn)化代數(shù)適應(yīng)度0 20 40 60 80 100 120 14064202468最優(yōu)個體適應(yīng)度進(jìn)化代數(shù)適應(yīng)度收斂精度和最快的收斂速度，在經(jīng)過 15~60 次進(jìn)化迭代后基本上達(dá)到了目標(biāo)精度，說明了tsPSO 算法的實(shí)用性能。 圖 Sphere 函數(shù)的 3D 圖形 （ 2） Rosenbrock 函數(shù) ： 2 2 2211( ) (1 0 0 ( ) ( 1 ) )ni i iif x x x x??? ? ? ?? 這是一個單峰函數(shù)，但并不易于求解。 本文采用進(jìn)化停滯步數(shù) t作為觸發(fā)條件 ,對個體極值 0p 和全局極值 gp 同時進(jìn)行隨機(jī)擾動 .極值擾動算子為 000 3 0 4。但在優(yōu)化后期中收斂速度變得緩慢 ,因而導(dǎo)致收斂精度低。除 idp 和 gdp 對搜索空間各維的聯(lián)系以外 ,每維的更新相互獨(dú)立。 ? 較大時，前一速度影響較大，全局搜索能力較 強(qiáng)，局部搜索能力較弱， ? 較小時，前一速度影響較小，局部搜索能力較強(qiáng)，全局搜索能力減弱。在粒子相互作用下，算法有能力達(dá)到新的搜索空間。 算法分析 參數(shù)設(shè)置是粒子群優(yōu)化算法研究的一項重要內(nèi)容，它對算法的優(yōu)化結(jié)果有較大的影響。當(dāng)粒子的飛行速度足夠小或達(dá)到預(yù)設(shè)的迭代步數(shù)時，算法停止迭代，輸出最優(yōu)解。 第 2 章 粒子群優(yōu)化算法 基本 粒子群算法 粒子群優(yōu)化 (Particle Swarm Optimization，簡稱 PSO)算法的基本思想是通過群體中個體之間的協(xié)作和信息共享來尋找最優(yōu)解，它包含有進(jìn)化計算和群集智能的特點(diǎn)。自 PSO 提出以來，由于它的計算快速性和算法本身的易實(shí)現(xiàn)性，引起了國際上相關(guān)領(lǐng)域眾多學(xué)者的關(guān)注和研究，其研究大致 可以 分為：算法本身 參數(shù)選取、拓?fù)浣Y(jié)構(gòu)、與其他進(jìn)化技術(shù)的融合及應(yīng)用。 無論是從理論研究還是應(yīng)用研究的角度分析， SI 理論及應(yīng)用研究都是具有重要學(xué)術(shù)意義和現(xiàn)實(shí)價值的。 經(jīng)典的優(yōu)化算法通常采用局部搜索方法，這些局部搜索方法要么是與特定問題相關(guān)，要么是局部搜索方法的變型，但它們有一個共同的特點(diǎn)就是通過迭代來提高問題域中唯一的候選解的近似程度。對于連續(xù)問題，該方法要求先對其進(jìn)行離散化處理，這樣就有可能產(chǎn)生離散誤差而永遠(yuǎn)達(dá)不到最優(yōu)解。 優(yōu)化問題中經(jīng)常用到的概念： 1. 解之間的距離測度函數(shù) 設(shè) A,f是某優(yōu)化問題的一個實(shí)例，定義 Dist： A A R??? 為計算該優(yōu)化問題中的兩個解之間的距離測 度函數(shù)。粒子群收斂于局部極值的根本原因在于進(jìn)化后期沒有找到優(yōu) 于全局最優(yōu)的位置，對個體極值和全局極值進(jìn)行隨機(jī)擾動，提出了帶極值擾動的粒子群優(yōu)化算法。 論文的主要工作有： （ 1） 對研究 PSO 算法相關(guān)基礎(chǔ)知識進(jìn)行回顧，主要是優(yōu)化問題和群體智能 。 優(yōu)化包括尋找最小值和最大值兩種情況 ?？偟膩碚f，求最優(yōu)解或近似最優(yōu)解的方法主要有三種：枚舉法、啟發(fā)式算法和搜索算法。 隨著計算機(jī)科學(xué)和技術(shù)的發(fā)展，從根本上改變了人類的生產(chǎn)和生活。 SI 的目的并不是忠實(shí)的模擬自然現(xiàn)象，而是利用他們的某些特點(diǎn)去解決實(shí)際問題。因此，對粒子群優(yōu)化算法具體實(shí)例應(yīng)用研究是 值得的、有意義的。混合 PSO 是改進(jìn)研究的熱點(diǎn)，其發(fā)展非常迅速。 基本原理 Eberhart 和 Kennedy 提出的原始 粒子群優(yōu)化算法可描述如下：設(shè)在一個 D 維的目標(biāo)搜索空間中，有 m個粒子組成一個群落，第 i 個粒子的位置用向量12, , , Di i i ix x x x??? ?????表示，飛行速度用12, , , Di i i iv v v v??? ?????表示，第 i 個粒子搜索到的最優(yōu)位置為 12, , , Di i i ip p p p??? ?????，整個群體搜索到的最優(yōu)位置為12, , , Dg g g gp p p p??? ?????，則用下式更新粒子的速度和位置： id 1 1v ( 1 ) ( )idt v t c r? ? ? id id 2 2 gd id（ p x (t) ） +c r（ p x (t) ） （ ） id id( 1 ) v ( 1 )x t t? ? ?idx (t) + （ ） 式中， i=1,2???m，分別表示不同的粒子。 （ 3） 計算兩個點(diǎn)函數(shù)值就是粒子群算法中的適應(yīng)值，計算用的函數(shù)就是粒子群算法中的適應(yīng)度函數(shù)。 1c 和 2c 分別調(diào)節(jié)粒子向個體最優(yōu)和群體最優(yōu)方向飛行的最大步長，決定粒子個體經(jīng)驗(yàn)和群體經(jīng)驗(yàn)對粒子自身運(yùn)行軌跡的影響，反映粒子群體之間的信息交流。 標(biāo)準(zhǔn)粒子群算法 （ bPSO） 為了更好的控制算法的尋優(yōu)能力， Shi 和 Eberhart 在記憶部分引入具有慣性權(quán)重，于是公式 (2． 1)和 (2． 2)可以修改成為以下兩個新的公式 ： 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 算法。另外 ,從式()～ 式 ()來看 ,位置與速度直接進(jìn)行加法運(yùn)算 ,而沒有粒子運(yùn)動時間概念 ,這也不符合現(xiàn)實(shí)生活中的運(yùn)動規(guī)律： x=vt。 由于 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??? ? ? ?????? ? ? ?? ? ? ? ?。*p ,經(jīng)歷新的搜索路徑和領(lǐng)域 ,因此發(fā)現(xiàn)更優(yōu)解的概率較大。 搜索空間 100 100ix? ? ? 。 具體參數(shù)設(shè)置為： 種群規(guī)模設(shè)為 m=15，粒子的維數(shù)為Dim=30，最大迭代步數(shù)為 150； max 1v ? ； 122cc??； 0 3。 MaxDT=1000。 y(i,:)=x(i,:)。 實(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。 搜索空間 100 100ix? ? ? 。 帶極值擾動的簡化粒子群優(yōu)化算法 sPSO 去掉了 PSO 進(jìn)化方程的粒子速度項而使原來的二階微分方程簡化為一階微分方程，僅由粒子位置控制進(jìn)化過程，避免了由粒子速度項引起的粒子發(fā)散而導(dǎo)致后期收斂變慢和精度低問題。 文獻(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 。第 2 項為“認(rèn)知 (cognition)”部分 ,表示粒子對自身的思考 。這種條件下，粒子群將收縮到當(dāng)前全局最好位置，更像一個局部算法。不過在文獻(xiàn)中也其他的取值，但是一般 1c 等于 2c ，并且范圍在 [0,4]之間。粒子的維數(shù)是根據(jù)具體問題的解空間的維數(shù)來確定的。該函數(shù)的圖形如下： 圖 函數(shù) 1 cos 3 xy x e?? ? ? 在 [0,4]區(qū)間上的曲線 當(dāng) x=，達(dá)到最大值 y=。 PSO 算法就是從這種模型中得到啟示并用于解決優(yōu)化問題的。 隨后，另一個參數(shù)稱之為收縮因子 (Contraction Factor)的系數(shù)被引入，目的是希望 PSO可以收斂。 首先，對任何一個算法，如果不從理論上對其研究，那對其行為將無法徹底剖析。 James Kennedy 和 Russell 在 2021 年出版了《 Swarm Intelligence》，是群智能發(fā)展的一個重要里程碑，因?yàn)榇藭r已有一些群智能理論和方法得到了應(yīng)用。該方法雖然保證不了一定能夠得到問題的最優(yōu)解，但若適當(dāng)?shù)乩靡恍┲R，就可近似的使解的質(zhì)量和求解效率一直能夠達(dá)到較好的平衡。 4. 全局最優(yōu) 設(shè) A,f是某優(yōu)化問題的一個實(shí)例，若 eN 滿足 ( *) ( )f x f x? ， xA?? ，則稱 eN 為在 A上的全局最優(yōu)。工程中很多的實(shí)際問 題在進(jìn)行數(shù)學(xué)建模后，都額可以抽象為一個組合優(yōu)化問題。 粒子群優(yōu)化算法及改進(jìn)的比較研究 摘要 粒子群優(yōu)化（ Particle Swarm Optimization， PSO）算法是一種優(yōu)化計算技術(shù)，由 Eberhart 博士和 Kennedy 博士提出，它源于對鳥群和魚群群體覓食運(yùn)動行為的模擬。美國工程院院士哈佛大學(xué)何毓琦（ Yuchi Ho）教授指 出“任何控制與決策問題本質(zhì)均可以歸結(jié)為優(yōu)化問題”。對于確定的 eN ，若 eN 滿足( *) ( )f x f x? ， *()x Ne x?? ，則稱 eN 為在 A 上的局部最優(yōu)。尋找一種搜索算法，該算法在可行解空間的一個子空間內(nèi)進(jìn)行搜索操作，以找到問題的最優(yōu)解或近似最優(yōu)解。 1999年， Bonabeau、 Dorigo 和 Theraulaz 在 《 Swarm Intelligence： From Natural to Artificial Systems》 一文中對群智能進(jìn)行了詳細(xì)的論述和分析，給出了群智能算法的一種定義：任何一種由昆蟲群體或其它動物社會行為機(jī) 制而激發(fā)設(shè)計出的算法或分布式解決問題的策略均屬于群智能算法。因而， PSO 算法從誕生起， 就引起了國內(nèi)外學(xué)者的廣泛關(guān)注，并掀起了該方向的研究熱潮，且在諸多領(lǐng)域得到了成功應(yīng)用，但是， PSO 的發(fā)展歷史尚短，在理論基礎(chǔ)與應(yīng)用推廣上都還存在一些問題，有待解決。動態(tài)慣性權(quán)重可以在 PSO 搜索過程中線性變化，亦可根據(jù)PSO 性能的某個測度而動態(tài)改變，比如模糊規(guī)則系統(tǒng)。當(dāng)個體察覺其它個體的信念較好的時候，它將進(jìn)行適應(yīng)性地調(diào) 整 。尋找函數(shù) 1 cos 3 xy x e?? ? ? 的在 [0,4]最大值。 （ 2） 粒子的維數(shù) D： D 也是整型參數(shù)。因此， Shi 和 Eberhart 建議，為了平衡隨機(jī)因素的作用，一般情況下設(shè)置 122cc??，大部分算法都采用這個建議。如果 ? =0，則粒子速度只取決于它當(dāng)前位置 ip 和曲 gp 的加權(quán)中心。 簡化粒子群優(yōu)化算法（ sPSO) 根據(jù)第 節(jié)中的分析 ,不含速度項的粒子群優(yōu)化方程可以簡化為 : id 1 1( 1 ) ( )idx t x t c r?? ? ? id id 2 2 gd id（ p x (t) ） +c r（ p x (t) ）