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

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

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

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

〇.最優(yōu)化的重要性（1）9一切學科都是建模與優(yōu)化在某個特定領域中的應用 概念模型(定性)→結構模型(圖) →數學模型→智能模型

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

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