現(xiàn)代優(yōu)化算法

現(xiàn)代優(yōu)化算法第1頁/共163頁目錄現(xiàn)在優(yōu)化算法概論模擬退火算法(SA)遺傳算法(GA)第2頁/共163頁P(yáng)art1概論主要是說明現(xiàn)代優(yōu)化算法的重要性。第3頁/共163頁現(xiàn)代優(yōu)化算法

現(xiàn)代優(yōu)化算法遺傳算法模擬退火算法禁忌搜索算法人工神經(jīng)網(wǎng)絡(luò)蟻群算法粒子群算法差分進(jìn)化算法特點(diǎn)：基于客觀世界中的一些自然現(xiàn)象；建立在計(jì)算機(jī)迭代計(jì)算的基礎(chǔ)上；具有普適性，可解決實(shí)際應(yīng)用問題。第4頁/共163頁數(shù)學(xué)建模競賽中的算法(1)93A非線性交調(diào)的頻率設(shè)計(jì):擬合、規(guī)劃93B足球隊(duì)排名次:矩陣論、圖論、層次分析法、整數(shù)規(guī)劃94A逢山開路:圖論、插值、動(dòng)態(tài)規(guī)劃94B鎖具裝箱問題:圖論、組合數(shù)學(xué)95A飛行管理問題

:非線性規(guī)劃、線性規(guī)劃95B天車與冶煉爐的作業(yè)調(diào)度:非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、層次分析法、PETRI方法、圖論方法、排隊(duì)論方法96A最優(yōu)捕魚策略：微分方程、積分、非線性規(guī)劃第5頁/共163頁96B節(jié)水洗衣機(jī)：非線性規(guī)劃97A零件參數(shù)設(shè)計(jì)：微積分、非線性規(guī)劃、隨機(jī)模擬97B截?cái)嗲懈睿航M合優(yōu)化、幾何變換、枚舉、蒙特卡羅、遞歸、最短路98A投資收益與風(fēng)險(xiǎn)：線性規(guī)劃、非線性規(guī)劃98B災(zāi)情巡視：最小生成樹、Hamilton圈、旅行商問題99A自動(dòng)化車床：積分、概率分布、隨機(jī)模擬、分布擬合度檢驗(yàn)數(shù)學(xué)建模競賽中的算法(2)第6頁/共163頁99B鉆井布局：幾何變換、枚舉、最大完全子圖、混合整數(shù)規(guī)劃00ADNA分類：神經(jīng)網(wǎng)絡(luò)、最小二乘擬合、統(tǒng)計(jì)分類00B管道訂購：最短路、二次規(guī)劃01A血管的三維重建：數(shù)據(jù)挖掘、曲面重建與擬合01B公交車調(diào)度：非線性規(guī)劃02A車燈光源優(yōu)化設(shè)計(jì)：最優(yōu)化02B彩票中的數(shù)學(xué)：概率與優(yōu)化數(shù)學(xué)建模競賽中的算法(3)第7頁/共163頁1.

蒙特卡羅方法(Monte-Carlo方法,MC)數(shù)學(xué)建模競賽常用算法(1)

該算法又稱計(jì)算機(jī)隨機(jī)性模擬方法，也稱統(tǒng)計(jì)試驗(yàn)方法。MC方法是一種基于“隨機(jī)數(shù)”的計(jì)算方法，能夠比較逼真地描述事物的特點(diǎn)及物理實(shí)驗(yàn)過程，解決一些數(shù)值方法難以解決的問題。MC方法的雛型可以追溯到十九世紀(jì)后期的蒲豐隨機(jī)投針試驗(yàn)，即著名的蒲豐問題。MC方法通過計(jì)算機(jī)仿真(模擬)解決問題，同時(shí)也可以通過模擬來檢驗(yàn)自己模型的正確性，是比賽中經(jīng)常使用的方法。第8頁/共163頁97年的A題每個(gè)零件都有自己的標(biāo)定值，也都有自己的容差等級(jí)，而求解最優(yōu)的組合方案將要面對(duì)著的是一個(gè)極其復(fù)雜的公式和108種容差選取方案，根本不可能去求解析解，那如何去找到最優(yōu)的方案呢？隨機(jī)性模擬搜索最優(yōu)方案就是其中的一種方法，在每個(gè)零件可行的區(qū)間中按照正態(tài)分布隨機(jī)的選取一個(gè)標(biāo)定值和選取一個(gè)容差值作為一種方案，然后通過蒙特卡羅算法仿真出大量的方案，從中選取一個(gè)最佳的。02年的B題關(guān)于彩票第二問，要求設(shè)計(jì)一種更好的方案，首先方案的優(yōu)劣取決于很多復(fù)雜的因素，同樣不可能刻畫出一個(gè)模型進(jìn)行求解，只能靠隨機(jī)仿真模擬。數(shù)學(xué)建模競賽常用算法第9頁/共163頁98年美國賽A題

生物組織切片的三維插值處理94年A題逢山開路

山體海拔高度的插值計(jì)算數(shù)學(xué)建模競賽常用算法(2)2.數(shù)據(jù)擬合、參數(shù)估計(jì)、插值等數(shù)據(jù)處理算法

比賽中通常會(huì)遇到大量的數(shù)據(jù)需要處理，而處理數(shù)據(jù)的關(guān)鍵就在于這些算法，通常使用MATLAB作為工具。與圖形處理有關(guān)的問題很多與擬合有關(guān)系。

此類問題在MATLAB中有很多函數(shù)可以調(diào)用，只有熟悉MATLAB，這些方法才能用好。第10頁/共163頁98年B題用很多不等式完全可以把問題刻畫清楚數(shù)學(xué)建模競賽常用算法(3)3.規(guī)劃類問題算法

此類問題主要有線性規(guī)劃、整數(shù)規(guī)劃、多元規(guī)劃、二次規(guī)劃等。競賽中很多問題都和數(shù)學(xué)規(guī)劃有關(guān)，可以說不少的模型都可以歸結(jié)為一組不等式作為約束條件、幾個(gè)函數(shù)表達(dá)式作為目標(biāo)函數(shù)的問題，遇到這類問題，求解就是關(guān)鍵了。

因此列舉出規(guī)劃后用Lindo、Lingo等軟件來進(jìn)行解決比較方便，所以還需要熟悉這兩個(gè)軟件。第11頁/共163頁98年B題、00年B題、95年鎖具裝箱等問題體現(xiàn)了圖論問題的重要性。數(shù)學(xué)建模競賽常用算法(4)4.

圖論問題

這類問題算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等問題。第12頁/共163頁92年B題用分枝定界法97年B題是典型的動(dòng)態(tài)規(guī)劃問題98年B題體現(xiàn)了分治算法數(shù)學(xué)建模競賽常用算法(5)5.計(jì)算機(jī)算法設(shè)計(jì)中的問題

計(jì)算機(jī)算法設(shè)計(jì)包括很多內(nèi)容：動(dòng)態(tài)規(guī)劃、回溯搜索、分治算法、分枝定界等計(jì)算機(jī)算法.

