數(shù)學建模中的常用算法課件

1、數(shù)學建模中的常用算法成都信息工程學院計算科學系 胡建成 2009-5-20 9/19/2022數(shù)學建模競賽網(wǎng)上資源CUMCM網(wǎng)站: MCM和ICM網(wǎng)站: http:/中國數(shù)學建模: 中科大建模網(wǎng)站: http:/MATLAB網(wǎng)站: GOOGLE大學9/19/2022數(shù)學建模競賽中的算法(1)93A 非線性交調(diào)的頻率設計: 擬合、規(guī)劃93B 足球隊排名次: 矩陣論、圖論、層次分析法、整數(shù)規(guī)劃94A 逢山開路: 圖論、插值、動態(tài)規(guī)劃94B 鎖具裝箱問題: 圖論、組合數(shù)學95A 飛行管理問題 : 非線性規(guī)劃、線性規(guī)劃95B 天車與冶煉爐的作業(yè)調(diào)度: 非線性規(guī)劃、動態(tài)規(guī)劃、層次分析法、PETRI方法、

2、圖論方法、排隊論方法96A 最優(yōu)捕魚策略：微分方程、積分、非線性規(guī)劃9/19/202296B 節(jié)水洗衣機：非線性規(guī)劃97A 零件參數(shù)設計：微積分、非線性規(guī)劃、隨機模擬97B 截斷切割：組合優(yōu)化、幾何變換、枚舉、蒙特卡羅、遞歸、最短路98A 投資收益與風險：線性規(guī)劃、非線性規(guī)劃98B 災情巡視：最小生成樹、Hamilton圈、旅行商問題99A 自動化車床：積分、概率分布、隨機模擬、分布擬合度檢驗數(shù)學建模競賽中的算法(2)9/19/202299B 鉆井布局：幾何變換、枚舉、最大完全子圖、混合整數(shù)規(guī)劃00A DNA分類：神經(jīng)網(wǎng)絡、最小二乘擬合、統(tǒng)計分類00B 管道訂購：最短路、二次規(guī)劃01A 血管的

3、三維重建：數(shù)據(jù)挖掘、曲面重建與擬合01B 公交車調(diào)度：非線性規(guī)劃02A 車燈光源優(yōu)化設計：最優(yōu)化02B 彩票中的數(shù)學：概率與優(yōu)化數(shù)學建模競賽中的算法(3)9/19/20221. 蒙特卡羅方法(Monte-Carlo方法, MC)數(shù)學建模競賽常用算法(1) 該算法又稱計算機隨機性模擬方法，也稱統(tǒng)計試驗方法。MC方法是一種基于“隨機數(shù)”的計算方法，能夠比較逼真地描述事物的特點及物理實驗過程，解決一些數(shù)值方法難以解決的問題。 MC方法的雛型可以追溯到十九世紀后期的蒲豐隨機投針試驗，即著名的蒲豐問題。 MC方法通過計算機仿真(模擬)解決問題，同時也可以通過模擬來檢驗自己模型的正確性，是比賽中經(jīng)常使用的

4、方法。9/19/202297年的A題 每個零件都有自己的標定值，也都有自己的容差等級，而求解最優(yōu)的組合方案將要面對著的是一個極其復雜的公式和108種容差選取方案，根本不可能去求解析解，那如何去找到最優(yōu)的方案呢？隨機性模擬搜索最優(yōu)方案就是其中的一種方法，在每個零件可行的區(qū)間中按照正態(tài)分布隨機的選取一個標定值和選取一個容差值作為一種方案，然后通過蒙特卡羅算法仿真出大量的方案，從中選取一個最佳的。02年的B題 關于彩票第二問，要求設計一種更好的方案，首先方案的優(yōu)劣取決于很多復雜的因素，同樣不可能刻畫出一個模型進行求解，只能靠隨機仿真模擬。數(shù)學建模競賽常用算法9/19/202298年B 題 用很多不等

5、式完全可以把問題刻畫清楚數(shù)學建模競賽常用算法(3)3. 規(guī)劃類問題算法 此類問題主要有線性規(guī)劃、整數(shù)規(guī)劃、多元規(guī)劃、二次規(guī)劃等。競賽中很多問題都和數(shù)學規(guī)劃有關，可以說不少的模型都可以歸結(jié)為一組不等式作為約束條件、幾個函數(shù)表達式作為目標函數(shù)的問題，遇到這類問題，求解就是關鍵了。 因此列舉出規(guī)劃后用Lindo、Lingo 等軟件來進行解決比較方便，所以還需要熟悉這兩個軟件。9/19/202298 年B 題、00年B 題、95 年鎖具裝箱等問題體現(xiàn)了圖論問題的重要性。數(shù)學建模競賽常用算法(4)4. 圖論問題 這類問題算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，

