1、.,1,模擬退火算法及模型,算法的提出模擬退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。算法的目的解決NP復(fù)雜性問題；克服優(yōu)化過程陷入局部極?。豢朔踔狄蕾囆?。,物理退火過程,.,2,模擬退火算法及模型,物理退火過程什么是退火：退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，達(dá)到某種穩(wěn)定狀態(tài)。,物理退火過程,.,3,模擬退火算法及模型,物理退火過程加溫過程增強(qiáng)粒子的熱運(yùn)動(dòng)，消除系統(tǒng)原先可能存在的非均勻態(tài)；等溫過程對(duì)于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自

2、由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡態(tài)；冷卻過程使粒子熱運(yùn)動(dòng)減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。,物理退火過程,.,4,10.1.1模擬退火算法的基本原理,數(shù)學(xué)表述在溫度T，分子停留在狀態(tài)r滿足Boltzmann概率分布,物理退火過程,.,5,10.1.1模擬退火算法的基本原理,數(shù)學(xué)表述在同一個(gè)溫度T，選定兩個(gè)能量E1E2，有在同一個(gè)溫度，分子停留在能量小的狀態(tài)的概率比停留在能量大的狀態(tài)的概率要大。,.,6,10.1.1模擬退火算法的基本原理,數(shù)學(xué)表述若|D|為狀態(tài)空間D中狀態(tài)的個(gè)數(shù)，D0是具有最低能量的狀態(tài)集合：當(dāng)溫度很高時(shí)，每個(gè)狀態(tài)概率基本相同，接近平

3、均值1/|D|；狀態(tài)空間存在超過兩個(gè)不同能量時(shí)，具有最低能量狀態(tài)的概率超出平均值1/|D|；當(dāng)溫度趨于0時(shí)，分子停留在最低能量狀態(tài)的概率趨于1。,.,7,10.1.1模擬退火算法的基本原理,Metropolis準(zhǔn)則（1953）以概率接受新狀態(tài)若在溫度T，當(dāng)前狀態(tài)i新狀態(tài)j若Ej=randrom0,1s=sj;Until抽樣穩(wěn)定準(zhǔn)則滿足；退溫tk+1=update(tk)并令k=k+1；Until算法終止準(zhǔn)則滿足；輸出算法搜索結(jié)果。,.,13,10.1.3模擬退火算法的計(jì)算步驟及收斂性,定義,.,14,10.1.3模擬退火算法的計(jì)算步驟及收斂性,定義一步轉(zhuǎn)移概率：n步轉(zhuǎn)移概率：若解空間有限，稱馬

4、爾可夫鏈為有限狀態(tài)；若，稱馬爾可夫鏈為時(shí)齊的。,馬爾科夫鏈,.,15,10.1.3模擬退火算法的計(jì)算步驟及收斂性,模擬退火算法對(duì)應(yīng)了一個(gè)馬爾可夫鏈模擬退火算法：新狀態(tài)接受概率僅依賴于新狀態(tài)和當(dāng)前狀態(tài)，并由溫度加以控制。若固定每一溫度，算法均計(jì)算馬氏鏈的變化直至平穩(wěn)分布，然后下降溫度，則稱為時(shí)齊算法；若無需各溫度下算法均達(dá)到平穩(wěn)分布，但溫度需按一定速率下降，則稱為非時(shí)齊算法。分析收斂性,.,16,10.1.3模擬退火算法的計(jì)算步驟及收斂性,模擬退火過程是從一個(gè)狀態(tài)（解）到另一個(gè)狀態(tài)（解）不斷地隨機(jī)游動(dòng)，我們稱這種游動(dòng)為變換。從鄰域Si中選出某個(gè)解j的方法稱為解的產(chǎn)生機(jī)制.從當(dāng)前解變換到下一個(gè)解的

