【文章內(nèi)容簡介】 局部極小，改進對溫度的控制方式； （ 6）選擇合適的初始狀態(tài)； （ 7）設(shè)計合適的算法終止準(zhǔn)則。 改進內(nèi)容 78 模擬退火算法的改進 智能優(yōu)化計算 ? 改進的方式 （ 1）增加升溫或重升溫過程，避免陷入局部極小； （ 2）增加記憶功能（記憶“ Best so far”狀態(tài)）； （ 3）增加補充搜索過程（以最優(yōu)結(jié)果為初始解）； （ 4）對每一當(dāng)前狀態(tài)，采用多次搜索策略，以概率接受區(qū)域內(nèi)的最優(yōu)狀態(tài)； （ 5）結(jié)合其它搜索機制的算法； （ 6）上述各方法的綜合。 改進內(nèi)容 79 模擬退火算法的改進 智能優(yōu)化計算 ? 改進的思路 （ 1）記錄“ Best so far”狀態(tài)，并即時更新； （ 2）設(shè)置雙閾值，使得在盡量保持最優(yōu)性的前提下減少計算量，即在各溫度下當(dāng)前狀態(tài)連續(xù) m1 步保持不變則認為 Metropolis抽樣穩(wěn)定，若連續(xù) m2 次退溫過程中所得最優(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*作為最終解輸出，停止算法。 一種改進的模擬退火算法 81 模擬退火算法的改進 智能優(yōu)化計算 ? 改進的抽樣過程 （ 1）令 k=0時的初始當(dāng)前狀態(tài)為 s’(0)=s(i)， q=0； （ 2）由狀態(tài) s通過狀態(tài)產(chǎn)生函數(shù)產(chǎn)生新狀態(tài) s’，計算增量 ?C’=C(s’)C(s)； （ 3）若 ?C’0，則接受 s’作為當(dāng)前解，并判斷 C(s*’)C(s’)? 若是，則令 s*’=s’， q=0；否則，令 q=q+1。若 ?C’0，則以概率 exp(?C’/t)接受 s’作為下一當(dāng)前狀態(tài)； （ 4）令 k=k+1，判斷 qm1? 若是，則轉(zhuǎn)第 (5)步；否則，返回第 (2)步； （ 5）將當(dāng)前最優(yōu)解 s*’和當(dāng)前狀態(tài) s’(k)返回改進退火過程。 一種改進的模擬退火算法 82 Part 3 遺傳算法 83 遺傳算法 (Geic Algorithm) ?進化算法 (Evolutionary Algorithm) 84 遺傳算法 (GA) ? Darwin(1859): “物竟天擇，適者生存 ” ? John Holland (university of Michigan, 1975) 《 Adaptation in Natural and Artificial System》 ? 遺傳算法作為一種有效的工具，已廣泛地應(yīng)用于最優(yōu)化問題求解之中 。 ? 遺傳算法是一種基于自然群體遺傳進化機制的自適應(yīng)全局優(yōu)化概率搜索算法。 它摒棄了傳統(tǒng)的搜索方式，模擬自然界生物進化過程，采用人工的方式對目標(biāo)空間進行隨機化搜索。 85 遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生 的 繁殖、交叉和基因突變 現(xiàn)象，在每次迭代中 都保留一組候選解，并按某種指標(biāo)從解群中選 取較優(yōu)的個體，利用 遺傳算子 (選擇、交叉和變 異 )對這些個體進行組合，產(chǎn)生新一代的候選解 群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。 遺傳算法的搜索機制 86 局部 全局 遺傳算法 (GA) 87 We have a dream!! I am at the top Height is ... I am not at the top. My high is better! I will continue 遺傳算法 (GA) GA第 0代 88 Dead one New one 遺傳算法 (GA) GA第 1代 89 Not at the top, Come Up!!! 遺傳算法 (GA) GA第 ?代 90 I am the BEST !!! 遺傳算法 (GA) GA第 N代 91 適者生存 (Survival of the Fittest) ? GA主要采用的進化規(guī)則是 “ 適者生存 ” ? 較好的解保留，較差的解淘汰 遺傳算法 (GA) 92 基本遺傳算法 基本遺傳算法 （ Simple Geic Algorithms, 簡稱 SGA）是一種統(tǒng)一的最基本的遺傳算法，它只 使用 選擇、交叉、變異 這三種基本遺傳算子，其遺傳 進化操作過程簡單，容易理解，是其他一些遺傳算法 的雛形和基礎(chǔ)，它不僅給各種遺傳算法提供了一個基 本框架，同時也具有一定的應(yīng)用價值。 93 SGA實例 1：函數(shù)最值 SGA參數(shù) : ? 編碼方式 : 二進制碼 . 00000?0。 01101 ? 13。 11111?31 ? 種群規(guī)模 : 4 ? 隨機初始群體 ? “ 轉(zhuǎn)盤賭 ” 選擇 ? 一點雜交 , 二進制變異 求函數(shù) f(x)=x2的最大值， x為自然數(shù)且 0≤x≤31. ? 手工方式完成演示 SGA過程 94 SGA實例 1 max x2 : 選擇操作 95 SGA實例 1 max x2 : 交叉操作 96 SGA實例 1 max x2 : 變異操作 97 SGA實例 2 : 連續(xù)函數(shù)最值 求下列函數(shù)的最大值 ： ( ) s i n ( 1 0 ) 2 . 0 [ 1 , 2 ]f x x x x?? ? ? ?98 SGA實例 2 : 編碼 ? 高精度 1100( , . . . , ) ( 2 ) [ , ]21LiLi Liyxb b x b x y????? ? ? ? ? ?? ??編碼 ? [x,y] ? {0,1}L 必須可逆 (一個表現(xiàn)型對應(yīng)一個基因型 ) ? 解碼算子 ： ?: {0,1}L ? [x,y] ? 染色體長度 L決定可行解的最大精度 長染色體 (慢進化 ) ? 實數(shù)問題 ： 變量 z為實數(shù)，如何把 {a1,…,a L} ? {0,1}L z∈ [x,y] 99 SGA實例 2 : 編碼 設(shè)定求解精確到 6位小數(shù)，因區(qū)間長度為 2(1)=3,則需將區(qū) 間分為 3X106等份。因 2097152＝ 221 3X106≤222＝ 4194304。故編碼的二進制串長 L=22。 212 1 0 2 1 002 ( 1 )( , . . . , ) 1 ( 2 ) [ 1 , 2 ]21iiLib b b???? ? ? ? ? ? ?? ?將一個二進制串 (b21b20…b0) 轉(zhuǎn)化為 10進制數(shù)： . 0000000000000000000000 ? 1。 1111111111111111111111 ? 2 1110000000111111000101 ? 888 = 1+3x(1110000000111111000101) 2 /(2221) = 1+3x3674053/(2221) 100 SGA實例 2 : 初始化種群、適應(yīng)函數(shù) ? 隨機初始化種群 ? 適應(yīng)函數(shù) 本實例目標(biāo)函數(shù)在定義域內(nèi)均大于 0， 且是求函數(shù)最大值，故直接引用目標(biāo)函數(shù)作為適應(yīng)函數(shù)： f(s) = f(x) 其中二進制串 s對于變量 x的值。 . s1 =0000001110000000010000 ? x1= 973 適應(yīng)值 : f(s1) = f(x1) = 878 s2=1110000000111111000101 ? x2= 888 適應(yīng)值 : f(s2) = f(x2) = 650 101 SGA實例 2 :遺傳操作 ? 選擇操作 (“輪盤賭 ” 選擇 ) ? 交叉操作 (單點交叉 ) 交叉前 (父 ): s1=00000 | 01110000000010000 s2=11100 | 00000111111000101 交叉后 (子 ): s’1=00000 | 00000111111000101 s’2=11100 | 01110000000010000 適應(yīng)值 : f(s’1) = f( 113) = 865 f(s’2) = f( 028) = 245 s’2的適應(yīng)值比其雙親個體的適應(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)大 變異操作有 ” 擾動 ” 作用，同時具有增加種群多 樣性的效果。 103 SGA實例 2 :模擬結(jié)果 遺傳算法的參數(shù) : 種群規(guī)模 : 50 染色體長度 : L=22 最大進化代數(shù) : 150 交叉概率 : Pc= 變異概率 : Pm= 104 SGA實例 2 :模擬結(jié)果 (最佳個體進化情況 ) 世代數(shù) 染色體編碼 變量 x 適應(yīng)值 1 4 11 17 34 40 54 71 89 150 1000111000010110001111 0000011011000101001111 0110101011100111001111 1110101011111101001111 1100001101111011001111 1101001000100011001111 1000110110100011001111 0100110110001011001111 1101001111110011001111 1101001111110011001111 624 416 860 536 290 443 699 897 549 549 806 362 286 004 402 232 155 162 274 274 105 遺傳算法簡介 智能優(yōu)化計算 ? 遺傳算法的基本思路 遺傳算法的思路與特點 106 遺傳算法簡介 智能優(yōu)化計算 ? 自組織、自適應(yīng)和自學(xué)習(xí)性 在編碼方案、適應(yīng)度函數(shù)及遺傳算子確定后，算法將利用進化過程中獲得的信息自行組織搜索。 遺傳算法的思路與特點 ? 概率轉(zhuǎn)換規(guī)則 強調(diào)概率轉(zhuǎn)換規(guī)則，而不是確定的轉(zhuǎn)換規(guī)則 ? 不需求導(dǎo) 只需目標(biāo)函數(shù)和適應(yīng)度函數(shù) ? 本質(zhì)并行性 內(nèi)在并行性與內(nèi)含并行性 107 生物進化與遺傳算法對應(yīng)關(guān)系 生物進化 遺傳算法 適者生存 適應(yīng)函數(shù)值最大的解被保留的概率最大 個體 問題的一個解 染色體 解的編碼 基因 編碼的元素 群體 被選定的一組解 種群 根據(jù)適應(yīng)函數(shù)選擇的一組解 交叉 以一定的方式由雙親產(chǎn)生后代的過程 變異 編碼的某些分量發(fā)生變化的過程 生存能力 適應(yīng)函數(shù) 108 遺傳算法的基本操作 ? 選擇 (selection):