6、最大流，二分匹配等問題。9/19/202292 年B 題用分枝定界法97 年B 題是典型的動態(tài)規(guī)劃問題98 年B 題體現(xiàn)了分治算法數(shù)學建模競賽常用算法(5)5. 計算機算法設計中的問題 計算機算法設計包括很多內(nèi)容：動態(tài)規(guī)劃、回溯搜索、分治算法、分枝定界等計算機算法. 這方面問題和ACM 程序設計競賽中的問題類似，可看一下與計算機算法有關的書。9/19/202297 年A 題、99 年B 題都可以用網(wǎng)格法搜索數(shù)學建模競賽常用算法(7) 網(wǎng)格算法和窮舉法一樣，只是網(wǎng)格法是連續(xù)問題的窮舉。此類算法運算量較大。7. 網(wǎng)格算法和窮舉算法 這種方法最好在運算速度較快的計算機中進行，還有要用高級語言來做，最

7、好不要用MATLAB 做網(wǎng)格，否則會算很久的。9/19/2022 很多問題都是實際來的，數(shù)據(jù)可以是連續(xù)的，而計算機只能處理離散的數(shù)據(jù)，因此需要將連續(xù)問題進行離散化處理后再用計算機求解。比如差分代替微分、求和代替積分等思想都是把連續(xù)問題離散化的常用方法。數(shù)學建模競賽常用算法(8)8. 連續(xù)問題離散化的方法9/19/202201年A 題中需要你會讀BMP 圖象98年美國A 題需要你知道三維插值計算03年B 題要求更高，不但需要編程計算還要進行處理數(shù)學建模競賽常用算法(10)10. 圖象處理算法 賽題中有一類問題與圖形有關，即使問題與圖形無關，論文中也會需要圖片來說明問題，這些圖形如何展示以及如何處

8、理就是需要解決的問題，通常使用MATLAB進行處理。 數(shù)模論文中也有很多圖片需要展示，解決這類問題要熟悉MATLAB圖形圖像工具箱。9/19/2022三個孩子的年齡(1)兩個多年未見的朋友相遇，聊了很多事情。A：既然你是數(shù)學教授，那你幫我算這個題，今天是個特殊日子：我三個兒子都在今天慶祝生日！那么你能算出他們都有多大嗎？B：好，但你得跟我講講他們的情況。A：好的，我給你一些提示，他們?nèi)齻€年齡之積是36.B：很好，但我還需要更多提示。9/19/2022三個孩子的年齡(2)A：我的大兒子的眼睛是藍色的。B考慮了一下說，但是，我還有一點信息來解決你的這個難題。B：哦，夠了，B給出了正確的答案，即三個

9、小孩的年齡。A：他們?nèi)齻€年齡之和等于那幢房子的窗戶個數(shù)。A指著對面的一幢房子說。9/19/2022三個孩子的年齡(3)根據(jù)對話信息，用搜索的方法來解此問題。信息1:三個小孩年齡之積為36只有以下8種可能，搜索范圍減少至8種情況:第一個小孩年齡36 18 12 9 9 6 6 4第二個小孩年齡 1 2 3 4 2 6 3 3第三個小孩年齡 1 1 1 1 2 1 2 39/19/2022三個孩子的年齡(4)信息2:三個小孩年齡之和等于窗戶數(shù)第一個小孩年齡36 18 12 9 9 6 6 4第二個小孩年齡 1 2 3 4 2 6 3 3第三個小孩年齡 1 1 1 1 2 1 2 3窗戶數(shù): 38

10、21 16 14 13 13 11 10如果窗戶數(shù)為38、21、16、14、11、10即可得出答案B還需信息，即窗戶數(shù)為13.則可能為(9、2、2)或(6、6、1)信息2:大兒子眼睛是藍色的得答案：(9、2、2)9/19/2022智能優(yōu)化算法 智能優(yōu)化算法又稱為現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強、且適合于并行處理的算法。這種算法一般具有嚴密的理論依據(jù),而不是單純憑借專家經(jīng)驗，理論上可以在一定的時間內(nèi)找到最優(yōu)解或近似最優(yōu)解。 9/19/2022智能優(yōu)化算法的特點 它們的共同特點：都是從任一解出發(fā)，按照某種機制，以一定的概率在整個求解空間中探索最優(yōu)解。由于它們可以把搜索空間擴展到整個

