【正文】 ? 相似性比較 組合優(yōu)化問題 金屬物體 解 粒子狀態(tài) 最優(yōu)解 能量最低的狀態(tài) 設(shè)定初溫 熔解過程 Metropolis抽樣過程 等溫過程 控制參數(shù)的下降 冷卻 目標(biāo)函數(shù) 能量 48 SA算法描述 49 案例講解 ? 已知敵方 100個(gè)目標(biāo)的經(jīng)度、緯度 我方有一個(gè)基地，經(jīng)度和緯度為（ 70,40）。 模擬退火算法的基本思想和步驟 三函數(shù)兩準(zhǔn)則 初始溫度 57 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì) 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 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è)計(jì) 智能優(yōu)化計(jì)算 ? 原則 (1)在固定溫度下，接受使目標(biāo)函數(shù)下降的候選解的概率要大于使目標(biāo)函數(shù)上升的候選解概率； (2)隨溫度的下降，接受使目標(biāo)函數(shù)上升的解的概率要逐漸減小； (3)當(dāng)溫度趨于零時(shí)，只能接受目標(biāo)函數(shù)下降的解。 模擬退火算法的優(yōu)缺點(diǎn) 65 模擬退火算法的實(shí)現(xiàn)與應(yīng)用 智能優(yōu)化計(jì)算 30城市 TSP問題（ d*= by D B Fogel） ? TSP Benchmark 問題 41 94。54 62。24 42。62 32。 30城市 TSP問題（ d*= by D B Fogel） 69 模擬退火算法的實(shí)現(xiàn)與應(yīng)用 智能優(yōu)化計(jì)算 ? 狀態(tài)產(chǎn)生函數(shù)的設(shè)計(jì) （ 1）互換操作，隨機(jī)交換兩個(gè)城市的順序； （ 2）逆序操作，兩個(gè)隨機(jī)位置間的城市逆序； （ 3）插入操作，隨機(jī)選擇某點(diǎn)插入某隨機(jī)位置。 一種改進(jìn)的模擬退火算法 81 模擬退火算法的改進(jìn) 智能優(yōu)化計(jì)算 ? 改進(jìn)的抽樣過程 （ 1）令 k=0時(shí)的初始當(dāng)前狀態(tài)為 s’(0)=s(i)， q=0； （ 2）由狀態(tài) s通過狀態(tài)產(chǎn)生函數(shù)產(chǎn)生新狀態(tài) s’，計(jì)算增量 ?C’=C(s’)C(s)； （ 3）若 ?C’0，則接受 s’作為當(dāng)前解，并判斷 C(s*’)C(s’)? 若是，則令 s*’=s’， q=0；否則，令 q=q+1。 01101 ? 13。 103 SGA實(shí)例 2 :模擬結(jié)果 遺傳算法的參數(shù) : 種群規(guī)模 : 50 染色體長度 : L=22 最大進(jìn)化代數(shù) : 150 交叉概率 : Pc= 變異概率 : Pm= 104 SGA實(shí)例 2 :模擬結(jié)果 (最佳個(gè)體進(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)化計(jì)算 ? 遺傳算法的基本思路 遺傳算法的思路與特點(diǎn) 106 遺傳算法簡介 智能優(yōu)化計(jì)算 ? 自組織、自適應(yīng)和自學(xué)習(xí)性 在編碼方案、適應(yīng)度函數(shù)及遺傳算子確定后，算法將利用進(jìn)化過程中獲得的信息自行組織搜索。 117 交叉 (crossover, Rebination) ? 遺傳交叉 (雜交、交配、有性重組 )操作發(fā)生在兩個(gè)染色體之間，由兩個(gè)被稱之為雙親的父代染色體，經(jīng)雜交以后，產(chǎn)生兩個(gè)具有雙親的部分基因的新的染色體，從而檢測搜索空間中新的點(diǎn)。 在 GA執(zhí)行的開始階段，染色體中一個(gè)特定位上的值 1可能與好的性 能緊密聯(lián)系，即搜索空間中某些初始染色體在那個(gè)位上的值 1可能一 致產(chǎn)生高的適應(yīng)值。 ? 群體中的每個(gè)染色體都需要計(jì)算適應(yīng)值 ? 適應(yīng)函數(shù)一般由 目標(biāo)函數(shù) 變換而成 123 適應(yīng)函數(shù) (Fitness Function) ? 適應(yīng)函數(shù)常見形式： ? 直接將目標(biāo)函數(shù)轉(zhuǎn)化為適應(yīng)函數(shù) ? 若目標(biāo)函數(shù)為最大化問題： Fitness(f(x)) = f(x) ? 若目標(biāo)函數(shù)為最小化問題： Fitness(f(x)) = f(x) ?缺點(diǎn) : (1)可能不滿足輪盤賭選擇中概率非負(fù)的要求 (2)某些代求解的函數(shù)值分布上相差很大，由此得到的評(píng)價(jià)適應(yīng)值可能不利于體現(xiàn)群體的評(píng)價(jià)性能，影響算法的性能。 初始化 P(t) 。 12( , , )1 , 2 , ,niiiM inim ize f x x xsu b je c t to l x u i n? ? ?無約束最優(yōu)化問題 : 130 無約束最優(yōu)化問題 GA解碼 ： 解碼時(shí)仍按各個(gè)變量的編碼順序分別實(shí)現(xiàn)常規(guī)的二進(jìn)制編碼 解碼方法。 約束最優(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)問題，是一個(gè) NP完全問題。如此 龐大的搜索空間，常規(guī)解法和計(jì)算工具都遇到計(jì)算上 的困難。 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 ? 交換兩個(gè)交叉點(diǎn)之間的編碼 ,(X表示未定碼 ) 141 TSP交叉 1:部分匹配交叉 (PMX) ? 子個(gè)體 C1， C2分別從其父個(gè)體中繼承未映射城市碼 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)系，對(duì)以上未定碼，使用最初雙親碼，得到子個(gè)體的對(duì)應(yīng)碼。 ? Scramble mutation 隨機(jī)選取個(gè)體上一段編碼 ,然后打亂這段編碼的順序。maxGenTerm39。boundaryMutation multiNonUnifMutation nonUnifMutation unifMutation39。 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。4 0 0] 152 GAOT:函數(shù)最值 (實(shí)例 ) 求下列函數(shù)的最大值 ： ( ) s i n ( 1 0 ) 2 . 0 [ 1 , 2 ]f x x x x?? ? ? ?153 GAOT:函數(shù)最值 (實(shí)例 2) function [sol,eval]=fitness(sol,options) x=sol(1)。arithXover heuristicXover simpleXover39。 ? 交叉和變異 。 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 ? 得到父個(gè)體 P2的排列順序 149378265,并將 C1已有 城市碼 4,5,6,7從中去掉，得到排列順序 19382，再將此順 序復(fù)制到 C1，復(fù)制點(diǎn)也是從第二個(gè)交叉點(diǎn)開始，得到 C1。 此向量是 1到 n的一個(gè)排列，即從 1到 n的每個(gè)整數(shù)在這 個(gè)向量中正好出現(xiàn)一次 ,不能有重復(fù)。實(shí)際應(yīng)用中， C也可解釋為費(fèi)用或旅行時(shí)間矩陣。這樣的處理實(shí)際不可 行，因?yàn)?找到一個(gè)可行解幾乎與找到最優(yōu)解一樣困難 。 % selection 重組 P(t) 。 (4) 按交叉概率 Pc進(jìn)行 交叉操作 ,生產(chǎn)新的個(gè)體 。 122 適應(yīng)函數(shù) (Fitness Function) ? GA在搜索中不依靠外部信息，僅以 適應(yīng)函數(shù) 為依據(jù)，利用群體中每個(gè)染色體 (個(gè)體 )的適應(yīng)值來進(jìn)行搜索。但當(dāng)雙親染色體相同時(shí)，交叉操作是不起作用的。 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 11000 00100 10010 01100 00011 適應(yīng)度 8 15 2 5 12 8 被選概率 0. 24 累加概率 8 23 25 30 42 50 染色體被選的概率 被選的染色體 115 選擇 (Selection) ? 輪盤上的片分配給群體的染色體 ， 使得每一個(gè)片的大小與對(duì)于染色體的適應(yīng)值成比例 ? 從群體中選擇一個(gè)染色體可視為旋轉(zhuǎn)一個(gè)輪盤 ， 當(dāng)輪盤停止時(shí) ，指針?biāo)傅钠瑢?duì)于的染色體就時(shí)要選的染色體 。 212 1 0 2 1 002 ( 1 )( , . . . , ) 1 ( 2 ) [ 1 , 2 ]21iiLib b b???? ? ? ? ? ? ?? ?將一個(gè)二進(jìn)制串 (b21b20…b0) 轉(zhuǎn)化為 10進(jìn)制數(shù)： . 0000000000000000000000 ? 1。 它摒棄了傳統(tǒng)的搜索方式，模擬自然界生物