智能優(yōu)化技術(shù)課件

智能優(yōu)化技術(shù)

IntelligentOptimizationTechnology

1馬龍華副教授浙江大學(xué)控制科學(xué)與工程系2011年5月目錄第一部分導(dǎo)言第二部分基于自然生命進(jìn)化的智能優(yōu)化技術(shù)

（遺傳算法GA,免疫優(yōu)化）第三部分基于群（swarm）的智能優(yōu)化技術(shù)

(蟻群優(yōu)化ACO，粒子群優(yōu)化PSO,捕食搜索PS,群落選址算法CLA)第四部分基于物理自然的智能計(jì)算技術(shù)

(模擬退火(SA),禁忌搜索TS,神經(jīng)網(wǎng)絡(luò)優(yōu)化NN)第五部分其他智能技術(shù)方法第六部分結(jié)語與展望

2教材中英文文獻(xiàn)：1.雷德明，嚴(yán)新平“多目標(biāo)智能優(yōu)化算法及其應(yīng)用”，科學(xué)出版社，2009年3月2.邢文訓(xùn)，謝金星“現(xiàn)代優(yōu)化計(jì)算方法”，清華大學(xué)出版社，1999年3第一部分 導(dǎo)言4第一章導(dǎo)言最優(yōu)化的重要性一.傳統(tǒng)優(yōu)化方法的基本步驟——三步曲二.傳統(tǒng)優(yōu)化方法的局限性三.實(shí)際問題中對最優(yōu)化方法的要求四.智能優(yōu)化算法的產(chǎn)生與發(fā)展五.應(yīng)用前景局限性和研究方向5〇.最優(yōu)化的重要性（1）從廣義上說：人類的一切活動(dòng)都是認(rèn)識世界和改造世界的過程即：認(rèn)識世界→ 改造世界 ↓ ↓

(建模過程)(優(yōu)化過程)

6〇.最優(yōu)化的重要性（2）一切學(xué)科都是建模與優(yōu)化在某個(gè)特定領(lǐng)域中的應(yīng)用 概念模型(定性)→結(jié)構(gòu)模型(圖)→ →數(shù)學(xué)模型→智能模型

7最優(yōu)化的重要性（2）從我們控制學(xué)科上說：優(yōu)化控制：如PID參數(shù)優(yōu)化整定，系統(tǒng)優(yōu)化：節(jié)能減排。8最優(yōu)化的重要性（3）最優(yōu)化理論的發(fā)展極值理論；運(yùn)籌學(xué)的興起(OperationResearch)；數(shù)學(xué)規(guī)劃：線性規(guī)劃(LP)；非線性規(guī)劃(NLP)；動(dòng)態(tài)規(guī)劃(PP)；馬爾托夫規(guī)劃(MDP)；排隊(duì)輪；決策論；存儲(chǔ)論。最優(yōu)化理論在國民經(jīng)濟(jì)中的廣泛應(yīng)用 9一.傳統(tǒng)優(yōu)化方法的基本步驟—三步曲（1）如下面框圖所示選一個(gè)初始解LP:大M，二階段法NLP:任意點(diǎn)或一個(gè)內(nèi)點(diǎn) 10一.傳統(tǒng)優(yōu)化方法的基本步驟—三步曲（2）停止判據(jù)——停止規(guī)則最優(yōu)性檢驗(yàn)LP:檢驗(yàn)數(shù) 當(dāng)∏≥0時(shí)有可能減小NLP:11一.傳統(tǒng)優(yōu)化方法的基本步驟—三步曲（3）向改進(jìn)方向移動(dòng)——改進(jìn)解LP:轉(zhuǎn)軸變換(進(jìn)基、退基)NLP:向負(fù)梯度方向移動(dòng)(共軛梯度方向、牛頓方向) 1213停機(jī)選擇一個(gè)初始解停止準(zhǔn)則向改進(jìn)方向移動(dòng)啟動(dòng)YN一.傳統(tǒng)優(yōu)化方法的基本步驟—三步曲（4）二.傳統(tǒng)優(yōu)化方法的局限性（1）對問題中目標(biāo)函數(shù)、約束函數(shù)有很高的要求——有顯式表達(dá)，線性、連續(xù)、可微，且高階可微;2. 只從一個(gè)初始點(diǎn)出發(fā)，難以進(jìn)行并行、網(wǎng)絡(luò)計(jì)算，難以提高計(jì)算效率；同時(shí)最優(yōu)解對初始點(diǎn)的強(qiáng)烈依賴性，容易陷入局部最優(yōu)解

14二.傳統(tǒng)優(yōu)化方法的局限性（2）最優(yōu)性達(dá)到的條件太苛刻——問題的函數(shù)為凸，可行域?yàn)橥?；在非雙凸條件下，沒有跳出局部最優(yōu)解的能力。沒有跳出局部最優(yōu)解的能力，是傳統(tǒng)優(yōu)化算法的致命弱點(diǎn)。

