過程建模8-智能優(yōu)化

下篇非線性系統(tǒng)建模8智能優(yōu)化應用8.1概述8.2各種算法簡介8.3遺傳算法及其應用(自學）8智能優(yōu)化應用8.1概述

智能優(yōu)化算法，或稱現(xiàn)代啟發(fā)式算法（Meta-HeuristicAlgorithms）它是通過模擬或揭示某些自然現(xiàn)象或過程而發(fā)展起來，其思想和內容涉及數學、物理學、生物進化、人工智能、神經科學和統(tǒng)計力學等方面，為解決復雜問題提供了新的思路和手段。它具有全局的、并行高效的優(yōu)化性能，魯棒性、通用性強，無需問題特殊信息等優(yōu)點。8智能優(yōu)化應用8.1概述非線性系統(tǒng)建模問題可轉換為如下非線性規(guī)劃問題的求解：有兩種數值解法——普通搜索法和智能搜索法回顧：8智能優(yōu)化應用智能優(yōu)化算法與普通搜索算法區(qū)別8.1概述普通搜索算法智能優(yōu)化算法初始值一個一組（種群）變量是否需要編碼不需要需要，映射為可進行啟發(fā)式操作的數據結構搜索策略確定性隨機性（概率型）目標函數常需要目標函數的導數信息僅需要目標函數信息搜索問題的連續(xù)性、凸性需滿足連續(xù)可微性、凸性不需要適用性小規(guī)模計算并行性、魯棒性、通用性8智能優(yōu)化應用8.1概述將有約束優(yōu)化問題直接按無約束問題處理是行不通的：隨機生成的初始點中可能有大量不可行解；優(yōu)化算子作用于可行解后可能產生不可行解。?智能優(yōu)化算法約束條件的處理目前還未找到一種能夠處理各種約束條件的一般化方法，只能針對具體問題及約束選用不同方法。搜索空間限定法對搜索空間的大小加以限制，使搜索空間中表示一個個體的解與解空間中表示一個可行解的點一一對應；實現(xiàn)方法：用編碼方式來保證；用程序來保證?？尚薪庾儞Q法在由個體基因型到個體表現(xiàn)型的變換中，尋找一種從個體基因型到個體表現(xiàn)型之間多對一的變換關系，使進化過程中所產生的個體總能通過這種變換而轉化成解空間中滿足約束條件的一個可行解。罰函數法對解空間中無對應可行解的個體，在計算其適應度時，用罰函數來降低該個體適應度，減少其被遺傳到下一代群體中的機會。A8智能優(yōu)化應用8.1概述8智能優(yōu)化應用智能優(yōu)化算法可研究問題缺乏普遍適用的算法收斂性理論；缺乏完備的計算搜索效率及時空復雜度理論評價體系；沒有建立起完備的算法結構框架；算法的理論基礎還不能清楚地解釋算法在應用過程中出現(xiàn)的各種問題；算法參數的選擇主要還是憑經驗選?。粚Σ僮魉阕拥淖饔脵C理及其作用效果的分析仍不充分；由于它們的研究機制和側重點的不同，使得研究成果相當分散。8.1概述8智能優(yōu)化應用模擬退火算法（SA）該算法建立在蒙特卡羅原理的基礎上，模擬固體退火過程，是一種啟發(fā)式隨機優(yōu)化方法，適合求解大規(guī)模優(yōu)化問題。特點：算法實現(xiàn)簡單，使用靈活，可跳出局部極值區(qū)，但收斂速度慢，有關控制參數難以確定等。8.2各種算法簡介8智能優(yōu)化應用禁忌搜索算法（TS）它是F.Glover在20世紀60年代末提出的一種模擬智力過程而擴展鄰域的啟發(fā)式搜索算法。特點：在搜索過程中獲得知識，能夠以較大的概率跳出局部極值，以其較高的求解質量和效率已在許多組合優(yōu)化問題中顯示出強大的尋優(yōu)能力，但存在對初始解依賴性較強及搜索僅能單對單操作的缺點。8.2各種算法簡介8智能優(yōu)化應用Hopfield神經網絡它是美國物理學家J.J.Hopfield于1982年首先提出的。其演變過程是一個非線性動力系統(tǒng)，系統(tǒng)的穩(wěn)定性可用所謂的“能量函數”（即李雅普諾夫或哈密爾頓函數）進行分析。如果把能量函數視為一個優(yōu)化問題的目標函數，那么從這個初態(tài)朝穩(wěn)定點的演變過程就是一個求解該優(yōu)化問題的過程。它主要用于模擬神經網絡的記憶機理特點：具有單調下降、并行計算和聯(lián)想記憶等優(yōu)點，但同時也存在著收斂速度慢，易陷入局部極值點等缺點，且網絡合適的隱含層數目和節(jié)點數目確定較困難。8.2各種算法簡介8智能優(yōu)化應用遺傳算法（GA）它是美國密執(zhí)安大學的JohnHolland教授于1975年首先提出的一類仿生型優(yōu)化算法。它是以達爾文的生物進化論“適者生存、優(yōu)勝劣汰”和孟德爾的遺傳變異理論“生物遺傳進化主要在染色體上，子代是父代遺傳基因在染色體上的有序排列”為基礎，模擬生物界進化過程。特點：具有大范圍全局搜索的能力，潛在的并行性、隨機性，魯棒性強，過程簡單。缺點是不能很好的利用系統(tǒng)反饋信息，冗余迭代多，影響求優(yōu)化解效率。8.2各種算法簡介8智能優(yōu)化應用螞蟻算法（ＡA）它是意大利學者M.Dorigo1991年提出的一種源于大自然新的仿生類隨機優(yōu)化算法。主要是通過螞蟻群體之間的信息傳遞而達到尋優(yōu)的目的。由于模擬仿真中使用了人工螞蟻的概念，因此亦稱螞蟻系統(tǒng)（antsystem簡稱AS）。其原理是一種正反饋機制或稱增強型學習系統(tǒng)，它通過信息素的不斷更新達到最終收斂于最優(yōu)路徑上。特點：具有并行、隨機、全局優(yōu)化的優(yōu)點，其缺點是初期信息素匱乏，求解速度慢。8.2各種算法簡介8智能優(yōu)化應用DNA計算它是美國加利福尼亞大學的Adleman博士1994年第一次提出的一種借助生物分子DNA的結構利用現(xiàn)代分子生物技術進行計算的新方法，它開創(chuàng)了以化學反應作為計算工具的先例，并成功地在DNA溶液試管中對哈密爾頓有向路徑問題進行求解實驗。特點：具有高度的并行性、海量存儲、低能耗、資源豐富等顯著特點。但最優(yōu)解如何分離、“輸出技術”瓶頸、“偽解”與“誤差”如何避免等面臨巨大的技術挑戰(zhàn)。8.2各種算法簡介8智能優(yōu)化應用算法創(chuàng)始人優(yōu)化機制關鍵參數SAKirkpatrik基于MonteCarlo的全局概率型串行搜索的優(yōu)化算法初始溫度、退溫函數、狀態(tài)產生方式、抽樣穩(wěn)定準則TSGlove具有記憶功能的全局逐步優(yōu)化算法列表大小、鄰域函數結構與數量GAHolland基于生物進化與遺傳思想的全局性并行優(yōu)化算法種群數目及復制、交叉、變異操作概率NNHopfield基于神經網絡原理及系統(tǒng)演變過程的一種聯(lián)想記憶并行優(yōu)化算法神經元數目、輸入輸出變量、隱含層數AADorigo具有強化學習功能的全局性并行優(yōu)化算法初始信息素、信息素增量、信息素積累量、消失因子、啟發(fā)因子DNAAdleman以化學反應為計算工具有巨大并行性的分子生物計算方法各種生物酶PCR、POA、超聲波降解、親和層析、克隆、誘變、分子純化、電泳、磁珠分離8.2各種算法簡介局部搜索，模擬退火，遺傳算法，禁忌搜索的形象比喻：

為了找出地球上最高的山，一群有志氣的兔子們開始想辦法.1．兔子朝著比現(xiàn)在高的地方跳去.他們找到了不遠處的最高山峰.但是這座山不一定是珠穆朗瑪峰.這就是局部搜索，它不能保證局部最優(yōu)值就是全局最優(yōu)值.*補充資料：8智能優(yōu)化應用8.2各種算法簡介2．兔子喝醉了.他隨機地跳了很長時間.這期間，它可能走向高處，也可能踏入平地。但是，他漸漸清醒了并朝最高方向跳去.這就是模擬退火.3．兔子們吃了失憶藥片，并被發(fā)射到太空，然后隨機落到了地球上的某些地方.他們不知道自己的使命是什么.但是，如果你過幾年就殺死一部分海拔低的兔子，多產的兔子們自己就會找到珠穆朗瑪峰.這就是遺傳算法.4.兔子們知道一個兔的力量是渺小的.他們互相轉告著，哪里的山已經找過，并且找過的每一座山他們都留下一只兔子做記號.他們制定了下一步去哪里尋找的策略.這就是禁忌搜索.

*補充資料：8智能優(yōu)化應用8.2各種算法簡介群體智能受社會性昆蟲行為的啟發(fā)，計算機工作者通過對社會性昆蟲的模擬產生了一系列對于傳統(tǒng)問題的新的解決方法，這些研究就是群集智能的研究.群集智能(Swarm

Intelligence)中的群體(Swarm)指的是“一組相互之間可以進行直接通信或者間接通信(通過改變局部環(huán)境)的主體，這組主體能夠合作進行分布問題求解”.所謂群集智能指的是“無智能的主體通過合作表現(xiàn)出智能行為的特性”.

*補充資料：8智能優(yōu)化應用8.2各種算法簡介遺傳算法是智能優(yōu)化算法的一種，是一種具有全局優(yōu)化性能、通用性強、且適合于并行處理的算法。與其它智能優(yōu)化算法具有共同的特點：都是從任一解出發(fā)，按照某種機制，以一定的概率在整個求解空間中探索最優(yōu)解。由于它們可以把搜索空間擴展到整個問題空間，因而具有全局優(yōu)化性能。物競天擇，強者生存8智能優(yōu)化應用8.3遺傳算法及應用遺傳算法是由美國的J.Holland教授于1975年在他的專著《自然界和人工系統(tǒng)的適應性》中首先提出的，它是一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法，或者說迭代自適應概率性搜索算法。8智能優(yōu)化應用8.2各種算法簡介函數優(yōu)化問題1975年，DeJong在其博士論文中結合模式定理進行了大量的純數值函數優(yōu)化計算實驗，樹立了遺傳算法的工作框架，得到了一些重要且具有指導意義的結論。他推薦了在大多數優(yōu)化問題中都比較適用的遺傳算法參數，還建立了著名的DeJong五函數測試平臺，定義了評價遺傳算法性能的在線指標和離線指標。8智能優(yōu)化應用8.3遺傳算法及應用

1.個體與種群

●個體就是模擬生物個體而對問題中的對象（一般就是問題的解）的一種稱呼，一個個體也就是搜索空間中的一個點。

●

種群(population)就是模擬生物種群而由若干個體組成的群體,它一般是整個搜索空間的一個很小的子集?！穹N群規(guī)模就是種群中個體的數量?；靖拍?智能優(yōu)化應用8.3遺傳算法及應用

2.適應度與適應度函數

●

適應度(fitness)就是借鑒生物個體對環(huán)境的適應程度,而對問題中的個體對象所設計的表征其優(yōu)劣的一種測度。

●適應度函數(fitnessfunction)就是問題中的全體個體與其適應度之間的一個對應關系。它一般是一個實值函數。該函數就是遺傳算法中指導搜索的評價函數。8智能優(yōu)化應用8.3遺傳算法及應用3.染色體與基因

染色體（chromosome）就是問題中個體的某種字符串形式的編碼表示。字符串中的字符也就稱為基因（gene）。例如：個體染色體

9----

1001（2，5，6）----0101011108智能優(yōu)化應用8.3遺傳算法及應用4.遺傳操作

亦稱遺傳算子(geneticoperator)，就是關于染色體的運算。遺傳算法中有三種遺傳操作:

●

選擇-復制(selection-reproduction)

●

交叉(crossover，亦稱交換、交配或雜交)

●

變異(mutation，亦稱突變)

8智能優(yōu)化應用8.3遺傳算法及應用

選擇-復制對于一個規(guī)模為N的種群S，按每個染色體xi的選擇概率P(xi)，分N次從S中隨機選定N個染色體，并進行復制。適應度函數選擇操作的任務就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。SGA中選擇算子采用輪盤賭選擇方法。

8智能優(yōu)化應用8.3遺傳算法及應用

交叉就是互換兩個染色體某些位上的基因。

s1′=01000101,s2′=10011011可以看做是原染色體s1和s2的子代染色體。

例如,設染色體s1=01001011,s2=10010101,交換其后4位基因,即8智能優(yōu)化應用8.3遺傳算法及應用

變異就是改變染色體某個(些)位上的基因。例如,設染色體s=11001101將其第三位上的0變?yōu)?,即s=11001101→11101101=s′。s′也可以看做是原染色體s的子代染色體。8智能優(yōu)化應用8.3遺傳算法及應用