11、問題空間，因而具有全局優(yōu)化性能。9/19/2022遺傳算法(Genetic Algorithm)進化算法(Evolutionary Algorithm)9/19/2022 遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標從解群中選取較優(yōu)的個體，利用遺傳算子(選擇、交叉和變異)對這些個體進行組合，產(chǎn)生新一代的候選解群，重復此過程，直到滿足某種收斂指標為止。遺傳算法的搜索機制9/19/2022局部全局遺傳算法(GA)9/19/2022We have a dream!I am at the topHeight is .I am not a

12、t the top.My high is better!I will continue遺傳算法(GA)GA-第0代9/19/2022Dead oneNew one遺傳算法(GA)GA-第1代9/19/2022Not at the top, Come Up!遺傳算法(GA)GA-第?代9/19/2022I am the BEST !遺傳算法(GA)GA-第N代9/19/2022適者生存(Survival of the Fittest)GA主要采用的進化規(guī)則是“適者生存”較好的解保留，較差的解淘汰遺傳算法(GA)9/19/2022生物進化與遺傳算法對應關系生物進化遺傳算法適者生存適應函數(shù)值最大的解

13、被保留的概率最大個體問題的一個解染色體解的編碼基因編碼的元素群體被選定的一組解種群根據(jù)適應函數(shù)選擇的一組解交叉以一定的方式由雙親產(chǎn)生后代的過程變異編碼的某些分量發(fā)生變化的過程環(huán)境適應函數(shù)9/19/2022遺傳算法的基本操作選擇(selection): 根據(jù)各個個體的適應值，按照一定的規(guī)則或方法，從第t代群體P(t)中選擇出一些優(yōu)良的個體遺傳到下一代群體P(t+1)中。 交叉(crossover): 將群體P(t)內(nèi)的各個個體隨機搭配成對，對每一個個體，以某個概率Pc (稱為交叉概率，crossvoer rate)交換它們之間的部分染色體。變異(mutation): 對群體P(t)中的每一個個體

14、，以某一概率Pm(稱為變異概率，mutation rate)改變某一個或一些基因座上基因值為其它的等位基因。9/19/2022如何設計遺傳算法如何進行編碼？如何產(chǎn)生初始種群？如何定義適應函數(shù)？如何進行遺傳操作(復制、交叉、變異)？如何產(chǎn)生下一代種群？如何定義停止準則？9/19/2022編碼(Coding)表現(xiàn)型空間編碼(Coding)解碼(Decoding)基因型空間 = 0,1L01110100101000100110010010100100019/19/2022選擇(Selection)選擇(復制)操作把當前種群的染色體按與適應值成正比例的概率復制到新的種群中 主要思想: 適應值較高的染色

15、體體有較大的選擇(復制)機會實現(xiàn)1：”輪盤賭”選擇(Roulette wheel selection)將種群中所有染色體的適應值相加求總和，染色體適應值按其比例轉(zhuǎn)化為選擇概率Ps產(chǎn)生一個在0與總和之間的的隨機數(shù)m從種群中編號為1的染色體開始，將其適應值與后續(xù)染色體的適應值相加，直到累加和等于或大于m9/19/2022選擇(Selection)設種群的規(guī)模為Nxi是i為種群中第i個染色體AC1/6 = 17%3/6 = 50%B2/6 = 33%fitness(A) = 3fitness(B) = 1fitness(C) = 2染色體xi被選概率9/19/2022選擇(Selection)染色體

16、的適應值和所占的比例輪盤賭選擇9/19/2022選擇(Selection)隨機數(shù)234913 386 27所選號碼 26 2 51 4所選染色體110000001111000011000111010010染色體編號 1 2 3 4 5 6染色體011101100000100100100110000011適應度 8 152 5 128被選概率40.10. 240.16適應度累計 8 23 25 30 42 50染色體被選的概率被選的染色體9/19/2022選擇(Selection)輪盤上的片分配給群體的染色體，使得每一個片的大小與對于染色體的適應值成比例從群體中選擇一個染色體

17、可視為旋轉(zhuǎn)一個輪盤，當輪盤停止時，指針所指的片對于的染色體就時要選的染色體。模擬“輪盤賭” 算法：r=random(0, 1)，s=0，i=0；如果sr，則轉(zhuǎn)(4)；s=s+p(xi)，i=i+1, 轉(zhuǎn)(2)xi即為被選中的染色體，輸出I結(jié)束9/19/2022選擇(Selection)其他選擇法：隨機遍歷抽樣(Stochastic universal sampling)局部選擇(Local selection)截斷選擇(Truncation selection)競標賽選擇(Tournament selection)特點：選擇操作得到的新的群體稱為交配池，交配池是當前代和下一代之間的中間群體，其