5、過程稱為轉(zhuǎn)移，它由產(chǎn)生機(jī)制的應(yīng)用和接受準(zhǔn)則的應(yīng)用兩部分組成。,.,17,10.1.3模擬退火算法的計(jì)算步驟及收斂性,.,18,10.1.3模擬退火算法的計(jì)算步驟及收斂性,.,19,10.1.4模擬退火算法實(shí)現(xiàn)的技術(shù)問題,冷卻進(jìn)度表控制參數(shù)值Tf的選取馬爾科夫鏈長(zhǎng)度Lk的選取控制參數(shù)衰減函數(shù)的選取,.,20,10.1.4模擬退火算法實(shí)現(xiàn)的技術(shù)問題,原則(1)在固定溫度下，接受使目標(biāo)函數(shù)下降的候選解的概率要大于使目標(biāo)函數(shù)上升的候選解概率；(2)隨溫度的下降，接受使目標(biāo)函數(shù)上升的解的概率要逐漸減??；(3)當(dāng)溫度趨于零時(shí)，只能接受目標(biāo)函數(shù)下降的解。方法具體形式對(duì)算法影響不大一般采用min1,exp(-

6、C/t),.,21,10.1.4模擬退火算法實(shí)現(xiàn)的技術(shù)問題,方法（1）均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值得方差為初溫；（2）隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差，根據(jù)差值，利用一定的函數(shù)確定初溫；（3）利用經(jīng)驗(yàn)公式。,初溫,.,22,10.1.4模擬退火算法實(shí)現(xiàn)的技術(shù)問題,時(shí)齊算法的溫度下降函數(shù)（1），越接近1溫度下降越慢，且其大小可以不斷變化；（2），其中t0為起始溫度，K為算法溫度下降的總次數(shù)。,溫度更新函數(shù),.,23,10.1.4模擬退火算法實(shí)現(xiàn)的技術(shù)問題,非時(shí)齊模擬退火算法每個(gè)溫度下只產(chǎn)生一個(gè)或少量候選解時(shí)齊算法常用的Metropolis抽樣穩(wěn)定準(zhǔn)則（1）檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否

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

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

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

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

11、發(fā)生某種變異，產(chǎn)生出新的染色體，這些新的染色體表現(xiàn)出新的性狀;編碼（coding）：表現(xiàn)型到基因型的映射；解碼（decoding）：從基因型到表現(xiàn)型的映射。,遺傳算法的基本原理和特點(diǎn),.,35,10.2遺傳算法,遺傳算法的基本思路,遺傳算法實(shí)現(xiàn)的技術(shù)問題,.,36,10.2遺傳算法,遺傳算法實(shí)現(xiàn)的技術(shù)問題,遺傳算法的工作步驟,.,37,10.2遺傳算法,遺傳算法實(shí)現(xiàn)的技術(shù)問題,.,38,10.2遺傳算法,問題的提出一元函數(shù)求最大值：,簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例,.,39,10.2遺傳算法,編碼表現(xiàn)型：x基因型：二進(jìn)制編碼（串長(zhǎng)取決于求解精度）串長(zhǎng)與精度之間的關(guān)系：若要求求解精度到6位小數(shù)，區(qū)間長(zhǎng)度為2

12、-(-1)3，即需將區(qū)間分為3/0.000001=3106等份。所以編碼的二進(jìn)制串長(zhǎng)應(yīng)為22位。,簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例,.,40,10.2遺傳算法,產(chǎn)生初始種群產(chǎn)生的方式：隨機(jī)產(chǎn)生的結(jié)果：長(zhǎng)度為22的二進(jìn)制串產(chǎn)生的數(shù)量：種群的大?。ㄒ?guī)模），如30，50，111101001110000101100011001100111010101011101010100011110010000100101111001001110011100100011001010011000000110000011010010000000000,簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例,.,41,10.2遺傳算法,計(jì)算適應(yīng)度不同的問題有不同的適應(yīng)度

