【正文】 ..................................... 28 參考文獻(xiàn) ....................................................................................................................................... 30 致謝 ............................................................................................................................................... 32 華北電力大學(xué)本科畢業(yè)設(shè)計（論文） 1 第 1 章 緒 論 優(yōu)化理論與方法是一門應(yīng)用性很強(qiáng)的學(xué)科，用于研究某些基于數(shù)學(xué)描述問題的最優(yōu)解。優(yōu)化成為一門獨立的學(xué)科是在 20 世紀(jì) 40 年代末，一方面，需要為實際生產(chǎn)中涌現(xiàn)的復(fù)雜優(yōu)化問題提供快速而實用的優(yōu)化算法；另一方面，包括泛函分析在內(nèi)的數(shù)學(xué)理論的發(fā)展也進(jìn)一步奠定了優(yōu)化理論的理論基礎(chǔ)。 優(yōu)化包括尋找最小值和最大值兩種情況 。距離測度函數(shù)的定義與優(yōu)化問題決策變量的表示 有很大關(guān)系，與優(yōu)化算法的性能也有非常大的關(guān)系。對于任意給定的 R? ?? ， eN 的數(shù)學(xué)描述為： :2{ | ( , ) }AeNAv x A D is t x v ??? ? ? 3. 局部最優(yōu) 設(shè) A,f是某優(yōu)化問題的一個實例， eN 為鄰域函數(shù)。 對于給定的 R? ?? ，集合 C={ : | ( x ) ( x* )| }x A f f ?? ? ?被稱為可接受解的集合?？偟膩碚f，求最優(yōu)解或近似最優(yōu)解的方法主要有三種：枚舉法、啟發(fā)式算法和搜索算法。另外，當(dāng)枚舉空間比較大時，該方法的求解效率比較低。 3)搜索算法。確定性搜索算法在尋優(yōu)過程中，一個搜索點到另一個搜索點轉(zhuǎn)移有確定的轉(zhuǎn)移方法和轉(zhuǎn)移關(guān)系，因而其過程可再現(xiàn)，其不足在于尋優(yōu)結(jié)果與初值有關(guān)，初值選取不當(dāng)往往有可能使搜索永遠(yuǎn)達(dá)不到最優(yōu)點。 隨著計算機(jī)科學(xué)和技術(shù)的發(fā)展，從根本上改變了人類的生產(chǎn)和生活。這就決定了經(jīng)典算法只能適用于求解小規(guī)模且定義非常明確的問題。 群體智能概述 群智能的概念最早是由 Beni、 Hackwood 和 Wang 在分子自動機(jī)系統(tǒng)中提出的。SI 已成為有別于傳統(tǒng)人工智能中連接主義、行 為主義和符號主義的一種新的關(guān)于智能的描述方法。 SI 的目的并不是忠實的模擬自然現(xiàn)象，而是利用他們的某些特點去解決實際問題。由于 SI 理論依據(jù)是源于對生物群落社會性的模擬，因此其相關(guān)數(shù)學(xué)分析還比較薄弱，這就導(dǎo)致了現(xiàn)有研究還存在一些問題。 PSO 與遺傳算法有些相似之處，首先，它們都是基于群體的優(yōu)化技術(shù)，亦即搜索軌道有多條，顯示出良好的并行性，其次，無需梯度信息，只需利用目標(biāo)的取值信息、具有很強(qiáng)的通用性，但是， PSO 比 GA 更簡單、操作更 方便。因此，對粒子群優(yōu)化算法收斂模型的建立和收斂性分析是十分有益的，也為以后的進(jìn)一步研究與新算法的提出都將提供很好的明示。因此，對粒子群優(yōu)化算法具體實例應(yīng)用研究是 值得的、有意義的。下面就這三個方面的研究情況做簡單的介紹。動態(tài)慣性權(quán)重能夠獲 得比固定值更為好的尋優(yōu)結(jié)果。 為了提高算法收斂的全局性，保證微粒的多樣性是其關(guān)鍵， PSO 算法有全局版本 PSO和局部版本 PSO，這兩種版本的差別在于粒子的鄰域不同，即與各粒子直接連 接的粒子數(shù)不同，局部 PSO 的粒子，鄰域僅為其兩邊有限的幾個粒子，而全局 PSO 的鄰域則為 該群體所有粒子，如此一來，全局 PSO 可看成是局部 PSO 的特殊情況，研究發(fā)現(xiàn)，全局 PSO收斂較快，但易陷入局部極??；而局部 PSO 可搜索到更優(yōu)的解，但速度稍慢?；旌?PSO 是改進(jìn)研究的熱點，其發(fā)展非常迅速。起初Kennedy 和 Eberhart 只是設(shè)想模擬鳥群覓食的過程，但后來發(fā)現(xiàn) PSO 算法是一種很好的優(yōu)化工具。這是一種信息共享機(jī)制，在心理學(xué)中對應(yīng)的是在尋求一致的認(rèn)知過程中，個體往往記住它們的信念，同時考慮其它個體的信念?！笆澄?” 就是優(yōu)化問題的最優(yōu)解。 基本原理 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，分別表示不同的粒子。 從社會學(xué)的角度來看，公式 ()的第一部分是“記憶”項，是粒子先前的速度，表示粒子當(dāng)前的速度要受到上一次速度的影響；公式第二部分是“自身認(rèn)知”項，是從當(dāng)前點指向粒子自身最好點的一個矢量，表示粒子的動作來源于自己經(jīng) 驗的部分，可以認(rèn)為是粒子自身的思考；公式的第三部分是“群體認(rèn)知’’項，是一個從當(dāng)前點指向種群最好點的矢量，反映了粒子間的協(xié)同合作和信息共享。 基本粒子群優(yōu)化算法的流程圖 如 圖 21： 圖 21 基本粒子群優(yōu)化算法流程圖 粒子群算法的具體表述 PSO 算法 過程我們轉(zhuǎn)化為一個數(shù)學(xué)問題。下面這些點就會按照一定的公式更改自己的位置，到達(dá)新位置后，再計算這兩個點的值，然后再按照一定的公式更新自己的位置。 （ 3） 計算兩個點函數(shù)值就是粒子群算法中的適應(yīng)值，計算用的函數(shù)就是粒子群算法中的適應(yīng)度函數(shù)。對于不同的優(yōu)化問題，在取得最優(yōu)結(jié)果時參數(shù)的設(shè)置往往是不完全相同的。然而，群體過大將導(dǎo)致計算時間大幅增加，并且當(dāng)群體數(shù)目增長至一定水平時，再增加粒子數(shù)目將不再有顯著的作用。如果 maxv 較大，粒子的探索能力強(qiáng)，但是容易飛過優(yōu)秀的搜索空間，錯過最優(yōu)解；如果 maxv較小，粒子的開發(fā)能力強(qiáng)，但是容易陷入局部最優(yōu)，可能使粒子無法移動足夠遠(yuǎn)的距離跳出局部最優(yōu)，從而不能到達(dá)解空間中的最佳位置。 1c 和 2c 分別調(diào)節(jié)粒子向個體最優(yōu)和群體最優(yōu)方向飛行的最大步長，決定粒子個體經(jīng)驗和群體經(jīng)驗對粒子自身運(yùn)行軌跡的影響，反映粒子群體之間的信息交流。其收斂速度比標(biāo)準(zhǔn)算法更快，但碰到復(fù)雜問題，比標(biāo)準(zhǔn)算法更容易陷入局部極點。此時，由于粒子只能搜索有限的區(qū)域，故很難找到好解。 （ 6） 粒子空間的初始化：這是由具體問題決定的。 標(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 算法。 初始時， Shi 將慣性權(quán)重取值為常數(shù)，但后來的試驗發(fā)現(xiàn)，動態(tài)慣性權(quán)重能夠獲得比定值更好的尋優(yōu)結(jié)果。這樣使得 PSO 在開始時搜索較大的區(qū)域，較大地定位最優(yōu)解的大致位置，隨 著權(quán)重的減小，粒子速度減慢，開始精細(xì)的局部搜索。慣性權(quán)重 ? 使 PSO 算法的性能得到很大提高。另外 ,從式()～ 式 ()來看 ,位置與速度直接進(jìn)行加法運(yùn)算 ,而沒有粒子運(yùn)動時間概念 ,這也不符合現(xiàn)實生活中的運(yùn)動規(guī)律： x=vt。故不失一般性 ,證明過程可以簡化到一維進(jìn)行 ,下標(biāo) d可以省略。 本定理的重要性在于說明 bPSO 算法可以沒有粒子速度的概念 ,避免了人為確定參數(shù)max, max[]vv? 而影響粒子的收斂速度和 收斂精度。 采用第 ,式 (8)可以變形為一階微分方程 : ( 1 ) ( ) ( )x t x t? ? ??? ? ? ? () 由式 ()和式 ()的比較可知 :改寫后的 sPSO 進(jìn)化方程不僅沒有粒子速度參數(shù) ,而且方程也由二階降到了一階 ,簡化了分析和控制粒子的進(jìn)化過程。 由于 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??? ? ? ?????? ? ? ?? ? ? ? ?。這主 要是粒子群難以擺脫局部極值的原因 ,也是 bPSO 的美中不足。 bPSO 收斂于局部極值的原因分析 實驗發(fā)現(xiàn) :當(dāng) bPSO 處于進(jìn)化停滯時 ,粒子群中的粒子都會出現(xiàn)“聚集”現(xiàn)象 ,直至突破進(jìn)化停滯局面 ,粒子才會“飛散”開去。(2)調(diào)整個體極值和全局極值為 39。*p ,經(jīng)歷新的搜索路徑和領(lǐng)域 ,因此發(fā)現(xiàn)更優(yōu)解的概率較大。 ggtTtT ggp r p p r p????， 其中 : 0,gtt分別表示個體極值和全局極值進(jìn)化停滯步數(shù) 。需要說明的是 , 0, gTT的取值大小決定了極值擾動算子生效的延遲長短 ,一般取值范圍為 3～ 0, gTT等于進(jìn)化世代數(shù)時 ,式 ()退化為式 ()。以上兩種策略結(jié)合，得到帶 極值擾動的簡化粒子群算法（ tsPSO）。 搜索空間 100 100ix? ? ? 。該函數(shù)在原理最優(yōu)點區(qū)域的適應(yīng)值地形很簡單，但靠近最優(yōu)的區(qū)域為香蕉狀。函數(shù)的 3D 圖形如圖 所示 。優(yōu)化算法很容易在通往全局 最優(yōu)點的路徑上陷入一個局部最優(yōu)點。 具體參數(shù)設(shè)置為： 種群規(guī)模設(shè)為 m=15，粒子的維數(shù)為Dim=30，最大迭代步數(shù)為 150； max 1v ? ； 122cc??； 0 3。 固定收斂精度下的迭代次數(shù) 4 個實驗在適應(yīng)度值為 610 的 收斂精度下經(jīng)過 20 次獨立運(yùn)行后的最大迭代次數(shù)、最小迭代次數(shù)、平均迭代次數(shù)見表 1。這表明，帶極值擾動的 sPSO 算法 具有非常高的優(yōu)化性能和實用性。 %給定初始化條件 c1=2。 MaxDT=1000。 %設(shè)置精度 (在已知最小值時候用 ) T0=3。 %賦初始值 %初始化種群的個體 (可以在這里限定位置和速度的范圍 ) for i=1:N for j=1:D x(i,j)=100*randn。 %Pg 為全局最優(yōu) for i=2:N if fitness(x(i,:),D)fitness(pg,D) pg=x(i,:)。 y(i,:)=x(i,:)。 %全體極值需要擾動的停止步數(shù) 闕值 t0=0。 %搜索空間維數(shù)（未知數(shù)個數(shù)） N=15。 %學(xué)習(xí)因子 2 wini=。 實驗名稱 迭代次數(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。 同樣比較 bPSO 和 tPSO 實驗可以看出： tPSO 總體上比 bPSO 的優(yōu)化效果好一些。 實驗結(jié)果及 分析 固定進(jìn)化迭代次數(shù)的收斂速度和精度 bPSO、 sPSO、 tPSO、 tsPSO 用三個測試函數(shù)進(jìn)行 測試，固定進(jìn)化迭代次數(shù)為 150次，（ 1）（ 2）（ 3）分別選用 Sphere 函數(shù)、 Rosenbrock 函數(shù)、 Rastrigin 函數(shù)作為測試函數(shù)，（ a）（ b）（ c）（ d）分別為用各個測試函數(shù)的 bPSO 算法、 sPSO 算法 、 tPSO 算法、 tsPSO算法的適應(yīng)度的對數(shù)值進(jìn)化曲線（注：為