MATLAB模擬退火算法和遺傳算法

1、10.1 模擬退火算法 模擬退火算法（Simulated Annealing Algorithm，簡記為SAA）是受金屬熱加工技術(shù)的啟迪而發(fā)展起來的一種隨機搜索算法。模擬退火算法及模型 算法的提出 模擬退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。算法的目的 解決NP復(fù)雜性問題； 克服優(yōu)化過程陷入局部極小； 克服初值依賴性。 物理退火過程模擬退火算法及模型 物理退火過程 什么是退火： 退火是指將固體加熱到足夠高的溫度，使分子呈隨機排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，達到某種穩(wěn)定狀態(tài)。 物理退火過程模擬退火算

2、法及模型 物理退火過程 加溫過程增強粒子的熱運動，消除系統(tǒng)原先可能存在的非均勻態(tài)； 等溫過程對于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進行，當(dāng)自由能達到最小時，系統(tǒng)達到平衡態(tài)； 冷卻過程使粒子熱運動減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。物理退火過程10.1.1 模擬退火算法的基本原理 數(shù)學(xué)表述 在溫度T，分子停留在狀態(tài)r滿足Boltzmann概率分布物理退火過程10.1.1 模擬退火算法的基本原理 數(shù)學(xué)表述 在同一個溫度T，選定兩個能量E1E2，有在同一個溫度，分子停留在能量小的狀態(tài)的概率比停留在能量大的狀態(tài)的概率要大。10.1.1 模擬退

3、火算法的基本原理 數(shù)學(xué)表述 若|D|為狀態(tài)空間D中狀態(tài)的個數(shù)，D0是具有最低能量的狀態(tài)集合： 當(dāng)溫度很高時，每個狀態(tài)概率基本相同，接近平均值1/|D|； 狀態(tài)空間存在超過兩個不同能量時，具有最低能量狀態(tài)的概率超出平均值1/|D| ； 當(dāng)溫度趨于0時，分子停留在最低能量狀態(tài)的概率趨于1。10.1.1 模擬退火算法的基本原理 Metropolis準(zhǔn)則（1953）以概率接受新狀態(tài) 若在溫度T，當(dāng)前狀態(tài)i 新狀態(tài)j 若Ej=randrom0,1 s=sj; Until 抽樣穩(wěn)定準(zhǔn)則滿足； 退溫tk+1=update(tk)并令k=k+1； Until 算法終止準(zhǔn)則滿足； 輸出算法搜索結(jié)果。10.1.3

4、 模擬退火算法的計算步驟及收斂性 定義 10.1.3 模擬退火算法的計算步驟及收斂性 定義 一步轉(zhuǎn)移概率： n步轉(zhuǎn)移概率： 若解空間有限，稱馬爾可夫鏈為有限狀態(tài)； 若 ，稱馬爾可夫鏈為時齊的。馬爾科夫鏈10.1.3 模擬退火算法的計算步驟及收斂性 模擬退火算法對應(yīng)了一個馬爾可夫鏈 模擬退火算法：新狀態(tài)接受概率僅依賴于新狀態(tài)和當(dāng)前狀態(tài)，并由溫度加以控制。 若固定每一溫度，算法均計算馬氏鏈的變化直至平穩(wěn)分布，然后下降溫度，則稱為時齊算法； 若無需各溫度下算法均達到平穩(wěn)分布，但溫度需按一定速率下降，則稱為非時齊算法。分析收斂性10.1.3 模擬退火算法的計算步驟及收斂性 模擬退火過程是從一個狀態(tài)（解

5、）到另一個狀態(tài)（解）不斷地隨機游動，我們稱這種游動為變換。 從鄰域Si中選出某個解j的方法稱為解的產(chǎn)生機制.從當(dāng)前解變換到下一個解的過程稱為轉(zhuǎn)移，它由產(chǎn)生機制的應(yīng)用和接受準(zhǔn)則的應(yīng)用兩部分組成。 10.1.3 模擬退火算法的計算步驟及收斂性 10.1.3 模擬退火算法的計算步驟及收斂性 10.1.4 模擬退火算法實現(xiàn)的技術(shù)問題冷卻進度表控制參數(shù)值Tf的選取馬爾科夫鏈長度Lk的選取控制參數(shù)衰減函數(shù)的選取10.1.4 模擬退火算法實現(xiàn)的技術(shù)問題原則 (1)在固定溫度下，接受使目標(biāo)函數(shù)下降的候選解的概率要大于使目標(biāo)函數(shù)上升的候選解概率； (2)隨溫度的下降，接受使目標(biāo)函數(shù)上升的解的概率要逐漸減小； (

6、3)當(dāng)溫度趨于零時，只能接受目標(biāo)函數(shù)下降的解。方法 具體形式對算法影響不大 一般采用min1,exp(-C/t)10.1.4 模擬退火算法實現(xiàn)的技術(shù)問題方法 （1）均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值得方差為初溫； （2）隨機產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差，根據(jù)差值，利用一定的函數(shù)確定初溫； （3）利用經(jīng)驗公式。 初溫10.1.4 模擬退火算法實現(xiàn)的技術(shù)問題時齊算法的溫度下降函數(shù) （1） ，越接近1溫度下降越慢，且其大小可以不斷變化； （2） ，其中t0為起始溫度，K為算法溫度下降的總次數(shù)。溫度更新函數(shù)10.1.4 模擬退火算法實現(xiàn)的技術(shù)問題非時齊模擬退火算法 每個溫度下只產(chǎn)生一個或少