遺傳算法基本流程框圖生成初始種群計算各個體適應度選擇-復制交叉變異生成新一代種群終止?結束基本遺傳算法SimpleGeneticAlgorithms，簡稱SGA，又稱簡單遺傳算法或標準遺傳算法。8智能優(yōu)化應用8.3遺傳算法及應用

算法中的一些控制參數：

■

種群規(guī)模

■

最大代數

■

交叉率(crossoverrate)就是參加交叉運算的染色體個數占全體染色體總數的比例，記為Pc,取值范圍一般為0.4～0.99。

■

變異率(mutationrate)是指發(fā)生變異的基因位數占全體染色體的基因總位數的比例，記為Pm，取值范圍一般為0.0001～0.1。8智能優(yōu)化應用8.3遺傳算法及應用基本遺傳算法步驟step1在搜索空間U上定義一個適應度函數f(x)，給定種群規(guī)模N，交叉率Pc和變異率Pm，代數T；

step2隨機產生U中的N個個體s1,s2,…,sN，組成初始種群S={s1,s2,…,sN}，置代數計數器t=1；

初始條件初始化8智能優(yōu)化應用8.3遺傳算法及應用

step3計算S中每個個體的適應度f(x)；

step4若終止條件滿足，則取S中適應度最大的個體作為所求結果，算法結束。否則繼續(xù)向下。

