第三章進化規(guī)劃與進化策略PPT課件

1、 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期1Evolutionary Programming, EPEvolutionary Strategy, ES第三章 進化規(guī)劃與進化策略 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期2簡介GA, EP & ES 統(tǒng)稱為進化計算(Evolutionary Computation，EC) 模擬生物界自然進化過程而建立的隨機優(yōu)化算法 三者獨立建立，基本思想相同但是又各自有所側(cè)重 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期3內(nèi) 容EP起源與發(fā)展EP機理EP流程圖EP特點EP實現(xiàn)EP基礎(chǔ)理論研究EP應(yīng)用領(lǐng)域EP簡單演示EP策略GA, EP

2、, ES三者的比較EC的統(tǒng)一框架ES起源與發(fā)展ES機理ES流程圖ES特點ES實現(xiàn)ES基礎(chǔ)理論研究ES應(yīng)用領(lǐng)域ES簡單演示ES策略 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期4EP起源與發(fā)展美國 L. J. Fogel 60年代 認為智能性體現(xiàn)在對環(huán)境的預(yù)知能力以及在一定目標指導(dǎo)下對環(huán)境做出合理響應(yīng)66年 Fogel基于模擬進化的人工智能 遭到質(zhì)疑92年 EP首屆年會 獲得承認 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期5EP機理優(yōu)化問題的解被視為個體隨機產(chǎn)生初始群體按照某種變異規(guī)則對群體進行變異操作產(chǎn)生新個體根據(jù)適應(yīng)度函數(shù)對所有個體進行評價，隨機保留最好的一半然后重復(fù)上述變異選擇過

3、程直到滿足終止條件 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期6EP流程圖開始隨機產(chǎn)生初始種群，并計算各個體的適配值算法收斂準則滿足否？輸出搜索結(jié)果Y變異概率滿足否？執(zhí)行變異操作YNN執(zhí)行選擇操作執(zhí)行復(fù)制操作 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期7EP特點只有變異，沒有交叉其他方面類似于GA 編碼空間 并行計算 適應(yīng)度函數(shù) 自適應(yīng)隨機搜索 簡單易行 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期8EP實現(xiàn)通用框架 確定問題編碼方案 確定適配值函數(shù) 設(shè)計選擇算子和變異算子 確定算法參數(shù) 確定算法終止條件 生成初始種群 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期9EP基礎(chǔ)