15三.實(shí)際問題中對最優(yōu)化方法的要求（1）對問題的描述要寬松(目標(biāo)和約束函數(shù))——

可以用一段程序來描述(程序中帶判斷、循環(huán))，函數(shù)可以非連續(xù)、非凸、非可微、非顯式；并不苛求最優(yōu)解——通常滿意解、理想解就可以了；16三.實(shí)際問題中對最優(yōu)化方法的要求（2）計(jì)算快速、高效,可隨時(shí)終止(根據(jù)時(shí)間定解的質(zhì)量)；能夠處理數(shù)據(jù)、信息的不確定性(如數(shù)據(jù)的模糊性，事件的隨機(jī)性)。17四.智能優(yōu)化算法的產(chǎn)生與發(fā)展（1）智能優(yōu)化算法的產(chǎn)生一個(gè)重要原因是為了改善傳統(tǒng)優(yōu)化算法局部鄰域收索，獲得全局最優(yōu)解。1975年holland提出遺傳算法

(GeneticAlgorithm)1977年Glouer提出禁忌搜索算法

(TabnSearch) 18四.智能優(yōu)化算法的產(chǎn)生與發(fā)展（2）1982年Kirkpatrick提出模擬退火算(SimulatedAnnealing)，以可控性概率接受劣解來逃離局部最優(yōu)。人工神經(jīng)元網(wǎng)絡(luò)1995年Dorigo提出蟻群算法

(AntColonyOptimization)19四.智能優(yōu)化算法的產(chǎn)生與發(fā)展（3）1995年Kennedy&Eherhart提出粒子群優(yōu)化(ParticleSwarmOptimization)其它文化算法(CulturalAlgorithm)人工生命算法(Artificial-LifeAlgorithm)20四.智能優(yōu)化算法的產(chǎn)生與發(fā)展（4）我們統(tǒng)稱以上算法為人工生命計(jì)算(ArtificialLifeComputation)人工生命計(jì)算+模糊邏輯(FuzzyLogic)=

軟計(jì)算(SoftComputation)人工生命計(jì)算+進(jìn)化編程=

進(jìn)化算法(Evolutionarycomputation)21五.應(yīng)用前景局限性和研究方向、注意事項(xiàng)（1）應(yīng)用前景十分廣闊——國民經(jīng)濟(jì)的各個(gè)領(lǐng)域局限性——不能保證最優(yōu)解，理論上不完備22五.應(yīng)用前景局限性和研究方向、注意事項(xiàng)（2）研究方向及注意事項(xiàng)以應(yīng)用為主，擴(kuò)大面向新問題的應(yīng)用；不要刻意做理論研究，若碰上也不拒絕;算法改進(jìn)表現(xiàn)在以下幾個(gè)方面：問題的描述、編碼方法、算法構(gòu)造及可行性修復(fù)策略;要進(jìn)行大量的上機(jī)計(jì)算；23五.應(yīng)用前景局限性和研究方向、注意事項(xiàng)（3）算例的選取，以下算例的說服力降序排列：網(wǎng)上的測試用例、文獻(xiàn)中的例子、實(shí)際例子、隨機(jī)產(chǎn)生的例子、自己編的例子;如何檢驗(yàn)算法的好壞：比較計(jì)算速度、可解規(guī)模、(從不同的隨機(jī)種子出發(fā))達(dá)優(yōu)率。24TSP問題的概述旅行商問題，即TSP問題（TravelingSalesmanProblem）是數(shù)學(xué)領(lǐng)域中著名問題之一。假設(shè)有一個(gè)旅行商人要拜訪N個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值，這是一個(gè)NP難問題25File:TspByGA.jpg26

第二部分基于自然進(jìn)化的智能計(jì)算技術(shù)

遺傳算法GA,免疫優(yōu)化27第三部分基于群（swarm）的智能計(jì)算技術(shù)粒子群優(yōu)化PSO,蟻群優(yōu)化ACO，捕食搜索PS,群落選址算法CLA2829遺傳算法(GA)的產(chǎn)生

1975年，Holland提出GA

著名的書：

AdaptationinNaturalandArtificialSystems(中文名稱：自然與人工系統(tǒng)的自適應(yīng)性)

后來，DeJong和Goldberg做了大量工作，使GA更加完善。一.導(dǎo)言（1）30遺傳算法(GA)的來源： 生物的進(jìn)化：自然選擇、適者生存生物的遺傳和變異

(GA)缺點(diǎn)：無人的主動(dòng)性； 解決方法有以下三個(gè)：定向培育隨機(jī)算法網(wǎng)格法一.導(dǎo)言（2）3132第四章基于物理自然的智能計(jì)算技術(shù)模擬