優(yōu)化算法模擬退火粒子群遺傳算法專家講座

1模擬退火算法2遺傳算法3粒子群算法優(yōu)化算法模擬退火粒子群遺傳算法專家講座第1頁1模擬退火算法一、模擬退火算法概念模擬退火算法起源于固體退火原理，將固體加溫至充分高，再讓其慢慢冷卻，加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而慢慢冷卻時粒子漸趨有序，在每個溫度都到達(dá)平衡態(tài)，最終在常溫時到達(dá)基態(tài)，內(nèi)能減為最小。

用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當(dāng)前解重復(fù)“產(chǎn)生新解→計算目標(biāo)函數(shù)差→接收或舍棄”迭代，并逐步衰減t值，算法終止時當(dāng)前解即為所得近似最優(yōu)解優(yōu)化算法模擬退火粒子群遺傳算法專家講座第2頁1模擬退火算法二、模擬退火算法模型

模擬退火算法能夠分為解空間、目標(biāo)函數(shù)和初始解三部分。三、

模擬退火基本思想(1)初始化：初始溫度T(充分大)，初始解狀態(tài)S(算法迭代起點)，每個T值迭代次數(shù)L；

(2)對k=1，……，L做第(3)至第6步：

(3)產(chǎn)生新解S′

(4)計算增量Δt′=C(S′)-C(S)，其中C(S)為評價函數(shù)

(5)若Δt′<0則接收S′作為新當(dāng)前解，不然以概率exp(-Δt′/T)接收S′作為新當(dāng)前解.（Metropo1is準(zhǔn)則）

(6)假如滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。

終止條件通常取為連續(xù)若干個新解都沒有被接收時終止算法。

(7)T逐步降低，且T>0，然后轉(zhuǎn)第2步。

優(yōu)化算法模擬退火粒子群遺傳算法專家講座第3頁1模擬退火算法四、模擬退火算法特點1.最終求得解與初始值無關(guān)，與初始解狀態(tài)S無關(guān)；2.含有漸近收斂性，在理論上是一個以概率1收斂于全局最優(yōu)解全局優(yōu)化算法；3.含有并行性。優(yōu)化算法模擬退火粒子群遺傳算法專家講座第4頁2遺傳算法一、遺傳算法概念

遺傳算法簡稱GA，是模擬自然界遺傳機制和生物進(jìn)化論而成一個并行隨機搜索最優(yōu)化方法。遺傳算法將“優(yōu)勝劣汰，適者生存”生物進(jìn)化原理引入優(yōu)化參數(shù)形成編碼串聯(lián)群體中，按所選擇適應(yīng)度函數(shù)并經(jīng)過遺傳中復(fù)制、交叉及變異對個體進(jìn)行篩選，使適應(yīng)度高個體被保留下來，組成新群體，新群體既繼承了上一代信息，又優(yōu)于上一代。這么周而復(fù)始，群體中個體適應(yīng)度不停提升，直到滿足一定條件。優(yōu)化算法模擬退火粒子群遺傳算法專家講座第5頁2遺傳算法二、遺傳算法基本操作（1）復(fù)制：復(fù)制操作能夠經(jīng)過隨機方法來實現(xiàn)。首先產(chǎn)生0~1之間均勻分布隨機數(shù)，若某串復(fù)制概率為40%，則當(dāng)產(chǎn)生隨機數(shù)在0.40~1.0之間時，該串被復(fù)制，不然被淘汰（2）交叉：在匹配池中任選兩個染色體，隨機選擇一點或多點交換點位置；交換雙親染色體交換點右邊部分，即可得到兩個新染色體數(shù)字串。（3）變異：在染色體以二進(jìn)制編碼系統(tǒng)中，它隨機地將染色體某一個基因由1變?yōu)?，或由0變?yōu)?。優(yōu)化算法模擬退火粒子群遺傳算法專家講座第6頁2遺傳算法三、遺傳算法特點（1）對參數(shù)編碼進(jìn)行操作，而非對參數(shù)本身；（2）同時使用多個搜索點搜索信息；（3）直接以目標(biāo)函數(shù)作為搜索信息；（4）使用概率搜索技術(shù)；（5）遺傳算法在解空間進(jìn)行高效啟發(fā)式搜索，而非盲目地窮舉或完全隨機搜索；（6）對于待尋優(yōu)函數(shù)基本無限制，它既不要求函數(shù)連續(xù)，也不要求函數(shù)可微；（7）含有并行計算特點.優(yōu)化算法模擬退火粒子群遺傳算法專家講座第7頁2遺傳算法三、遺傳算法應(yīng)用（1）函數(shù)優(yōu)化；

（2）組合優(yōu)化；（3）生產(chǎn)調(diào)度問題；（4）自動控制：利用遺傳算法進(jìn)行控制器參數(shù)優(yōu)化、基于遺傳算法含糊控制規(guī)則學(xué)習(xí)、基于遺傳算法參數(shù)辨識、基于遺傳算法神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化和權(quán)值學(xué)習(xí)；（5）機器人；（6）圖像處理；（7）人工生命；（8）遺傳編程；

