優(yōu)化算法_模擬退火_粒子群_遺傳算法

《優(yōu)化算法_模擬退火_粒子群_遺傳算法》由會(huì)員分享，可在線閱讀，更多相關(guān)《優(yōu)化算法_模擬退火_粒子群_遺傳算法（19頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、優(yōu)化算法1模擬退火算法2遺傳算法3粒子群算法1模擬退火算法一、模擬退火算法概念 模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其慢慢冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而慢慢冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。 用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解計(jì)算目標(biāo)函數(shù)差接受或舍棄”的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解1模擬退火算法二、模擬退火算法模型 模擬退火算法可以分為解空

2、間、目標(biāo)函數(shù)和初始解三部分。 三、 模擬退火的基本思想(1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(算法迭代的起點(diǎn))， 每個(gè)T值的迭代次數(shù)L ；(2) 對(duì)k=1，L做第(3)至第6步： (3) 產(chǎn)生新解S (4) 計(jì)算增量t=C(S)-C(S)，其中C(S)為評(píng)價(jià)函數(shù) (5) 若t0，然后轉(zhuǎn)第2步。 1模擬退火算法四、模擬退火算法特點(diǎn)1.最終求得的解與初始值無關(guān)，與初始解狀態(tài)S無關(guān)；2.具有漸近收斂性，在理論上是一種以概率1收斂于全局最優(yōu)解的全局優(yōu)化算法；3.具有并行性。2遺傳算法一、遺傳算法概念 遺傳算法簡稱GA，是模擬自然界遺傳機(jī)制和生物進(jìn)化論而成的一種并行隨機(jī)搜索最優(yōu)化方法。遺傳算

3、法將“優(yōu)勝劣汰，適者生存”的生物進(jìn)化原理引入優(yōu)化參數(shù)形成的編碼串聯(lián)群體中，按所選擇的適應(yīng)度函數(shù)并通過遺傳中的復(fù)制、交叉及變異對(duì)個(gè)體進(jìn)行篩選，使適應(yīng)度高的個(gè)體被保留下來，組成新的群體，新的群體既繼承了上一代的信息，又優(yōu)于上一代。這樣周而復(fù)始，群體中個(gè)體適應(yīng)度不斷提高，直到滿足一定的條件。2遺傳算法二、遺傳算法基本操作（1）復(fù)制復(fù)制：復(fù)制操作可以通過隨機(jī)方法來實(shí)現(xiàn)。首先產(chǎn)生01之間均勻分布的隨機(jī)數(shù)，若某串的復(fù)制概率為40%，則當(dāng)產(chǎn)生的隨機(jī)數(shù)在0.401.0之間時(shí)，該串被復(fù)制，否則被淘汰（2）交叉交叉：在匹配池中任選兩個(gè)染色體，隨機(jī)選擇一點(diǎn)或多點(diǎn)交換點(diǎn)位置；交換雙親染色體交換點(diǎn)右邊的部分，即可得到兩

4、個(gè)新的染色體數(shù)字串。（3）變異變異：在染色體以二進(jìn)制編碼的系統(tǒng)中，它隨機(jī)地將染色體的某一個(gè)基因由1變?yōu)?，或由0變?yōu)?。2遺傳算法三、遺傳算法特點(diǎn)（1）對(duì)參數(shù)的編碼進(jìn)行操作，而非對(duì)參數(shù)本身；（2）同時(shí)使用多個(gè)搜索點(diǎn)的搜索信息；（3）直接以目標(biāo)函數(shù)作為搜索信息；（4）使用概率搜索技術(shù)；（5）遺傳算法在解空間進(jìn)行高效啟發(fā)式搜索，而非盲目地窮舉或完全隨機(jī)搜索；（6）對(duì)于待尋優(yōu)的函數(shù)基本無限制，它既不要求函數(shù)連續(xù)，也不要求函數(shù)可微；（7）具有并行計(jì)算的特點(diǎn).2遺傳算法三、遺傳算法的應(yīng)用（1）函數(shù)優(yōu)化； （2）組合優(yōu)化； （3）生產(chǎn)調(diào)度問題；（4）自動(dòng)控制：利用遺傳算法進(jìn)行控制器參數(shù)的優(yōu)化、基于遺傳算法

5、的模糊控制規(guī)則的學(xué)習(xí)、基于遺傳算法的參數(shù)辨識(shí)、基于遺傳算法的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化和權(quán)值學(xué)習(xí)；（5）機(jī)器人； （6）圖像處理； （7）人工生命；（8）遺傳編程； （9）機(jī)器學(xué)習(xí)；2遺傳算法四、遺傳算法的應(yīng)用步驟一：確定決策變量及各種約束條件，即確定出個(gè)體的表現(xiàn)型X和問題的解空間；二：建立優(yōu)化模型，即確定出目標(biāo)函數(shù)的類型及數(shù)學(xué)描述形式或量化方法；三：確定表示可行解的染色體編碼方法，即確定出個(gè)體的基因型x及遺傳算法的搜索空間；四：確定解碼方法，即確定出由個(gè)體基因型x到個(gè)體表現(xiàn)型X的對(duì)應(yīng)關(guān)系或轉(zhuǎn)換方法；五：確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法，即確定出由目標(biāo)函數(shù)值到個(gè)體適應(yīng)度的轉(zhuǎn)換規(guī)則；六：設(shè)計(jì)遺傳算子，即確定