這方面問題和ACM程序設(shè)計(jì)競賽中的問題類似，可看一下與計(jì)算機(jī)算法有關(guān)的書。第13頁/共163頁97年A題用模擬退火算法00年B題用神經(jīng)網(wǎng)絡(luò)分類算法01年B題這種難題也可以使用神經(jīng)網(wǎng)絡(luò)美國89年A題也和BP算法有關(guān)系美國03年B題伽馬刀問題也是目前研究的課題，目前算法最佳的是遺傳算法。最優(yōu)化理論的三大非經(jīng)典算法:

模擬退火法(SA)、神經(jīng)網(wǎng)絡(luò)(NN)、遺傳算法(GA)

近幾年的賽題越來越復(fù)雜，很多問題沒有什么很好的模型可以借鑒，于是這三類算法很多時(shí)候可以派上用場。第14頁/共163頁97年A題、99年B題都可以用網(wǎng)格法搜索數(shù)學(xué)建模競賽常用算法(7)

網(wǎng)格算法和窮舉法一樣，只是網(wǎng)格法是連續(xù)問題的窮舉。此類算法運(yùn)算量較大。7.網(wǎng)格算法和窮舉算法

這種方法最好在運(yùn)算速度較快的計(jì)算機(jī)中進(jìn)行，還有要用高級(jí)語言來做，最好不要用MATLAB做網(wǎng)格，否則會(huì)算很久的。第15頁/共163頁

很多問題都是實(shí)際來的，數(shù)據(jù)可以是連續(xù)的，而計(jì)算機(jī)只能處理離散的數(shù)據(jù)，因此需要將連續(xù)問題進(jìn)行離散化處理后再用計(jì)算機(jī)求解。比如差分代替微分、求和代替積分等思想都是把連續(xù)問題離散化的常用方法。數(shù)學(xué)建模競賽常用算法(8)8.連續(xù)問題離散化的方法第16頁/共163頁

數(shù)值分析研究各種求解數(shù)學(xué)問題的數(shù)值計(jì)算方法，特別是適合于計(jì)算機(jī)實(shí)現(xiàn)方法與算法。數(shù)學(xué)建模競賽常用算法(9)9.數(shù)值分析方法

它的主要內(nèi)容包括函數(shù)的數(shù)值逼近、數(shù)值微分與數(shù)值積分、非線性方程的數(shù)值解法、數(shù)值代數(shù)、常微分方程數(shù)值解等。數(shù)值分析是計(jì)算數(shù)學(xué)的一個(gè)重要分支，把理論與計(jì)算緊密結(jié)合,是現(xiàn)代科學(xué)計(jì)算的基礎(chǔ)。MATLAB等數(shù)學(xué)軟件中已經(jīng)有很多數(shù)值分析的函數(shù)可以直接調(diào)用。第17頁/共163頁01年A題中需要你會(huì)讀BMP圖象98年美國A題需要你知道三維插值計(jì)算03年B題要求更高，不但需要編程計(jì)算還要進(jìn)行處理數(shù)學(xué)建模競賽常用算法(10)10.圖象處理算法

賽題中有一類問題與圖形有關(guān)，即使問題與圖形無關(guān)，論文中也會(huì)需要圖片來說明問題，這些圖形如何展示以及如何處理就是需要解決的問題，通常使用MATLAB進(jìn)行處理。

數(shù)模論文中也有很多圖片需要展示，解決這類問題要熟悉MATLAB圖形圖像工具箱。第18頁/共163頁優(yōu)化模型

實(shí)際問題中的優(yōu)化模型x~決策變量f(x)~目標(biāo)函數(shù)gi(x)0~約束條件數(shù)學(xué)規(guī)劃線性規(guī)劃(LP)二次規(guī)劃(QP)非線性規(guī)劃(NLP)純整數(shù)規(guī)劃(PIP)混合整數(shù)規(guī)劃(MIP)整數(shù)規(guī)劃(IP)0-1整數(shù)規(guī)劃一般整數(shù)規(guī)劃連續(xù)規(guī)劃第19頁/共163頁最優(yōu)化問題(OptimizationProblem)最優(yōu)化問題:組合優(yōu)化問題(CombinatorialOptimizationProblem):最優(yōu)化問題中的解空間X或S由離散集合構(gòu)成。其中很多問題是NP完全(NondeterministicPolynomialCompleteness)問題.第20頁/共163頁待解決的問題

連續(xù)性問題，以微積分為基礎(chǔ)，規(guī)模較小傳統(tǒng)的優(yōu)化方法理論上的準(zhǔn)確與完美，主要方法：線性與非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、多目標(biāo)規(guī)劃、整數(shù)規(guī)劃等；排隊(duì)論、庫存論、對(duì)策論、決策論等。傳統(tǒng)的評(píng)價(jià)方法算法收斂性、收斂速度

傳統(tǒng)優(yōu)化方法

第21頁/共163頁現(xiàn)代優(yōu)化算法

現(xiàn)代優(yōu)化算法又稱智能優(yōu)化算法或現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強(qiáng)、且適合于并行處理的算法。這種算法一般具有嚴(yán)密的理論依據(jù)，而不是單純憑借專家經(jīng)驗(yàn)，理論上可以在一定的時(shí)間內(nèi)找到最優(yōu)解或近似最優(yōu)解。第22頁/共163頁待解決的問題

離散性、連續(xù)的、不確定性、大規(guī)?，F(xiàn)代的優(yōu)化方法啟發(fā)式算法（heuristicalgorithm）追求滿意（近似解）實(shí)用性強(qiáng)（解決實(shí)際工程問題）現(xiàn)代的評(píng)價(jià)方法算法復(fù)雜性

現(xiàn)代優(yōu)化方法

第23頁/共163頁現(xiàn)代優(yōu)化算法的特點(diǎn)

它們的共同特點(diǎn)：都是從任一解出發(fā)，按照某種機(jī)制，以一定的概率在整個(gè)求解空間中探索最優(yōu)解。由于它們可以把搜索空間擴(kuò)展到整個(gè)問題空間，因而具有全局優(yōu)化性能。第24頁/共163頁全局優(yōu)化(Rastrigin’sFunction)全局最小點(diǎn)(0,0)/help/toolbox/gads/f14773.html第25頁/共163頁現(xiàn)代優(yōu)化算法特點(diǎn)：1)不依賴于初始條件；2)不與求解空間有緊密關(guān)系,對(duì)解域無可微或連續(xù)的要求;容易實(shí)現(xiàn)，求解穩(wěn)健。3)但收斂速度慢，能獲得全局最優(yōu)；適合于求解空間不知的情況。4)SA、GA可應(yīng)用于大規(guī)模、多峰多態(tài)函數(shù)、含離散變量等全局優(yōu)化問題；求解速度和質(zhì)量遠(yuǎn)超過常規(guī)方法。第26頁/共163頁常用的現(xiàn)代優(yōu)化算法

遺傳算法

GeneticAlgorithm，簡稱GA模擬退火算法

SimulatedAnnealing，簡稱SA禁忌搜索算法

TabuSearch，簡稱TS神經(jīng)網(wǎng)絡(luò)算法

NeuralNetworkAlgorithm，簡稱NNA粒子群算法

ParticleSwarmOptimization，簡稱PSO差分進(jìn)化算法