（9）機器學(xué)習(xí)；優(yōu)化算法模擬退火粒子群遺傳算法專家講座第8頁2遺傳算法四、遺傳算法應(yīng)用步驟一：確定決議變量及各種約束條件，即確定出個體表現(xiàn)型X和問題解空間；二：建立優(yōu)化模型，即確定出目標(biāo)函數(shù)類型及數(shù)學(xué)描述形式或量化方法；三：確定表示可行解染色體編碼方法，即確定出個體基因型x及遺傳算法搜索空間；四：確定解碼方法，即確定出由個體基因型x到個體表現(xiàn)型X對應(yīng)關(guān)系或轉(zhuǎn)換方法；五：確定個體適應(yīng)度量化評價方法，即確定出由目標(biāo)函數(shù)值到個體適應(yīng)度轉(zhuǎn)換規(guī)則；六：設(shè)計遺傳算子，即確定選擇運算、交叉運算、變異運算等遺傳算子詳細(xì)操作方法。七：確定遺傳算法相關(guān)運行參數(shù)，即M,G,Pc,Pm等參數(shù)。優(yōu)化算法模擬退火粒子群遺傳算法專家講座第9頁2遺傳算法四、遺傳算法應(yīng)用步驟優(yōu)化算法模擬退火粒子群遺傳算法專家講座第10頁3粒子群算法一、粒子群算法（PSO）基本思想

它是經(jīng)過模擬鳥群覓食行為而發(fā)展起來一個基于群體協(xié)作隨機搜索算法。通常認(rèn)為它是群集智能一個。它能夠被納入多主體優(yōu)化系統(tǒng)。搜尋當(dāng)前離食物最近鳥周圍區(qū)域依據(jù)自己飛行經(jīng)驗判斷食物所在已知鳥位置鳥當(dāng)前位置和食物之間距離求解找到食物最優(yōu)策略優(yōu)化算法模擬退火粒子群遺傳算法專家講座第11頁3粒子群算法每個尋優(yōu)問題解都被想像成一只鳥，稱為“粒子;全部粒子都由一個FitnessFunction確定適應(yīng)值以判斷當(dāng)前位置好壞;每一個粒子必須賦予記憶功效，能記住所搜尋到最正確位置;每一個粒子還有一個速度以決定飛行距離和方向，這個速度依據(jù)它本身飛行經(jīng)驗以及同伴飛行經(jīng)驗進(jìn)行動態(tài)調(diào)整。優(yōu)化算法模擬退火粒子群遺傳算法專家講座第12頁3粒子群算法二、粒子群算法求解最優(yōu)解D維空間中，有m個粒子；

粒子i位置：xi=(xi1,xi2,…xiD)，將xi代入適應(yīng)函數(shù)F(xi)求適應(yīng)值；粒子i速度：vi=(vi1,vi2,…viD)粒子i個體經(jīng)歷過最好位置：pbesti=(pi1,pi2,…piD)種群所經(jīng)歷過最好位置：gbest=(g1,g2,…gD)通常，在第d（1≤d≤D）維位置改變范圍限定在[Xmin,d,Xmax,d]內(nèi)，速度改變范圍限定在[-Vmax,d,Vmax,d]內(nèi)。pbestxigbestvi優(yōu)化算法模擬退火粒子群遺傳算法專家講座第13頁3粒子群算法粒子i第d維速度更新公式：

粒子i第d維位置更新公式：

—第k次迭代粒子i飛行速度矢量第d維分量

—第k次迭代粒子i位置矢量第d維分量

c1,c2—加速度常數(shù)，調(diào)整學(xué)習(xí)最大步長

r1,r2—兩個隨機函數(shù)，取值范圍[0，1]，以增加搜索隨機性

w—慣性權(quán)重，非負(fù)數(shù)，調(diào)整對解空間搜索范圍pbest

gbest優(yōu)化算法模擬退火粒子群遺傳算法專家講座第14頁3粒子群算法三、粒子群算法流程優(yōu)化算法模擬退火粒子群遺傳算法專家講座第15頁3粒子群算法1.群族初始化：以隨機方式求出每一粒子初始位置與速度；2.計算適應(yīng)度：依據(jù)

適應(yīng)度函數(shù)計算出其適應(yīng)度值以作為判斷每個粒子好壞；3.尋找Pbest：找出每個粒子到當(dāng)前為止，搜尋過程中最優(yōu)解；4.尋找gbest：找出全部粒子到當(dāng)前為止所搜尋到全體最優(yōu)解；5.更新速度與位置：依據(jù)速度和位移更新公式，更新每個粒子移動方向與速度；6.判斷是否收斂：通常算法到達(dá)最大迭代次數(shù)Gmax或者最正確適應(yīng)度函數(shù)值增量小于某個給定罰值時算法停頓。優(yōu)化算法模擬退火粒子群遺傳算法專家講座第16頁3粒子群算法四、粒子群算法組成要素群體大小m：m很?。合萑刖植孔顑?yōu)解可能性很大

；m很大：PSO優(yōu)化能力很好，計算量大；普通取10-30個。權(quán)重因子——慣性權(quán)重w：w=0：粒子很輕易趨向于同一位置

w?。簝A向于局部探索,精細(xì)搜索當(dāng)前小區(qū)域

w大：擴展新搜索區(qū)域,利于全局搜索普通取[0.9,1.2]即可。權(quán)重因子——學(xué)習(xí)因子c1，c2：普通c1等于c2,而且范圍在0和4之間；最大速度Vm：

Vm較