1、第5章演化策略,武漢大學(xué)計(jì)算機(jī)學(xué)院,5.1 演化策略的一般結(jié)構(gòu),演化策略是由德國的Rechenberg和Schwefel在20世紀(jì)60年代初期提出來的，目前已形成演化計(jì)算的一個(gè)重要分支。演化策略主要用于連續(xù)參數(shù)優(yōu)化問題。 在下面的討論中，假定問題是求解下列連續(xù)優(yōu)化問題： 在更一般的情形，問題是求解下列約束優(yōu)化問題： 其中,5.1 演化策略的一般結(jié)構(gòu),早期的演化策略種群中只包含一個(gè)個(gè)體，稱之為父體。在演化過程中，僅有一種遺傳算子：變異。在每一演化代，通過將變異算子應(yīng)用到父體上得到一個(gè)后代，然后將后代與父體進(jìn)行比較，若后代比父體好且滿足所有的約束條件，則后代成為下一代種群中的父體，否則父體保持不變

2、。這種演化策略稱為(1+1)演化策略。,算法5.1 (1+1)-演化策略,5.1 演化策略的一般結(jié)構(gòu),下面用一個(gè)例子來說明(1+1)-演化策略的一步迭代. 考慮下列優(yōu)化問題： 其中 . 假定第t代種群中的父體為 , 那么有,5.1 演化策略的一般結(jié)構(gòu),由于 且有 ， ，故 將替換 成為下一代種群中的父體，即有 。 在高斯變異算子中， 是算法的參數(shù)，它的值確定了 后代的變化范圍，所以 稱為變異步長。,5.1 演化策略的一般結(jié)構(gòu),(1+1)演化策略沒有體現(xiàn)種群的作用，本質(zhì)上是一種局部搜索策略，具有明顯的局限性。 隨后，Rechenberg又提出了( +1)-演化策略。后來Schwefel又提出了

3、演化策略和 演化策略。,5.2 演化策略的實(shí)現(xiàn)技術(shù),1 表示 (1)二元表示 (2) 三元表示,5.2 演化策略的實(shí)現(xiàn)技術(shù),2 變異 下面討論二元表示變異算子的實(shí)現(xiàn)方式. (1) 當(dāng) 時(shí),變異算子下式實(shí)現(xiàn) 其中 是一個(gè)常數(shù)，由用戶給定.通常有 經(jīng)變異后所得到的后代為,5.2 演化策略的實(shí)現(xiàn)技術(shù),(1) 當(dāng) 時(shí),變異算子下式實(shí)現(xiàn) 其中 , 經(jīng)變異后所得到的后代為,5.2 演化策略的實(shí)現(xiàn)技術(shù),3 重組 演化策略中的重組算子由兩個(gè)或多個(gè)父體得到一個(gè)后代。為了得到 個(gè)后代，需要運(yùn)用重組算子 次。 (1)離散重組 假設(shè)兩個(gè)父體分別為 則由這兩個(gè)父體重組得到的后代為 ，其中,5.2 演化策略的實(shí)現(xiàn)技術(shù),(

4、2) 中值重組 由兩個(gè)父體重組得到的后代為 上面兩種重組可以以下列方式進(jìn)行推廣：為了得到后代 ，對每個(gè) ，從種群中隨機(jī)地抽取兩個(gè)父體x和y，然后對x和y的第i個(gè)分量進(jìn)行重組。,5.2 演化策略的實(shí)現(xiàn)技術(shù),這種重組方式稱為全局重組。若對每個(gè)分量進(jìn)行離散重組，則稱為全局離散重組。若每個(gè)分量進(jìn)行中值重組，則稱為全局中值重組。 4 父體選擇 演化策略中的父體選擇與個(gè)體的適應(yīng)值無關(guān)。每當(dāng)重組算子需要一個(gè)父體時(shí)，則從 個(gè)個(gè)體所組成的種群中隨機(jī)地選取。,5.2 演化策略的實(shí)現(xiàn)技術(shù),5 存活選擇 演化策略的存活選擇策略有兩種： 選擇和 選擇。這兩種選擇策略都是確定性的。 在從 個(gè)父代個(gè)體產(chǎn)生 個(gè)后代并計(jì)算其適應(yīng)值后， 選擇從 個(gè)后代中擇優(yōu)選擇 個(gè)個(gè)體作為下一代種群，而 選擇從 個(gè)父代個(gè)體和 個(gè)后代中擇優(yōu)選擇 個(gè)個(gè)體作為下一代種群。,5.3 應(yīng)用實(shí)例,考慮下面的Ackley函數(shù)極小化問題 求解該問題的演化策略設(shè)計(jì)如下： (1)表示,5.3 應(yīng)用實(shí)例,(2) 適應(yīng)函數(shù)：適應(yīng)函數(shù)取為目標(biāo)函數(shù)。 (3)重組算子：對變量部分使用離散重組，對策略參數(shù)部分使用全局中值重組。 (4)存活選擇：使用 選擇，其中 ， 。 (5)終止準(zhǔn)則：當(dāng)進(jìn)行200000次函數(shù)值計(jì)算或發(fā)現(xiàn)最優(yōu)解后終止算法。 (6)種群初始化：初始種群中每個(gè)個(gè)體的變量部分隨機(jī)地產(chǎn)生，每個(gè)分量均勻地分布在