18、規(guī)模為初始群體規(guī)模。選擇操作的作用效果是提高了群體的平均適應值(低適應值個體趨于淘汰，高適應值個體趨于選擇)，但這也損失了群體的多樣性。選擇操作沒有產(chǎn)生新的個體，群體中最好個體的適應值不會改變。9/19/2022交叉(crossover, Recombination)遺傳交叉(雜交、交配、有性重組)操作發(fā)生在兩個染色體之間，由兩個被稱之為雙親的父代染色體，經(jīng)雜交以后，產(chǎn)生兩個具有雙親的部分基因的新的染色體，從而檢測搜索空間中新的點。選擇(復制)操作每次作用在一個染色體上，而交叉操作每次作用在從交配池中隨機選取的兩個個體上(交叉概率Pc)。交叉產(chǎn)生兩個子染色體，他們與其父代不同，且彼此不同, 每

19、個子染色體都帶有雙親染色體的遺傳基因。9/19/2022單點交叉(1-point crossover)在雙親的父代染色體中隨機產(chǎn)生一個交叉點位置在交叉點位置分離雙親染色體互換交叉點位置右邊的基因碼產(chǎn)生兩個子代染色體交叉概率Pc 一般范圍為(60%, 90%)，平均約80%11111111父代1111000000000000子代111100000000000011111111交叉點位置9/19/2022交叉(crossover, Recombination)單點交叉操作可以產(chǎn)生與父代染色體完全不同的子代染色體；它不會改變父代染色體中相同的基因。但當雙親染色體相同時，交叉操作是不起作用的。假如交叉

20、概率Pc 50%,則交配池中50%的染色體(一半染色體)將進行交叉操作，余下的50%的染色體進行選擇(復制)操作。GA利用選擇和交叉操作可以產(chǎn)生具有更高平均適應值和更好染色體的群體9/19/2022變異(Mutation)以變異概率Pm改變?nèi)旧w的某一個基因,當以二進制編碼時，變異的基因由0變成1，或者由1變成0。變異概率Pm 一般介于1/種群規(guī)模與1/染色體長度之間，平均約1-2%11010100父代01010101子代變異基因變異基因9/19/2022變異(Mutation)比起選擇和交叉操作，變異操作是GA中的次要操作，但它在恢復群體中失去的多樣性方面具有潛在的作用。 在GA執(zhí)行的開始階

21、段，染色體中一個特定位上的值1可能與好的性能緊密聯(lián)系，即搜索空間中某些初始染色體在那個位上的值1可能一致產(chǎn)生高的適應值。因為越高的適應值與染色體中那個位上的值1相聯(lián)系，選擇操作就越會使群體的遺傳多樣性損失。 等到達一定程度時，值0會從整個群體中那個位上消失，然而全局最優(yōu)解可能在染色體中那個位上為0。如果搜索范圍縮小到實際包含全局最優(yōu)解的那部分搜索空間，在那個位上的值0就可能正好是到達全局最優(yōu)解所需要的。9/19/2022適應函數(shù)(Fitness Function)GA在搜索中不依靠外部信息，僅以適應函數(shù)為依據(jù)，利用群體中每個染色體(個體)的適應值來進行搜索。以染色體適應值的大小來確定該染色體被