13、計(jì)算方法本例：直接用目標(biāo)函數(shù)作為適應(yīng)度函數(shù)將某個(gè)體轉(zhuǎn)化為-1,2區(qū)間的實(shí)數(shù)：s=x=0.637197計(jì)算x的函數(shù)值（適應(yīng)度）：f(x)=xsin(10x)+2.0=2.586345,簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例,.,42,10.2遺傳算法,計(jì)算適應(yīng)度二進(jìn)制與十進(jìn)制之間的轉(zhuǎn)換：第一步，將一個(gè)二進(jìn)制串（b21b20b0）轉(zhuǎn)化為10進(jìn)制數(shù)：第二步，x對(duì)應(yīng)的區(qū)間-1,2內(nèi)的實(shí)數(shù)：,簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例,(0000000000000000000000)-1(1111111111111111111111)2,.,43,10.2遺傳算法,遺傳操作選擇：輪盤賭選擇法；交叉：?jiǎn)吸c(diǎn)交叉；變異：小概率變異,簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例,

14、.,44,10.2遺傳算法,模擬結(jié)果設(shè)置的參數(shù)：種群大小50；交叉概率0.75；變異概率0.05；最大代數(shù)200。得到的最佳個(gè)體：smax=;xmax=1.8506;f(xmax)=3.8503;,簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例,.,45,10.2遺傳算法,模擬結(jié)果進(jìn)化的過程：,簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例,.,46,10.2遺傳算法,編碼原則完備性（completeness）：?jiǎn)栴}空間的所有解都能表示為所設(shè)計(jì)的基因型；健全性（soundness）：任何一個(gè)基因型都對(duì)應(yīng)于一個(gè)可能解；非冗余性（non-redundancy）：?jiǎn)栴}空間和表達(dá)空間一一對(duì)應(yīng)。,.,47,10.2遺傳算法,適應(yīng)度函數(shù)的重要性適應(yīng)度函數(shù)的選取

15、直接影響遺傳算法的收斂速度以及能否找到最優(yōu)解。一般而言，適應(yīng)度函數(shù)是由目標(biāo)函數(shù)變換而成的，對(duì)目標(biāo)函數(shù)值域的某種映射變換稱為適應(yīng)度的尺度變換（fitnessscaling）。,適應(yīng)度函數(shù)及其尺度變換,.,48,10.2遺傳算法,幾種常見的適應(yīng)度函數(shù)若目標(biāo)函數(shù)為最大化問題：若目標(biāo)函數(shù)為最小化問題：,適應(yīng)度函數(shù)及其尺度變換,.,49,10.2遺傳算法,適應(yīng)度函數(shù)的線性變換法f=*f+系數(shù)的確定滿足以下條件：縮放前后的平均適應(yīng)度相等.favg=favg縮放后的最大適應(yīng)度要等于原平均適應(yīng)度的指定倍數(shù)fmax=cmultfavgcmult=1.02.0,適應(yīng)度函數(shù)及其尺度變換,.,50,10.2遺傳算法,

16、適應(yīng)度函數(shù)的作用適應(yīng)度函數(shù)設(shè)計(jì)不當(dāng)有可能出現(xiàn)欺騙問題：（1）進(jìn)化初期，個(gè)別超常個(gè)體控制選擇過程；（2）進(jìn)化末期，個(gè)體差異太小導(dǎo)致陷入局部極值。,適應(yīng)度函數(shù)及其尺度變換,.,51,10.2遺傳算法,適應(yīng)度函數(shù)的設(shè)計(jì)單值、連續(xù)、非負(fù)、最大化合理、一致性計(jì)算量小通用性強(qiáng),適應(yīng)度函數(shù)及其尺度變換,.,52,10.2遺傳算法,個(gè)體選擇概率的常用分配方法按比例的適應(yīng)度分配（proportionalfitnessassignment）某個(gè)體i，其適應(yīng)度為fi，則其被選取的概率Pi為：,遺傳操作選擇,.,53,10.2遺傳算法,常用選擇方法輪盤賭選擇法（roulettewheelselection）,遺傳操作

