【正文】 000 00100 10010 01100 00011 適應(yīng)度 8 15 2 5 12 8 被選概率 0. 24 累加概率 8 23 25 30 42 50 染色體被選的概率 被選的染色體 115 選擇 (Selection) ? 輪盤上的片分配給群體的染色體 ， 使得每一個片的大小與對于染色體的適應(yīng)值成比例 ? 從群體中選擇一個染色體可視為旋轉(zhuǎn)一個輪盤 ， 當(dāng)輪盤停止時 ，指針?biāo)傅钠瑢τ诘娜旧w就時要選的染色體 。 122 適應(yīng)函數(shù) (Fitness Function) ? GA在搜索中不依靠外部信息，僅以 適應(yīng)函數(shù) 為依據(jù)，利用群體中每個染色體 (個體 )的適應(yīng)值來進(jìn)行搜索。 % selection 重組 P(t) 。實(shí)際應(yīng)用中， C也可解釋為費(fèi)用或旅行時間矩陣。 9 3 7 8 2 6 5 1 4 P2 x x x 4 5 6 7 x x c1 3 8 2 4 5 6 7 1 9 c1 3 4 7 8 2 6 5 9 1 c2 ? 得到父個體 P2的排列順序 149378265,并將 C1已有 城市碼 4,5,6,7從中去掉，得到排列順序 19382，再將此順 序復(fù)制到 C1，復(fù)制點(diǎn)也是從第二個交叉點(diǎn)開始，得到 C1。arithXover heuristicXover simpleXover39。 gatool GA解決的問題類 : m a x ( )xim ize f x m i n ( )xim ize f x?? 最大化問題要轉(zhuǎn)化為最小化問題 m in ( )xim ize f x? 最小化問題 155 Geic Algorithm and Direct Search Toolbox (GAamp。maxGenTerm39。 1 2 3 4 5 6 7 8 9 9 3 7 8 2 6 5 1 4 x x x 4 5 6 7 x x x x x 8 2 6 5 x x P1 P2 映射關(guān)系： 4 ? 5 ? 7 ?5 c1 c2 ? 交換兩個交叉點(diǎn)之間的編碼 ,(X表示未定碼 ) 141 TSP交叉 1:部分匹配交叉 (PMX) ? 子個體 C1， C2分別從其父個體中繼承未映射城市碼 1 2 3 4 5 6 7 8 9 9 3 7 8 2 6 5 1 4 9 3 x 4 5 6 7 1 x 1 x 3 8 2 6 5 x 9 P1 P2 c1 c2 映射關(guān)系 ： 4 ? 5 ? 7 ?5 9 3 2 4 5 6 7 1 8 1 7 3 8 2 6 5 4 9 c1 c2 ? 再根據(jù)映射關(guān)系，對以上未定碼，使用最初雙親碼，得到子個體的對應(yīng)碼。 約束最優(yōu)化問題 134 組合最優(yōu)化問題 典型問題： 旅行商問題 (Traveling Salesman Problem) 作業(yè)調(diào)度問題 (Job Shop Scheduling Problem) 背包問題 (Knapsack Problem) 圖著色問題 … … … 很多組合最優(yōu)化問題是 NP難問題 或 NP完全問題 135 旅行商問題 (TSP) TSP，也稱貨郎擔(dān)問題，是一個 NP完全問題。 初始化 P(t) 。 在 GA執(zhí)行的開始階段，染色體中一個特定位上的值 1可能與好的性 能緊密聯(lián)系，即搜索空間中某些初始染色體在那個位上的值 1可能一 致產(chǎn)生高的適應(yīng)值。 103 SGA實(shí)例 2 :模擬結(jié)果 遺傳算法的參數(shù) : 種群規(guī)模 : 50 染色體長度 : L=22 最大進(jìn)化代數(shù) : 150 交叉概率 : Pc= 變異概率 : Pm= 104 SGA實(shí)例 2 :模擬結(jié)果 (最佳個體進(jìn)化情況 ) 世代數(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)化計算 ? 遺傳算法的基本思路 遺傳算法的思路與特點(diǎn) 106 遺傳算法簡介 智能優(yōu)化計算 ? 自組織、自適應(yīng)和自學(xué)習(xí)性 在編碼方案、適應(yīng)度函數(shù)及遺傳算子確定后，算法將利用進(jìn)化過程中獲得的信息自行組織搜索。 一種改進(jìn)的模擬退火算法 81 模擬退火算法的改進(jìn) 智能優(yōu)化計算 ? 改進(jìn)的抽樣過程 （ 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。62 32。54 62。 模擬退火算法的基本思想和步驟 三函數(shù)兩準(zhǔn)則 初始溫度 57 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 ? 原則 產(chǎn)生的候選解應(yīng)遍布全部解空間 (保證全局最優(yōu)解 ) ? 方法 在當(dāng)前狀態(tài)的鄰域結(jié)構(gòu)內(nèi)以一定概率方式（均勻分布、正態(tài)分布、指數(shù)分布等）產(chǎn)生 狀態(tài)產(chǎn)生函數(shù) 58 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計 智能優(yōu)化計算 ? 原則 (1)在固定溫度下，接受使目標(biāo)函數(shù)下降的候選解的概率要大于使目標(biāo)函數(shù)上升的候選解概率； (2)隨溫度的下降，接受使目標(biāo)函數(shù)上升的解的概率要逐漸減??； (3)當(dāng)溫度趨于零時，只能接受目標(biāo)函數(shù)下降的解。 物理退火過程 39 模擬退火算法及模型 等溫過程 —— 對于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時，系統(tǒng)達(dá)到平衡態(tài)； ? 物理退火過程 加溫過程 —— 增強(qiáng)粒子的熱運(yùn)動，消除系統(tǒng)原先可能存在的非均勻態(tài)； 冷卻過程 —— 使粒子熱運(yùn)動減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。容易實(shí)現(xiàn)，求解穩(wěn)健。 19 優(yōu)化模型 實(shí)際問題中 的優(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)化問題 (Optimization Problem) 最優(yōu)化問題 : 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)化問題 (Combinatorial Optimization Problem ) : 最優(yōu)化問題中的解空間 X或 S由離散集合構(gòu)成。 A：他們?nèi)齻€年齡之和等于那幢房子的窗戶個數(shù)。假設(shè)我方飛機(jī)的速度為 1000公里 /小時。37 84。58 69。 30城市 TSP問題（ d*= by D B Fogel） 2 8 3 5 9 1 4 6 7 2 8 3 5 9 1 4 6 7 2 8 3 5 9 1 4 6 7 2 8 1 5 9 3 4 6 7 2 8 3 4 1 9 5 6 7 2 3 5 9 8 1 4 6 7 70 模擬退火算法的實(shí)現(xiàn)與應(yīng)用 智能優(yōu)化計算 ? 參數(shù)設(shè)定 截止溫度 tf=。 11111?31 ? 種群規(guī)模 : 4 ? 隨機(jī)初始群體 ? “ 轉(zhuǎn)盤賭 ” 選擇 ? 一點(diǎn)雜交 , 二進(jìn)制變異 求函數(shù) f(x)=x2的最大值， x為自然數(shù)且 0≤x≤31. ? 手工方式完成演示 SGA過程 94 SGA實(shí)例 1 max x2 : 選擇操作 95 SGA實(shí)例 1 max x2 : 交叉操作 96 SGA實(shí)例 1 max x2 : 變異操作 97 SGA實(shí)例 2 : 連續(xù)函數(shù)最值 求下列函數(shù)的最大值 ： ( ) s i n ( 1 0 ) 2 . 0 [ 1 , 2 ]f x x x x?? ? ? ?98 SGA實(shí)例 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決定可行解的最大精度 長染色體 (慢進(jìn)化 ) ? 實(shí)數(shù)問題 ： 變量 z為實(shí)數(shù)，如何把 {a1,…,a L} ? {0,1}L z∈ [x,y] 99 SGA實(shí)例 2 : 編碼 設(shè)定求解精確到 6位小數(shù)，因區(qū)間長度為 2(1)=3,則需將區(qū) 間分為 3X106等份。 ? 選擇 (復(fù)制 )操作每次作用在一個染色體上，而交叉操作每次作用在從交配池中隨機(jī)選取的兩個個體上 (交叉概率 Pc)。 124 適應(yīng)函數(shù) (Fitness Function) ? 界限構(gòu)造法 m in m in( ) , ( )F it ne ss ( ( ) )0f x C f x Cfxothe rs????? ??? ， ? 目標(biāo)函數(shù)為最大化問題 其中 Cmin為 f(x)的最小估計值 m a x m a x( ) , ( )F i t ne ss ( ( ) )0C f x f x Cfxot he rs???????? ， ? 目標(biāo)函數(shù)為最小化問題 其中 Cmaxn為 f(x)的最大估計值 125 停止準(zhǔn)則 (Termination Criteria) ? 種群中個體的 最大適應(yīng)值 超過預(yù)設(shè)定值 ? 種群中個體的 平均適應(yīng)值 超過預(yù)設(shè)定值 ? 種群中個體的 進(jìn)化代數(shù) 超過預(yù)設(shè)定值 126 基本步驟 (Step by Step) (1) 隨機(jī)產(chǎn)生 初始種群 。 二進(jìn)制遺傳編碼示意圖如下： 131 約束最優(yōu)化問題 常規(guī)解法 ： (1)把約束問題轉(zhuǎn)化為無約束問題，在用無約束問題方法求解，如 罰函數(shù)法 (2)改進(jìn)無約束問題的方法，再用于約束問題，如梯度投影法、廣義簡約梯度法 12( , , )( ) 0 , 1 , 2 , ,( ) 0 , 1 , 2 , , 1 , 2 , ,niiiiiM ini m iz e f x x xg x i mh x i ll x u i n????? ? ?約束最優(yōu)化問題 : 132 約束最優(yōu)化問題 ? 遺傳算法求解關(guān)鍵 : 約束條件的處理 等式約束可以包含到適應(yīng)函數(shù)，僅考慮不等式約束。只能尋找近似解法，如神經(jīng)網(wǎng)絡(luò)方法、模擬 退火法、遺傳算法等。 選取的編碼不一定是鄰接編碼 147 TSP的 GA過程 ? 從 N個隨機(jī)起點(diǎn)開始產(chǎn)生 N條路徑， N為種群的規(guī)模 。] mutOps傳遞給交叉函數(shù)的參數(shù)表 ,如 [4 0 0。4 100 3。 ? 選擇交叉對使在平均性能之上的個體