7、量候選解時齊算法常用的Metropolis抽樣穩(wěn)定準(zhǔn)則 （1）檢驗?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定； （2）連續(xù)若干步的目標(biāo)值變化較??； （3）按一定的步數(shù)抽樣。 內(nèi)循環(huán)終止準(zhǔn)則10.1.4 模擬退火算法實現(xiàn)的技術(shù)問題模擬退火算法的優(yōu)點 質(zhì)量高； 初值魯棒性強； 簡單、通用、易實現(xiàn)。模擬退火算法的缺點 由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此優(yōu)化過程較長。 模擬退火算法的優(yōu)缺點模擬退火算法的實現(xiàn)與應(yīng)用算法流程 30城市TSP問題模擬退火算法的實現(xiàn)與應(yīng)用運行過程 30城市TSP問題模擬退火算法的實現(xiàn)與應(yīng)用運行過程 30城市TSP問題模擬退火算法的實現(xiàn)與應(yīng)用運

8、行過程 30城市TSP問題10.2 遺傳算法 遺傳算法（Genetic Algorithm，簡稱GA）是一種以自然選擇和遺傳理論為基礎(chǔ)，將生物進化過程中適者生存規(guī)則與種群內(nèi)部染色體的隨機交換機制相結(jié)合的隨機化搜索算法。10.2 遺傳算法 達爾文的自然選擇說遺傳（heredity）：子代和父代具有相 同或相似的性狀，保證物種的穩(wěn)定性；變異（variation）：子代與父代，子代不同個體之間總有差異，是生命多樣性的根源；生存斗爭和適者生存：具有適應(yīng)性變異的個體被保留，不具適應(yīng)性變異的個體被淘汰。 自然選擇過程是長期的、緩慢的、連續(xù)的過程。 生物進化理論和遺傳學(xué)的基本知識 10.2 遺傳算法 遺傳學(xué)

9、基本概念與術(shù)語基因座（locus）：遺傳基因在染色體中所占據(jù)的位置，同一基因座可能有的全部基因稱為等位基因（allele）；個體（individual）：指染色體帶有特征的實體；種群（population）：個體的集合，該集合內(nèi)個體數(shù)稱為種群的大小； 遺傳算法的基本原理和特點 10.2 遺傳算法 遺傳學(xué)基本概念與術(shù)語進化（evolution）：生物在其延續(xù)生存的過程中，逐漸適應(yīng)其生存環(huán)境，使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱為進化；適應(yīng)度（fitness）：度量某個物種對于生存環(huán)境的適應(yīng)程度。對生存環(huán)境適應(yīng)程度較高的物種將獲得更多的繁殖機會，而對生存環(huán)境適應(yīng)程度較低的物種，其繁殖機會就會相對

10、較少，甚至逐漸滅絕; 遺傳算法的基本原理和特點10.2 遺傳算法 遺傳學(xué)基本概念與術(shù)語選擇（selection）：指決定以一定的概率從種群中選擇若干個體的操作 ；復(fù)制（reproduction）：細胞在分裂時，遺傳物質(zhì)DNA通過復(fù)制而轉(zhuǎn)移到新產(chǎn)生的細胞中，新的細胞就繼承了舊細胞的基因;交叉（crossover）：在兩個染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個新的染色體。又稱基因重組，俗稱“雜交”; 遺傳算法的基本原理和特點10.2 遺傳算法 遺傳學(xué)基本概念與術(shù)語變異（mutation）：在細胞進行復(fù)制時可能以很小的概率產(chǎn)生某些復(fù)制差錯，從而使DNA發(fā)生某種變異，產(chǎn)生出

