【正文】 PSO 算法在求解復(fù)雜的函數(shù)優(yōu)化 問題時對函數(shù)的要求相當(dāng)寬，并不要求函數(shù)有解析解、可微，甚至連續(xù)。特別，若約束集為 nDR? ，則最優(yōu)化問題稱為無約束最優(yōu)化問題 重慶大學(xué)本科學(xué)生畢業(yè)設(shè)計 （論文） 4 基于 PSO 算法的函數(shù)優(yōu)化 16 min ( )nxRfx? (4. 2) 約束 最優(yōu)化問題通常寫為 m in ( ). . ( ) 0 1 , 2 , ,( ) 0 1 , 2 , ,ijfxs t g x i mh x j l???? (4. 3) 當(dāng)目標(biāo)函數(shù)和約束函數(shù)中到少有一個是 x 的非線性函數(shù)，式 和式 稱為非線性規(guī)劃。在第二次世界大戰(zhàn)中，由于軍事上的需要產(chǎn)生了運籌學(xué)，提出了大量不能用古典方法解決的最優(yōu)化問題，從而產(chǎn)生了如線性規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃、網(wǎng)絡(luò)流規(guī)劃等新的方法。 //最大速度限制 if (SwarmAdjust[i].iVec[k] MAX_V) { SwarmAdjust[i].iVec[k] = MAX_V。 //對微粒位置進行調(diào)整 for (i=0。 for (i=0。 i()()。 int iResult = 0。在 UML 中，描述程序的運行順序不再是以往面向過程編程時采用的流程圖了。在 本文中我們就用面向?qū)ο缶幊碳夹g(shù)，在 的環(huán)境下，用 C++語言實現(xiàn) PSO 算法 。 最小速度 minv 的值一般設(shè)定為 maxv? ，作用和 maxv 相同。 異 步 PSO 對 PSO 的改進上述算法的實現(xiàn)基本上都集中在同步處理上即各個粒子的每一次搜索行為都處在 同一個迭代步中進行的 。由 于 PSO 搜索過程很大程度上依賴 Pbest 和 Gbest， 它的搜索區(qū)域這兩個極值的限制 ， 選擇機制的引入將會減弱其影響 。 文獻 [17]中提出的引入簡 單遺傳算法 ， 組合為復(fù)合粒子群優(yōu)化算法 。然而在有些測試函數(shù)的求解過程中，使用收縮因子的 PSO 在給定的迭代次數(shù)內(nèi)無法達到全局極值點。 慣性權(quán)重 ? 應(yīng)不斷減少，從而使得微粒群算法在初期具有較強的全局收斂能力，而晚期具有較強的局部收斂能力。為此， Yuhui Shi[15]提出了帶有慣性權(quán)重的改進微粒群算法。 STEP 3: 對于每個微粒，將其適應(yīng)值與所經(jīng)歷過的最好位置 iP 的適應(yīng)值進行比較 ， 若較好，則將其作為當(dāng)前的最好位置。 為了討論方便，設(shè) ()fX 為最小化的目標(biāo)函數(shù)，則微粒 i 的當(dāng)前最好位置由下式確定 [4] ( ) ( ( 1 ) ) ( )( 1 ) ( 1 ) ( ( 1 ) ) ( )i i iii i iP t f X t P tPt X t f X t P t????? ? ? ? ??若若 (2. 1) 設(shè)群體中的微粒數(shù)為 s ，群體中所有微粒所經(jīng)歷過的最好位置為 ()gPt稱為全局最好位置。 PSO 算法的原理 微粒群算法與其他進化類算法相類似，也采用“群體”與“進化”的概念 。 Angeline Peter J 將進化規(guī)劃中使用的聯(lián)賽選擇法引入 PSO 算法 [12] 。 文獻 [6]給出了一種用模糊規(guī)則動態(tài)調(diào)整慣性權(quán)重方法 ， 通過對當(dāng)前最好性能的評價 (CBPE)對慣性權(quán)重制定相應(yīng)的隸屬度函數(shù)和模糊推理規(guī)則 ，確定慣性權(quán)重的增量 。 PSO 算法 在多峰函數(shù)中也能很快收斂到全局最優(yōu)點，并 且算法的實現(xiàn)也很簡單，所以在短短十幾年來，對它的研究數(shù)量程與日俱增的趨勢。這就是信念的社會性及智能性所在。 自然界中各種生物體均具有一定的群體行為，而人工生命的主要研究領(lǐng)域之一就是探索自然界生物的群體行為，從而在計算機上構(gòu)建其群體模型。 最后結(jié)論表明， PSO 算法在解復(fù)雜函數(shù)的優(yōu)化問題中求解精確 ， 并且 收斂速度快。 本文 表述了 目前國內(nèi)外對 PSO 算法的研究情況，及其產(chǎn)生的背景； 詳細(xì)介紹了 該 算法的原理， 說明了標(biāo)準(zhǔn) PSO 算法的算法流程，在此基礎(chǔ)上提到了改進的 PSO 算法的相關(guān)研究情況；接著運 用 C++編程 語言，利用面向?qū)ο缶幊痰募夹g(shù)用程序 實現(xiàn)了該算法 ；文中 簡要介紹了編程思路，提取了程序中的關(guān)鍵代碼，作為說明 程序 實現(xiàn) 算法 的一部 分內(nèi)容 ； 論文中 還 提到了優(yōu)化問題的 相關(guān) 知識， 并用已經(jīng)實現(xiàn)的 PSO程序?qū)θ齻€經(jīng)典的測試函數(shù)進行了測試 作為本文的主要結(jié)論 。 仿佛數(shù)學(xué)的演繹正在揭 示著生物界進化的神秘過程，而且把它變成一種非常有效的工具。其關(guān)鍵在于如何保證微粒降落在最好解處而不降落在其他解處。 這也是其優(yōu)于其他進化算法的地方。 為此 ， Shi Y 和 Eberhart R 提出一種 修正算法 [5] ， 在傳統(tǒng) PSO 算法的速度更新公式中加入慣性權(quán)重 ， 它決定了微粒先前速度對當(dāng)前速度的影響程度 ， 從而起到平衡算法全局搜索和局部搜索能力的作用 。 文獻 [11]根據(jù)耗散結(jié)構(gòu)的自組織性 ， 提出一種耗散微粒群優(yōu)化算法 (DPSO) ，該算法通過附加噪聲持續(xù)為微粒群引入負(fù)熵 ， 從而使群體不斷進化 。之后， Shi 等 引入慣性權(quán)重 ω 來更好地控制開發(fā) (exploitation)和探索 (exploration)，形成了當(dāng)前的標(biāo)準(zhǔn)版本 [2]。對干最小化問題，目標(biāo)函數(shù)值越小，對應(yīng)的適應(yīng)值越好。 STEP 2: 評價 每個微粒的適應(yīng)值。甚至對于同一個問題而言，進化過程中也要求不同的比例。因此，隨著迭代次數(shù)的增加 。 Eberhart 和 Shi 將分別利用 maxv 和收縮 因 子來往制微粒速度的兩種算法性能做了比較，結(jié)果表明，后者比前者通常具有更好的收斂率。 復(fù)合PSO 將 PSO 控制參數(shù)的選取也作為一個優(yōu)化問題 ， 在搜索過程中逐代優(yōu)選 。 混合 PSO[4] 借鑒遺傳算法的思想 ， 研究者們提出了混 合 PSO 算法 (Hybrid PSO)的概念 。 混合 PSO 算法由于局部搜索能力增強 ， 可找到最優(yōu)點 ， 且可克服早熟收斂問題 ， 但是以計算時間的增加為代價的 。如果 maxv 太高，微粒可能會飛過好解；如果 maxv 太小，微粒不能在局部好區(qū)間之外進行足夠的探索，導(dǎo)致陷入局部優(yōu)值。該算法是一個與現(xiàn)實世界聯(lián)系很緊密的算法，在編程技術(shù)中， 面向?qū)ο缶幊痰膹陌l(fā)點就是用對現(xiàn)實世界中事件抽象出來的對象來組織編寫程序，從而達到方便表現(xiàn)現(xiàn)實世界的目的。上一節(jié)中提到的類圖就是 UML 中的一部分。 1．方法名稱： EvaluateParticleValue 方法功能： 評價適應(yīng)值 int SwarmBird::EvaluateParticleValue(void) { int i。 for (i=0。 int i。 int i。 重慶大學(xué)本科學(xué)生畢業(yè)設(shè)計 （論文） 3 PSO 算法的實現(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])。 早在 17 在歐洲就有人提出了各種極值的問題以及求解方法但由于當(dāng)時無系統(tǒng)的理論，所以發(fā)展緩慢。 最優(yōu)化問題的一般形式為 ..min ( )st D fx? (4. 1) 其中， nxR? 是決策變量， ()fx為目標(biāo)函數(shù)， nDR? 為約束集或可行域。 各種 求解方法中一維搜索法的作用范圍很窄缺點也明顯，二分法只具有線線性收斂速度， Newton 法、 法和 Fibonacci 法只適合于單峰函數(shù)，也即只有局部收斂性；其它方法在求解時又大都要計算函數(shù) 的梯度，在維數(shù)很高的情況下是相當(dāng)麻煩的。 取 函數(shù) ()fx為 21( ) ( 2 0 0 )niif x x???? (4. 4) 則測試最優(yōu)化問題表述 為： 2 ()minxRfx? (4. 5) 函數(shù) ()fx為球面模型，它是單峰 函數(shù)，用來區(qū)分局部優(yōu)化器的優(yōu)劣。 圖 隨機選取坐標(biāo)點實例化微粒群 重慶大學(xué)本科學(xué)生畢業(yè)設(shè)計 （論文） 4 基于 PSO 算法的函數(shù)優(yōu)化 19 執(zhí)行結(jié)果如圖 所示。對比圖 和圖 的結(jié)果可以發(fā)現(xiàn)，最小值相差 ) ? ? ? ?，位置 Y 方向相差 ，均在誤差允許范圍內(nèi)，故我們認(rèn)為在二維情況下用 PSO 算法解函數(shù) Rastrigrin 是可取的。 重慶大學(xué)本科學(xué)生畢業(yè)設(shè)計 （論文） 4 基于 PSO 算法的函數(shù)優(yōu)化 23 020040060080002004006008000200400600800xR o s e n b r o c k （香蕉）函數(shù)三維情況粒子位置圖yz 圖 Rosenbrock 函數(shù)三維情況 其中每條連續(xù)的線表示一個粒子在三維空間中的一條運動軌跡。從理論上講，演化規(guī)劃具有更多的機會在優(yōu)化 點附近開發(fā)，而 PSO 則有更多的機會更快地飛到有更好解的區(qū)域，如果“意識”能提供有用的信息。在此謹(jǐn)向?qū)熤乱宰钪孕牡母兄x。 本文在對標(biāo)準(zhǔn)微粒群算法進行分析的基礎(chǔ)上用 C++語言編程實現(xiàn)了其算法。如果所討論的函數(shù)受到嚴(yán)重的噪音干擾而呈現(xiàn)非常不規(guī)則的形狀，同時 所求的不一定是精確的最優(yōu)值，則 PSO 算法能得到很好的應(yīng)用。其最小值m in ( ) 19 .6 68 01 8fx ? ， 最小值 位置 (316 201 201)， ， 。vv? ? ? 復(fù)雜 函數(shù)優(yōu)化 由一小節(jié)我們可以看出，算法的正確性。在文獻 [19]中，推薦第二組， 故在下面的實驗中我們 取權(quán)重系數(shù)為重慶大學(xué)本科學(xué)生畢業(yè)設(shè)計 （論文） 4 基于 PSO 算法的函數(shù)優(yōu)化 18 ?? ， 1 ? ， 2 ? 。由 小節(jié)部分可以看出，最大速度 maxv 決定當(dāng)前 位置與最好位置之間的區(qū)域精度， maxv 的取值對求解結(jié)果會有很大的影響。 最優(yōu)化問題 的 解法 線性規(guī)劃是最優(yōu)化方法中理論完整、方法成熟、應(yīng)用最廣泛的一個分支。 由于工程與技術(shù)的復(fù)雜化、大型化和精密化，經(jīng)濟計劃與管理科學(xué)化與綜合化，使得一個環(huán)節(jié)決策的好壞，對經(jīng)濟效果有著重大的影響。 } } return iResult。 for (k=0。 } } return iResult。 jDIM。 i++) { 重慶大學(xué)本科學(xué)生畢業(yè)設(shè)計 （論文） 3 PSO 算法的實現(xiàn) 12 //調(diào)用 bird 的 EvaluateParticleValue 方法 SwarmAdjust[i].EvaluateParticleValue()。我們所完成的系統(tǒng)在粒子處于二維空間時，對其運動進行了可視化顯示。 圖 bird 類圖 屬性說明： DIM ：空間維數(shù) Pos[DIM] ： bird 當(dāng)前處于的位置 Vec[DIM] ： bird 當(dāng)前的速度 PbestPosition[DIM] ： bird 局部最優(yōu)位置 dPbestValue ： bird 局部最優(yōu)值 fValue ： bird 評價值 方法說明： EvaluateParticleValue(void)() ：計算 bird 評價值 Init() ：初始化 bird 對象 另外抽象出的一個類是 SwarmBird 也即鳥群，它包含了粒子群中的所有粒重慶大學(xué)本科學(xué)生畢業(yè)設(shè)計 （論文） 3 PSO 算法的實現(xiàn) 10 子，并具有調(diào)整粒子位置，取得最優(yōu)值的各個方法，這些方法與標(biāo)準(zhǔn)算法流程中的步驟是一一對應(yīng)的。慣性權(quán)重 ? 使微粒