step5按選擇概率P(xi)所決定的選中機會，每次從S中隨機選定1個個體并將其染色體復制，共做N次，然后將復制所得的N個染色體組成群體S1；判斷終止條件復制8智能優(yōu)化應用8.3遺傳算法及應用step6按交叉率Pc所決定的參加交叉的染色體數c，從S1中隨機確定c個染色體，配對進行交叉操作，并用產生的新染色體代替原染色體，得群體S2；

step7按變異率Pm所決定的變異次數m，從S2中隨機確定m個染色體，分別進行變異操作，并用產生的新染色體代替原染色體，得群體S3；

step8將群體S3作為新一代種群，即用S3代替S，t=t+1，轉step3；交叉變異更新8智能優(yōu)化應用8.3遺傳算法及應用遺傳算法應用舉例

例利用遺傳算法求解區(qū)間［0,31］上的二次函數y=x2的最大值。

y=x2

31

XY8智能優(yōu)化應用8.3遺傳算法及應用

分析

原問題可轉化為在區(qū)間［0,31］中搜索能使y取最大值的點a的問題。那么，［0,31］中的點x就是個體,函數值f(x)恰好就可以作為x的適應度，區(qū)間［0,31］就是一個(解)空間。這樣,只要能給出個體x的適當染色體編碼,該問題就可以用遺傳算法來解決。約束條件怎么實現(xiàn)？8智能優(yōu)化應用8.3遺傳算法及應用

解

(1)設定種群規(guī)模,編碼染色體，產生初始種群。將種群規(guī)模設定為4；用5位二進制數編碼染色體；取下列個體組成初始種群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

(2)定義適應度函數,取適應度函數：f(x)=x2

8智能優(yōu)化應用8.3遺傳算法及應用首先計算種群S1中各個體s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)的適應度f(si)。容易求得f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=3618智能優(yōu)化應用8.3遺傳算法及應用再計算種群S1中各個體的選擇概率。選擇概率的計算公式為由此可求得

P(s1)=P(13)=0.