現代優化算法ppt課件(2)(已修改)

　

【正文】 現代優化算法 潘克家 202288 2 目錄 ? 現在優化算法概論 ? 模擬退火算法 (SA) ? 遺傳算法 (GA) 3 Part 1 概論 主要是說明現代優化算法的重要性。 4 現代優化算法 ? 現代優化算法 遺傳算法 模擬退火算法 禁忌搜索算法 人工神經網絡 蟻群算法 粒子群算法 差分進化算法 特點： ? 基于客觀世界中的一些自然現象； ? 建立在計算機迭代計算的基礎上； ? 具有普適性，可解決實際應用問題。 5 數學建模競賽中的算法 (1) ? 93A 非線性交調的頻率設計 : 擬合、規劃 ? 93B 足球隊排名次 : 矩陣論、圖論、層次分析法、整數規劃 ? 94A 逢山開路 : 圖論、插值、動態規劃 ? 94B 鎖具裝箱問題 : 圖論、組合數學 ? 95A 飛行管理問題 : 非線性規劃、線性規劃 ? 95B 天車與冶煉爐的作業調度 : 非線性規劃、動態規劃、層次分析法、 PETRI方法、圖論方法、排隊論方法 ? 96A 最優捕魚策略 ： 微分方程、積分、非線性規劃 6 ? 96B 節水洗衣機 ： 非線性規劃 ? 97A 零件參數設計 ： 微積分、非線性規劃、隨機模擬 ? 97B 截斷切割 ： 組合優化、幾何變換、枚舉、蒙特卡羅、遞歸、最短路 ? 98A 投資收益與風險 ： 線性規劃、非線性規劃 ? 98B 災情巡視 ： 最小生成樹、 Hamilton圈、旅行商問題 ? 99A 自動化車床 ： 積分、概率分布、隨機模擬、分布擬合度檢驗 數學建模競賽中的算法 (2) 7 ? 99B 鉆井布局 ： 幾何變換、枚舉、最大完全子圖、混合整數規劃 ? 00A DNA分類 ： 神經網絡、最小二乘擬合、統計分類 ? 00B 管道訂購 ： 最短路、二次規劃 ? 01A 血管的三維重建 ： 數據挖掘、曲面重建與擬合 ? 01B 公交車調度 ： 非線性規劃 ? 02A 車燈光源優化設計 ： 最優化 ? 02B 彩票中的數學 ： 概率與優化 數學建模競賽中的算法 (3) 14 ? 97年 A 題用模擬退火算法 ? 00年 B 題用神經網絡分類算法 ? 01年 B 題這種難題也可以使用神經網絡 ? 美國 89年 A 題也和 BP 算法 有關系 ? 美國 03年 B 題 伽馬刀問題也是目前研究的課題，目前算法最佳的是遺傳算法 。 最優化理論的三大非經典算法 : 模擬退火法 (SA)、神經網絡 (NN)、遺傳算法 (GA) 近幾年的賽題越來越復雜，很多問題沒有什么很好的 模型可以借鑒，于是這三類算法很多時候可以派上用場。 19 優化模型 實際問題中 的優化模型 1( ) ( ) , ( , ). . ( ) 0 , 1 , 2 ,TniM in M a x z f x xs t g i m????或 xxxx~決策變量 f(x)~目標函數 gi(x)?0~約束條件 數學規劃 線性規劃 (LP) 二次規劃 (QP) 非線性規劃 (NLP) 純整數規劃 (PIP) 混合整數規劃 (MIP) 整數規劃 (IP) 01整數規劃 一般整數規劃 連續規劃 20 最優化問題 (Optimization Problem) 最優化問題 : 1212( ) ( , , , )( , , , )nnM i nim i ze f x f x x xsub j e c t t o x x x x S X?? ? ?組合優化問題 (Combinatorial Optimization Problem ) : 最優化問題中的解空間 X或 S由離散集合構成。其中很 多問題是 NP完全 (Nondeterministic Polynomial Completeness)問題 . 21 ? 待解決的問題 連續性問題，以微積分為基礎， 規模較小 ? 傳統的優化方法 理論上的準確與完美，主要方法：線性與非線性規劃、動態規劃、多目標規劃、整數規劃等；排隊論、庫存論、對策論、決策論等。 ? 傳統的評價方法 算法收斂性、收斂速度 傳統優化方法 22 現代優化算法 現代優化算法 又稱 智能優化算法 或 現代啟發式算法 ，是一種具有全局優化性能、通用性強、且適合于并行處理的算法。這種算法一般具有嚴密的理論依據，而不是單純憑借專家經驗，理論上可以在一定的時間內找到最優解或近似最優解。 23 ? 待解決的問題 離散性、連續的、不確定性、 大規模 ? 現代的優化方法 啟發式算法（ heuristic algorithm） 追求滿意（近似解） 實用性強（解決實際工程問題） ? 現代的評價方法 算法復雜性 現代優化方法 24 現代優化算法的特點 它們的共同特點：都是從任一解出發，按照 某種機制，以 一定的概率 在整個求解空間中探索 最優解。由于它們可以把搜索空間擴展到整個問 題空間，因而具有 全局優化性能 。 25 全局優化 (Rastrigin’s Function) 221 2 1 2( ) 20 10( c os 2 c os 2 )Ras x x x x x??? ? ? ? ?全局最小點(0,0) ? 26 現代優化算法 特點： 1)不依賴于初始條件； 2)不與求解空間有緊密關系 ,對解域無可微或連續的要求 。容易實現，求解穩健。 3)但收斂速度慢，能獲得全局最優；適合于求解空間不知的情況。 4)SA、 GA可應用于大規模、多峰多態函數、含離散變量等全局優化問題；求解速度和質量遠超過常規方法。 27 常用的現代優化算法 ? 遺傳算法 Geic Algorithm，簡稱 GA ? 模擬退火算法 Simulated Annealing，簡稱 SA ? 禁忌搜索算法 Tabu Search，簡稱 TS ? 神經網絡算法 Neural Network Algorithm，簡稱 NNA ? 粒子群算法 Particle Swarm Optimization， 簡稱 PSO ? 差分進化算法 Differential Evolution， 簡稱 DE 28 搜索示例：三個孩子的年齡 (1) 兩個多年未見的朋友相遇，聊了很多事情。 … A： 既然你是數學教授，那你幫我算這個題，今天是 個特殊日子：我三個兒子都在今天慶祝生日！那么你 能算出他們都有多大嗎？ B：好，但你得跟我講講他們的情況。 A：好的，我給你一些提示，他們三個年齡之積是 36. B：很好，但我還需要更多提示。 29 三個孩子的年齡 (2) A：我的大兒子的眼睛是藍色的。 B考慮了一下說， 但是，我還有一點信息來解決你的這 個難題。 B：哦，夠了， B 給出了正確的答案，即三個小孩的年齡。 A：他們三個年齡之和等于那幢房子的窗戶個數。 A指著對面的一幢房子說。 30 三個孩子的年齡 (3) 根據對話信息，用 搜索 的方法來解此問題。 信息 1:三個小孩年齡之積為 36 只有以下 8種可能，搜索范圍減少至 8種情況 : 第一個小孩年齡 36 18 12 9 9 6 6 4 第二個小孩年齡 1 2 3 4 2 6 3 3 第三個小孩年齡 1 1 1 1 2 1 2 3 31 三個孩子的年齡 (4) 信息 2:三個小孩年齡之和等于窗戶數 第一個小孩年齡 36 18 12 9 9 6 6 4 第二個小孩年齡 1 2 3 4 2 6 3 3 第三個小孩年齡 1 1 1 1 2 1 2 3 窗戶數 : 38 21 16 14 13 13 11 10 如果窗戶數為 3 2 1 1 1 10即可得出答案 B還需信息，即窗戶數為 13. 則可能為 ( 2)或 ( 1) 信息 2:大兒子眼睛是藍色的 得答案： ( 2) 32 ? 典型問題 —— 旅行商問題（ Traveling salesman problem, TSP） 1 2 3 4 12 1 8 10 3 2 搜索示例： TSP問題 給定 n個城市和兩兩 城市之間的距離，要 求確定一條經過各城 市當且僅當一次的最 短路線。 33 ? 典型問題 —— 旅行商問題 城市數 24 25 26 27 28 29 30 31 計算 時間 1 sec 24 sec 10 min hour day day year 325 year TSP的搜索的困難 計算復雜度：指數災難 34 Part 2 模擬退火法 35 36 37 模擬退火算法及模型 ? 算法的提出 模擬退火算法最早的思想由 Metropolis等（ 1953）提出，1983年 Kirkpatrick等將其應用于組合優化。 物理退火過程 ? 算法的目的 解決 NP復雜性 問題； 克服優化過程陷入局部極小； 克服初值依賴性。 38 ? 什么是退火： 退火是指將固體加熱到足夠高的溫度，使分子呈隨機排列狀態，然后逐步降溫使之冷卻，最后分子以低能狀態排列，固體達到某種穩定狀態。 物理退火過程 39 模擬退火算法及模型 等溫過程 —— 對于與環境換熱而溫度不變的封閉系統，系統狀態的自發變化總是朝自由能減少的方向進行，當自由能達到最小時，系統達到平衡態； ? 物理退火過程 加溫過程 —— 增強粒子的熱運動，消除系統原先可能存在的非均勻態； 冷卻過程 —— 使粒子熱運動減弱并漸趨有序，系統能量逐漸下降，從而得到低能的晶體結構。 40 41 模擬退火算法及模型 智能優化計算 ? 數學表述 在溫度 T，分子停留在狀態 r滿足 Boltzmann概率分布 物理退火過程 ????????????????????????Ds BBBTksETZTZkrrEETkrETZrEEP)(e x p)()(B o l t z m a n n0)()(e x p)(1)}({子：為概率分布的標準化因常數。為的能量，表示狀態機變量，表示分子能量的一個隨42 模擬退火算法及模型 智能優化計算 ? 數學表述 在 同一個溫度 T，選定兩個能量 E1E2，有 物理退火過程 ?????????????? ??????????? ?????TkEETkETZEEPEEP BB12121 e x p1e x p)(1}{}{1 0 在同一個溫度，分子停留在能量小的狀態的概率比停留在能量大的狀態的概率要大。 43 智能優化計算 若 |D|為狀態空間 D中狀態的