【正文】 6 100 3。 ? 利用最優(yōu)方法搜索每條路徑的局部最優(yōu)解 。 138 TSP編碼 :路徑表示 染色體表示成所有城市的一個(gè)排列，若有 n個(gè)城市，一 條可能路徑編碼為長(zhǎng)度為 n的整數(shù)向量 (i1,i2,… ,in),其中 ik表示第 ik個(gè)城市。 假設(shè)按無約束問題那樣求解，在搜索過程中計(jì)算目標(biāo)函 數(shù)值，并檢查是否有約束違反。 (2) 計(jì)算種群體中每個(gè)個(gè)體的 適應(yīng)度值 ,判斷是否滿足停止條件，若不滿足，則轉(zhuǎn)第 (3)步 ,否則轉(zhuǎn)第(6)步 。 ? 交叉產(chǎn)生兩個(gè)子染色體，他們與其父代不同，且彼此不同 , 每個(gè)子染色體都帶有雙親染色體的遺傳基因。因 2097152＝ 221 3X106≤222＝ 4194304。 退溫系數(shù) alpha=。71 71。54 67。我方派一架飛機(jī)從基地出發(fā)，偵察完敵方所有目標(biāo)，再返回原來的基地。 A指著對(duì)面的一幢房子說。其中很 多問題是 NP完全 (Nondeterministic Polynomial Completeness)問題 . 21 ? 待解決的問題 連續(xù)性問題，以微積分為基礎(chǔ)， 規(guī)模較小 ? 傳統(tǒng)的優(yōu)化方法 理論上的準(zhǔn)確與完美，主要方法：線性與非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、多目標(biāo)規(guī)劃、整數(shù)規(guī)劃等；排隊(duì)論、庫(kù)存論、對(duì)策論、決策論等。 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ì)解域無可微或連續(xù)的要求 。 38 ? 什么是退火： 退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。 Until 抽樣穩(wěn)定準(zhǔn)則滿足； 退溫 tk+1=update(tk)并令 k=k+1； Until 算法終止準(zhǔn)則滿足； 輸出算法搜索結(jié)果。71 44。82 7。 一種改進(jìn)的模擬退火算法 80 模擬退火算法的改進(jìn) 智能優(yōu)化計(jì)算 ? 改進(jìn)的退火過程 （ 1）給定初溫 t0，隨機(jī)產(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*作為最終解輸出，停止算法。 102 SGA實(shí)例 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)大 變異操作有 ” 擾動(dòng) ” 作用，同時(shí)具有增加種群多 樣性的效果。 ? 變異概率 Pm 一般介于 1/種群規(guī)模與 1/染色體長(zhǎng)度之間，平均約 12% 1 1 0 1 0 1 0 0 父代 0 1 0 1 0 1 0 1 子代 變異基因 變異基因 121 變異 (Mutation) ? 比起選擇和交叉操作， 變異操作 是 GA中的次要操作，但它在恢復(fù)群體中失去的 多樣性 方面具有潛在的作用。 127 流程圖 (Flow Chart) 128 SGA偽碼描述 Procedure Geic Algorithm begin t = 0 。 ? 關(guān)鍵是如何設(shè)計(jì)罰函數(shù)； ? 不同問題需要設(shè)計(jì)不同的罰函數(shù)； ? 對(duì)一般的約束處理，通常很困難。 1 2 3 4 5 5 4 3 2 1 1 2 3 2 1 5 4 3 4 5 一般的交叉操作會(huì)產(chǎn)生不合適的解，如 140 TSP交叉 1:部分匹配交叉 (PMX) ? 雙親 P1,P2隨機(jī)選取兩個(gè)交叉點(diǎn)，得到一個(gè)匹配段 ,根據(jù)交叉點(diǎn)中間段給出映射關(guān)系。如 [1e6 1 0] termFN終止函數(shù)的名稱 ,如 [39。DS) 包含工具 : 遺傳算法 /直接搜索 運(yùn)行方式 : mand line。] xOverOps傳遞給交叉函數(shù)的參數(shù)表，如 [2 0。 同理的 C2， 144 TSP交叉 3:循環(huán)交叉 (CX) ? CX操作中子個(gè)體中的城市碼順序根據(jù)任一父?jìng)€(gè)體產(chǎn)生 ? 確定循環(huán)編碼 ? 復(fù)制循環(huán)編碼到子個(gè)體 145 TSP變異 ? Insert Mutation 隨機(jī)選取個(gè)體中兩個(gè)編碼，然后把第二個(gè)編碼放在第一 個(gè)編碼之后，其他編碼順次調(diào)節(jié)位置。 ? 實(shí)際 :一位推銷員從自己所在城市出發(fā)，必須遍訪所有城市之后又回到原來的城市，求使其旅行費(fèi)用最少的路徑。 % crossover and mutation 計(jì)算 P(t) 的適應(yīng)值 。以染色體適應(yīng)值的大小來確定該染色體被遺傳到下一代群體中的概率 。 ? 模擬 “ 輪盤賭 ” 算法 ： (1)r=random(0, 1)， s=0， i=0； (2)如果 s≥r， 則轉(zhuǎn) (4)； (3)s=s+p(xi)， i=i+1, 轉(zhuǎn) (2) (4)xi即為被選中的染色體 ， 輸出 I (5)結(jié)束 116 選擇 (Selection) ? 其他選擇法 ： ? 隨機(jī)遍歷抽樣 (Stochastic universal sampling) ? 局部選擇 (Local selection) ? 截?cái)噙x擇 (Truncation selection) ? 競(jìng)標(biāo)賽選擇 (Tournament selection) ? 特點(diǎn) ： 選擇操作得到的新的群體稱為 交配池 ，交配池是當(dāng)前代和下一代之間的中間群體，其規(guī)模為初始群體規(guī)模。 85 遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生 的 繁殖、交叉和基因突變 現(xiàn)象，在每次迭代中 都保留一組候選解，并按某種指標(biāo)從解群中選 取較優(yōu)的個(gè)體，利用 遺傳算子 (選擇、交叉和變 異 )對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解 群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。4 50 66 67 智能優(yōu)化計(jì)算 ? 算法流程 給 給 給 給 給 給 給 給給 給 給 給 給 Si給 給 給 給 給 Sj給 給 給 給 給 給 給 s *給 給 給 給 給 給 給 給 給 給給 給m i n { 1 , e x p [ ( C ( sj) C ( si) ) / tk] } = r a n d o m [ 0 , 1 ]給 給 給 給 給 給 給 給 給 給 給 給 給 給 給 給 k = 0M e t r o p o l i s 給 給 給 給 給 給 給 給 給 給tk + 1= u p d a t e ( tk)給 k = k + 1給 S i 給 S j ， 給 給 給 給 給 給 給 給 s *給 給 給 給 給 給給 給YNYNYN68 模擬退火算法的實(shí)現(xiàn)與應(yīng)用 智能優(yōu)化計(jì)算 ? 初始溫度的計(jì)算 for i=1:100 route=randperm(CityNum)。83 46。 內(nèi)循環(huán)終止準(zhǔn)則 63 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì) 智能優(yōu)化計(jì)算 ? 常用方法 （ 1）設(shè)置終止溫度的閾值； （ 2）設(shè)置外循環(huán)迭代次數(shù)； （ 3）算法搜索到的最優(yōu)值連續(xù)若干步保持不變； （ 4）概率分析方法。 45 模擬退火算法及模型 智能優(yōu)化計(jì)算 否則，以概率 p=exp[(EjEi)/kBT] 接受 j 為當(dāng)前狀態(tài)。 A：好的，我給你一些提示，他們?nèi)齻€(gè)年齡之積是 36. B：很好，但我還需要更多提示?，F(xiàn)代優(yōu)化算法 潘克家 202288 2 目錄 ? 現(xiàn)在優(yōu)化算法概論 ? 模擬退火算法 (SA) ? 遺傳算法 (GA) 3 Part 1 概論 主要是說明現(xiàn)代優(yōu)化算法的重要性。 … A： 既然你是數(shù)學(xué)教授，那你幫我算這個(gè)題，今天是 個(gè)特殊日子：我三個(gè)兒子都在今天慶祝生日！那么你 能算出他們都有多大嗎？ B：好，但你得跟我講講他們的情況。 模擬退火算法 能量最低狀態(tài) 非能量最低狀態(tài) ???????? ???TkrETZrEEP B)(ex p)(1)}({? 數(shù)學(xué)表述 44 模擬退火算法及模型 智能優(yōu)化計(jì)算 ? Metropolis準(zhǔn)則（ 1953） —— 以概率接受新狀態(tài) 物理退火過程 固體在恒定溫度下達(dá)到熱平衡的過程可以用 Monte Carlo方法 （計(jì)算機(jī)隨機(jī)模擬方法）加以模擬，雖然該方法簡(jiǎn)單，但必須大量采樣才能得到比較精確的結(jié)果，計(jì)算量很大。 62 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì) 智能優(yōu)化計(jì)算 ? 非時(shí)齊模擬退火算法 每個(gè)溫度下只產(chǎn)生一個(gè)或少量候選解 ? 時(shí)齊算法 —— 常用的 Metropolis抽樣穩(wěn)定準(zhǔn)則 （ 1）檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定； （ 2）連續(xù)若干步的目標(biāo)值變化較小； （ 3）按一定的步數(shù)抽樣。22 60。44 35。 它摒棄了傳統(tǒng)的搜索方式，模擬自然界生物進(jìn)化過程，采用人工的方式對(duì)目標(biāo)空間進(jìn)行隨機(jī)化搜索。 109 如何設(shè)計(jì)遺傳算法 ? 如何進(jìn)行編碼？ ? 如何產(chǎn)生初始種群？ ? 如何定義適應(yīng)函數(shù)？ ? 如何進(jìn)行遺傳操作 (復(fù)制、交叉、變異 )？ ? 如何產(chǎn)生下一代種群？ ? 如何定義停止準(zhǔn)則 ？ 110 編碼 (Coding) 表現(xiàn)型空間 編碼 (Coding) 解碼 (Decoding) 基因型空間 = {0,1}L 011101001 010001001 10010010 10010001 111 選擇 (Selection) ? 選擇 (復(fù)制 )操作把當(dāng)前種群的染色體按與適應(yīng)值成正比例的概率復(fù)制到新的種群中 ? 主要思想 : 適應(yīng)值較高的染色體體有較大的選擇機(jī)會(huì) ? 實(shí)現(xiàn) 1： “ 輪盤賭 ” 選擇 (Roulette wheel selection) ? 將種群中所有染色體編號(hào)，并根據(jù)各自適應(yīng)值計(jì)算按比例分配的概率 ? 依次計(jì)算染色體累加概率 ? 產(chǎn)生 (0,1)之間隨機(jī)數(shù)，若其最多能大于序列中第 m個(gè)值，則第 m個(gè)染色體被隨機(jī)選擇 112 選擇 (Selection) 設(shè)種群的規(guī)模為 N xi是 i為種群中第 i個(gè)染色體 A C 1/6 = 17% 3/6 = 50% B 2/6 = 33% fitness(A) = 3 fitness(B) = 1 fitness(C) = 2 1()()()isi NjjFxpxFx???染色體 xi被選概率 113 選擇 (Selection) 染色體的適應(yīng)值和所占的比例 輪盤賭選擇 114 選擇 (Selection) 隨機(jī)數(shù) 23 49 13 38 6 27 所選號(hào)碼 2 6 2 5 1 4 所選染色體 11000 00011 11000 01100 01110 10010 染色體編號(hào) 1 2 3 4 5 6 染色體 01110 11