22、遺傳到下一代群體中的概率。染色體適應值越大，該染色體被遺傳到下一代的概率也越大；反之，染色體的適應值越小，該染色體被遺傳到下一代的概率也越小。因此適應函數(shù)的選取至關重要，直接影響到GA的收斂速度以及能否找到最優(yōu)解。群體中的每個染色體都需要計算適應值適應函數(shù)一般由目標函數(shù)變換而成9/19/2022適應函數(shù)(Fitness Function)適應函數(shù)常見形式：直接將目標函數(shù)轉(zhuǎn)化為適應函數(shù)若目標函數(shù)為最大化問題： Fitness(f(x) = f(x)若目標函數(shù)為最小化問題： Fitness(f(x) = -f(x)缺點: (1)可能不滿足輪盤賭選擇中概率非負的要求 (2)某些代求解的函數(shù)值分布上相

23、差很大，由此得到的評價適應值可能不利于體現(xiàn)群體的評價性能，影響算法的性能。9/19/2022適應函數(shù)(Fitness Function)界限構(gòu)造法 目標函數(shù)為最大化問題其中Cmin為f(x)的最小估計值 目標函數(shù)為最小化問題其中Cmaxn為f(x)的最大估計值9/19/2022停止準則(Termination Criteria)種群中個體的最大適應值超過預設定值種群中個體的平均適應值超過預設定值種群中個體的進化代數(shù)超過預設定值9/19/2022基本步驟(Step by Step)(1) 隨機產(chǎn)生初始種群;(2) 計算種群體中每個個體的適應度值,判斷是否滿足停止條件，若不滿足，則轉(zhuǎn)第(3)步,否

24、則轉(zhuǎn)第(6)步;(3) 按由個體適應值所決定的某個規(guī)則選擇將進入下一代的個體;(4) 按交叉概率Pc進行交叉操作,生產(chǎn)新的個體;(5) 按變異概率Pm進行變異操作,生產(chǎn)新的個體;(6) 輸出種群中適應度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。9/19/2022流程圖(Flow Chart)9/19/2022基本遺傳算法基本遺傳算法（Simple Genetic Algorithms,簡稱SGA）是一種統(tǒng)一的最基本的遺傳算法，它只使用選擇、交叉、變異這三種基本遺傳算子，其遺傳進化操作過程簡單，容易理解，是其他一些遺傳算法的雛形和基礎，它不僅給各種遺傳算法提供了一個基本框架，同時也具有一定的應用價

25、值。9/19/2022SGA偽碼描述Procedure Genetic Algorithm begint = 0 ;初始化 P(t) ;計算 P(t) 的適應值 ;while (不滿足停止準則) do begin t = t+1 ; 從P(t-1)中選擇 P(t) ; % selection 重組 P(t) ; % crossover and mutation 計算 P(t) 的適應值; end end9/19/2022遺傳算法的應用函數(shù)優(yōu)化 函數(shù)優(yōu)化是遺傳算法的經(jīng)典應用領域，也是對遺傳算法進行性能測試評價的常用算例。對于一些非線性、多模型、多目標的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，而遺傳

26、算法卻可以方便地得到較好的結(jié)果。遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用于很多學科。下面列舉一些遺傳算法的主要應用領域。9/19/2022遺傳算法的應用組合優(yōu)化 遺傳算法是尋求組合優(yōu)化問題滿意解的最佳工具之一，實踐證明，遺傳算法對于組合優(yōu)化問題中的NP完全問題非常有效。例如，遺傳算法已經(jīng)在求解旅行商問題(Traveling Salesman Problem , TSP)、背包問題(Knapsack Problem)、裝箱問題(Bin Packing Problem) 等方面得到成功的應用。生產(chǎn)調(diào)度問題 生產(chǎn)調(diào)度問題在很

27、多情況下所建立起來的數(shù)學模型難以精確求解，即使經(jīng)過一些簡化之后可以進行求解也會因簡化得太多而使求解結(jié)果與實際相差太遠?，F(xiàn)在遺傳算法已經(jīng)成為解決復雜調(diào)度問題的有效工具。9/19/2022遺傳算法的應用自動控制 遺傳算法已經(jīng)在自動控制領域中得到了很好的應用，例如基于遺傳算法的模糊控制器的優(yōu)化設計、基于遺傳算法的參數(shù)辨識、基于遺傳算法的模糊控制規(guī)則的學習、利用遺傳算法進行人工神經(jīng)網(wǎng)絡的結(jié)構(gòu)優(yōu)化設計和權(quán)值學習等。機器人智能控制 機器人是一類復雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于對人工自適應系統(tǒng)的研究，所以機器人智能控制自然成為遺傳算法的一個重要應用領域。 9/19/2022遺傳算法的應

28、用圖象處理和模式識別 圖像處理和模式識別是計算機視覺中的一個重要研究領域。在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地存在一些誤差，這些誤差會影響圖像處理的效果。如何使這些誤差最小是使計算機視覺達到實用化的重要要求，遺傳算法在這些圖像處理中的優(yōu)化計算方面得到了很好的應用。人工生命 人工生命是用計算機、機械等人工媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。自組織能力和自學習能力是人工生命的兩大重要特征。人工生命與遺傳算法有著密切的關系，基于遺傳算法的進化模型是研究人工生命現(xiàn)象的重要理論基礎。9/19/2022遺傳算法的應用遺傳程序設計 Koza發(fā)展了遺傳程序設計的概念，他使

29、用了以LISP語言所表示的編碼方法，基于對一種樹形結(jié)構(gòu)所進行的遺傳操作來自動生成計算機程序。 機器學習 基于遺傳算法的機器學習，在很多領域中都得到了應用。例如基于遺傳算法的機器學習可用來調(diào)整人工神經(jīng)網(wǎng)絡的連接權(quán)，也可以用于人工神經(jīng)網(wǎng)絡的網(wǎng)絡結(jié)構(gòu)優(yōu)化設計。分類器系統(tǒng)在多機器人路徑規(guī)劃系統(tǒng)中得到了成功的應用。9/19/2022SGA實例1：函數(shù)最值SGA參數(shù):編碼方式: 二進制碼 e.g. 000000; 01101 13; 1111131種群規(guī)模: 4隨機初始群體“轉(zhuǎn)盤賭”選擇一點雜交, 二進制變異 求函數(shù)f(x)=x2的最大值，x為自然數(shù)且0 x31.手工方式完成演示SGA過程9/19/202

30、2SGA實例1 max x2 : 選擇操作9/19/2022SGA實例1 max x2 : 交叉操作9/19/2022SGA實例1 max x2 : 變異操作9/19/2022SGA實例2 : 連續(xù)函數(shù)最值求下列函數(shù)的最大值：9/19/2022SGA實例2 : 編碼高精度 編碼 x,y 0,1L 必須可逆(一個表現(xiàn)型對應一個基因型) 解碼算子：: 0,1L x,y 染色體長度L決定可行解的最大精度長染色體(慢進化) 實數(shù)問題：變量z為實數(shù)，如何把a1,aL 0,1Lzx,y9/19/2022SGA實例2 : 編碼設定求解精確到6位小數(shù)，因區(qū)間長度位2-(-1)=3,則需將區(qū)間分為3X106等份

31、。因 2097152221 3X1062224194304。故編碼的二進制串長L=22。將一個二進制串(b21b20b0)轉(zhuǎn)化為10進制數(shù)：e.g. -1; 2 1.627 888 1.627888 = -1+3x(1110000000111111000101) 2 /(222-1) = -1+3x3674053/(222-1)9/19/2022SGA實例2 : 初始化種群、適應函數(shù)隨機初始化種群適應函數(shù) 本實例目標函數(shù)在定義域內(nèi)均大于0，且是求函數(shù)最大值，故直接引用目標函數(shù)作為適應函數(shù)： f(s) = f(x) 其中二進制串s對于變量x的值。 e.g. s1 = x1= -0.958 973

32、 適應值: f(s1) = f(x1) =1.078 878 s2= x2= 1.627 888 適應值: f(s2) = f(x2) = 3.250 6509/19/2022SGA實例2 :遺傳操作選擇操作(“輪盤賭”選擇)交叉操作(單點交叉) 交叉前(父): s1= s2= 交叉后(子): s1= s2= 適應值: f(s1) = f(-0.998 113) =1.940 865 f(s2) = f(1.666 028) = 3.459 245 s2的適應值比其雙親個體的適應值高。9/19/2022SGA實例2 :遺傳操作變異操作 變異前(父): s2= 變異后(子): s2= 適應值 f

33、(s2) = f(1.721 638) = 0.917 743 比 f(s2)小 變異前(父): s2= 變異后(子): s”2= 適應值 f(s”2) = f(1.630 818) = 3.343 555 比 f(s2)大變異操作有”擾動”作用，同時具有增加種群多樣性的效果。9/19/2022SGA實例2 :模擬結(jié)果遺傳算法的參數(shù): 種群規(guī)模: 50 染色體長度: L=22 最大進化代數(shù): 150 交叉概率: Pc=0.25 變異概率: Pm=0.01 9/19/2022SGA實例2 :模擬結(jié)果(最佳個體進化情況)世代數(shù)染色體編碼變量x適應值1411173440547189150100011

34、10000101100011110000011011000101001111011010101110011100111111101010111111010011111100001101111011001111110100100010001100111110001101101000110011110100110110001011001111110100111111001100111111010011111100110011111.831 6241.842 4161.854 8601.847 5361.853 2901.848 4431.848 6991.850 8971.850 5491.850

35、 5493.534 8063.790 3623.833 2863.842 0043.843 4023.846 2323.847 1553.850 1623.850 2743.850 2749/19/2022最優(yōu)化問題(Optimization Problem)最優(yōu)化問題:組合優(yōu)化問題(Combinatorial Optimization Problem ) :最優(yōu)化問題中的解空間X或S由離散集合構(gòu)成。其中很多問題是NP完全(Nondeterministic Polynomial Completeness)問題.9/19/2022最優(yōu)化問題算法傳統(tǒng)的優(yōu)化方法(局部優(yōu)化方法) 共軛梯度法、牛頓法、

36、單純形方法等特點: 1)依賴于初始條件。2)與求解空間有緊密關系，促使較快地收斂到局部 解，但同時對 解域有約束，如連續(xù)性或可微性。利用這些約束，收斂快。 3)有些方法，如Davison-Fletcher-Powell直接依賴于至少一階導數(shù)；共軛梯度法隱含地依賴于梯度。9/19/2022最優(yōu)化問題算法全局優(yōu)化方法 下降軌線法、Monte-Carlo隨機試驗法、模擬退火法、GA等特點：1)不依賴于初始條件；2)不與求解空間有緊密關系,對解域無可微或連續(xù)的要求;容易實現(xiàn)，求解穩(wěn)健。3)但收斂速度慢,能獲得全局最優(yōu);適合于求解空間不知的情況。4)GA可應用于大規(guī)模、多峰多態(tài)函數(shù)、含離散變量等全局優(yōu)化

