【正文】 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ù)的最大值 ： ( ) s i n ( 1 0 ) 2 . 0 [ 1 , 2 ]f x x x x?? ? ? ?153 GAOT:函數(shù)最值 (實例 2) function [sol,eval]=fitness(sol,options) x=sol(1)。boundaryMutation multiNonUnifMutation nonUnifMutation unifMutation39。arithXover heuristicXover simpleXover39。maxGenTerm39。 ? 交叉和變異 。 ? Scramble mutation 隨機(jī)選取個體上一段編碼 ,然后打亂這段編碼的順序。 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ù)制點也是從第二個交叉點開始，得到 C1。 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 ? 交換兩個交叉點之間的編碼 ,(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)碼。 此向量是 1到 n的一個排列，即從 1到 n的每個整數(shù)在這 個向量中正好出現(xiàn)一次 ,不能有重復(fù)。如此 龐大的搜索空間，常規(guī)解法和計算工具都遇到計算上 的困難。實際應(yīng)用中， C也可解釋為費用或旅行時間矩陣。 約束最優(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完全問題。這樣的處理實際不可 行，因為 找到一個可行解幾乎與找到最優(yōu)解一樣困難 。 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解碼 ： 解碼時仍按各個變量的編碼順序分別實現(xiàn)常規(guī)的二進(jìn)制編碼 解碼方法。 % selection 重組 P(t) 。 初始化 P(t) 。 (4) 按交叉概率 Pc進(jìn)行 交叉操作 ,生產(chǎn)新的個體 。 ? 群體中的每個染色體都需要計算適應(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) ?缺點 : (1)可能不滿足輪盤賭選擇中概率非負(fù)的要求 (2)某些代求解的函數(shù)值分布上相差很大，由此得到的評價適應(yīng)值可能不利于體現(xiàn)群體的評價性能，影響算法的性能。 122 適應(yīng)函數(shù) (Fitness Function) ? GA在搜索中不依靠外部信息，僅以 適應(yīng)函數(shù) 為依據(jù)，利用群體中每個染色體 (個體 )的適應(yīng)值來進(jìn)行搜索。 在 GA執(zhí)行的開始階段，染色體中一個特定位上的值 1可能與好的性 能緊密聯(lián)系，即搜索空間中某些初始染色體在那個位上的值 1可能一 致產(chǎn)生高的適應(yīng)值。但當(dāng)雙親染色體相同時，交叉操作是不起作用的。 117 交叉 (crossover, Rebination) ? 遺傳交叉 (雜交、交配、有性重組 )操作發(fā)生在兩個染色體之間，由兩個被稱之為雙親的父代染色體，經(jīng)雜交以后，產(chǎn)生兩個具有雙親的部分基因的新的染色體，從而檢測搜索空間中新的點。 109 如何設(shè)計遺傳算法 ? 如何進(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ī)會 ? 實現(xiàn) 1： “ 輪盤賭 ” 選擇 (Roulette wheel selection) ? 將種群中所有染色體編號，并根據(jù)各自適應(yīng)值計算按比例分配的概率 ? 依次計算染色體累加概率 ? 產(chǎn)生 (0,1)之間隨機(jī)數(shù)，若其最多能大于序列中第 m個值，則第 m個染色體被隨機(jī)選擇 112 選擇 (Selection) 設(shè)種群的規(guī)模為 N xi是 i為種群中第 i個染色體 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 所選號碼 2 6 2 5 1 4 所選染色體 11000 00011 11000 01100 01110 10010 染色體編號 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) ? 輪盤上的片分配給群體的染色體 ， 使得每一個片的大小與對于染色體的適應(yīng)值成比例 ? 從群體中選擇一個染色體可視為旋轉(zhuǎn)一個輪盤 ， 當(dāng)輪盤停止時 ，指針?biāo)傅钠瑢τ诘娜旧w就時要選的染色體 。 103 SGA實例 2 :模擬結(jié)果 遺傳算法的參數(shù) : 種群規(guī)模 : 50 染色體長度 : L=22 最大進(jìn)化代數(shù) : 150 交叉概率 : Pc= 變異概率 : Pm= 104 SGA實例 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)化計算 ? 遺傳算法的基本思路 遺傳算法的思路與特點 106 遺傳算法簡介 智能優(yōu)化計算 ? 自組織、自適應(yīng)和自學(xué)習(xí)性 在編碼方案、適應(yīng)度函數(shù)及遺傳算子確定后，算法將利用進(jìn)化過程中獲得的信息自行組織搜索。 212 1 0 2 1 002 ( 1 )( , . . . , ) 1 ( 2 ) [ 1 , 2 ]21iiLib b b???? ? ? ? ? ? ?? ?將一個二進(jìn)制串 (b21b20…b0) 轉(zhuǎn)化為 10進(jìn)制數(shù)： . 0000000000000000000000 ? 1。 01101 ? 13。 它摒棄了傳統(tǒng)的搜索方式，模擬自然界生物進(jìn)化過程，采用人工的方式對目標(biāo)空間進(jìn)行隨機(jī)化搜索。 一種改進(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。 30城市 TSP問題（ d*= by D B Fogel） 71 模擬退火算法的實現(xiàn)與應(yīng)用 智能優(yōu)化計算 ? 運行過程 30城市 TSP問題（ d*= by D B Fogel） 72 模擬退火算法的實現(xiàn)與應(yīng)用 智能優(yōu)化計算 ? 運行過程 30城市 TSP問題（ d*= by D B Fogel） 73 模擬退火算法的實現(xiàn)與應(yīng)用 智能優(yōu)化計算 ? 運行過程 30城市 TSP問題（ d*= by D B Fogel） 74 模擬退火算法的實現(xiàn)與應(yīng)用 智能優(yōu)化計算 ? 運行過程 30城市 TSP問題（ d*= by D B Fogel） 75 模擬退火算法的實現(xiàn)與應(yīng)用 智能優(yōu)化計算 ? 運行過程 30城市 TSP問題（ d*= by D B Fogel） 76 模擬退火算法的實現(xiàn)與應(yīng)用 智能優(yōu)化計算 ? 運行結(jié)果 30城市 TSP問題（ d*= by D B Fogel） 77 模擬退火算法的改進(jìn) 智能優(yōu)化計算 ? 改進(jìn)的可行方案 （ 1）設(shè)計合適的狀態(tài)產(chǎn)生函數(shù)； （ 2）設(shè)計高效的退火歷程； （ 3）避免狀態(tài)的迂回搜索； （ 4）采用并行搜索結(jié)構(gòu)； （ 5）避免陷入局部極小，改進(jìn)對溫度的控制方式； （ 6）選擇合適的初始狀態(tài)； （ 7）設(shè)計合適的算法終止準(zhǔn)則。 30城市 TSP問題（ d*= by D B Fogel） 69 模擬退火算法的實現(xiàn)與應(yīng)用 智能優(yōu)化計算 ? 狀態(tài)產(chǎn)