4、理論研究類似于GA，面臨同樣的問題 主要是收斂性分析：是否收斂？收斂性能？數(shù)學(xué)工具類似 隨機模型理論相對GA,研究結(jié)果更少，基礎(chǔ)更薄弱 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期10EP應(yīng)用領(lǐng)域類似于GA，非常廣泛主要是人工智能方面 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期11EP簡單演示問題：求（1）編碼： 編碼長度為5（2）初始群體生成：群體大小設(shè)置為4，隨機產(chǎn)生四個個體： 編碼： 01101，11000，01000，10011 解碼： 13 24 8 19 適應(yīng)度： 169 576 64 361（3）適應(yīng)度函數(shù)：31,.,1 , 0,)(max2xxxf1111100000

5、 x2)(xxf by 謝廣明 ， 20052006學(xué)年度第一學(xué)期12（4）變異：發(fā)生變異的概率取 單點變異：隨機選取某點改變碼值 01101 01100 11000 1000001000 01010 10011 10111（5）選擇：選擇最好的四個 編碼: 01101 01100 11000 10000 01000 01010 10011 10111 解: 13 12 24 16 8 10 19 23 適應(yīng)度: 169 144 。 新群體的產(chǎn)生： 11000 10000 10011 10111（6）重復(fù)上述操作20次 ,或許就能夠得到最優(yōu)解！0.8mPEP簡單演示 by 謝廣明 ， 2005

6、2006學(xué)年度第一學(xué)期13EP策略針對不同實際問題需要調(diào)整相應(yīng)策略同一個實際問題不同的人也有不同的做法編碼方案：比GA更靈活適應(yīng)度函數(shù)設(shè)計：與GA類似初始種群：與GA類似選擇算子變異算子 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期14EP策略編碼方案比GA靈活, 因為沒有交叉算子實數(shù)編碼：無需編碼和解碼序列編碼：例如TSP的路徑表達更自由開放的編碼 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期15EP策略選擇算子經(jīng)典策略:對每個個體都進行變異，使得個體總數(shù)加倍，然后從中剔除一半。當然可以采用GA中所提出的各種算子變異算子經(jīng)典：高斯變異當然可以采用GA中所提出的各種算子 by 謝廣明

7、， 20052006學(xué)年度第一學(xué)期16ES起源與發(fā)展歐洲 德國柏林技術(shù)大學(xué)學(xué)生 I. Rechenberg, H.P. Schwefel 60年代問題：用風(fēng)洞做實驗，確定氣流中物體的最優(yōu)外形。解決：按照自然突變和自然選擇的物種進化思想，對物體的外形參數(shù)進行隨機變化尋找最優(yōu)外形。 反映：當時人們無法接受90年 歐洲首屆國際會議 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期17ES機理優(yōu)化問題的解被視為個體隨機產(chǎn)生初始群體按照某種重組規(guī)則產(chǎn)生新個體按照某種變異規(guī)則對群體進行變異操作產(chǎn)生新個體按照某種選擇規(guī)則選擇新群體的組成然后重復(fù)上述變異選擇過程直到滿足終止條件 by 謝廣明 ， 200520

8、06學(xué)年度第一學(xué)期18ES流程圖開始隨機產(chǎn)生初始種群，并計算各個體的適配值算法收斂準則滿足否？輸出搜索結(jié)果Y執(zhí)行復(fù)制操作重組概率滿足否?執(zhí)行重組操作變異概率滿足否？執(zhí)行變異操作YYNNN執(zhí)行選擇操作 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期19ES特點重組類似于交叉 更靈活自由其他方面類似于GA 編碼空間 并行計算 適應(yīng)度函數(shù) 自適應(yīng)隨機搜索 簡單易行 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期20ES實現(xiàn)通用框架 確定問題編碼方案 確定適配值函數(shù) 設(shè)計重組算子，選擇算子和變異算子 確定算法參數(shù) 確定算法終止條件 生成初始種群 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期21

9、ES基礎(chǔ)理論研究類似于GA，面臨同樣的問題 主要是收斂性分析：是否收斂？收斂性能？數(shù)學(xué)工具類似 隨機模型理論相對GA,研究結(jié)果更少，基礎(chǔ)更薄弱 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期22ES應(yīng)用領(lǐng)域類似于GA，非常廣泛主要是人工智能方面 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期23ES簡單演示問題：求（1）編碼： （2）初始群體生成：群體大小設(shè)置為4，隨機產(chǎn)生四個個體： 解碼： 13 24 8 19 適應(yīng)度： 169 576 64 361（3）適應(yīng)度函數(shù)：31,.,1 , 0,)(max2xxxf0 31x 2)(xxf by 謝廣明 ， 20052006學(xué)年度第一學(xué)期24（

10、4）重組：隨機平均重組2次產(chǎn)生兩個新個體 11= (13+8)/2 16=( 24+ 8)/2（5）變異：發(fā)生變異的概率取 高斯變異1311 810 2425 1918 1111 1617（6）選擇：選擇最好的四個 新群體的產(chǎn)生： 25 18 17 11（7）重復(fù)上述操作20次 ,或許就能夠得到最優(yōu)解！0.8mPES簡單演示 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期25ES策略針對不同實際問題需要調(diào)整相應(yīng)策略同一個實際問題不同的人也有不同的做法編碼方案：比GA更靈活適應(yīng)度函數(shù)設(shè)計：與GA類似初始種群：與GA類似選擇算子重組算子：與GA類似,更靈活變異算子 by 謝廣明 ， 200520

11、06學(xué)年度第一學(xué)期26ES策略編碼方案 比GA較靈活, 因為重組算子比較交叉算子靈活 實數(shù)編碼：無需編碼和解碼 序列編碼：例如TSP的路徑表達 更自由開放的編碼 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期27ES策略選擇算子：完全確定經(jīng)典策略: (,)ES： 用個父個體產(chǎn)生個個體 從新個體種選擇個個體作為子代。(+)ES： 用個父個體產(chǎn)生個個體 從父個體與新個體中選擇個個體作為子代。變異算子 經(jīng)典：高斯變異當然可以采用GA中所提出的各種算子 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期28GA, EP, ES三者的比較相同點：模擬自然進化過程隨機優(yōu)化過程側(cè)重點： GA 基因?qū)哟蔚淖兓瑥娬{(diào)交叉的作用，抑止變異的作用，隨機性選擇 EP 個體層面的變化，強調(diào)變異，沒有交叉 ES 種群層面的變化，強調(diào)變異，有交叉（重組），確定性選擇 by 謝廣明 ， 20052006學(xué)年度第一學(xué)期29進化計算的一般