DifferentialEvolution，簡稱DE第27頁/共163頁搜索示例：三個(gè)孩子的年齡(1)兩個(gè)多年未見的朋友相遇，聊了很多事情。…A：既然你是數(shù)學(xué)教授，那你幫我算這個(gè)題，今天是個(gè)特殊日子：我三個(gè)兒子都在今天慶祝生日！那么你能算出他們都有多大嗎？B：好，但你得跟我講講他們的情況。A：好的，我給你一些提示，他們?nèi)齻€(gè)年齡之積是36.B：很好，但我還需要更多提示。第28頁/共163頁三個(gè)孩子的年齡(2)A：我的大兒子的眼睛是藍(lán)色的。B考慮了一下說，但是，我還有一點(diǎn)信息來解決你的這個(gè)難題。B：哦，夠了，B給出了正確的答案，即三個(gè)小孩的年齡。A：他們?nèi)齻€(gè)年齡之和等于那幢房子的窗戶個(gè)數(shù)。A指著對(duì)面的一幢房子說。第29頁/共163頁三個(gè)孩子的年齡(3)根據(jù)對(duì)話信息，用搜索的方法來解此問題。信息1:三個(gè)小孩年齡之積為36只有以下8種可能，搜索范圍減少至8種情況:第一個(gè)小孩年齡36181299664第二個(gè)小孩年齡12342633第三個(gè)小孩年齡11112123第30頁/共163頁三個(gè)孩子的年齡(4)信息2:三個(gè)小孩年齡之和等于窗戶數(shù)第一個(gè)小孩年齡36181299664第二個(gè)小孩年齡12342633第三個(gè)小孩年齡11112123窗戶數(shù):3821161413131110如果窗戶數(shù)為38、21、16、14、11、10即可得出答案B還需信息，即窗戶數(shù)為13.則可能為(9、2、2)或(6、6、1)信息2:大兒子眼睛是藍(lán)色的得答案：(9、2、2)第31頁/共163頁典型問題——旅行商問題（Travelingsalesmanproblem,TSP）

123412181032搜索示例：TSP問題

給定n個(gè)城市和兩兩城市之間的距離，要求確定一條經(jīng)過各城市當(dāng)且僅當(dāng)一次的最短路線。第32頁/共163頁典型問題——旅行商問題

城市數(shù)2425262728293031計(jì)算時(shí)間1sec24sec10min4.3hour4.9day136.5day10.8year325yearTSP的搜索的困難計(jì)算復(fù)雜度：指數(shù)災(zāi)難第33頁/共163頁P(yáng)art2模擬退火法第34頁/共163頁第35頁/共163頁第36頁/共163頁模擬退火算法及模型

算法的提出

模擬退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。物理退火過程算法的目的解決NP復(fù)雜性問題；克服優(yōu)化過程陷入局部極??；克服初值依賴性。第37頁/共163頁什么是退火：退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。物理退火過程第38頁/共163頁模擬退火算法及模型

等溫過程——對(duì)于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡態(tài)；物理退火過程

加溫過程——增強(qiáng)粒子的熱運(yùn)動(dòng)，消除系統(tǒng)原先可能存在的非均勻態(tài)；

冷卻過程——使粒子熱運(yùn)動(dòng)減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。第39頁/共163頁第40頁/共163頁模擬退火算法及模型

智能優(yōu)化計(jì)算數(shù)學(xué)表述

在溫度T，分子停留在狀態(tài)r滿足Boltzmann概率分布物理退火過程第41頁/共163頁模擬退火算法及模型

智能優(yōu)化計(jì)算數(shù)學(xué)表述在同一個(gè)溫度T，選定兩個(gè)能量E1<E2，有

物理退火過程<1>0

在同一個(gè)溫度，分子停留在能量小的狀態(tài)的概率比停留在能量大的狀態(tài)的概率要大。第42頁/共163頁智能優(yōu)化計(jì)算

若|D|為狀態(tài)空間D中狀態(tài)的個(gè)數(shù)，D0是具有最低能量的狀態(tài)集合：

1、當(dāng)溫度很高時(shí)，每個(gè)狀態(tài)概率基本相同，接近平均值1/|D|；

2、狀態(tài)空間存在超過兩個(gè)不同能量時(shí)，具有最低能量狀態(tài)的概率超出平均值1/|D|；

3、當(dāng)溫度趨于0時(shí)，分子停在最低能量狀態(tài)概率趨于1。模擬退火算法能量最低狀態(tài)非能量最低狀態(tài)數(shù)學(xué)表述第43頁/共163頁模擬退火算法及模型

智能優(yōu)化計(jì)算Metropolis準(zhǔn)則（1953）——以概率接受新狀態(tài)

物理退火過程

固體在恒定溫度下達(dá)到熱平衡的過程可以用MonteCarlo方法（計(jì)算機(jī)隨機(jī)模擬方法）加以模擬，雖然該方法簡單，但必須大量采樣才能得到比較精確的結(jié)果，計(jì)算量很大。第44頁/共163頁模擬退火算法及模型

智能優(yōu)化計(jì)算

否則，以概率p=exp[-(Ej-Ei)/kBT]

接受j為當(dāng)前狀態(tài)。物理退火過程Metropolis準(zhǔn)則（1953）——以概率接受新狀態(tài)

若在溫度T，當(dāng)前狀態(tài)i→新狀態(tài)j

若Ej<Ei，則接受j為當(dāng)前狀態(tài)；即：p大于[0,1)區(qū)間的隨機(jī)數(shù)，則仍接受狀態(tài)j

為當(dāng)前狀態(tài)；否則保留狀態(tài)i

為當(dāng)前狀態(tài)。第45頁/共163頁模擬退火算法及模型

智能優(yōu)化計(jì)算Metropolis準(zhǔn)則（1953）——以概率接受新狀態(tài)

p=exp[-(Ej-Ei)/kBT]

物理退火過程

在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新狀態(tài)。

在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)；第46頁/共163頁組合優(yōu)化與物理退火的相似性智能優(yōu)化計(jì)算相似性比較

組合優(yōu)化問題金屬物體解粒子狀態(tài)最優(yōu)解能量最低的狀態(tài)設(shè)定初溫熔解過程Metropolis抽樣過程等溫過程控制參數(shù)的下降冷卻目標(biāo)函數(shù)能量第47頁/共163頁SA算法描述第48頁/共163頁案例講解已知敵方100個(gè)目標(biāo)的經(jīng)度、緯度我方有一個(gè)基地，經(jīng)度和緯度為（70,40）。假設(shè)我方飛機(jī)的速度為1000公里/小時(shí)。我方派一架飛機(jī)從基地出發(fā)，偵察完敵方所有目標(biāo)，再返回原來的基地。在敵方每一目標(biāo)點(diǎn)的偵察時(shí)間不計(jì)，求該架飛機(jī)所花費(fèi)的時(shí)間（假設(shè)我方飛機(jī)巡航時(shí)間可以充分長）。第49頁/共163頁問題分析第50頁/共163頁算法描述(解空間與目標(biāo)函數(shù))第51頁/共163頁算法描述一次迭代由三步組成第52頁/共163頁算法描述第53頁/共163頁案例講解第54頁/共163頁模擬退火算法及模型

智能優(yōu)化計(jì)算基本步驟

給定初溫t=t0，隨機(jī)產(chǎn)生初始狀態(tài)s=s0，令k=0；