6、選擇運(yùn)算、交叉運(yùn)算、變異運(yùn)算等遺傳算子的具體操作方法。七：確定遺傳算法的有關(guān)運(yùn)行參數(shù)，即M,G,Pc,Pm等參數(shù)。2遺傳算法四、遺傳算法的應(yīng)用步驟3粒子群算法一、粒子群算法（PSO）的基本思想 它是通過模擬鳥群覓食行為而發(fā)展起來的一種基于群體協(xié)作的隨機(jī)搜索算法。通常認(rèn)為它是群集智能的一種。它可以被納入多主體優(yōu)化系統(tǒng)。搜尋目前離的食物最近的鳥的周圍區(qū)域根據(jù)自己飛行的經(jīng)驗(yàn)判斷食物所在已知鳥的位置鳥當(dāng)前位置和食物之間的距離求解找到食物的最優(yōu)策略3粒子群算法q 每個(gè)尋優(yōu)的問題解都被想像成一只鳥，稱為“粒子;q 所有的粒子都由一個(gè)Fitness Function 確定適應(yīng)值以判斷目前的位置好壞;q 每一

7、個(gè)粒子必須賦予記憶功能，能記住所搜尋到的最佳位置;q 每一個(gè)粒子還有一個(gè)速度以決定飛行的距離和方向，這個(gè)速度根據(jù)它本身的飛行經(jīng)驗(yàn)以及同伴的飛行經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)調(diào)整。 3粒子群算法二、粒子群算法求解最優(yōu)解q D維空間中，有m個(gè)粒子； 粒子i位置：xi=(xi1,xi2,xiD)，將xi代入適應(yīng)函數(shù)F(xi)求適應(yīng)值； 粒子i速度：vi=(vi1,vi2,viD) 粒子i個(gè)體經(jīng)歷過的最好位置：pbesti=(pi1,pi2,piD) 種群所經(jīng)歷過的最好位置：gbest=(g1,g2,gD) 通常，在第d（1dD）維的位置變化范圍限定在Xmin,d ,Xmax,d內(nèi)，速度變化范圍限定在-Vmax,d ,

8、Vmax,d內(nèi)。pbestxigbestvi3粒子群算法q 粒子i的第d維速度更新公式： q 粒子i的第d維位置更新公式： 第k次迭代粒子i飛行速度矢量的第d維分量 第k次迭代粒子i位置矢量的第d維分量 c1,c2加速度常數(shù)，調(diào)節(jié)學(xué)習(xí)最大步長 r1,r2兩個(gè)隨機(jī)函數(shù)，取值范圍0，1，以增加搜索隨機(jī)性 w 慣性權(quán)重，非負(fù)數(shù)，調(diào)節(jié)對(duì)解空間的搜索范圍kidxkidv11kkkidididxxvkk-111idid1 12 2v =wv()()kkididdidc r pbestxc r gbestxpbestgbest3粒子群算法三、粒子群算法流程3粒子群算法1.群族初始化：以隨機(jī)的方式求出每一粒子

9、的初始位置與速度；2.計(jì)算適應(yīng)度：根據(jù) 適應(yīng)度函數(shù)計(jì)算出其適應(yīng)度值以作為判斷每個(gè)粒子的好壞；3.尋找Pbest：找出每個(gè)粒子到目前為止，搜尋過程中的最優(yōu)解；4.尋找gbest：找出所有粒子到目前為止所搜尋到的全體最優(yōu)解；5.更新速度與位置：根據(jù)速度和位移更新公式，更新每個(gè)粒子的移動(dòng)方向與速度；6.判斷是否收斂：通常算法達(dá)到最大迭代次數(shù)Gmax或者最佳適應(yīng)度函數(shù)值的增量小于某個(gè)給定的罰值時(shí)算法停止。3粒子群算法四、粒子群算法構(gòu)成要素群體大小m：m很?。合萑刖植孔顑?yōu)解的可能性很大 ；m很大：PSO的優(yōu)化能力很好，計(jì)算量大；一般取10-30個(gè)。權(quán)重因子慣性權(quán)重w： w=0：粒子很容易趨向于同一位置 w小：傾向于局部探索,精細(xì)搜索目前的小區(qū)域 w大：擴(kuò)展新的搜索區(qū)域,利于全局搜索一般取0.9,1.2即可。權(quán)重因子學(xué)習(xí)因子c1，c2：一般c1等于c2,并且范圍在0和4之間；最大速度Vm： Vm較大時(shí)，探索能力增強(qiáng)，但粒子容易飛過最優(yōu)解； Vm較小時(shí)，開發(fā)能力增強(qiáng)，但容易陷入局部最優(yōu) Vm一般設(shè)為每維變量的取值范圍。 12343粒子群算法四、粒子群算法優(yōu)點(diǎn)1、參數(shù)較少，容易調(diào)整2、局部與全局結(jié)合，收斂速度快