37、問題;求解速度和質(zhì)量遠超過常規(guī)方法。9/19/2022無約束最優(yōu)化問題GA編碼：X=(x1,x2,xn)的各個變量可以按二進制編碼方法分別編碼。對于變量xi的上、下限約束lixi ui(i=1,2,n)，依據(jù)解的精度要求(有效位數(shù))求得各個變量X=(x1,x2,xn)的二進制碼位數(shù)(m1,m2,mn)(確定方法類似于SGA實例2)，因此將n個二進制位串順序連接起來，構(gòu)成一個個體的染色體編碼，編碼的總位數(shù)mm1+m2+mn。無約束最優(yōu)化問題:9/19/2022無約束最優(yōu)化問題GA解碼：解碼時仍按各個變量的編碼順序分別實現(xiàn)常規(guī)的二進制編碼解碼方法。二進制遺傳編碼示意圖如下：9/19/2022約束最

38、優(yōu)化問題常規(guī)解法：(1)把約束問題轉(zhuǎn)化為無約束問題，在用無約束問題方法求解，如罰函數(shù)法(2)改進無約束問題的方法，再用于約束問題，如梯度投影法、廣義簡約梯度法約束最優(yōu)化問題:9/19/2022約束最優(yōu)化問題遺傳算法求解關鍵: 約束條件的處理等式約束可以包含到適應函數(shù)，僅考慮不等式約束。 假設按無約束問題那樣求解，在搜索過程中計算目標函數(shù)值，并檢查是否有約束違反。如果沒有違反，則表明是可行解，就根據(jù)目標函數(shù)指定一適應值；否則，就是不可行解，因而沒有適應值(適應值為0)。這樣的處理實際不可行，因為找到一個可行解幾乎與找到最優(yōu)解一樣困難。9/19/2022一般解法：通過引入罰函數(shù)，從不可行解中得到一

