【正文】 g Salesman Problem) 作業(yè)調(diào)度問(wèn)題 (Job Shop Scheduling Problem) 背包問(wèn)題 (Knapsack Problem) 圖著色問(wèn)題 … … … 很多組合最優(yōu)化問(wèn)題是 NP難問(wèn)題 或 NP完全問(wèn)題 135 旅行商問(wèn)題 (TSP) TSP，也稱(chēng)貨郎擔(dān)問(wèn)題，是一個(gè) NP完全問(wèn)題。 TSP描述： ? 圖論 :設(shè)圖 G=(V,E),其中 V是頂點(diǎn)集， E是邊集。設(shè)C=(cij)是與 E相聯(lián)系的距離矩陣。尋找一條通過(guò)所有頂點(diǎn)且每個(gè)頂點(diǎn)只通過(guò)一次的最短距離回路(Hamilton回路 )。實(shí)際應(yīng)用中， C也可解釋為費(fèi)用或旅行時(shí)間矩陣。 ? 實(shí)際 :一位推銷(xiāo)員從自己所在城市出發(fā)，必須遍訪(fǎng)所有城市之后又回到原來(lái)的城市，求使其旅行費(fèi)用最少的路徑。 136 巡回旅行商問(wèn)題 (TSP) 中國(guó)貨郎擔(dān)問(wèn)題 : ? 城市數(shù) : 40 ? 城市編號(hào)1,2,… ,40 ? 尋找一條最短路徑 137 TSP復(fù)雜性 搜索空間龐大 TSP涉及求多個(gè)變量的函數(shù)的最小值，求解很困難。 其可能的路徑條數(shù)隨著城市數(shù)目 n成指數(shù)增長(zhǎng)，如， 5個(gè)城市對(duì)應(yīng) 12條路徑； 10個(gè)城市對(duì)應(yīng) 181440條 路徑； 100個(gè)城市對(duì)應(yīng) 。如此 龐大的搜索空間，常規(guī)解法和計(jì)算工具都遇到計(jì)算上 的困難。只能尋找近似解法，如神經(jīng)網(wǎng)絡(luò)方法、模擬 退火法、遺傳算法等。 138 TSP編碼 :路徑表示 染色體表示成所有城市的一個(gè)排列，若有 n個(gè)城市，一 條可能路徑編碼為長(zhǎng)度為 n的整數(shù)向量 (i1,i2,… ,in),其中 ik表示第 ik個(gè)城市。 例如 : 路徑編碼向量 (5 1 7 8 9 4 6 2 3)直接表示一條 旅行路程 (517894623)。 此向量是 1到 n的一個(gè)排列，即從 1到 n的每個(gè)整數(shù)在這 個(gè)向量中正好出現(xiàn)一次 ,不能有重復(fù)。這樣，基本遺傳 算法的基因操作生成的個(gè)體不能滿(mǎn)足這一約束條件，需 尋求其他遺傳操作。 139 TSP交叉 需其他方式的交叉 (重組 )操作 , 如部分匹配交叉 (Partially Matched Crossover,PMX)、 順序交叉 (Ordered Crossover,OX)、 循環(huán)交叉 (Cycle Crossover,CX)、 邊重組 (Edge Rebination)。 1 2 3 4 5 5 4 3 2 1 1 2 3 2 1 5 4 3 4 5 一般的交叉操作會(huì)產(chǎn)生不合適的解，如 140 TSP交叉 1:部分匹配交叉 (PMX) ? 雙親 P1,P2隨機(jī)選取兩個(gè)交叉點(diǎn)，得到一個(gè)匹配段 ,根據(jù)交叉點(diǎn)中間段給出映射關(guān)系。 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分別從其父?jìng)€(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)碼。映射關(guān)系存在傳遞關(guān)系，則選擇未定碼交換。 142 TSP交叉 2:順序交叉 (OX) ? 雙親 P1,P2隨機(jī)選取兩個(gè)交叉點(diǎn) 1 2 3 4 5 6 7 8 9 9 3 7 8 2 6 5 1 4 P1 P2 x x x 4 5 6 7 x x x x x 8 2 6 5 x x c1 c2 ? 兩個(gè)交叉點(diǎn)間的中間段保存不變 ? 子個(gè)體 C1的未定碼的確定需要父?jìng)€(gè)體 P2的未選定城市碼，子個(gè)體 C2的未定碼的確定需要父?jìng)€(gè)體 P1的未選定城市碼。 143 TSP交叉 2:順序交叉 (OX) ? 記取父?jìng)€(gè)體 P2從第二個(gè)交叉點(diǎn)開(kāi)始城市碼的排列順序，當(dāng)?shù)竭_(dá)表尾時(shí)，返回表頭繼續(xù)記錄，直到第二個(gè)交叉點(diǎn)。 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 ? 得到父?jìng)€(gè)體 P2的排列順序 149378265,并將 C1已有 城市碼 4,5,6,7從中去掉，得到排列順序 19382，再將此順 序復(fù)制到 C1，復(fù)制點(diǎn)也是從第二個(gè)交叉點(diǎn)開(kāi)始，得到 C1。 同理的 C2， 144 TSP交叉 3:循環(huán)交叉 (CX) ? CX操作中子個(gè)體中的城市碼順序根據(jù)任一父?jìng)€(gè)體產(chǎn)生 ? 確定循環(huán)編碼 ? 復(fù)制循環(huán)編碼到子個(gè)體 145 TSP變異 ? Insert Mutation 隨機(jī)選取個(gè)體中兩個(gè)編碼，然后把第二個(gè)編碼放在第一 個(gè)編碼之后，其他編碼順次調(diào)節(jié)位置。 ? Swap mutation 隨機(jī)選取個(gè)體中兩個(gè)編碼，然后交換它們的位置。 146 TSP變異 ? Inversion mutation 隨機(jī)選取個(gè)體中一段編碼，然后顛倒這段編碼的順序 。 ? Scramble mutation 隨機(jī)選取個(gè)體上一段編碼 ,然后打亂這段編碼的順序。 選取的編碼不一定是鄰接編碼 147 TSP的 GA過(guò)程 ? 從 N個(gè)隨機(jī)起點(diǎn)開(kāi)始產(chǎn)生 N條路徑， N為種群的規(guī)模 。 ? 利用最優(yōu)方法搜索每條路徑的局部最優(yōu)解 。 ? 選擇交叉對(duì)使在平均性能之上的個(gè)體得到更多的子代 。 ? 交叉和變異 。 ? 搜索每條路徑得到其極小解，如果不收斂，則回到第 3步；否則，停止。 148 GA的 MATLAB實(shí)現(xiàn) 軟件平臺(tái) (Software Platforms): ? MATLAB ? Geic Algorithm and Direct Search Toolbox ? MATLAB (or )+GAOT ? GAOT: Geic Algorithm Optimization Toolbox ? 美國(guó) North Carolina State University開(kāi)發(fā) ? MATLAB (or )+GEATbx ? GEATbx: Geic and Evolutionary Algorithm Toolbox ? 英國(guó) The University of Sheffield開(kāi)發(fā) ? 《 MATLAB遺傳算法工具箱及應(yīng)用 》 (雷英杰等 ,西安電子科技大學(xué)出版社 ,2022)基于此工具箱 149 GAOT工具箱 核心函數(shù) ： (1) [pop]=initializega(num,bounds,eevalFN,eevalOps,options) 初始種群的生成函數(shù) 【 輸出參數(shù) 】 pop生成的初始種群 【 輸入?yún)?shù) 】 num種群中的個(gè)體數(shù)目 bounds代表變量的上下界的矩陣 eevalFN適應(yīng)度函數(shù) eevalOps傳遞給適應(yīng)度函數(shù)的參數(shù) options選擇編碼形式 (浮點(diǎn)編碼或是二進(jìn)制編碼 )與精度，如 [type prec]， type為 1時(shí)選擇浮點(diǎn)編碼，否則為二進(jìn)制編碼 prec變量進(jìn)行二進(jìn)制編碼時(shí)指定的精度，默認(rèn) [1e6 1] 150 GAOT工具箱 (2) [x,endPop,bPop,traceInfo] = ga(bounds,evalFN,evalOps,startPop,opts,termFN,termOps,selectFN,… selectOps,xOverFNs,xOverOps,mutFNs,mutOps) 遺傳算法函數(shù) 【 輸出參數(shù) 】 x求得的最優(yōu)解 endPop最終得到的種群 bPop最優(yōu)種群的一個(gè)搜索軌跡 traceInfo每代種群中最優(yōu)及平均個(gè)體構(gòu)成的矩陣 【 輸入?yún)?shù) 】 bounds代表變量上下界的矩陣 evalFN適應(yīng)度函數(shù) evalOps傳遞給適應(yīng)度函數(shù)的參數(shù) startPop初始種群 151 GAOT工具箱 【 輸入?yún)?shù) 】 opts [epsilon prob_ops display]， opts(1:2)等同于 initializega的 options參數(shù)，第三個(gè)參數(shù)控制是否輸出，一般為 0。如 [1e6 1 0] termFN終止函數(shù)的名稱(chēng) ,如 [39。maxGenTerm39。] termOps傳遞個(gè)終止函數(shù)的參數(shù) ,如 [100] selectFN選擇函數(shù)的名稱(chēng) ,如 [39。normGeomSelect39。] selectOps傳遞個(gè)選擇函數(shù)的參數(shù) ,如 [] xOverFNs交叉函數(shù)名稱(chēng)表，以空格分開(kāi)，如[39。arithXover heuristicXover simpleXover39。] xOverOps傳遞給交叉函數(shù)的參數(shù)表，如 [2 0。2 3。2 0] mutFNs變異函數(shù)表，如 [39。boundaryMutation multiNonUnifMutation nonUnifMutation unifMutation39。] mutOps傳遞給交叉函數(shù)的參數(shù)表 ,如 [4 0 0。6 100 3。4 100 3。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)。 eval = x*sin(10*pi*x)+。 MATLAB 運(yùn)行結(jié)果 ： 154 Geic Algorithm and Direct Search Toolbox (GAamp。DS) 包含工具 : 遺傳算法 /直接搜索 運(yùn)行方式 : mand line。 gatool GA解決的問(wèn)題類(lèi) : m a x ( )xim ize f x m i n ( )xim ize f x?? 最大化問(wèn)題要轉(zhuǎn)化為最小化問(wèn)題 m in ( )xim ize f x? 最小化問(wèn)題 155 Geic Algorithm and Direct Search Toolbox (GAamp。DS) ? 最優(yōu)化問(wèn)題 ()( ) 0 , 1 , ... ,( ) 0 , 1 , ... ,xeqiiM i ni m i ze f xsuc h t hatAx bA x be qC x i mC x i m m tL b x U B????? ? ???156 案例講解 ? 同前一個(gè)案例講解問(wèn)題相同 157 算例 2:TSP 城市數(shù)： 40 158 算例 2:TSP 城市數(shù)： 100 159 ? 參考書(shū) [1] 邢文訓(xùn) , 謝金星 . 現(xiàn)代優(yōu)化計(jì)算方法 . 北京 : 清華大學(xué)出版社 , 2022. [2] 王凌 . 智能優(yōu)化算法及其應(yīng)用 . 北京 : 清華大學(xué)出版社 , 2022. [3] 閻平凡 , 張長(zhǎng)水 . 人工神經(jīng)網(wǎng)絡(luò)與模擬進(jìn)化計(jì)算 . 北京 : 清華大學(xué)出版社 , 2022. 160 ? 參考書(shū) [4]王小平 , 曹立明 . 遺傳算法 —— 理論、應(yīng)用與軟件實(shí)現(xiàn) . 西安 : 西安交通大學(xué)出版社 , 2022. [5]黃席樾等 . 現(xiàn)代智能算法理論及應(yīng)用 . 北京：科學(xué)出版社 , 2022. [6]高尚 , 楊靜宇 . 群智能算法及其應(yīng)用 . 北京 : 中國(guó)水利水電出版社 , 2022. 161 思考 智能優(yōu)化計(jì)算 用遺傳算法解決下面函數(shù)的極小值問(wèn)題： 32|| ,20)/)2c o s(e x p ()/ x p (20)(5015012??????? ????iiiiixenxnxXf ?162 Thank you! Any question?