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