RepeatRepeat

產(chǎn)生新狀態(tài)sj=Genete(s)；

ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽樣穩(wěn)定準(zhǔn)則滿足；退溫tk+1=update(tk)并令k=k+1；

Until算法終止準(zhǔn)則滿足；輸出算法搜索結(jié)果。模擬退火算法的基本思想和步驟第55頁/共163頁模擬退火算法及模型

智能優(yōu)化計(jì)算影響優(yōu)化結(jié)果的主要因素

給定初溫t=t0，隨機(jī)產(chǎn)生初始狀態(tài)s=s0，令k=0；

RepeatRepeat

產(chǎn)生新狀態(tài)sj=Genete(s)；

ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽樣穩(wěn)定準(zhǔn)則滿足；退溫tk+1=update(tk)并令k=k+1；

Until算法終止準(zhǔn)則滿足；輸出算法搜索結(jié)果。模擬退火算法的基本思想和步驟三函數(shù)兩準(zhǔn)則初始溫度第56頁/共163頁3.3模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算華東理工大學(xué)自動(dòng)化系2007年原則

產(chǎn)生的候選解應(yīng)遍布全部解空間(保證全局最優(yōu)解)方法

在當(dāng)前狀態(tài)的鄰域結(jié)構(gòu)內(nèi)以一定概率方式（均勻分布、正態(tài)分布、指數(shù)分布等）產(chǎn)生狀態(tài)產(chǎn)生函數(shù)第57頁/共163頁模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算原則

(1)在固定溫度下，接受使目標(biāo)函數(shù)下降的候選解的概率要大于使目標(biāo)函數(shù)上升的候選解概率；

(2)隨溫度的下降，接受使目標(biāo)函數(shù)上升的解的概率要逐漸減??；

(3)當(dāng)溫度趨于零時(shí)，只能接受目標(biāo)函數(shù)下降的解。方法

具體形式對(duì)算法影響不大,一般采用min[1,exp(-?C/t)]狀態(tài)接受函數(shù)第58頁/共163頁模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算收斂性分析

通過理論分析可以得到初溫的解析式，但解決實(shí)際問題時(shí)難以得到精確的參數(shù)；初溫應(yīng)充分大；實(shí)驗(yàn)表明

初溫越大，獲得高質(zhì)量解的機(jī)率越大，但花費(fèi)較多的計(jì)算時(shí)間；初溫第59頁/共163頁模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算方法

（1）均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值得方差為初溫；（2）隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差，根據(jù)差值，利用一定的函數(shù)確定初溫；（3）利用經(jīng)驗(yàn)公式。初溫第60頁/共163頁模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算時(shí)齊算法的溫度下降函數(shù)

（1），α越接近1溫度下降越慢，且其大小可以不斷變化；（2），其中t0為起始溫度，K為算法溫度下降的總次數(shù)。溫度更新函數(shù)若固定每一溫度，算法均計(jì)算至平穩(wěn)分布，然后下降溫度，則稱為時(shí)齊算法；若無需各溫度下算法均達(dá)到平穩(wěn)分布，但溫度需按一定速率下降，則稱為非時(shí)齊算法。第61頁/共163頁模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算非時(shí)齊模擬退火算法

每個(gè)溫度下只產(chǎn)生一個(gè)或少量候選解時(shí)齊算法——常用的Metropolis抽樣穩(wěn)定準(zhǔn)則

（1）檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定；（2）連續(xù)若干步的目標(biāo)值變化較??；（3）按一定的步數(shù)抽樣。內(nèi)循環(huán)終止準(zhǔn)則第62頁/共163頁模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算常用方法

（1）設(shè)置終止溫度的閾值；（2）設(shè)置外循環(huán)迭代次數(shù)；（3）算法搜索到的最優(yōu)值連續(xù)若干步保持不變；（4）概率分析方法。外循環(huán)終止準(zhǔn)則第63頁/共163頁智能優(yōu)化計(jì)算模擬退火算法的優(yōu)點(diǎn)

質(zhì)量高；初值魯棒性強(qiáng)；簡單、通用、易實(shí)現(xiàn)。模擬退火算法的缺點(diǎn)

由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此優(yōu)化過程較長。模擬退火算法的優(yōu)缺點(diǎn)第64頁/共163頁模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算30城市TSP問題（d*=423.741byDBFogel）

TSPBenchmark問題

4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450第65頁/共163頁第66頁/共163頁智能優(yōu)化計(jì)算算法流程

第67頁/共163頁模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算初始溫度的計(jì)算

fori=1:100route=randperm(CityNum);fval0(i)=CalDist(dislist,route);endt0=-(max(fval0)-min(fval0))/log(0.9);

30城市TSP問題（d*=423.741byDBFogel）

第68頁/共163頁模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算狀態(tài)產(chǎn)生函數(shù)的設(shè)計(jì)（1）互換操作，隨機(jī)交換兩個(gè)城市的順序；（2）逆序操作，兩個(gè)隨機(jī)位置間的城市逆序；（3）插入操作，隨機(jī)選擇某點(diǎn)插入某隨機(jī)位置。30城市TSP問題（d*=423.741byDBFogel）

283591467283591467283591467281593467283419567235981467第69頁/共163頁模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算參數(shù)設(shè)定

截止溫度tf=0.01;

退溫系數(shù)alpha=0.90;

內(nèi)循環(huán)次數(shù)L=200*CityNum;30城市TSP問題（d*=423.741byDBFogel）

第70頁/共163頁模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過程

30城市TSP問題（d*=423.741byDBFogel）

第71頁/共163頁模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過程

30城市TSP問題（d*=423.741byDBFogel）

第72頁/共163頁模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過程

30城市TSP問題（d*=423.741byDBFogel）

第73頁/共163頁模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過程

30城市TSP問題（d*=423.741byDBFogel）

第74頁/共163頁模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過程

30城市TSP問題（d*=423.741byDBFogel）

第75頁/共163頁模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行結(jié)果

30城市TSP問題（d*=423.741byDBFogel）

第76頁/共163頁模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算改進(jìn)的可行方案

（1）設(shè)計(jì)合適的狀態(tài)產(chǎn)生函數(shù)；（2）設(shè)計(jì)高效的退火歷程；（3）避免狀態(tài)的迂回搜索；（4）采用并行搜索結(jié)構(gòu)；（5）避免陷入局部極小，改進(jìn)對(duì)溫度的控制方式；（6）選擇合適的初始狀態(tài)；（7）設(shè)計(jì)合適的算法終止準(zhǔn)則。

改進(jìn)內(nèi)容第77頁/共163頁

模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算改進(jìn)的方式

（1）增加升溫或重升溫過程，避免陷入局部極?。唬?）增加記憶功能（記憶“Bestsofar”狀態(tài)）；（3）增加補(bǔ)充搜索過程（以最優(yōu)結(jié)果為初始解）；（4）對(duì)每一當(dāng)前狀態(tài)，采用多次搜索策略，以概率接受區(qū)域內(nèi)的最優(yōu)狀態(tài)；（5）結(jié)合其它搜索機(jī)制的算法；（6）上述各方法的綜合。

改進(jìn)內(nèi)容第78頁/共163頁

模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算改進(jìn)的思路