11、新的染色體，這些新的染色體表現(xiàn)出新的性狀;編碼（coding）：表現(xiàn)型到基因型的映射；解碼（decoding）：從基因型到表現(xiàn)型的映射。 遺傳算法的基本原理和特點10.2 遺傳算法 遺傳算法的基本思路 遺傳算法實現(xiàn)的技術(shù)問題10.2 遺傳算法 遺傳算法實現(xiàn)的技術(shù)問題 遺傳算法的工作步驟10.2 遺傳算法 遺傳算法實現(xiàn)的技術(shù)問題10.2 遺傳算法 問題的提出 一元函數(shù)求最大值： 簡單函數(shù)優(yōu)化的實例 10.2 遺傳算法 編碼 表現(xiàn)型：x 基因型：二進制編碼（串長取決于求解精度） 串長與精度之間的關(guān)系： 若要求求解精度到6位小數(shù)，區(qū)間長度為2-(-1)3，即需將區(qū)間分為3/0.000001=3106

12、等份。 所以編碼的二進制串長應(yīng)為22位。 簡單函數(shù)優(yōu)化的實例 10.2 遺傳算法 產(chǎn)生初始種群 產(chǎn)生的方式：隨機 產(chǎn)生的結(jié)果：長度為22的二進制串 產(chǎn)生的數(shù)量：種群的大?。ㄒ?guī)模），如30，50， 1111010011100001011000 1100110011101010101110 1010100011110010000100 1011110010011100111001 0001100101001100000011 0000011010010000000000 簡單函數(shù)優(yōu)化的實例 10.2 遺傳算法 計算適應(yīng)度 不同的問題有不同的適應(yīng)度計算方法 本例：直接用目標(biāo)函數(shù)作為適應(yīng)度函數(shù) 將某個

13、體轉(zhuǎn)化為-1,2區(qū)間的實數(shù)： s= x=0.637197 計算x的函數(shù)值（適應(yīng)度）： f(x)=xsin(10 x)+2.0=2.586345 簡單函數(shù)優(yōu)化的實例 10.2 遺傳算法 計算適應(yīng)度 二進制與十進制之間的轉(zhuǎn)換： 第一步，將一個二進制串（b21b20b0）轉(zhuǎn)化為10進制數(shù)： 第二步，x對應(yīng)的區(qū)間-1,2內(nèi)的實數(shù)： 簡單函數(shù)優(yōu)化的實例 (0000000000000000000000)-1(1111111111111111111111)210.2 遺傳算法 遺傳操作 選擇：輪盤賭選擇法； 交叉：單點交叉； 變異：小概率變異 簡單函數(shù)優(yōu)化的實例 10.2 遺傳算法 模擬結(jié)果 設(shè)置的參數(shù)：

14、種群大小50；交叉概率0.75；變異概率0.05；最大代數(shù)200。 得到的最佳個體： smax=; xmax=1.8506; f(xmax)=3.8503; 簡單函數(shù)優(yōu)化的實例 10.2 遺傳算法 世代數(shù)自變量適應(yīng)度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.8503模擬結(jié)果 進化的過程： 簡單函數(shù)優(yōu)化的實例 10.2 遺傳算法 編碼原則完備性（completeness）：問題空間的所有解都能表示為所設(shè)計的基因型；健全性（s

15、oundness）：任何一個基因型都對應(yīng)于一個可能解；非冗余性（non-redundancy）：問題空間和表達空間一一對應(yīng)。 10.2 遺傳算法 適應(yīng)度函數(shù)的重要性 適應(yīng)度函數(shù)的選取直接影響遺傳算法的收斂速度以及能否找到最優(yōu)解。 一般而言，適應(yīng)度函數(shù)是由目標(biāo)函數(shù)變換而成的，對目標(biāo)函數(shù)值域的某種映射變換稱為適應(yīng)度的尺度變換（fitness scaling）。 適應(yīng)度函數(shù)及其尺度變換 10.2 遺傳算法 幾種常見的適應(yīng)度函數(shù)若目標(biāo)函數(shù)為最大化問題： 若目標(biāo)函數(shù)為最小化問題： 適應(yīng)度函數(shù)及其尺度變換 10.2 遺傳算法 適應(yīng)度函數(shù)的線性變換法 f=*f+ 系數(shù)的確定滿足以下條件： 縮放前后的平均適應(yīng)

