智能優(yōu)化方法-第1章導(dǎo)言

1智能優(yōu)化方法

AI-BasedOptimizationMethodsByWangHongfengPhDISE,NEUChina2013不是最優(yōu)解2課程安排No.1 導(dǎo)言、偽隨機(jī)數(shù)的產(chǎn)生方法No.2 禁忌搜索No.3 模擬退火No.4 進(jìn)化算法之GA-INo.5 進(jìn)化算法之GA-II3課程安排No.6其他進(jìn)化算法(ES,EP,GP)No.7群體智能算法(PSO)No.8群體智能算法(ACO)No.9智能優(yōu)化領(lǐng)域的新進(jìn)展4課程理解這是一門關(guān)于計(jì)算智能的課程這是一門介紹優(yōu)化工具的課程這是一門注重技巧學(xué)習(xí)的課程讓我們共勉?。?！5教材《智能優(yōu)化方法》汪定偉王俊偉王洪峰等編著高等教育出版社中英文文獻(xiàn)6第一章 導(dǎo)言7第一章導(dǎo)言〇.最優(yōu)化的重要性一.傳統(tǒng)優(yōu)化方法的基本步驟——三步曲二.傳統(tǒng)優(yōu)化方法的局限性三.實(shí)際問題中對(duì)最優(yōu)化方法的要求四.智能優(yōu)化算法的產(chǎn)生與發(fā)展五.應(yīng)用前景局限性和研究方向、注意事項(xiàng)六.優(yōu)化領(lǐng)域的新進(jìn)展七.學(xué)習(xí)這門課程需要具備的基礎(chǔ)8人類的一切活動(dòng)都是認(rèn)識(shí)世界和改造世界的過程即：認(rèn)識(shí)世界→ 改造世界 ↓ ↓

(建模)→(優(yōu)化)

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

〇.最優(yōu)化的重要性（2）10最優(yōu)化理論的發(fā)展極值理論運(yùn)籌學(xué)的興起(OR)數(shù)學(xué)規(guī)劃：線性規(guī)劃(LP)；非線性規(guī)劃(NLP)；動(dòng)態(tài)規(guī)劃(DP)；馬爾可夫規(guī)劃(MDP)最優(yōu)化理論在國(guó)民經(jīng)濟(jì)中的廣泛應(yīng)用 〇.最優(yōu)化的重要性（3）11如右圖所示選一個(gè)初始解LP：大M法，二階段法NLP：任意點(diǎn)或一個(gè)內(nèi)點(diǎn) 一.傳統(tǒng)優(yōu)化方法的基本步驟—三步曲（1）停止選初始解停止判據(jù)改進(jìn)解開始YN12停止判據(jù)——最優(yōu)性檢驗(yàn)LP：檢驗(yàn)數(shù)當(dāng)∏≥0時(shí)有可能減小NLP：一.傳統(tǒng)優(yōu)化方法的基本步驟—三步曲（2）13向改進(jìn)方向移動(dòng)——改進(jìn)解LP：轉(zhuǎn)軸變換（進(jìn)基、退基）NLP：向負(fù)梯度方向移動(dòng)（共軛梯度方向、牛頓方向）一.傳統(tǒng)優(yōu)化方法的基本步驟—三步曲（3）14停止選擇一個(gè)初始解最優(yōu)性檢驗(yàn)向改進(jìn)方向移動(dòng)開始YN一.傳統(tǒng)優(yōu)化方法的基本步驟—三步曲（4）15對(duì)問題中目標(biāo)函數(shù)、約束函數(shù)有很高的要求——有顯式表達(dá)，線性、連續(xù)、可微，且高階可微2. 只從一個(gè)初始點(diǎn)出發(fā)，難以進(jìn)行并行、網(wǎng)絡(luò)計(jì)算，難以提高計(jì)算效率

二.傳統(tǒng)優(yōu)化方法的局限性（1）16最優(yōu)性達(dá)到的條件太苛刻——目標(biāo)函數(shù)為凸，可行域?yàn)橥乖诜请p凸條件下，沒有跳出局部最優(yōu)解的能力二.傳統(tǒng)優(yōu)化方法的局限性（2）17對(duì)問題的描述要寬松（目標(biāo)和約束函數(shù)）——可以用一段程序來(lái)描述(程序中帶判斷、循環(huán))，函數(shù)可以非連續(xù)、非凸、非可微、非顯式并不苛求最優(yōu)解——通常滿意解、理想解，甚至可行解就可以三.實(shí)際問題中對(duì)最優(yōu)化方法的要求（1）18計(jì)算快速、高效，可隨時(shí)終止（根據(jù)時(shí)間定解的質(zhì)量）能夠處理數(shù)據(jù)和信息的不確定性（如數(shù)據(jù)的模糊性，事件的隨機(jī)性）三.實(shí)際問題中對(duì)最優(yōu)化方法的要求（2）19啟發(fā)式算法：1977年Glover提出禁忌搜索(TS)1982年Kirkpatrick提出模擬退火(SA)進(jìn)化算法：1965年Rechenberg等提出進(jìn)化策略(ES)1975年Holland提出遺傳算法(GA)四.智能優(yōu)化算法的產(chǎn)生與發(fā)展（1）20進(jìn)化算法：1995年Fogel提出進(jìn)化規(guī)劃(EP)1995年Tackett提出遺傳規(guī)劃(GP)群體智能算法：1995年Kennedy等提出粒子群優(yōu)化算法(PSO)1995年Dorigo提出蟻群算法(ACO)四.智能優(yōu)化算法的產(chǎn)生與發(fā)展（2）21其他算法：1994年Reynolds提出文化算法(CA)1995年Storn等提出差分進(jìn)化(DE)1998年Linhares提出捕食搜索算法(PS)2002年Narayanan提出量子進(jìn)化算法(QEA)2004年Wang提出群落選址算法(CLA)四.智能優(yōu)化算法的產(chǎn)生與發(fā)展（3）22應(yīng)用前景十分廣闊——國(guó)民經(jīng)濟(jì)的各個(gè)領(lǐng)域局限性——不能保證最優(yōu)解，理論上不完備五.應(yīng)用前景局限性和研究方向、注意事項(xiàng)（1）23研究方向及注意事項(xiàng)以應(yīng)用為主，擴(kuò)大面向新問題的應(yīng)用；不要刻意做理論研究，若碰上也不拒絕算法改進(jìn)表現(xiàn)在以下幾個(gè)方面：?jiǎn)栴}的描述、編碼方法、算法構(gòu)造及可行性修復(fù)策略要進(jìn)行大量的上機(jī)計(jì)算五.應(yīng)用前景局限性和研究方向、注意事項(xiàng)（2）24算例的選取以下算例的說(shuō)服力降序排列：網(wǎng)上的測(cè)試用例、文獻(xiàn)中的例子、實(shí)際例子、隨機(jī)產(chǎn)生的例子、自己編的例子Benchmark的不斷發(fā)展如何檢驗(yàn)算法的好壞：比較計(jì)算速度、可解規(guī)模、（從不同的隨機(jī)種子出發(fā)）達(dá)優(yōu)率——客觀公正與良心！五.應(yīng)用前景局限性和研究方向、注意事項(xiàng)（3）25隨著人們關(guān)注的系統(tǒng)越來(lái)越復(fù)雜，最優(yōu)化技術(shù)也相應(yīng)不斷發(fā)展最優(yōu)化方法的發(fā)展1940s－1970s：數(shù)學(xué)規(guī)劃階段——目標(biāo)和約束是解析函數(shù)1970s—