（1）記錄“Bestsofar”狀態(tài)，并即時(shí)更新；（2）設(shè)置雙閾值，使得在盡量保持最優(yōu)性的前提下減少計(jì)算量，即在各溫度下當(dāng)前狀態(tài)連續(xù)m1步保持不變則認(rèn)為Metropolis抽樣穩(wěn)定，若連續(xù)m2次退溫過程中所得最優(yōu)解不變則認(rèn)為算法收斂。

一種改進(jìn)的模擬退火算法第79頁/共163頁

模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算改進(jìn)的退火過程

（1）給定初溫t0，隨機(jī)產(chǎn)生初始狀態(tài)s，令初始最優(yōu)解s*=s，當(dāng)前狀態(tài)為s(0)=s，i=p=0；（2）令t=ti，以t，s*和s(i)調(diào)用改進(jìn)的抽樣過程，返回其所得最優(yōu)解s*’和當(dāng)前狀態(tài)s’(k)，令當(dāng)前狀態(tài)s(i)=s’(k)；（3）判斷C(s*)<C(s*’)?若是，則令p=p+1；否則，令s*=s*’，p=0；（4）退溫ti+1=update(ti)，令i=i+1；（5）判斷p>m2?若是，則轉(zhuǎn)第(6)步；否則，返回第(2)步；（6）以最優(yōu)解s*作為最終解輸出，停止算法。

一種改進(jìn)的模擬退火算法第80頁/共163頁

模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算改進(jìn)的抽樣過程

（1）令k=0時(shí)的初始當(dāng)前狀態(tài)為s’(0)=s(i)，q=0；（2）由狀態(tài)s通過狀態(tài)產(chǎn)生函數(shù)產(chǎn)生新狀態(tài)s’，計(jì)算增量?C’=C(s’)-C(s)；（3）若?C’<0，則接受s’作為當(dāng)前解，并判斷C(s*’)>C(s’)?若是，則令s*’=s’，q=0；否則，令q=q+1。若?C’>0，則以概率exp(-?C’/t)接受s’作為下一當(dāng)前狀態(tài)；（4）令k=k+1，判斷q>m1?若是，則轉(zhuǎn)第(5)步；否則，返回第(2)步；（5）將當(dāng)前最優(yōu)解s*’和當(dāng)前狀態(tài)s’(k)返回改進(jìn)退火過程。

一種改進(jìn)的模擬退火算法第81頁/共163頁P(yáng)art3遺傳算法第82頁/共163頁遺傳算法(GeneticAlgorithm)進(jìn)化算法(EvolutionaryAlgorithm)第83頁/共163頁遺傳算法(GA)Darwin(1859):“物竟天擇，適者生存”JohnHolland(universityofMichigan,1975)

《AdaptationinNaturalandArtificialSystem》遺傳算法作為一種有效的工具，已廣泛地應(yīng)用于最優(yōu)化問題求解之中。遺傳算法是一種基于自然群體遺傳進(jìn)化機(jī)制的自適應(yīng)全局優(yōu)化概率搜索算法。它摒棄了傳統(tǒng)的搜索方式，模擬自然界生物進(jìn)化過程，采用人工的方式對(duì)目標(biāo)空間進(jìn)行隨機(jī)化搜索。第84頁/共163頁

遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個(gè)體，利用遺傳算子(選擇、交叉和變異)對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。遺傳算法的搜索機(jī)制第85頁/共163頁局部全局遺傳算法(GA)第86頁/共163頁Wehaveadream!!IamatthetopHeightis...Iamnotatthetop.Myhighisbetter!Iwillcontinue遺傳算法(GA)GA-----第0代第87頁/共163頁DeadoneNewone遺傳算法(GA)GA----第1代第88頁/共163頁Notatthetop,ComeUp!!!遺傳算法(GA)GA----第?代第89頁/共163頁IamtheBEST!!!遺傳算法(GA)GA----第N代第90頁/共163頁適者生存(SurvivaloftheFittest)GA主要采用的進(jìn)化規(guī)則是“適者生存”較好的解保留，較差的解淘汰遺傳算法(GA)第91頁/共163頁基本遺傳算法基本遺傳算法（SimpleGeneticAlgorithms,簡稱SGA）是一種統(tǒng)一的最基本的遺傳算法，它只使用選擇、交叉、變異這三種基本遺傳算子，其遺傳進(jìn)化操作過程簡單，容易理解，是其他一些遺傳算法的雛形和基礎(chǔ)，它不僅給各種遺傳算法提供了一個(gè)基本框架，同時(shí)也具有一定的應(yīng)用價(jià)值。第92頁/共163頁SGA實(shí)例1：函數(shù)最值SGA參數(shù):編碼方式:二進(jìn)制碼

e.g.000000;0110113;1111131種群規(guī)模:4隨機(jī)初始群體“轉(zhuǎn)盤賭”選擇一點(diǎn)雜交,二進(jìn)制變異求函數(shù)f(x)=x2的最大值，x為自然數(shù)且0≤x≤31.手工方式完成演示SGA過程第93頁/共163頁SGA實(shí)例1maxx2:選擇操作第94頁/共163頁SGA實(shí)例1maxx2:交叉操作第95頁/共163頁SGA實(shí)例1maxx2:變異操作第96頁/共163頁SGA實(shí)例2:連續(xù)函數(shù)最值求下列函數(shù)的最大值：第97頁/共163頁SGA實(shí)例2:編碼高精度

編碼[x,y]{0,1}L

必須可逆(一個(gè)表現(xiàn)型對(duì)應(yīng)一個(gè)基因型)

解碼算子：:{0,1}L

[x,y]

染色體長度L決定可行解的最大精度長染色體(慢進(jìn)化)

實(shí)數(shù)問題：變量z為實(shí)數(shù)，如何把{a1,…,aL}

{0,1}Lz∈[x,y]第98頁/共163頁SGA實(shí)例2:編碼設(shè)定求解精確到6位小數(shù)，因區(qū)間長度為2-(-1)=3,則需將區(qū)間分為3X106等份。因2097152＝221<3X106≤222＝4194304。故編碼的二進(jìn)制串長L=22。將一個(gè)二進(jìn)制串(b21b20…b0)轉(zhuǎn)化為10進(jìn)制數(shù)：e.g.<0000000000000000000000>-1;<1111111111111111111111>2<1110000000111111000101>1.6278881.627888=-1+3x(1110000000111111000101)2

/(222-1)=-1+3x3674053/(222-1)第99頁/共163頁SGA實(shí)例2:初始化種群、適應(yīng)函數(shù)隨機(jī)初始化種群適應(yīng)函數(shù)本實(shí)例目標(biāo)函數(shù)在定義域內(nèi)均大于0，且是求函數(shù)最大值，故直接引用目標(biāo)函數(shù)作為適應(yīng)函數(shù)：

f(s)=f(x)

其中二進(jìn)制串s對(duì)于變量x的值。

e.g.s1=<0000001110000000010000>x1=-0.958973

適應(yīng)值:f(s1)=f(x1)=1.078878

s2=<1110000000111111000101>x2=1.627888

適應(yīng)值:f(s2)=f(x2)=3.250650第100頁/共163頁SGA實(shí)例2:遺傳操作選擇操作(“輪盤賭”選擇)交叉操作(單點(diǎn)交叉)