39、些信息。將罰函數(shù)包含到適應函數(shù)中。關鍵是如何設計罰函數(shù)；不同問題需要設計不同的罰函數(shù)；對一般的約束處理，通常很困難。約束最優(yōu)化問題9/19/2022組合最優(yōu)化問題典型問題：巡回旅行商問題(Traveling Salesman Problem)作業(yè)調(diào)度問題(Job Shop Scheduling Problem)背包問題(Knapsack Problem)圖著色問題 很多組合最優(yōu)化問題是NP難問題或NP完全問題9/19/2022巡回旅行商問題(TSP)TSP，也稱貨郎擔問題，是一個NP完全問題。TSP描述：圖論:設圖G=(V,E),其中V是頂點集，E是邊集。設C=(cij)是與E相聯(lián)系的距離矩陣

40、。尋找一條通過所有頂點且每個頂點只通過一次的最短距離回路(Hamilton回路)。實際應用中，C也可解釋為費用或旅行時間矩陣。實際:一位推銷員從自己所在城市出發(fā)，必須遍訪所有城市之后又回到原來的城市，求使其旅行費用最少的路徑。9/19/2022巡回旅行商問題(TSP)中國貨郎擔問題:城市數(shù): 40城市編號1,2,40尋找一條最短路徑9/19/2022TSP復雜性搜索空間龐大TSP涉及求多個變量的函數(shù)的最小值，求解很困難。其可能的路徑條數(shù)隨著城市數(shù)目n成指數(shù)增長，如，5個城市對應12條路徑；10個城市對應181 440條路徑；100個城市對應4.6663X10155條路徑。如此龐大的搜索空間，常

41、規(guī)解法和計算工具都遇到計算上的困難。只能尋找近似解法，如神經(jīng)網(wǎng)絡方法、模擬退火法、遺傳算法等。9/19/2022TSP編碼:路徑表示染色體表示成所有城市的一個排列，若有n個城市，一條可能路徑編碼為長度為n的整數(shù)向量(i1,i2,in),其中ik表示第ik個城市。例如: 路徑編碼向量(5 1 7 8 9 4 6 2 3)直接表示一條旅行路程(5-1-7-8-9-4-6-2-3)。此向量是1到n的一個排列，即從1到n的每個整數(shù)在這個向量中正好出現(xiàn)一次,不能有重復。這樣，基本遺傳算法的基因操作生成的個體不能滿足這一約束條件，需尋求其他遺傳操作。9/19/2022TSP交叉需其他方式的交叉(重組)操作