17、選擇,.,54,10.2遺傳算法,實(shí)值重組離散重組子個(gè)體的每個(gè)變量可以按等概率隨機(jī)地挑選父?jìng)€(gè)體。,遺傳操作交叉/基因重組,父?jìng)€(gè)體112255父?jìng)€(gè)體2123434,子個(gè)體112345子個(gè)體212434,.,55,10.2遺傳算法,實(shí)值重組中間重組子個(gè)體父?jìng)€(gè)體1（父?jìng)€(gè)體2父?jìng)€(gè)體1）是比例因子，由-d,1+d上均勻分布地隨機(jī)數(shù)產(chǎn)生。d=0時(shí)為中間重組，一般取d=0.25。子代的每個(gè)變量均產(chǎn)生一個(gè)。,遺傳操作交叉/基因重組,.,56,10.2遺傳算法,實(shí)值重組中間重組,遺傳操作交叉/基因重組,父?jìng)€(gè)體112255父?jìng)€(gè)體2123434,子個(gè)體1子個(gè)體2,值樣本10.51.1-0.1值樣本20.10.80.

18、5,120.5（12312）=67.5,67.5,251.1（425）=1.9,1.9,2.1,120.1（12312）=23.1,23.1,8.2,19.5,.,57,10.2遺傳算法,實(shí)值重組線性重組,遺傳操作交叉/基因重組,父?jìng)€(gè)體112255父?jìng)€(gè)體2123434,子個(gè)體1子個(gè)體2,值樣本10.5值樣本20.1,120.5（12312）=67.5,67.5,250.5（425）=14.5,14.5,19.5,120.1（12312）=23.1,23.1,22.9,7.9,.,58,10.2遺傳算法,實(shí)值重組線性重組,遺傳操作交叉/基因重組,.,59,10.2遺傳算法,二進(jìn)制交叉單點(diǎn)交叉,遺

19、傳操作交叉/基因重組,.,60,10.2遺傳算法,二進(jìn)制交叉多點(diǎn)交叉,遺傳操作交叉/基因重組,.,61,10.2遺傳算法,變異是將某一個(gè)體的某一位字符進(jìn)行補(bǔ)運(yùn)算，即將1變?yōu)?，或?qū)?變?yōu)?.,遺傳操作變異,.,62,10.2遺傳算法,運(yùn)行程序,算法的設(shè)計(jì)與實(shí)現(xiàn),.,63,10.2遺傳算法,運(yùn)行程序,算法的設(shè)計(jì)與實(shí)現(xiàn),.,64,10.2遺傳算法,運(yùn)行程序,算法的設(shè)計(jì)與實(shí)現(xiàn),.,65,10.2遺傳算法,運(yùn)行程序,算法的設(shè)計(jì)與實(shí)現(xiàn),.,66,10.2遺傳算法,模式將種群中的個(gè)體即基因串中的相似樣板稱為模式。在二進(jìn)制編碼的串中，模式是基于三個(gè)字符集（0，1，*）的字符串，符號(hào)*稱作通配符，代表任意字符，即0或1。如模式*1*描述了一個(gè)四個(gè)元的子集010，011，110，111。,模式定理,.,67,10.2遺傳算法,模式階和定義距模式H中確定位置的個(gè)數(shù)（即H中0或1的個(gè)數(shù)）稱為模式H的模式階，記作O(H)，如O(011*1*)=4。模式階用來反映不同模式間確定性的差異，模式階越高，模式的確定性就越高，所匹配的樣本個(gè)數(shù)就越少。,模式定理,.,68,10.2遺傳算法,模式階和定義距模式H中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離稱為模式的定義距，記作(H)，如(011*1*)=5-1=4。階數(shù)相同的模式會(huì)有不同的性質(zhì)，定義距就反映了這種性質(zhì)的差異。,模式定理,.,69,10.2遺傳