交叉前(父):

s1=<00000|01110000000010000>s2=<11100|00000111111000101>

交叉后(子):

s’1=<00000|

00000111111000101>s’2=<11100|

01110000000010000>

適應(yīng)值:f(s’1)=f(-0.998113)=1.940865f(s’2)=f(1.666028)=3.459245

s’2的適應(yīng)值比其雙親個(gè)體的適應(yīng)值高。第101頁/共163頁SGA實(shí)例2:遺傳操作變異操作

變異前(父):

s2=<1110000000111111000101>

變異后(子):

s’2=<1110100000111111000101>

適應(yīng)值

f(s’2)=f(1.721638)=0.917743

比f(s2)小

變異前(父):

s2=<1110000000111111000101>

變異后(子):

s”2=<1110000001111111000101>

適應(yīng)值

f(s”2)=f(1.630818)=3.343555比f(s2)大變異操作有”擾動(dòng)”作用，同時(shí)具有增加種群多樣性的效果。第102頁/共163頁SGA實(shí)例2:模擬結(jié)果遺傳算法的參數(shù):

種群規(guī)模:50

染色體長度:L=22

最大進(jìn)化代數(shù):150

交叉概率:Pc=0.25

變異概率:Pm=0.01

第103頁/共163頁SGA實(shí)例2:模擬結(jié)果(最佳個(gè)體進(jìn)化情況)世代數(shù)染色體編碼變量x適應(yīng)值141117344054718915010001110000101100011110000011011000101001111011010101110011100111111101010111111010011111100001101111011001111110100100010001100111110001101101000110011110100110110001011001111110100111111001100111111010011111100110011111.8316241.8424161.8548601.8475361.8532901.8484431.8486991.8508971.8505491.8505493.5348063.7903623.8332863.8420043.8434023.8462323.8471553.8501623.8502743.850274第104頁/共163頁

遺傳算法簡介

智能優(yōu)化計(jì)算遺傳算法的基本思路

遺傳算法的思路與特點(diǎn)

第105頁/共163頁

遺傳算法簡介

智能優(yōu)化計(jì)算自組織、自適應(yīng)和自學(xué)習(xí)性在編碼方案、適應(yīng)度函數(shù)及遺傳算子確定后，算法將利用進(jìn)化過程中獲得的信息自行組織搜索。

遺傳算法的思路與特點(diǎn)

概率轉(zhuǎn)換規(guī)則強(qiáng)調(diào)概率轉(zhuǎn)換規(guī)則，而不是確定的轉(zhuǎn)換規(guī)則不需求導(dǎo)只需目標(biāo)函數(shù)和適應(yīng)度函數(shù)本質(zhì)并行性內(nèi)在并行性與內(nèi)含并行性第106頁/共163頁生物進(jìn)化與遺傳算法對(duì)應(yīng)關(guān)系生物進(jìn)化遺傳算法適者生存適應(yīng)函數(shù)值最大的解被保留的概率最大個(gè)體問題的一個(gè)解染色體解的編碼基因編碼的元素群體被選定的一組解種群根據(jù)適應(yīng)函數(shù)選擇的一組解交叉以一定的方式由雙親產(chǎn)生后代的過程變異編碼的某些分量發(fā)生變化的過程生存能力適應(yīng)函數(shù)第107頁/共163頁遺傳算法的基本操作選擇(selection):

根據(jù)各個(gè)個(gè)體的適應(yīng)值，按照一定的規(guī)則或方法，從第t代群體P(t)中選擇出一些優(yōu)良的個(gè)體遺傳到下一代群體P(t+1)中。交叉(crossover):

將群體P(t)內(nèi)的各個(gè)個(gè)體隨機(jī)搭配成對(duì)，對(duì)每一個(gè)個(gè)體，以某個(gè)概率Pc

(稱為交叉概率，crossvoerrate)交換它們之間的部分染色體。變異(mutation):

對(duì)群體P(t)中的每一個(gè)個(gè)體，以某一概率Pm(稱為變異概率，mutationrate)改變某一個(gè)或一些基因座上基因值為其它的等位基因。第108頁/共163頁如何設(shè)計(jì)遺傳算法如何進(jìn)行編碼？如何產(chǎn)生初始種群？如何定義適應(yīng)函數(shù)？如何進(jìn)行遺傳操作(復(fù)制、交叉、變異)？如何產(chǎn)生下一代種群？如何定義停止準(zhǔn)則？第109頁/共163頁編碼(Coding)表現(xiàn)型空間編碼(Coding)解碼(Decoding)基因型空間={0,1}L0111010010100010011001001010010001第110頁/共163頁選擇(Selection)選擇(復(fù)制)操作把當(dāng)前種群的染色體按與適應(yīng)值成正比例的概率復(fù)制到新的種群中

主要思想:適應(yīng)值較高的染色體體有較大的選擇機(jī)會(huì)實(shí)現(xiàn)1：“輪盤賭”選擇(Roulettewheelselection)將種群中所有染色體編號(hào)，并根據(jù)各自適應(yīng)值計(jì)算按比例分配的概率依次計(jì)算染色體累加概率產(chǎn)生(0,1)之間隨機(jī)數(shù)，若其最多能大于序列中第m個(gè)值，則第m個(gè)染色體被隨機(jī)選擇第111頁/共163頁選擇(Selection)設(shè)種群的規(guī)模為Nxi是i為種群中第i個(gè)染色體AC1/6=17%3/6=50%B2/6=33%fitness(A)=3fitness(B)=1fitness(C)=2染色體xi被選概率第112頁/共163頁選擇(Selection)染色體的適應(yīng)值和所占的比例輪盤賭選擇第113頁/共163頁選擇(Selection)隨機(jī)數(shù)23491338627所選號(hào)碼262514所選染色體110000001111000011000111010010染色體編號(hào)123456染色體011101100000100100100110000011適應(yīng)度81525128被選概率0.160.30.040.10.240.16累加概率8

23253042