16、度相等. favg= favg 縮放后的最大適應(yīng)度要等于原平均適應(yīng)度 的指定倍數(shù) fmax= cmult favg cmult =1.02.0 適應(yīng)度函數(shù)及其尺度變換 10.2 遺傳算法 適應(yīng)度函數(shù)的作用 適應(yīng)度函數(shù)設(shè)計不當(dāng)有可能出現(xiàn)欺騙問題： （1）進化初期，個別超常個體控制選擇過程； （2）進化末期，個體差異太小導(dǎo)致陷入局部極值。 適應(yīng)度函數(shù)及其尺度變換 10.2 遺傳算法 適應(yīng)度函數(shù)的設(shè)計單值、連續(xù)、非負、最大化合理、一致性計算量小通用性強 適應(yīng)度函數(shù)及其尺度變換 10.2 遺傳算法 個體選擇概率的常用分配方法按比例的適應(yīng)度分配（proportional fitness assignme

17、nt） 某個體i，其適應(yīng)度為fi，則其被選取的概率Pi為： 遺傳操作選擇 個體ff2P12.56.250.1821.01.000.0333.09.000.2641.21.440.0452.14.410.1360.80.640.0272.56.250.1881.31.690.0590.90.810.02101.83.240.0910.2 遺傳算法 個體1234567891011適應(yīng)度2.01.81.61.41.21.00.80.60.40.20.1選擇概率0.180.160.150.130.110.090.070.060.030.020.0累計概率0.180.340.490.620.730.82

18、0.890.950.981.001.00常用選擇方法輪盤賭選擇法（roulette wheel selection） 遺傳操作選擇 10.2 遺傳算法 實值重組離散重組 子個體的每個變量可以按等概率隨機地挑選父個體。 遺傳操作交叉/基因重組 父個體1 12 25 5父個體2 123 4 34子個體1 123 4 5子個體2 12 4 3410.2 遺傳算法 實值重組中間重組 子個體父個體1（父個體2父個體1） 是比例因子，由-d,1+d上均勻分布地隨機數(shù)產(chǎn)生。 d=0時為中間重組，一般取d=0.25。 子代的每個變量均產(chǎn)生一個 。 遺傳操作交叉/基因重組 10.2 遺傳算法 實值重組中間重組

19、遺傳操作交叉/基因重組 父個體1 12 25 5父個體2 123 4 34子個體1子個體2值樣本1 0.5 1.1 -0.1值樣本2 0.1 0.8 0.5120.5（12312）=67.567.5251.1（425）=1.91.92.1120.1（12312）=23.123.18.219.510.2 遺傳算法 實值重組線性重組 遺傳操作交叉/基因重組 父個體1 12 25 5父個體2 123 4 34子個體1子個體2值樣本1 0.5值樣本2 0.1120.5（12312）=67.567.5250.5（425）=14.514.519.5120.1（12312）=23.123.122.97.91

20、0.2 遺傳算法 實值重組線性重組 遺傳操作交叉/基因重組 10.2 遺傳算法 二進制交叉單點交叉 遺傳操作交叉/基因重組 10.2 遺傳算法 二進制交叉多點交叉 遺傳操作交叉/基因重組 10.2 遺傳算法 變異是將某一個體的某一位字符進行補運算，即將1變?yōu)?，或?qū)?變?yōu)?. 遺傳操作變異 10.2 遺傳算法 運行程序 算法的設(shè)計與實現(xiàn) 10.2 遺傳算法 運行程序 算法的設(shè)計與實現(xiàn) 10.2 遺傳算法 運行程序 算法的設(shè)計與實現(xiàn) 10.2 遺傳算法 運行程序 算法的設(shè)計與實現(xiàn) 10.2 遺傳算法 模式 將種群中的個體即基因串中的相似樣板稱為模式。 在二進制編碼的串中，模式是基于三個字符集（0

21、，1，*）的字符串，符號*稱作通配符，代表任意字符，即0或1。 如模式 *1* 描述了一個四個元的子集010，011，110，111。 模式定理 10.2 遺傳算法 模式階和定義距 模式 H 中確定位置的個數(shù)（即H 中0或1的個數(shù)）稱為模式 H 的模式階，記作 O(H)，如 O(0 1 1 * 1 *)=4。 模式階用來反映不同模式間確定性的差異，模式階越高，模式的確定性就越高，所匹配的樣本個數(shù)就越少。 模式定理 10.2 遺傳算法 模式階和定義距 模式 H 中第一個確定位置和最后一個確定位置之間的距離稱為模式的定義距，記作 (H)，如 (0 1 1 * 1 * *)=5-1=4。 階數(shù)相同的模式會有不同的性質(zhì)，定義距就反映了這種性質(zhì)的差異。 模式定理 10.2 遺傳算法 平均適應(yīng)度 模式H的平均適應(yīng)度是指在一個確定的群體內(nèi)，與H相匹配的所有個體之平均適應(yīng)度，記做f(H). 模式定理 10.2 遺傳算法 模式定理（schema theore