【正文】 2 PSO 算法 3 2 PSO 算法 Kennedy[1]和 Eberhart 在 1995 年的 lEEE 國際神經(jīng)網(wǎng)絡(luò)學(xué)術(shù)會(huì)議上正式發(fā)表了題為 “ Particle Swarm Optimization” 的文章，標(biāo)志著微粒群算法的誕生。人們通過對(duì)動(dòng)物社會(huì)行為的觀察，發(fā)現(xiàn)在群體中對(duì)信息的社會(huì)共享有利于在演化中獲得優(yōu)勢， 并以此作為開發(fā) PSO 算法的基礎(chǔ)。之后， Shi 等 引入慣性權(quán)重 ω 來更好地控制開發(fā) (exploitation)和探索 (exploration)，形成了當(dāng)前的標(biāo)準(zhǔn)版本 [2]。同樣也是依據(jù)個(gè)體（微粒）的適應(yīng)值大小進(jìn)行操作。該飛行速度由個(gè)體的飛行經(jīng)驗(yàn)和群體的飛行經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)調(diào)整。 12( , , , )i i i inV v v v? 為微粒 i 的當(dāng)前飛行速度。對(duì)干最小化問題，目標(biāo)函數(shù)值越小，對(duì)應(yīng)的適應(yīng)值越好。則 [4] 1 2 1 2( ) { ( ) , ( ) , , ( ) } | ( ( ) ) m in{ ( ( ) ) , ( ( ) ) , , ( ( ) ) }g n g nP t P t P t P t f P t f P t f P t f P t?? (2. 2) 有了以上定義，基本微粒群算法的進(jìn)化方程可描述為 [4]： 重慶大學(xué)本科學(xué)生畢業(yè)設(shè)計(jì) （論文） 2 PSO 算法 4 1 1 2 2( 1 ) ( 1 ) ( ( ) ( ) ) ( ( ) ( ) )ij ij j ij ij j gj ijv t v t c r p t x t c r p t x t? ? ? ? ? ? ? (2. 3) ( 1 ) ( ) ( 1 )ij ij ijx t x t v t? ? ? ? (2. 4) 其中 ： 下標(biāo) “ j ” 表示微粒的第 j 維， “ i ” 表示微粒 i ， “ t ” 表示第 t 代， 12,cc為 加速常數(shù)，通常在 0～ 2 間取值， 12~ ( 0 ,1), ~ ( 0 ,1)r U r U為兩個(gè)相互獨(dú)立的隨機(jī)函數(shù)。 2c 調(diào)節(jié)微粒向全局最好位置飛行的步長。如果問題的搜索空間限定在 max max[ , ]xx? 內(nèi)，則可設(shè)定 m a x m a x , k x k? ? ? ?。 STEP 2: 評(píng)價(jià) 每個(gè)微粒的適應(yīng)值。 STEP 4: 對(duì)每個(gè)微粒，將其適應(yīng)值與全局所經(jīng)歷的最好位置 gP 的適應(yīng)值進(jìn)行比較，若較好，則將其 作為當(dāng)前的全局最好位置。 STEP 6: 如未達(dá)到結(jié) 束 條件通常為足夠好的適應(yīng)值或達(dá)到一個(gè)預(yù)設(shè)最大代數(shù)（ maxG ） 則返回步驟 STEP 2。 3) 對(duì)任意 ,ij，在 max max[ , ]vv? 內(nèi)服從均勻分布產(chǎn)生 ijv 。甚至對(duì)于同一個(gè)問題而言，進(jìn)化過程中也要求不同的比例。其進(jìn)化方程為 [15] 重慶大學(xué)本科學(xué)生畢業(yè)設(shè)計(jì) （論文） 2 PSO 算法 5 1 1 2 2( 1 ) ( ) ( ( ) ( ) ) ( ( ) ( ) )ij ij j ij ij g j ijv t v t c r p t x t c r p t x t?? ? ? ? ? ? (2. 5) ( 1 ) ( ) ( 1 )ij ij ijx t x t v t? ? ? ? (2. 6) 當(dāng)慣性權(quán)重 1?? 時(shí)，式 與式 相同從而表明帶慣性權(quán)重的微粒群算法是基本微粒群算法的擴(kuò)展。 慣性權(quán)重 ? 表明微粒原先的速度能在多大程度上得到保留。 但文獻(xiàn) [15]的實(shí)驗(yàn)結(jié)果表明，1?? 要好一些。因此，隨著迭代次數(shù)的增加 。 帶有收縮因子的微粒群算法 在 Clerc[16,17]的研究中，提出了收縮因子的概 念。通過正確地選擇這些控制參數(shù) 。接下來首先討論一個(gè)與帶有收縮因子的微粒群算法相關(guān)的收斂模式特例。 Eberhart 和 Shi 將分別利用 maxv 和收縮 因 子來往制微粒速度的兩種算法性能做了比較，結(jié)果表明，后者比前者通常具有更好的收斂率。按用 Eberhart 和 Shi 的觀點(diǎn) 。為了降低這種影 響 ，他們建議在使用收縮因子時(shí)首先對(duì)算法進(jìn)行限定，比如設(shè) 參數(shù) max maxvx? ，或者預(yù)先設(shè)置搜素空間的大小。 復(fù)合 PSO 與其 他進(jìn)化算法類似 ， PSO 算法也有一些控制自身特性的參數(shù) ， 它們與被優(yōu)化的問題相關(guān) ， 其設(shè)置將嚴(yán)重影響算法的尋優(yōu)和收斂特性 。 復(fù)合PSO 將 PSO 控制參數(shù)的選取也作為一個(gè)優(yōu)化問題 ， 在搜索過程中逐代優(yōu)選 。 實(shí)驗(yàn)結(jié)果表明這種復(fù)合 PSO 的搜索精度有明顯提高 ， 但計(jì)算時(shí)間有所增加 ， 收斂速度有所下降 。 對(duì)這個(gè)問題提出的 策略有 ： 空間鄰域法 ， 鄰域拓?fù)浞?， 社會(huì)趨同法等 。 直接控 制 PSO 算 法的參數(shù)來保持種群多樣性為前饋策略 ， 根據(jù)種群進(jìn)化過程多樣性測度函數(shù)來保持種群多樣性為反饋策略 。 混合 PSO[4] 借鑒遺傳算法的思想 ， 研究者們提出了混 合 PSO 算法 (Hybrid PSO)的概念 。 混合 PSO 算法就是將基本 PSO 算法和選擇機(jī)制相結(jié)合而得到的 。 Noel 等人提出的一個(gè)利用梯度信息的混合 PSO 算法 ， 其主要思想是利用梯度信息使 算法搜索到局部最優(yōu)點(diǎn) ， 該方法的最大特點(diǎn)是不需要鄰居結(jié)構(gòu) ， 可節(jié)省標(biāo)準(zhǔn) PSO 算法需要比較的計(jì)算量 ， 加快了收斂速度 。Parsopoulos[18]等人提出采用非線性單純形方法 (NSM) 來初始化 PSO。 混合 PSO 算法由于局部搜索能力增強(qiáng) ， 可找到最優(yōu)點(diǎn) ， 且可克服早熟收斂問題 ， 但是以計(jì)算時(shí)間的增加為代價(jià)的 。 粒子在很大程度上失去了獨(dú)立性 ，以至于最優(yōu)粒子的信息不能及時(shí)的共享 。 實(shí)驗(yàn)表明 ， 這種異步模式的收斂速度 較同步模式有顯著的提高 [16]。對(duì)算法的改進(jìn)研究方向主要是尋找合適的權(quán)重參數(shù)值 和合適的結(jié)構(gòu)，其他主要的改進(jìn)方向還有離散化和多目標(biāo)化 。如果 maxv 太高，微?？赡軙?huì)飛過好解；如果 maxv 太小，微粒不能在局部好區(qū)間之外進(jìn)行足夠的探索，導(dǎo)致陷入局部優(yōu)值。 該限制有 3個(gè)目的： 1)防止計(jì)算溢出； 2)實(shí)現(xiàn)人工學(xué)習(xí)和態(tài)度轉(zhuǎn)變； 3)決定問題空間搜索的粒度。慣性權(quán)重 ? 使微粒保持運(yùn)動(dòng)慣性，使其有擴(kuò)展搜索空間的趨勢，有能力探索新的區(qū)域。低的值允許微粒在被拉回之前可以在目標(biāo)區(qū)域外徘徊，而高的值則導(dǎo)致微粒突然的沖向或越重慶大學(xué)本科學(xué)生畢業(yè)設(shè)計(jì) （論文） 2 PSO 算法 8 過目標(biāo)區(qū)域 [2]。該算法是一個(gè)與現(xiàn)實(shí)世界聯(lián)系很緊密的算法，在編程技術(shù)中， 面向?qū)ο缶幊痰膹陌l(fā)點(diǎn)就是用對(duì)現(xiàn)實(shí)世界中事件抽象出來的對(duì)象來組織編寫程序，從而達(dá)到方便表現(xiàn)現(xiàn)實(shí)世界的目的。 按照現(xiàn)實(shí)情況，我們把微粒群中的粒子抽象成系統(tǒng)中的最小單位，命名為bird（ 取鳥群之鳥之意）。 圖 bird 類圖 屬性說明： DIM ：空間維數(shù) Pos[DIM] ： bird 當(dāng)前處于的位置 Vec[DIM] ： bird 當(dāng)前的速度 PbestPosition[DIM] ： bird 局部最優(yōu)位置 dPbestValue ： bird 局部最優(yōu)值 fValue ： bird 評(píng)價(jià)值 方法說明： EvaluateParticleValue(void)() ：計(jì)算 bird 評(píng)價(jià)值 Init() ：初始化 bird 對(duì)象 另外抽象出的一個(gè)類是 SwarmBird 也即鳥群，它包含了粒子群中的所有粒重慶大學(xué)本科學(xué)生畢業(yè)設(shè)計(jì) （論文） 3 PSO 算法的實(shí)現(xiàn) 10 子，并具有調(diào)整粒子位置，取得最優(yōu)值的各個(gè)方法，這些方法與標(biāo)準(zhǔn)算法流程中的步驟是一一對(duì)應(yīng)的。 圖 SwarmBird 類圖 屬性說明： w ：權(quán)重參數(shù) ? c1 ：權(quán)重參數(shù) 1c c2 ：權(quán)重參數(shù) 2c gbest ：全局最優(yōu)值的索引 方法說明： InitSwarm(bird b) ：用參數(shù) b 初始化 SwarmBird 對(duì)象 SetPara(CSetDlg amp。上一節(jié)中提到的類圖就是 UML 中的一部分。在 UML 中，我們用時(shí)序圖來表現(xiàn)系統(tǒng)中各個(gè)類的調(diào)用和被調(diào)用關(guān)系。我們所完成的系統(tǒng)在粒子處于二維空間時(shí)，對(duì)其運(yùn)動(dòng)進(jìn)行了可視化顯示。 : sy st e m : S w a r m B i r d : b i r d1 : I n i t S w a r m ( b i r d b )3 : S e t P a r a ( C S e t D l g amp。 1．方法名稱： EvaluateParticleValue 方法功能： 評(píng)價(jià)適應(yīng)值 int SwarmBird::EvaluateParticleValue(void) { int i。 for (i=0。 i++) { 重慶大學(xué)本科學(xué)生畢業(yè)設(shè)計(jì) （論文） 3 PSO 算法的實(shí)現(xiàn) 12 //調(diào)用 bird 的 EvaluateParticleValue 方法 SwarmAdjust[i].EvaluateParticleValue()。 } 2．方法名稱： GetPartParticleValue 方法功能： 取得每個(gè)粒子的局部最優(yōu)值，并將它保存在容器 SwarmAdjust中 int SwarmBird::GetPartParticleValue(void) { int i。 for (i=0。 i++) { if(SwarmAdjust[i].fValue SwarmAdjust[i].dPbestValue) { //給局部最佳變量賦值 SwarmAdjust[i].dPbestValue = SwarmAdjust[i].fValue。 jDIM。 } } } return iResult。 int i。 i() ()。 } } return iResult。 double fRand1 = 。 int i。 i() ()。 for (k=0。 k++) { fRand1 = (double)rand() / (double)RAND_MAX。 重慶大學(xué)本科學(xué)生畢業(yè)設(shè)計(jì) （論文） 3 PSO 算法的實(shí)現(xiàn) 14 //速度調(diào)整 SwarmAdjust[i].iVec[k] = w * SwarmAdjust[i].iVec[k] + c1 * fRand1 * (SwarmAdjust[i].iPbestPosition[k] SwarmAdjust[i].iPos[k]) + c2 * fRand2 * (SwarmAdjust[gbest].iPbestPosition[k] SwarmAdjust[i].iPos[k])。 } //最小速度限制 if (SwarmAdjust[i].iVec[k] MIN_V) { SwarmAdjust[i].iVec[k] = MIN_V。 } } return iResult。即期望 達(dá)到投資最少、利潤最大、時(shí)間最省、產(chǎn)量最高、質(zhì)量最好等目標(biāo)，這些目標(biāo)都可以由最優(yōu)化方法來實(shí)現(xiàn)。 早在 17 在歐洲就有人提出了各種極值的問題以及求解方法但由于當(dāng)時(shí)無系統(tǒng)的理論，所以發(fā)展緩慢。此后，最優(yōu)化理論和方法逐漸得到豐富和發(fā)展。 由于工程與技術(shù)的復(fù)雜化、大型化和精密化，經(jīng)濟(jì)計(jì)劃與管理科學(xué)化與綜合化，使得一個(gè)環(huán)節(jié)決策的好壞，對(duì)經(jīng)濟(jì)效果有著重大的影響。 最 優(yōu)化 問題的提法 尋找最優(yōu)化方案的方法稱為最優(yōu)化方法是用數(shù)學(xué)的結(jié)果和計(jì)算機(jī)的數(shù)值計(jì)算的方法去尋找一個(gè)最佳的均攤，而不必列舉和 計(jì)算所有可能選擇。 最優(yōu)化問題的一般形式為 ..min ( )st D fx? (4. 1) 其中， nxR? 是決策變量， ()f