【正文】 gatool GA解決的問題類 : m a x ( )xim ize f x m i n ( )xim ize f x?? 最大化問題要轉化為最小化問題 m in ( )xim ize f x? 最小化問題 155 Geic Algorithm and Direct Search Toolbox (GAamp。4 0 0] 152 GAOT:函數最值 (實例 ) 求下列函數的最大值 ： ( ) s i n ( 1 0 ) 2 . 0 [ 1 , 2 ]f x x x x?? ? ? ?153 GAOT:函數最值 (實例 2) function [sol,eval]=fitness(sol,options) x=sol(1)。boundaryMutation multiNonUnifMutation nonUnifMutation unifMutation39。arithXover heuristicXover simpleXover39。maxGenTerm39。 ? 交叉和變異 。 ? Scramble mutation 隨機選取個體上一段編碼 ,然后打亂這段編碼的順序。 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，再將此順 序復制到 C1，復制點也是從第二個交叉點開始，得到 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 映射關系： 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 映射關系 ： 4 ? 5 ? 7 ?5 9 3 2 4 5 6 7 1 8 1 7 3 8 2 6 5 4 9 c1 c2 ? 再根據映射關系，對以上未定碼，使用最初雙親碼，得到子個體的對應碼。 此向量是 1到 n的一個排列，即從 1到 n的每個整數在這 個向量中正好出現(xiàn)一次 ,不能有重復。如此 龐大的搜索空間，常規(guī)解法和計算工具都遇到計算上 的困難。實際應用中， C也可解釋為費用或旅行時間矩陣。 約束最優(yōu)化問題 134 組合最優(yōu)化問題 典型問題： 旅行商問題 (Traveling Salesman Problem) 作業(yè)調度問題 (Job Shop Scheduling Problem) 背包問題 (Knapsack Problem) 圖著色問題 … … … 很多組合最優(yōu)化問題是 NP難問題 或 NP完全問題 135 旅行商問題 (TSP) TSP，也稱貨郎擔問題，是一個 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ī)的二進制編碼 解碼方法。 % selection 重組 P(t) 。 初始化 P(t) 。 (4) 按交叉概率 Pc進行 交叉操作 ,生產新的個體 。 ? 群體中的每個染色體都需要計算適應值 ? 適應函數一般由 目標函數 變換而成 123 適應函數 (Fitness Function) ? 適應函數常見形式： ? 直接將目標函數轉化為適應函數 ? 若目標函數為最大化問題： Fitness(f(x)) = f(x) ? 若目標函數為最小化問題： Fitness(f(x)) = f(x) ?缺點 : (1)可能不滿足輪盤賭選擇中概率非負的要求 (2)某些代求解的函數值分布上相差很大，由此得到的評價適應值可能不利于體現(xiàn)群體的評價性能，影響算法的性能。 122 適應函數 (Fitness Function) ? GA在搜索中不依靠外部信息，僅以 適應函數 為依據，利用群體中每個染色體 (個體 )的適應值來進行搜索。 在 GA執(zhí)行的開始階段，染色體中一個特定位上的值 1可能與好的性 能緊密聯(lián)系，即搜索空間中某些初始染色體在那個位上的值 1可能一 致產生高的適應值。但當雙親染色體相同時，交叉操作是不起作用的。 117 交叉 (crossover, Rebination) ? 遺傳交叉 (雜交、交配、有性重組 )操作發(fā)生在兩個染色體之間，由兩個被稱之為雙親的父代染色體，經雜交以后，產生兩個具有雙親的部分基因的新的染色體，從而檢測搜索空間中新的點。 109 如何設計遺傳算法 ? 如何進行編碼？ ? 如何產生初始種群？ ? 如何定義適應函數？ ? 如何進行遺傳操作 (復制、交叉、變異 )？ ? 如何產生下一代種群？ ? 如何定義停止準則 ？ 110 編碼 (Coding) 表現(xiàn)型空間 編碼 (Coding) 解碼 (Decoding) 基因型空間 = {0,1}L 011101001 010001001 10010010 10010001 111 選擇 (Selection) ? 選擇 (復制 )操作把當前種群的染色體按與適應值成正比例的概率復制到新的種群中 ? 主要思想 : 適應值較高的染色體體有較大的選擇機會 ? 實現(xiàn) 1： “ 輪盤賭 ” 選擇 (Roulette wheel selection) ? 將種群中所有染色體編號，并根據各自適應值計算按比例分配的概率 ? 依次計算染色體累加概率 ? 產生 (0,1)之間隨機數，若其最多能大于序列中第 m個值，則第 m個染色體被隨機選擇 112 選擇 (Selection) 設種群的規(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) 染色體的適應值和所占的比例 輪盤賭選擇 114 選擇 (Selection) 隨機數 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 適應度 8 15 2 5 12 8 被選概率 0. 24 累加概率 8 23 25 30 42 50 染色體被選的概率 被選的染色體 115 選擇 (Selection) ? 輪盤上的片分配給群體的染色體 ， 使得每一個片的大小與對于染色體的適應值成比例 ? 從群體中選擇一個染色體可視為旋轉一個輪盤 ， 當輪盤停止時 ，指針所指的片對于的染色體就時要選的染色體 。 103 SGA實例 2 :模擬結果 遺傳算法的參數 : 種群規(guī)模 : 50 染色體長度 : L=22 最大進化代數 : 150 交叉概率 : Pc= 變異概率 : Pm= 104 SGA實例 2 :模擬結果 (最佳個體進化情況 ) 世代數 染色體編碼 變量 x 適應值 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)化計算 ? 自組織、自適應和自學習性 在編碼方案、適應度函數及遺傳算子確定后，算法將利用進化過程中獲得的信息自行組織搜索。 212 1 0 2 1 002 ( 1 )( , . . . , ) 1 ( 2 ) [ 1 , 2 ]21iiLib b b???? ? ? ? ? ? ?? ?將一個二進制串 (b21b20…b0) 轉化為 10進制數： . 0000000000000000000000 ? 1。 01101 ? 13。 它摒棄了傳統(tǒng)的搜索方式，模擬自然界生物進化過程，采用人工的方式對目標空間進行隨機化搜索。 一種改進的模擬退火算法 81 模擬退火算法的改進 智能優(yōu)化計算 ? 改進的抽樣過程 （ 1）令 k=0時的初始當前狀態(tài)為 s’(0)=s(i)， q=0； （ 2）由狀態(tài) s通過狀態(tài)產生函數產生新狀態(tài) s’，計算增量 ?C’=C(s’)C(s)； （ 3）若 ?C’0，則接受 s’作為當前解，并判斷 C(s*’)C(s’)? 若是，則令 s*’=s’， q=0；否則，令 q=q+1。 30城市 TSP問題（ d*= by D B Fogel） 71 模擬退火算法的實現(xiàn)與應用 智能優(yōu)化計算 ? 運行過程 30城市 TSP問題（ d*= by D B Fogel） 72 模擬退火算法的實現(xiàn)與應用 智能優(yōu)化計算 ? 運行過程 30城市 TSP問題（ d*= by D B Fogel） 73 模擬退火算法的實現(xiàn)與應用 智能優(yōu)化計算 ? 運行過程 30城市 TSP問題（ d*= by D B Fogel） 74 模擬退火算法的實現(xiàn)與應用 智能優(yōu)化計算 ? 運行過程 30城市 TSP問題（ d*= by D B Fogel） 75 模擬退火算法的實現(xiàn)與應用 智能優(yōu)化計算 ? 運行過程 30城市 TSP問題（ d*= by D B Fogel） 76 模擬退火算法的實現(xiàn)與應用 智能優(yōu)化計算 ? 運行結果 30城市 TSP問題（ d*= by D B Fogel） 77 模擬退火算法的改進 智能優(yōu)化計算 ? 改進的可行方案 （ 1）設計合適的狀態(tài)產生函數； （ 2）設計高效的退火歷程； （ 3）避免狀態(tài)的迂回搜索； （ 4）采用并行搜索結構； （ 5）避免陷入局部極小，改進對溫度的控制方式； （ 6）選擇合適的初始狀態(tài)； （ 7）設計合適的算法終止準則。 30城市 TSP問題（ d*= by D B Fogel） 69 模擬退火算法的實現(xiàn)與應用 智能優(yōu)化計算 ? 狀態(tài)產