【正文】 法 /直接搜索 運行方式 : mand line。4 100 3。2 0] mutFNs變異函數(shù)表，如 [39。] selectOps傳遞個選擇函數(shù)的參數(shù) ,如 [] xOverFNs交叉函數(shù)名稱表，以空格分開，如[39。如 [1e6 1 0] termFN終止函數(shù)的名稱 ,如 [39。 ? 選擇交叉對使在平均性能之上的個體得到更多的子代 。 146 TSP變異 ? Inversion mutation 隨機選取個體中一段編碼，然后顛倒這段編碼的順序 。 143 TSP交叉 2:順序交叉 (OX) ? 記取父個體 P2從第二個交叉點開始城市碼的排列順序，當(dāng)?shù)竭_表尾時，返回表頭繼續(xù)記錄，直到第二個交叉點。 1 2 3 4 5 5 4 3 2 1 1 2 3 2 1 5 4 3 4 5 一般的交叉操作會產(chǎn)生不合適的解，如 140 TSP交叉 1:部分匹配交叉 (PMX) ? 雙親 P1,P2隨機選取兩個交叉點，得到一個匹配段 ,根據(jù)交叉點中間段給出映射關(guān)系。 例如 : 路徑編碼向量 (5 1 7 8 9 4 6 2 3)直接表示一條 旅行路程 (517894623)。 其可能的路徑條數(shù)隨著城市數(shù)目 n成指數(shù)增長，如， 5個城市對應(yīng) 12條路徑； 10個城市對應(yīng) 181440條 路徑； 100個城市對應(yīng) 。尋找一條通過所有頂點且每個頂點只通過一次的最短距離回路(Hamilton回路 )。 ? 關(guān)鍵是如何設(shè)計罰函數(shù)； ? 不同問題需要設(shè)計不同的罰函數(shù)； ? 對一般的約束處理，通常很困難。如果沒有違反，則表明是 可行解，就根據(jù)目標(biāo)函數(shù)指定一適應(yīng)值；否則，就是不可 行解，因而沒有適應(yīng)值 (適應(yīng)值為 0)。 對于變量 xi的上、下限約束 li≤xi ≤ ui(i=1,2,… ,n)，依據(jù)解 的精度要求 (有效位數(shù) )求得各個變量 X=(x1,x2,… ,xn)的二進制 碼位數(shù) (m1,m2,… ,mn)(確定方法類似于 SGA實例 2)，因此將 n個二進制位串順序連接起來，構(gòu)成一個個體的染色體編碼，編 碼的總位數(shù) m＝ m1+m2+… +mn。 從 P(t1)中選擇 P(t) 。 127 流程圖 (Flow Chart) 128 SGA偽碼描述 Procedure Geic Algorithm begin t = 0 。 (3) 按由個體適應(yīng)值所決定的某個規(guī)則 選擇 進入下一代的個體 。因此適應(yīng)函數(shù)的選取至關(guān)重要，直接影響到 GA的收斂速度以及能否找到最優(yōu)解。如果搜索范圍縮小到實際包含全局 最優(yōu)解的那部分搜索空間，在那個位上的值 0就可能正好是到達全局最 優(yōu)解所需要的。 ? 變異概率 Pm 一般介于 1/種群規(guī)模與 1/染色體長度之間，平均約 12% 1 1 0 1 0 1 0 0 父代 0 1 0 1 0 1 0 1 子代 變異基因 變異基因 121 變異 (Mutation) ? 比起選擇和交叉操作， 變異操作 是 GA中的次要操作，但它在恢復(fù)群體中失去的 多樣性 方面具有潛在的作用。 118 單點交叉 (1point crossover) ? 在雙親的父代染色體中隨機產(chǎn)生一個交叉點位置 ? 在交叉點位置分離雙親染色體 ? 互換交叉點位置右邊的基因碼產(chǎn)生兩個子代染色體 ? 交叉概率 Pc 一般范圍為 (60%, 90%)，平均約 80% 1 1 1 1 1 1 1 1 父代 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 子代 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 交叉點位置 119 交叉 (crossover, Rebination) ? 單點交叉操作可以產(chǎn)生與父代染色體完全不同的子代染色體；它不會改變父代染色體中相同的基因。選擇操作沒有產(chǎn)生新的個體，群體中最好個體的適應(yīng)值不會改變。 ? 變異 (mutation): 對群體 P(t)中的每一個個體，以某一概率 Pm(稱為變異概率， mutation rate)改變某一個或一些基因座上基因值為其它的等位基因。 102 SGA實例 2 :遺傳操作 ? 變異操作 變異前 (父 ): s2=1110000000111111000101 變異后 (子 ): s’2=1110100000111111000101 適應(yīng)值 f(s’2) = f( 638) = 743 比 f(s2)小 變異前 (父 ): s2=1110000000111111000101 變異后 (子 ): s”2=1110000001111111000101 適應(yīng)值 f(s”2) = f( 818) = 555 比 f(s2)大 變異操作有 ” 擾動 ” 作用，同時具有增加種群多 樣性的效果。故編碼的二進制串長 L=22。 93 SGA實例 1：函數(shù)最值 SGA參數(shù) : ? 編碼方式 : 二進制碼 . 00000?0。 ? 遺傳算法是一種基于自然群體遺傳進化機制的自適應(yīng)全局優(yōu)化概率搜索算法。 一種改進的模擬退火算法 80 模擬退火算法的改進 智能優(yōu)化計算 ? 改進的退火過程 （ 1）給定初溫 t0，隨機產(chǎn)生初始狀態(tài) s，令初始最優(yōu)解 s*=s，當(dāng)前狀態(tài)為 s(0)=s， i=p=0； （ 2）令 t=ti，以 t， s*和 s(i)調(diào)用改進的抽樣過程，返回其所得最優(yōu)解 s*’和當(dāng)前狀態(tài) s’(k)，令當(dāng)前狀態(tài) s(i)=s’(k)； （ 3）判斷 C(s*)C(s*’)? 若是，則令 p=p+1；否則，令 s*=s*’， p=0； （ 4）退溫 ti+1=update(ti)，令 i=i+1； （ 5）判斷 pm2? 若是，則轉(zhuǎn)第 (6)步；否則，返回第 (2)步； （ 6）以最優(yōu)解 s*作為最終解輸出，停止算法。 內(nèi)循環(huán)次數(shù) L=200*CityNum。 end t0=(max(fval0)min(fval0))/log()。41 26。82 7。74 78。25 38。18 54。71 44。25 62。 ? 模擬退火算法的缺點 由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此優(yōu)化過程較長。 溫度更新函數(shù) 10 ,0 ,1 ????? ?? ktt kk0tKkKtk??? 若固定每一溫度，算法均計算至平穩(wěn)分布，然后下降溫度，則稱為時齊算法； ? 若無需各溫度下算法均達到平穩(wěn)分布，但溫度需按一定速率下降，則稱為非時齊算法。 Until 抽樣穩(wěn)定準則滿足； 退溫 tk+1=update(tk)并令 k=k+1； Until 算法終止準則滿足； 輸出算法搜索結(jié)果。在敵方每一目標(biāo)點的偵察時間不計，求該架飛機所花費的時間（假設(shè)我方飛機巡航時間可以充分長）。 46 模擬退火算法及模型 智能優(yōu)化計算 ? Metropolis準則（ 1953） —— 以概率接受新狀態(tài) p=exp[(EjEi)/kBT] 物理退火過程 ? 在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新狀態(tài)。 43 智能優(yōu)化計算 若 |D|為狀態(tài)空間 D中狀態(tài)的個數(shù)， D0是具有最低能量的狀態(tài)集合： 當(dāng)溫度很高時，每個狀態(tài)概率基本相同，接近平均值1/|D|； 狀態(tài)空間存在超過兩個不同能量時，具有最低能量狀態(tài)的概率超出平均值 1/|D| ； 當(dāng)溫度趨于 0時，分子停在最低能量狀態(tài)概率趨于 1。 38 ? 什么是退火： 退火是指將固體加熱到足夠高的溫度，使分子呈隨機排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達到某種穩(wěn)定狀態(tài)。 30 三個孩子的年齡 (3) 根據(jù)對話信息，用 搜索 的方法來解此問題。 B考慮了一下說， 但是，我還有一點信息來解決你的這 個難題。 27 常用的現(xiàn)代優(yōu)化算法 ? 遺傳算法 Geic Algorithm，簡稱 GA ? 模擬退火算法 Simulated Annealing，簡稱 SA ? 禁忌搜索算法 Tabu Search，簡稱 TS ? 神經(jīng)網(wǎng)絡(luò)算法 Neural Network Algorithm，簡稱 NNA ? 粒子群算法 Particle Swarm Optimization， 簡稱 PSO ? 差分進化算法 Differential Evolution， 簡稱 DE 28 搜索示例：三個孩子的年齡 (1) 兩個多年未見的朋友相遇，聊了很多事情。 25 全局優(yōu)化 (Rastrigin’s Function) 221 2 1 2( ) 20 10( c os 2 c os 2 )Ras x x x x x??? ? ? ? ?全局最小點(0,0) ? 26 現(xiàn)代優(yōu)化算法 特點： 1)不依賴于初始條件； 2)不與求解空間有緊密關(guān)系 ,對解域無可微或連續(xù)的要求 。 ? 傳統(tǒng)的評價方法 算法收斂性、收斂速度 傳統(tǒng)優(yōu)化方法 22 現(xiàn)代優(yōu)化算法 現(xiàn)代優(yōu)化算法 又稱 智能優(yōu)化算法 或 現(xiàn)代啟發(fā)式算法 ，是一種具有全局優(yōu)化性能、通用性強、且適合于并行處理的算法。 5 數(shù)學(xué)建模競賽中的算法 (1) ? 93A 非線性交調(diào)的頻率設(shè)計 : 擬合、規(guī)劃 ? 93B 足球隊排名次 : 矩陣論、圖論、層次分析法、整數(shù)規(guī)劃 ? 94A 逢山開路 : 圖論、插值、動態(tài)規(guī)劃 ? 94B 鎖具裝箱問題 : 圖論、組合數(shù)學(xué) ? 95A 飛行管理問題 : 非線性規(guī)劃、線性規(guī)劃 ? 95B 天車與冶煉爐的作業(yè)調(diào)度 : 非線性規(guī)劃、動態(tài)規(guī)劃、層次分析法、 PETRI方法、圖論方法、排隊論方法 ? 96A 最優(yōu)捕魚策略 ： 微分方程、積分、非線性規(guī)劃 6 ? 96B 節(jié)水洗衣機 ： 非線性規(guī)劃 ? 97A 零件參數(shù)設(shè)計 ： 微積分、非線性規(guī)劃、隨機模擬 ? 97B 截斷切割 ： 組合優(yōu)化、幾何變換、枚舉、蒙特卡羅、遞歸、最短路 ? 98A 投資收益與風(fēng)險 ： 線性規(guī)劃、非線性規(guī)劃 ? 98B 災(zāi)情巡視 ： 最小生成樹、 Hamilton圈、旅行商問題 ? 99A 自動化車床 ： 積分、概率分布、隨機模擬、分布擬合度檢驗 數(shù)學(xué)建模競賽中的算法 (2) 7 ? 99B 鉆井布局 ： 幾何變換、枚舉、最大完全子圖、混合整數(shù)規(guī)劃 ? 00A DNA分類 ： 神經(jīng)網(wǎng)絡(luò)、最小二乘擬合、統(tǒng)計分類 ? 00B 管道訂購 ： 最短路、二次規(guī)劃 ? 01A 血管的三維重建 ： 數(shù)據(jù)挖掘、曲面重建與擬合 ? 01B 公交車調(diào)度 ： 非線性規(guī)劃 ? 02A 車燈光源優(yōu)化設(shè)計 ： 最優(yōu)化 ? 02B 彩票中的數(shù)學(xué) ： 概率與優(yōu)化 數(shù)學(xué)建模競賽中的算法 (3) 14 ? 97年 A 題用模擬退火算法 ? 00年 B 題用神經(jīng)網(wǎng)絡(luò)分類算法 ? 01年 B 題這種難題也可以使用神經(jīng)網(wǎng)絡(luò) ? 美國 89年 A 題也和 BP 算法 有關(guān)系 ? 美國 03年 B 題 伽馬刀問題也是目前研究的課題，目前算法最佳的是遺傳算法 。 4 現(xiàn)代優(yōu)化算法 ? 現(xiàn)代優(yōu)化算法 遺傳算法 模擬退火算法 禁忌搜索算法 人工神經(jīng)網(wǎng)絡(luò) 蟻群算法 粒子群算法 差分進化算法 特點： ? 基于客觀世界中的一些自然現(xiàn)象； ? 建立在計算機迭代計算的基礎(chǔ)上； ? 具有普適性，可解決實際應(yīng)用問題。其中很 多問題是 NP完全 (Nondeterministic Polynomial Completeness)問題 . 21 ? 待解決的問題 連續(xù)性問題，以微積分為基礎(chǔ)， 規(guī)模較小 ? 傳統(tǒng)的優(yōu)化方法 理論上的準確與完美，主要方法：線性與非線性規(guī)劃、動態(tài)規(guī)劃、多目標(biāo)規(guī)劃、整數(shù)規(guī)劃等；排隊論、庫存論、對策論、決策論等。由于它們可以把搜索空間擴展到整個問 題空間，因而具有 全局優(yōu)化性能 。 4)SA、 GA可應(yīng)用于大規(guī)模、多峰多態(tài)函數(shù)、含離散變量等全局優(yōu)化問題；求解速度和質(zhì)量遠超過常規(guī)方法。 29 三個孩子