【正文】 r and mutation 計算 P(t) 的適應(yīng)值 。 133 一般解法 ： 通過引入罰函數(shù)，從不可行解中得到一些信 息。 ? 實際 :一位推銷員從自己所在城市出發(fā)，必須遍訪所有城市之后又回到原來的城市，求使其旅行費用最少的路徑。這樣，基本遺傳 算法的基因操作生成的個體不能滿足這一約束條件，需 尋求其他遺傳操作。 同理的 C2， 144 TSP交叉 3:循環(huán)交叉 (CX) ? CX操作中子個體中的城市碼順序根據(jù)任一父個體產(chǎn)生 ? 確定循環(huán)編碼 ? 復(fù)制循環(huán)編碼到子個體 145 TSP變異 ? Insert Mutation 隨機選取個體中兩個編碼，然后把第二個編碼放在第一 個編碼之后，其他編碼順次調(diào)節(jié)位置。 ? 搜索每條路徑得到其極小解，如果不收斂，則回到第 3步；否則，停止。] xOverOps傳遞給交叉函數(shù)的參數(shù)表，如 [2 0。 eval = x*sin(10*pi*x)+。DS) 包含工具 : 遺傳算法 /直接搜索 運行方式 : mand line。2 0] mutFNs變異函數(shù)表，如 [39。如 [1e6 1 0] termFN終止函數(shù)的名稱 ,如 [39。 146 TSP變異 ? Inversion mutation 隨機選取個體中一段編碼，然后顛倒這段編碼的順序 。 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)系。 其可能的路徑條數(shù)隨著城市數(shù)目 n成指數(shù)增長，如， 5個城市對應(yīng) 12條路徑； 10個城市對應(yīng) 181440條 路徑； 100個城市對應(yīng) 。 ? 關(guān)鍵是如何設(shè)計罰函數(shù)； ? 不同問題需要設(shè)計不同的罰函數(shù)； ? 對一般的約束處理，通常很困難。 對于變量 xi的上、下限約束 li≤xi ≤ ui(i=1,2,… ,n)，依據(jù)解 的精度要求 (有效位數(shù) )求得各個變量 X=(x1,x2,… ,xn)的二進(jìn)制 碼位數(shù) (m1,m2,… ,mn)(確定方法類似于 SGA實例 2)，因此將 n個二進(jìn)制位串順序連接起來，構(gòu)成一個個體的染色體編碼，編 碼的總位數(shù) m＝ m1+m2+… +mn。 127 流程圖 (Flow Chart) 128 SGA偽碼描述 Procedure Geic Algorithm begin t = 0 。因此適應(yīng)函數(shù)的選取至關(guān)重要，直接影響到 GA的收斂速度以及能否找到最優(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ù)群體中失去的 多樣性 方面具有潛在的作用。選擇操作沒有產(chǎn)生新的個體，群體中最好個體的適應(yīng)值不會改變。 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)大 變異操作有 ” 擾動 ” 作用，同時具有增加種群多 樣性的效果。 93 SGA實例 1：函數(shù)最值 SGA參數(shù) : ? 編碼方式 : 二進(jìn)制碼 . 00000?0。 一種改進(jìn)的模擬退火算法 80 模擬退火算法的改進(jìn) 智能優(yōu)化計算 ? 改進(jìn)的退火過程 （ 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)用改進(jìn)的抽樣過程，返回其所得最優(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*作為最終解輸出，停止算法。 end t0=(max(fval0)min(fval0))/log()。82 7。25 38。71 44。 ? 模擬退火算法的缺點 由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此優(yōu)化過程較長。 Until 抽樣穩(wěn)定準(zhǔn)則滿足； 退溫 tk+1=update(tk)并令 k=k+1； Until 算法終止準(zhǔn)則滿足； 輸出算法搜索結(jié)果。 46 模擬退火算法及模型 智能優(yōu)化計算 ? Metropolis準(zhǔn)則（ 1953） —— 以概率接受新狀態(tài) p=exp[(EjEi)/kBT] 物理退火過程 ? 在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新狀態(tài)。 38 ? 什么是退火： 退火是指將固體加熱到足夠高的溫度，使分子呈隨機排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。 B考慮了一下說， 但是，我還有一點信息來解決你的這 個難題。 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ù)的要求 。 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 題 伽馬刀問題也是目前研究的課題，目前算法最佳的是遺傳算法 。其中很 多問題是 NP完全 (Nondeterministic Polynomial Completeness)問題 . 21 ? 待解決的問題 連續(xù)性問題，以微積分為基礎(chǔ)， 規(guī)模較小 ? 傳統(tǒng)的優(yōu)化方法 理論上的準(zhǔn)確與完美，主要方法：線性與非線性規(guī)劃、動態(tài)規(guī)劃、多目標(biāo)規(guī)劃、整數(shù)規(guī)劃等；排隊論、庫存論、對策論、決策論等。 4)SA、 GA可應(yīng)用于大規(guī)模、多峰多態(tài)函數(shù)、含離散變量等全局優(yōu)化問題；求解速度和質(zhì)量遠(yuǎn)超過常規(guī)方法。 A指著對面的一幢房子說。為的能量，表示狀態(tài)機變量，表示分子能量的一個隨42 模擬退火算法及模型 智能優(yōu)化計算 ? 數(shù)學(xué)表述 在 同一個溫度 T，選定兩個能量 E1E2，有 物理退火過程 ?????????????? ??????????? ?????TkEETkETZEEPEEP BB12121 e x p1e x p)(1}{}{1 0 在同一個溫度，分子停留在能量小的狀態(tài)的概率比停留在能量大的狀態(tài)的概率要大。我方派一架飛機從基地出發(fā)，偵察完敵方所有目標(biāo)，再返回原來的基地。 初溫 61 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計 智能優(yōu)化計算 ? 時齊算法的溫度下降函數(shù) （ 1） ， α越接近 1溫度下降越慢，且其大小可以不斷變化； （ 2） ，其中 t0為起始溫度， K為算法溫度下降的總次數(shù)。54 67。64 60。71 71。45 21。 退溫系數(shù) alpha=。 一種改進(jìn)的模擬退火算法 82 Part 3 遺傳算法 83 遺傳算法 (Geic Algorithm) ?進(jìn)化算法 (Evolutionary Algorithm) 84 遺傳算法 (GA) ? Darwin(1859): “物竟天擇，適者生存 ” ? John Holland (university of Michigan, 1975) 《 Adaptation in Natural and Artificial System》 ? 遺傳算法作為一種有效的工具，已廣泛地應(yīng)用于最優(yōu)化問題求解之中 。因 2097152＝ 221 3X106≤222＝ 4194304。 ? 交叉 (crossover): 將群體 P(t)內(nèi)的各個個體隨機搭配成對，對每一個個體，以某個概率 Pc (稱為交叉概率， crossvoer rate)交換它們之間的部分染色體。 ? 交叉產(chǎn)生兩個子染色體，他們與其父代不同，且彼此不同 , 每個子染色體都帶有雙親染色體的遺傳基因。 等到達(dá)一定程度時，值 0會從整個群體中那個位上消失，然而全局最 優(yōu)解可能在染色體中那個位上為 0。 (2) 計算種群體中每個個體的 適應(yīng)度值 ,判斷是否滿足停止條件，若不滿足，則轉(zhuǎn)第 (3)步 ,否則轉(zhuǎn)第(6)步 。 while (不滿足停止準(zhǔn)則 ) do begin t = t+1 。 假設(shè)按無約束問題那樣求解，在搜索過程中計算目標(biāo)函 數(shù)值，并檢查是否有約束違反。設(shè)C=(cij)是與 E相聯(lián)系的距離矩陣。 138 TSP編碼 :路徑表示 染色體表示成所有城市的一個排列，若有 n個城市，一 條可能路徑編碼為長度為 n的整數(shù)向量 (i1,i2,… ,in),其中 ik表示第 ik個城市。 142 TSP交叉 2:順序交叉 (OX) ? 雙親 P1,P2隨機選取兩個交叉點 1 2 3 4 5 6 7 8 9 9 3 7 8 2 6 5 1 4 P1 P2 x x x 4 5 6 7 x x x x x 8 2 6 5 x x c1 c2 ? 兩個交叉點間的中間段保存不變 ? 子個體 C1的未定碼的確定需要父個體 P2的未選定城市碼，子個體 C2的未定碼的確定需要父個體 P1的未選定城市碼。 ? 利用最優(yōu)方法搜索每條路徑的局部最優(yōu)解 。normGeomSelect39。6 100 3