42、,如部分匹配交叉(Partially Matched Crossover,PMX)、順序交叉(Ordered Crossover,OX)、循環(huán)交叉(Cycle Crossover,CX)、邊重組(Edge Recombination)。1 2 3 4 55 4 3 2 11 2 3 2 15 4 3 4 5一般的交叉操作會產(chǎn)生不合適的解，如9/19/2022TSP交叉1:部分匹配交叉(PMX)雙親P1,P2隨機選取兩個交叉點，得到一個匹配段,根據(jù)交叉點中間段給出映射關系。123456789937826514xxx4567xxxxx8265xxP1P2映射關系：4 8、5 2、7 5c1c2 交

43、換兩個交叉點之間的編碼,(X表示未定碼)9/19/2022TSP交叉1:部分匹配交叉(PMX)子個體C1，C2分別從其父個體中繼承未映射城市碼12345678993782651493x45671x1x38265x9P1P2c1c2映射關系：4 8、5 2、7 5932456718173826549c1c2 再根據(jù)映射關系，對以上未定碼，使用最初雙親碼，得到子個體的對應碼。映射關系存在傳遞關系，則選擇未定碼交換。9/19/2022TSP交叉2:順序交叉(OX)雙親P1,P2隨機選取兩個交叉點123456789937826514P1P2xxx4567xxxxx8265xxc1c2 兩個交叉點間的中

44、間段保存不變 子個體C1的未定碼的確定需要父個體P2的未選定城市碼，子個體C2的未定碼的確定需要父個體P1的未選定城市碼。9/19/2022TSP交叉2:順序交叉(OX)記取父個體P2從第二個交叉點開始城市碼的排列順序，當?shù)竭_表尾時，返回表頭繼續(xù)記錄，直到第二個交叉點。937826514P2xxx4567xxc1382456719c1347826591c2 得到父個體P2的排列順序1-4-9-3-7-8-2-6-5,并將C1已有城市碼4,5,6,7從中去掉，得到排列順序1-9-3-8-2，再將此順序復制到C1，復制點也是從第二個交叉點開始，得到C1。同理的C2，9/19/2022TSP交叉3:

45、循環(huán)交叉(CX)CX操作中子個體中的城市碼順序根據(jù)任一父個體產(chǎn)生確定循環(huán)編碼 復制循環(huán)編碼到子個體9/19/2022TSP變異Insert Mutation隨機選取個體中兩個編碼，然后把第二個編碼放在第一個編碼之后，其他編碼順次調(diào)節(jié)位置。 Swap mutation隨機選取個體中兩個編碼，然后交換它們的位置。9/19/2022TSP變異Inversion mutation隨機選取個體中一段編碼，然后顛倒這段編碼的順序。 Scramble mutation隨機選取個體上一段編碼,然后打亂這段編碼的順序。選取的編碼不一定是鄰接編碼9/19/2022TSP的GA過程從N個隨機起點開始產(chǎn)生N條路徑，N

46、為種群的規(guī)模;利用最優(yōu)方法搜索每條路徑的局部最優(yōu)解;選擇交叉對使在平均性能之上的個體得到更多的子代;交叉和變異;搜索每條路徑得到其極小解，如果不收斂，則回到第3步；否則，停止。9/19/2022GA的MATLAB實現(xiàn)軟件平臺(Software Platforms):MATLAB 7.xGenetic Algorithm and Direct Search Toolbox2.0.1 MATLAB 6.x(or 7.x)+GAOTGAOT: Genetic Algorithm Optimization Toolbox美國North Carolina State University開發(fā)MATLAB

47、 6.x(or 7.x)+GEATbxGEATbx: Genetic and Evolutionary Algorithm Toolbox 英國The University of Sheffield開發(fā)MATLAB遺傳算法工具箱及應用(雷英杰等,西安電子科技大學出版社,2005)基于此工具箱 9/19/2022GAOT工具箱核心函數(shù)： pop=initializega(num,bounds,eevalFN,eevalOps,options) -初始種群的生成函數(shù) 【輸出參數(shù)】 pop-生成的初始種群 【輸入?yún)?shù)】 num-種群中的個體數(shù)目 bounds-代表變量的上下界的矩陣 eevalFN-適應度函數(shù) eevalOps-傳遞給適應度函數(shù)的參數(shù) options-選擇編碼形式(浮點編碼或是二進制編碼)與精度，如 type prec，type-為1時選擇浮點編碼，否則為二進制編碼prec-變量進行二進制編碼時指定的精度，默認1e-6 19/19/2022GAOT工具箱(2) x,endPop,bPop,traceInfo = ga(bounds,evalFN,evalOps,startPop,opts,termFN,termOps,select