50染色體被選的概率被選的染色體第114頁/共163頁選擇(Selection)輪盤上的片分配給群體的染色體，使得每一個(gè)片的大小與對(duì)于染色體的適應(yīng)值成比例從群體中選擇一個(gè)染色體可視為旋轉(zhuǎn)一個(gè)輪盤，當(dāng)輪盤停止時(shí)，指針?biāo)傅钠瑢?duì)于的染色體就時(shí)要選的染色體。模擬“輪盤賭”算法：r=random(0,1)，s=0，i=0；如果s≥r，則轉(zhuǎn)(4)；s=s+p(xi)，i=i+1,轉(zhuǎn)(2)xi即為被選中的染色體，輸出I結(jié)束第115頁/共163頁選擇(Selection)其他選擇法：隨機(jī)遍歷抽樣(Stochasticuniversalsampling)局部選擇(Localselection)截?cái)噙x擇(Truncationselection)競標(biāo)賽選擇(Tournamentselection)特點(diǎn)：選擇操作得到的新的群體稱為交配池，交配池是當(dāng)前代和下一代之間的中間群體，其規(guī)模為初始群體規(guī)模。選擇操作的作用效果是提高了群體的平均適應(yīng)值(低適應(yīng)值個(gè)體趨于淘汰，高適應(yīng)值個(gè)體趨于選擇)，但這也損失了群體的多樣性。選擇操作沒有產(chǎn)生新的個(gè)體，群體中最好個(gè)體的適應(yīng)值不會(huì)改變。第116頁/共163頁交叉(crossover,Recombination)遺傳交叉(雜交、交配、有性重組)操作發(fā)生在兩個(gè)染色體之間，由兩個(gè)被稱之為雙親的父代染色體，經(jīng)雜交以后，產(chǎn)生兩個(gè)具有雙親的部分基因的新的染色體，從而檢測搜索空間中新的點(diǎn)。選擇(復(fù)制)操作每次作用在一個(gè)染色體上，而交叉操作每次作用在從交配池中隨機(jī)選取的兩個(gè)個(gè)體上(交叉概率Pc)。交叉產(chǎn)生兩個(gè)子染色體，他們與其父代不同，且彼此不同,每個(gè)子染色體都帶有雙親染色體的遺傳基因。第117頁/共163頁單點(diǎn)交叉(1-pointcrossover)在雙親的父代染色體中隨機(jī)產(chǎn)生一個(gè)交叉點(diǎn)位置在交叉點(diǎn)位置分離雙親染色體互換交叉點(diǎn)位置右邊的基因碼產(chǎn)生兩個(gè)子代染色體交叉概率Pc

一般范圍為(60%,90%)，平均約80%11111111父代1111000000000000子代111100000000000011111111交叉點(diǎn)位置第118頁/共163頁交叉(crossover,Recombination)單點(diǎn)交叉操作可以產(chǎn)生與父代染色體完全不同的子代染色體；它不會(huì)改變父代染色體中相同的基因。但當(dāng)雙親染色體相同時(shí)，交叉操作是不起作用的。假如交叉概率Pc

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

在GA執(zhí)行的開始階段，染色體中一個(gè)特定位上的值1可能與好的性能緊密聯(lián)系，即搜索空間中某些初始染色體在那個(gè)位上的值1可能一致產(chǎn)生高的適應(yīng)值。因?yàn)樵礁叩倪m應(yīng)值與染色體中那個(gè)位上的值1相聯(lián)系，選擇操作就越會(huì)使群體的遺傳多樣性損失。等到達(dá)一定程度時(shí)，值0會(huì)從整個(gè)群體中那個(gè)位上消失，然而全局最優(yōu)解可能在染色體中那個(gè)位上為0。如果搜索范圍縮小到實(shí)際包含全局最優(yōu)解的那部分搜索空間，在那個(gè)位上的值0就可能正好是到達(dá)全局最優(yōu)解所需要的。第121頁/共163頁適應(yīng)函數(shù)(FitnessFunction)GA在搜索中不依靠外部信息，僅以適應(yīng)函數(shù)為依據(jù)，利用群體中每個(gè)染色體(個(gè)體)的適應(yīng)值來進(jìn)行搜索。以染色體適應(yīng)值的大小來確定該染色體被遺傳到下一代群體中的概率。染色體適應(yīng)值越大，該染色體被遺傳到下一代的概率也越大；反之，染色體的適應(yīng)值越小，該染色體被遺傳到下一代的概率也越小。因此適應(yīng)函數(shù)的選取至關(guān)重要，直接影響到GA的收斂速度以及能否找到最優(yōu)解。群體中的每個(gè)染色體都需要計(jì)算適應(yīng)值適應(yīng)函數(shù)一般由目標(biāo)函數(shù)變換而成第122頁/共163頁適應(yīng)函數(shù)(FitnessFunction)適應(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)缺點(diǎn):(1)可能不滿足輪盤賭選擇中概率非負(fù)的要求

(2)某些代求解的函數(shù)值分布上相差很大，由此得到的評(píng)價(jià)適應(yīng)值可能不利于體現(xiàn)群體的評(píng)價(jià)性能，影響算法的性能。第123頁/共163頁適應(yīng)函數(shù)(FitnessFunction)界限構(gòu)造法

目標(biāo)函數(shù)為最大化問題其中Cmin為f(x)的最小估計(jì)值

目標(biāo)函數(shù)為最小化問題其中Cmaxn為f(x)的最大估計(jì)值第124頁/共163頁停止準(zhǔn)則(TerminationCriteria)種群中個(gè)體的最大適應(yīng)值超過預(yù)設(shè)定值種群中個(gè)體的平均適應(yīng)值超過預(yù)設(shè)定值種群中個(gè)體的進(jìn)化代數(shù)超過預(yù)設(shè)定值第125頁/共163頁基本步驟(StepbyStep)(1)隨機(jī)產(chǎn)生初始種群;(2)計(jì)算種群體中每個(gè)個(gè)體的適應(yīng)度值,判斷是否滿足停止條件，若不滿足，則轉(zhuǎn)第(3)步,否則轉(zhuǎn)第(6)步;(3)按由個(gè)體適應(yīng)值所決定的某個(gè)規(guī)則選擇進(jìn)入下一代的個(gè)體;(4)按交叉概率Pc進(jìn)行交叉操作,生產(chǎn)新的個(gè)體;(5)按變異概率Pm進(jìn)行變異操作,生產(chǎn)新的個(gè)體;(6)輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。第126頁/共163頁流程圖(FlowChart)第127頁/共163頁SGA偽碼描述ProcedureGeneticAlgorithm

begint=0;初始化P(t);計(jì)算P(t)的適應(yīng)值;while(不滿足停止準(zhǔn)則)dobegint=t+1;

從P(t-1)中選擇P(t);%selection

重組P(t);%crossoverandmutation

計(jì)算P(t)的適應(yīng)值;end

end第128頁/共163頁無約束最優(yōu)化問題GA編碼：X=(x1,x2,…,xn)的各個(gè)變量可以按二進(jìn)制編碼方法分別編碼。對(duì)于變量xi的上、下限約束li≤xi≤

ui(i=1,2,…,n)，依據(jù)解的精度要求(有效位數(shù))求得各個(gè)變量X=(x1,x2,…,xn)的二進(jìn)制碼位數(shù)(m1,m2,…,mn)(確定方法類似于SGA實(shí)例2)，因此將n個(gè)二進(jìn)制位串順序連接起來，構(gòu)成一個(gè)個(gè)體的染色體編碼，編碼的總位數(shù)m＝m1+m2+…+mn。無約束最優(yōu)化問題:第129頁/共163頁無約束最優(yōu)化問題GA解碼：解碼時(shí)仍按各個(gè)變量的編碼順序分別實(shí)現(xiàn)常規(guī)的二進(jìn)制編碼解碼方法。二進(jìn)制遺傳編碼示意圖如下：第130頁/共163頁約束最優(yōu)化問題常規(guī)解法：(1)把約束問題轉(zhuǎn)化為無約束問題，在用無約束問題方法求解，如罰函數(shù)法(2)改進(jìn)無約束問題的方法，再用于約束問題，如梯度投影法、廣義簡約梯度法約束最優(yōu)化問題:第131頁/共163頁約束最優(yōu)化問題遺傳算法求解關(guān)鍵:約束條件的處理等式約束可以包含到適應(yīng)函數(shù)，僅考慮不等式約束。假設(shè)按無約束問題那樣求解，在搜索過程中計(jì)算目標(biāo)函數(shù)值，并檢查是否有約束違反。如果沒有違反，則表明是可行解，就根據(jù)目標(biāo)函數(shù)指定一適應(yīng)值；否則，就是不可行解，因而沒有適應(yīng)值(適應(yīng)值為0)。這樣的處理實(shí)際不可行，因?yàn)檎业揭粋€(gè)可行解幾乎與找到最優(yōu)解一樣困難。第132頁/共163頁一般解法：通過引入罰函數(shù)，從不可行解中得到一些信息。將罰函數(shù)包含到適應(yīng)函數(shù)中。關(guān)鍵是如何設(shè)計(jì)罰函數(shù)；不同問題需要設(shè)計(jì)不同的罰函數(shù)；對(duì)一般的約束處理，通常很困難。約束最優(yōu)化問題第133頁/共163頁組合最優(yōu)化問題典型問題：旅行商問題(TravelingSalesmanProblem)作業(yè)調(diào)度問題(JobShopSchedulingProblem)背包問題(KnapsackProblem)圖著色問題…

…

…很多組合最優(yōu)化問題是NP難問題或NP完全問題第134頁/共163頁旅行商問題(TSP)TSP，也稱貨郎擔(dān)問題，是一個(gè)NP完全問題。TSP描述：圖論:設(shè)圖G=(V,E),其中V是頂點(diǎn)集，E是邊集。設(shè)C=(cij)是與E相聯(lián)系的距離矩陣。尋找一條通過所有頂點(diǎn)且每個(gè)頂點(diǎn)只通過一次的最短距離回路(Hamilton回路)。實(shí)際應(yīng)用中，C也可解釋為費(fèi)用或旅行時(shí)間矩陣。實(shí)際:一位推銷員從自己所在城市出發(fā)，必須遍訪所有城市之后又回到原來的城市，求使其旅行費(fèi)用最少的路徑。第135頁/共163頁巡回旅行商問題(TSP)中國貨郎擔(dān)問題:城市數(shù):40城市編號(hào)1,2,…,40尋找一條最短路徑第136頁/共163頁TSP復(fù)雜性搜索空間龐大TSP涉及求多個(gè)變量的函數(shù)的最小值，求解很困難。其可能的路徑條數(shù)隨著城市數(shù)目n成指數(shù)增長，如，5個(gè)城市對(duì)應(yīng)12條路徑；10個(gè)城市對(duì)應(yīng)181440條路徑；100個(gè)城市對(duì)應(yīng)4.6663X10155條路徑。如此龐大的搜索空間，常規(guī)解法和計(jì)算工具都遇到計(jì)算上的困難。只能尋找近似解法，如神經(jīng)網(wǎng)絡(luò)方法、模擬退火法、遺傳算法等。第137頁/共163頁TSP編碼:路徑表示染色體表示成所有城市的一個(gè)排列，若有n個(gè)城市，一條可能路徑編碼為長度為n的整數(shù)向量(i1,i2,…,in),其中ik表示第ik個(gè)城市。例如:路徑編碼向量(517894623)直接表示一條旅行路程(5->1->7->8->9->4->6->2->3)。此向量是1到n的一個(gè)排列，即從1到n的每個(gè)整數(shù)在這個(gè)向量中正好出現(xiàn)一次,不能有重復(fù)。這樣，基本遺傳算法的基因操作生成的個(gè)體不能滿足這一約束條件，需尋求其他遺傳操作。第138頁/共163頁TSP交叉需其他方式的交叉(重組)操作,如部分匹配交叉(PartiallyMatchedCrossover,PMX)、順序交叉(OrderedCrossover,OX)、循環(huán)交叉(CycleCrossover,CX)、邊重組(EdgeRecombination)。12345543211232154345一般的交叉操作會(huì)產(chǎn)生不合適的解，如第139頁/共163頁TSP交叉1:部分匹配交叉(PMX)雙親P1,P2隨機(jī)選取兩個(gè)交叉點(diǎn)，得到一個(gè)匹配段,根據(jù)交叉點(diǎn)中間段給出映射關(guān)系。123456789937826514xxx4567xxxxx8265xxP1P2映射關(guān)系：48、52、75c1c2

交換兩個(gè)交叉點(diǎn)之間的編碼,(X表示未定碼)第140頁/共163頁TSP交叉1:部分匹配交叉(PMX)子個(gè)體C1，C2分別從其父個(gè)體中繼承未映射城市碼12345678993782651493x45671x1x38265x9P1P2c1c2映射關(guān)系：48、52、75932456718173826549c1c2

再根據(jù)映射關(guān)系，對(duì)以上未定碼，使用最初雙親碼，得到子個(gè)體的對(duì)應(yīng)碼。映射關(guān)系存在傳遞關(guān)系，則選擇未定碼交換。第141頁/共163頁TSP交叉2:順序交叉(OX)雙親P1,P2隨機(jī)選取兩個(gè)交叉點(diǎn)123456789937826514P1P2xxx4567xxxxx8265xxc1c2

兩個(gè)交叉點(diǎn)間的中間段保存不變

子個(gè)體C1的未定碼的確定需要父個(gè)體P2的未選定城市碼，子個(gè)體C2的未定碼的確定需要父個(gè)體P1的未選定城市碼。第142頁/共163頁TSP交叉2:順序交叉(OX)記取父個(gè)體P2從第二個(gè)交叉點(diǎn)開始城市碼的排列順序，當(dāng)?shù)竭_(dá)表尾時(shí)，返回表頭繼續(xù)記錄，直到第二個(gè)交叉點(diǎn)。937826514P2xxx4567xxc1382456719c1347826591c2

得到父個(gè)體P2的排列順序1-4-9-3-7-8-2-6-5,并將C1已有城市碼4,5,6,7從中去掉，得到排列順序1-9-3-8-2，再將此順序復(fù)制到C1，復(fù)制點(diǎn)也是從第二個(gè)交叉點(diǎn)開始，得到C1。同理的C2，第143頁/共163頁TSP交叉3:循環(huán)交叉(CX)CX操作中子個(gè)體中的城市碼順序根據(jù)任一父個(gè)體產(chǎn)生確定循環(huán)編碼

復(fù)制循環(huán)編碼到子個(gè)體第144頁/共163頁TSP變異InsertMutation隨機(jī)選取個(gè)體中兩個(gè)編碼，然后把第二個(gè)編碼放在第一個(gè)編碼之后，其他編碼順次調(diào)節(jié)位置。

Swapmutation隨機(jī)選取個(gè)體中兩個(gè)編碼，然后交換它們的位置。第145頁/共163頁TSP變異Inversionmutation隨機(jī)選取個(gè)體中一段編碼，然后顛倒這段編碼的順序。

Scramblemutation隨機(jī)選取個(gè)體上一段編碼,然后打亂這段編碼的順序。選取的編碼不一定是鄰接編碼第146頁/共163頁TSP的GA過程從N個(gè)隨機(jī)起點(diǎn)開始產(chǎn)生N條路徑，N為種群的規(guī)模;利用最優(yōu)方法搜索每條路徑的局部最優(yōu)解;選擇交叉對(duì)使在平均性能之上的個(gè)體得到更多的子代;交叉和變異;搜索每條路徑得到其極小解，如果不