ch2智能優(yōu)化算法-研究生

第二章智能優(yōu)化算法第二章智能優(yōu)化算法概述進(jìn)化計算及其應(yīng)用模擬退火算法及其應(yīng)用群智能算法及其應(yīng)用3參考教材王凌,?智能優(yōu)化算法及其應(yīng)用?,清華大學(xué)出版社,施普林格出版社,2001年10月第1版.王小玉,?遺傳算法—理論、應(yīng)用與軟件實現(xiàn)?,西安交通大學(xué)出版社,2002年1月第1版王耀南,?智能信息處理技術(shù)?,高等教育出版社,2003年8月第1版.42.1概述一、最優(yōu)化問題分類可分為函數(shù)優(yōu)化問題和組合優(yōu)化問題兩大類。函數(shù)優(yōu)化問題：最小化和最大化優(yōu)化對象：一定區(qū)間S內(nèi)的連續(xù)變量最小化問題的一般描述：求Xmin

S使f(Xmin)在S上全局最小符號化表示為：

X

S:f(Xmin)

f(X)S為Rn上的有界子集，即變量的定義域f:S→R為n維實值函數(shù)52.1概述一、最優(yōu)化問題分類函數(shù)優(yōu)化問題最大化問題的一般描述：求Xmax

S使f(Xmax)在S上全局最大符號化表示為：

X

S:f(Xmax)

f(X)S為Rn上的有界子集，即變量的定義域f:S→R為n維實值函數(shù)82.1概述經(jīng)典算法如：線性規(guī)劃、動態(tài)規(guī)劃、整數(shù)規(guī)劃、分枝定界等運(yùn)籌學(xué)中的傳統(tǒng)算法。算法計算復(fù)雜性一般很大，只適于求解小規(guī)模問題，在工程中往往不實用。構(gòu)造型算法用構(gòu)造的方法快速建立問題的解，通常算法的優(yōu)化質(zhì)量差，難以滿足工程需要。調(diào)度中的典型構(gòu)造型算法有：Johnson法、Palmer法、基于枚舉樹的分區(qū)法等。92.1概述改進(jìn)型算法，或稱鄰域搜索算法從任一解出發(fā)，通過對其鄰域的不斷搜索和當(dāng)前解的替換來實現(xiàn)優(yōu)化。根據(jù)搜索行為，可分為局部搜索法和指導(dǎo)性搜索法〔如SA、GA〕?；谙到y(tǒng)動態(tài)演化的方法將優(yōu)化過程轉(zhuǎn)化為系統(tǒng)動態(tài)的演化過程，基于系統(tǒng)動態(tài)的演化來實現(xiàn)優(yōu)化，如神經(jīng)網(wǎng)絡(luò)、蟻群算法、混沌搜索等?；旌闲退惴ㄉ鲜龈魉惴◤慕Y(jié)構(gòu)或操作上混合而產(chǎn)生的各類算法。2.2進(jìn)化算法及其應(yīng)用2.2.1進(jìn)化算法簡介2.2.2遺傳算法與生物進(jìn)化學(xué)說2.2.3遺傳算法的計算機(jī)實現(xiàn)2.2.4遺傳算法解決TSP問題2.2.5遺傳算法的特點(diǎn)10產(chǎn)生背景主要特點(diǎn)理論根底分類說明2.2.1進(jìn)化算法簡介一、產(chǎn)生背景對自身的大腦信息處理機(jī)制進(jìn)行模擬----人工神經(jīng)網(wǎng)絡(luò)理論對自身模糊性的思維方式進(jìn)行類比----模糊系統(tǒng)對自然界中動植物的免疫機(jī)理進(jìn)行模擬----免疫系統(tǒng)對自身進(jìn)化這一更為宏觀的過程學(xué)習(xí)----進(jìn)化算法(EvolutionaryComputation，EC)2.2.1進(jìn)化算法簡介進(jìn)化算法是一種模擬生物進(jìn)化過程與機(jī)制求解問題的自組織、自適應(yīng)人工智能技術(shù)。優(yōu)勝劣汰，適者生存進(jìn)化規(guī)則繁殖、變異、競爭、選擇指導(dǎo)思想進(jìn)化算法是建立在模擬生物進(jìn)化過程的根底上而產(chǎn)生的一種隨機(jī)搜索優(yōu)化技術(shù)2.2.1進(jìn)化算法簡介2.2.1進(jìn)化算法簡介二、主要特點(diǎn)在算法中主要表現(xiàn)為全局搜索方式，表達(dá)在下面幾個方面有指導(dǎo)搜索：依據(jù)是每個個體的適應(yīng)度值自適應(yīng)搜索：通過進(jìn)化操作改進(jìn)群體性能漸進(jìn)式尋優(yōu)：每代進(jìn)化的結(jié)果都優(yōu)于上一代并行式搜索：對每一代群體所有個體同時進(jìn)行黑箱式結(jié)構(gòu)：只要研究輸入和輸出而不需考慮過程全局最優(yōu)解：在整個搜索區(qū)域的各個局部同時進(jìn)行內(nèi)在學(xué)習(xí)型：學(xué)習(xí)是一種有保存的行為穩(wěn)健性強(qiáng)：不同的條件和環(huán)境下算法適用和有效性2.2.1進(jìn)化算法簡介三、理論根底進(jìn)化計算是模擬生物進(jìn)化理論而形成的一種全局優(yōu)化自適應(yīng)概率搜索的算法理論。具有深厚的生物學(xué)理論根底：遺傳：父代利用遺傳基因?qū)⒆陨淼幕蛐畔⒔桓督o下一代〔子代〕，屬性特征相同或相近。變異：子代和父代，以及子代各個體之間存在著一定的差異，在進(jìn)化過程中是隨機(jī)發(fā)生的。生存斗爭和適者生存：適應(yīng)性變異較強(qiáng)的個體被保存下來，而適應(yīng)性變異較弱的個體那么被淘汰。2.2.1進(jìn)化算法簡介四、分類說明從進(jìn)化的過程性質(zhì)進(jìn)行區(qū)分，與進(jìn)化算法相關(guān)的算法可細(xì)分為：遺傳算法：最具代表性也是最根本的進(jìn)化策略：側(cè)重于數(shù)值分析進(jìn)化規(guī)劃：介于數(shù)值分析與人工智能之間遺傳規(guī)劃：偏向以程式表現(xiàn)人工智能行為進(jìn)化動力學(xué)：偏向進(jìn)化的自組織和系統(tǒng)動力學(xué)特性分類系統(tǒng)：適應(yīng)動態(tài)環(huán)境學(xué)習(xí)動態(tài)模擬系統(tǒng)：用以觀察復(fù)雜系統(tǒng)交互元胞自動機(jī)：研究人工生命蟻群系統(tǒng)：模擬螞蟻群體行為172.2.2遺傳算法與生物進(jìn)化學(xué)說1885年，達(dá)爾文用自然選擇來解釋物種的起源和生物的進(jìn)化，達(dá)爾文的自然選擇學(xué)說包括三個方面：

遺傳 變異 生存斗爭和適者生存182.2.2遺傳算法與生物進(jìn)化學(xué)說20世紀(jì)20年代，一些學(xué)者用統(tǒng)計生物學(xué)和種群遺傳學(xué)的成就重新解釋達(dá)爾文自然選擇理論，形成現(xiàn)代綜合進(jìn)化論。種群遺傳學(xué)認(rèn)為：在一定地域中一個物種的全體成員構(gòu)成一個種群；生物的進(jìn)化是種群的進(jìn)化，每一代個體基因型的改變會影響種群基因庫的組成，而種群基因庫組成的變化就是這一種群的進(jìn)化。192.2.2遺傳算法與生物進(jìn)化學(xué)說GA中與生物學(xué)相關(guān)的概念與術(shù)語：個體種群適應(yīng)度選擇交叉變異優(yōu)化問題中的描述：解解集/解空間評價函數(shù)/目標(biāo)函數(shù)/尋優(yōu)函數(shù)產(chǎn)生新解的方法2.2.3遺傳算法的計算機(jī)實現(xiàn) 20世紀(jì)60年代中期，J.Holland在前人工作根底上，提出位串編碼技術(shù)。這種技術(shù)適用于變異和交叉操作，而且強(qiáng)調(diào)將交叉作為主要的遺傳操作。 隨后，Holland將該算法用于自然和人工系統(tǒng)的自適應(yīng)行為研究中，在1975出版了開創(chuàng)性著作“AdaptationinNaturalandArtificalSystem〞。 以后更是將算法進(jìn)行了推廣，并應(yīng)用到優(yōu)化以及學(xué)習(xí)中，正式將其命名為遺傳算法(GeneticAlgorithms，簡稱GA)。21遺傳算法根本思路：計算開始時，隨機(jī)初始化一定數(shù)目的個體〔即種群〕，并計算每個個體的適應(yīng)度值，產(chǎn)生第一代〔初始代〕。如果不滿足優(yōu)化準(zhǔn)那么，開始新一代的計算：按照適應(yīng)度值選擇個體，產(chǎn)生下一代；父代按一定概率進(jìn)行交叉操作，產(chǎn)生子代；所有的子代按一定概率變異，形成新的一代。計算新子代的適應(yīng)度值。這一過程循環(huán)執(zhí)行，直到滿足優(yōu)化準(zhǔn)那么為止。2.2.3遺傳算法的計算機(jī)實現(xiàn)22遺傳算法根本流程2.2.3遺傳算法的計算機(jī)實現(xiàn)23需要解決的問題：種群適應(yīng)度函數(shù)復(fù)制〔選擇〕交叉變異編碼：首先需要解決的問題遺傳操作242.2.3遺傳算法的計算機(jī)實現(xiàn)什么是編碼？解題過程中，每個具體的解就對應(yīng)一個個體。簡單來說，編碼就是將問題的解用一種碼來表示，從而將問題的解(狀態(tài))空間與GA的碼空間相對應(yīng)。252.2.3遺傳算法的計算機(jī)實現(xiàn)編碼的意義：編碼方案很大程度上決定了如何進(jìn)行群體的遺傳運(yùn)算及其運(yùn)算效率。一個好的編碼方案，可以使遺傳運(yùn)算簡單地實現(xiàn)和執(zhí)行。否那么，可能使運(yùn)算難以實現(xiàn)。編碼是應(yīng)用GA時要解決的首要問題，也是設(shè)計GA的一個關(guān)鍵步驟，選擇或設(shè)計一種適宜的編碼方案對算法的性能和效率意義重大。262.2.3遺傳算法的計算機(jī)實現(xiàn)例：考慮一元函數(shù)求最大值的優(yōu)化問題272.2.3遺傳算法的計算機(jī)實現(xiàn)f(x)在區(qū)間[-1,2]可微，先用微分法求取f(x)的最大值。上式的解有無窮多個：

i是一種接近于0的實數(shù)遞減序列。i為奇數(shù)時，xi對應(yīng)局部極大值點(diǎn)；i為偶數(shù)時，xi對應(yīng)局部極小點(diǎn)。x19是區(qū)間[-1,2]內(nèi)的最大點(diǎn)。282.2.3遺傳算法的計算機(jī)實現(xiàn)步驟1：編碼

已有的編碼方案：二進(jìn)制編碼、Delta編碼、格雷碼編碼、實數(shù)編碼、自然數(shù)編碼、符號編碼、動態(tài)變量編碼、鏈表編碼、矩陣編碼、樹型編碼、量子比特編碼……292.2.3遺傳算法的計算機(jī)實現(xiàn)步驟1：編碼

最常用的編碼方法：二進(jìn)制編碼使用二值編碼符號集{0,1}。每個個體是一個二進(jìn)制符號串，串長與求解精度有關(guān)。根據(jù)模式理論，采用二進(jìn)制編碼算法處理的模式最多，幾乎任何問題都可以用二進(jìn)制編碼來表達(dá)。因此，二進(jìn)制編碼應(yīng)用是最早和最廣泛的，它是GA中最常用的一種編碼方案。302.2.3遺傳算法的計算機(jī)實現(xiàn)設(shè)：求解精度為6位小數(shù)因為，采用二進(jìn)制編碼方法，不能表示小數(shù)和負(fù)數(shù)所以，將閉區(qū)間[-1,2]改為：[0,3

106]又因為：3

106=(1011011100011011000000)2 2097152=221<3×106<222=4194304所以，編碼的二進(jìn)制串長至少需要22位

312.2.3遺傳算法的計算機(jī)實現(xiàn)窮盡編碼：二進(jìn)制串(0000000000000000000000) 表示區(qū)間端點(diǎn)值-1

二進(jìn)制串 表示區(qū)間端點(diǎn)值2

不窮盡編碼？322.2.3遺傳算法的計算機(jī)實現(xiàn)將一個二進(jìn)制串〔b21b20…b0〕轉(zhuǎn)化為區(qū)間[-1,2]內(nèi)對應(yīng)的實數(shù)，需要采用以下步驟：將二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)x’將x’轉(zhuǎn)化為區(qū)間[-1，2]內(nèi)的實數(shù)x332.2.3遺傳算法的計算機(jī)實現(xiàn)步驟1：編碼二進(jìn)制編碼的主要優(yōu)點(diǎn)：編碼、解碼操作簡單易行選擇、交叉和變異等遺傳操作便于實現(xiàn)符合最小符號集編碼原那么便于利用模式定理對算法進(jìn)行理論分析。342.2.3遺傳算法的計算機(jī)實現(xiàn)步驟2：產(chǎn)生初始種群產(chǎn)生一定數(shù)目的個體組成種群初始個體的產(chǎn)生方法：隨機(jī)法、啟發(fā)法。種群規(guī)模是影響算法優(yōu)化性能和效率的因素之一。種群規(guī)模是指種群中個體數(shù)目。種群太小，不能提供足夠的采樣點(diǎn)，導(dǎo)致算法性能很差，甚至得不到問題的可行解。種群太大，盡管可增加優(yōu)化信息以阻止早熟收斂的發(fā)生，但會增加計算量，使收斂時間太長。352.2.3遺傳算法的計算機(jī)實現(xiàn)步驟3：計算適應(yīng)度遺傳算法在進(jìn)化搜索中根本不利用外部信息，僅以適應(yīng)度函數(shù)為依據(jù)，利用種群中每個個體的適應(yīng)度值來進(jìn)行搜索。一般，適應(yīng)度函數(shù)是由目標(biāo)函數(shù)變換而成。假設(shè)目標(biāo)函數(shù)為最大化問題：Fit(x)=f(x)假設(shè)目標(biāo)函數(shù)為最小化問題：Fit(x)=-f(x)本例的目標(biāo)函數(shù)在定義域內(nèi)均大于0，而且求函數(shù)最大值，可直接引用目標(biāo)函數(shù)作為適應(yīng)度函數(shù)：f(s)=f(x)，式中，二進(jìn)制串s對應(yīng)變量x的值。362.2.3遺傳算法的計算機(jī)實現(xiàn)設(shè)某個個體的二進(jìn)制為：s372.2.3遺傳算法的計算機(jī)實現(xiàn)設(shè)有三個個體的二進(jìn)制為：s1s2s3分別對應(yīng)于變量：x1=0.637197、x2=-0.958973、x3=1.627888個體的適應(yīng)度為：f(s1)=f(x1)=2.586345、f(s2)=f(x2)=1.078878f(s3)=f(x3)=3.250650三個個體中s3的適應(yīng)度最大，因此，s3為最正確個體。38步驟4：選擇選擇操作決定從父代種群中選取哪些個體遺傳到下一代種群中，它以個體的適應(yīng)度值為評價指標(biāo)，對種群中個體進(jìn)行優(yōu)勝劣汰。最常用的算子：比例選擇算子〔選擇的蒙特卡羅法〕根本思想：每個個體被選中的概率與其適應(yīng)度值成正比。設(shè)種群規(guī)模為M，個體i的適應(yīng)度值為fi，那么個體i被選中的概率Pi為：2.2.3遺傳算法的計算機(jī)實現(xiàn)39當(dāng)Pi給定后，產(chǎn)生[0,1]區(qū)間內(nèi)的均勻隨機(jī)數(shù)來決定哪個個體參加交叉操作。即：用賭輪方式?jīng)Q定個體的選擇份數(shù)。個體i1234567適應(yīng)度值fi1.3640.8680.3723.3481.7361.243.348

fi=12.4選擇概率Pi0.110.070.030.270.140.100.27

Pi=fi/fi

2.2.3遺傳算法的計算機(jī)實現(xiàn)402.1遺傳算法及其應(yīng)用41經(jīng)選擇產(chǎn)生的交叉種群由以下個體組成：1,2,3,5,6,9,……2.2.3遺傳算法的計算機(jī)實現(xiàn)個體i1234567891011適應(yīng)度fi2.01.81.61.41.21.00.80.60.40.20.1

fi=11.1選擇概率0.180.160.140.130.110.090.070.050.040.020.01fi/

fi累積概率0.180.340.480.610.720.810.880.930.970.991.00輪數(shù)1234567891011隨機(jī)數(shù)0.810.320.960.010.650.42……………42步驟5：交叉在選擇操作根底上，根據(jù)交叉概率pc進(jìn)行交叉操作：把兩個父個體的局部結(jié)構(gòu)進(jìn)行替換重組，生成新個體。對應(yīng)于二進(jìn)制編碼，常用的交叉算子是：單點(diǎn)交叉。交叉點(diǎn)的范圍為：[1，N-1]，N為二進(jìn)制串的串長。交叉操作時，個體以該點(diǎn)為分界相互交換變量。2.2.3遺傳算法的計算機(jī)實現(xiàn)43設(shè)經(jīng)過選擇操作，得到兩個個體：

s2s3=(11100|

)隨機(jī)選擇一個交叉點(diǎn)，交叉后產(chǎn)生新的子個體：

s2’=(00000|)s3f(s2’)=f(-0.998113)=1.940865、f(s3’)=f(1.666028)=3.4592452.2.3遺傳算法的計算機(jī)實現(xiàn)44pc控制交叉操作頻率，使局部被選擇的個體進(jìn)行交叉操作pc太大，個體更新過快，高適應(yīng)度值的個體很快被破壞。pc太小，很少進(jìn)行交叉操作，使搜索停滯不前。本例中，交叉概率取為：pc=0.82.2.3遺傳算法的計算機(jī)實現(xiàn)45步驟6：變異基于二進(jìn)制編碼的GA中，變異是指將被選中個體的某一位進(jìn)行翻轉(zhuǎn)操作，即：將1換為0，將0換為1。設(shè)以一小概率選擇了第5位變異：s3=(1110000000s3’=(11101f(s3’)=f(1.721638)=0.917743f(s3)=3.250650假設(shè)選擇第10位變異，產(chǎn)生的新個體為：s3’’=(1110100001f(s3’’)=f(1.630818)=3.343555f(s3)=3.2506502.2.3遺傳算法的計算機(jī)實現(xiàn)46不是所有被選擇的個體，都要進(jìn)行變異操作。變異概率是加大種群多樣性的重要因素。概率太小很難產(chǎn)生新個體。概率太大會使GA成為隨機(jī)搜索?；诙M(jìn)制編碼的GA中，通常一個較低的變異率足以防止整個種群中任一位置的基因一直保持不變。本例中，變異概率取為：pm=0.01

2.2.3遺傳算法的計算機(jī)實現(xiàn)47步驟7：算法的終止判斷最常用的終止條件：事先給定一個最大進(jìn)化步數(shù)；判斷最正確優(yōu)化值是否連續(xù)假設(shè)干步?jīng)]有明顯變化。2.2.3遺傳算法的計算機(jī)實現(xiàn)482.2.4遺傳算法求解TSP問題編碼最常用策略：路徑編碼直接采用城市在路徑中的位置來構(gòu)造用于優(yōu)化的狀態(tài)。例：九城市TSP問題，路徑：5-4-1-7-9-8-6-2-3路徑編碼：(541798623)49502.2.4遺傳算法求解TSP問題512.2.5遺傳算法的特點(diǎn)GA是一種通用的優(yōu)化算法，它的優(yōu)點(diǎn)有：編碼技術(shù)和遺傳操作比較簡單；優(yōu)化不受限制性條件的約束；隱含并行性和全局解空間搜索。隨著計算機(jī)技術(shù)的開展，GA愈來愈得到人們的重視，并在機(jī)器學(xué)習(xí)、模式識別、圖像處理、神經(jīng)網(wǎng)絡(luò)、優(yōu)化控制、組合優(yōu)化、VLSI設(shè)計、遺傳學(xué)等領(lǐng)域得到了成功應(yīng)用。522.3模擬退火算法及其應(yīng)用模擬退火算法〔SimulatedAnnealing，SA)是一種通用的優(yōu)化算法。已在：生產(chǎn)調(diào)度、控制工程、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、圖像處理等工程領(lǐng)域中得到了廣泛應(yīng)用。2.3.1模擬退火算法與物理退火過程2.3.2模擬退火算法的計算機(jī)實現(xiàn)2.3.3模擬退火算法解決TSP問題2.3.4模擬退火算法的特點(diǎn)532.3.1SA算法與物理退火過程SA算法是基于MenteCarlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是：基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。54物理退火過程由以下三局部組成：加溫過程增強(qiáng)粒子熱運(yùn)動，使其偏離平衡位置。當(dāng)溫度足夠高時，固體熔解為液體，消除系統(tǒng)可能存在的非均勻態(tài)，使隨后進(jìn)行的冷卻過程以某一平衡態(tài)為起點(diǎn)。等溫過程對于與周圍環(huán)境交換熱量而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總朝自由能減少的方向進(jìn)行，當(dāng)自由能到達(dá)最小時，系統(tǒng)到達(dá)平衡態(tài)。冷卻過程使粒子的熱運(yùn)動減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。2.3.1SA算法與物理退火過程55為了模擬固體在恒定溫度下到達(dá)熱平衡的過程，可采用MonteCarlo方法，該方法簡單，但必須大量采樣才能得到較精確結(jié)果，計算量很大。考慮到物理系統(tǒng)傾向于能量較低的狀態(tài)，而熱運(yùn)動又阻礙它準(zhǔn)確落到最低態(tài)，采樣時著重取那些有重要奉獻(xiàn)的狀態(tài)那么可較快到達(dá)較好的結(jié)果。1953年，Metropolis等據(jù)此提出了重要性采樣法〔也稱為Metropolis準(zhǔn)那么〕，即以概率接受新狀態(tài)。2.3.1SA算法與物理退火過程56Metropolis準(zhǔn)那么：在溫度t，由當(dāng)前狀態(tài)i產(chǎn)生新狀態(tài)j，兩者的能量分別為Ci和Cj，假設(shè)Cj<Ci，那么接受新狀態(tài)j為當(dāng)前狀態(tài)；否那么，假設(shè)概率pr=exp[-(Cj-Ci)/(kt)]大于[0,1)區(qū)間內(nèi)的隨機(jī)數(shù)，仍接受新狀態(tài)j為當(dāng)前狀態(tài);假設(shè)不成立，那么保存狀態(tài)i為當(dāng)前狀態(tài)。其中，k為Boltzmann常數(shù)。2.3.1SA算法與物理退火過程57SA算法的根本思路：由某一較高初溫開始，利用具有概率突跳特性的Metropolis抽樣策略在解空間中隨機(jī)搜索，伴隨溫度的不斷下降重復(fù)抽樣過程，最終得到問題的全局最優(yōu)解。2.3.1SA算法與物理退火過程581953年，Metropolis等提出SA思想。1983年，Kirkpatrick〔柯克帕特里克〕等將其用于組合優(yōu)化，目的在于：為具有NP復(fù)雜性的問題提供有效的近似求解算法；克服優(yōu)化過程陷入局部極??；克服初值依賴性。2.3.1SA算法與物理退火過程

模擬退火算法流程圖5960需要解決的問題：狀態(tài)產(chǎn)生函數(shù)狀態(tài)接受函數(shù)溫度更新函數(shù)〔退溫函數(shù)〕內(nèi)循環(huán)終止準(zhǔn)那么〔抽樣穩(wěn)定準(zhǔn)那么〕外循環(huán)終止準(zhǔn)那么〔退火結(jié)束準(zhǔn)那么〕初溫編碼能量函數(shù)2.3.2模擬退火算法的計算機(jī)實現(xiàn)退火歷程三函數(shù)二準(zhǔn)那么61例：考慮一元函數(shù)求最大值的優(yōu)化問題2.3.2模擬退火算法的計算機(jī)實現(xiàn)62步驟1：確定編碼方式和能量函數(shù)〔目標(biāo)函數(shù)〕最常用的編碼方案：實數(shù)編碼，以實數(shù)來表示求解狀態(tài)。s=1.8函數(shù)優(yōu)化問題中，能量函數(shù)由待優(yōu)化函數(shù)變換而成。假設(shè)目標(biāo)函數(shù)為最大化問題：C(s)=-f(s)假設(shè)目標(biāo)函數(shù)為最小化問題：C(s)=f(s)2.3.2模擬退火算法的計算機(jī)實現(xiàn)注意：與遺傳算法適應(yīng)度函數(shù)設(shè)計的區(qū)別63步驟2：確定初溫實驗說明，初溫t0越大，獲得高質(zhì)量解的幾率越大，但計算時間增加。初溫確實定應(yīng)折衷考慮優(yōu)化質(zhì)量和效率。常用確實定初溫的方法包括：均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值的方差為初溫。隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差|?max|，計算初溫，t0=-?max/lnpr初始接受概率pr理論上接近于1。設(shè)為某個較大的常數(shù)。2.3.2模擬退火算法的計算機(jī)實現(xiàn)64步驟3：確定初始狀態(tài)〔初始解〕理論上，初始狀態(tài)可以隨機(jī)取。為了提高優(yōu)化效率，可采用啟發(fā)式算法快速得到一個解，并以此為SA的初始狀態(tài)。2.3.2模擬退火算法的計算機(jī)實現(xiàn)65步驟4：狀態(tài)產(chǎn)生函數(shù)〔新解產(chǎn)生函數(shù)〕設(shè)計的出發(fā)點(diǎn)是盡可能保證產(chǎn)生的候選解遍布全部解空間。最常用的狀態(tài)產(chǎn)生函數(shù)：snew=sold+為擾動幅度參數(shù)，為隨機(jī)擾動變量。隨機(jī)擾動可服從柯西分布、高斯分布、均勻分布。2.3.2模擬退火算法的計算機(jī)實現(xiàn)66柯西分布：a為尺度參數(shù)高斯分布：

為方差，均值為0均勻分布：2.3.2模擬退火算法的計算機(jī)實現(xiàn)67步驟5：狀態(tài)接受函數(shù)該函數(shù)的引入是SA算法實現(xiàn)全局搜索的最關(guān)鍵因素，一般以概率方式給出。最常用的狀態(tài)接受函數(shù)：min{1,exp[-(C(sj)-C(si))/tk]}random[0,1]?設(shè)計狀態(tài)接受函數(shù)，應(yīng)該遵循以下原那么：固定溫度下，接受使目標(biāo)函數(shù)值下降的候選解的概率要大于使目標(biāo)函數(shù)值上升的候選解的概率；隨溫度下降，接受使目標(biāo)函數(shù)值上升解的概率要逐漸減??；當(dāng)溫度趨于零時，只能接受目標(biāo)函數(shù)值下降的解。2.3.2模擬退火算法的計算機(jī)實現(xiàn)68步驟6：內(nèi)循環(huán)終止準(zhǔn)那么或稱Metropolis抽樣穩(wěn)定準(zhǔn)那么

常用的抽樣穩(wěn)定準(zhǔn)那么包括：檢驗?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定；連續(xù)假設(shè)干步的目標(biāo)值變化較??；按一定的步數(shù)抽樣。2.3.2模擬退火算法的計算機(jī)實現(xiàn)69步驟7：退溫函數(shù)用于在外循環(huán)中修改溫度值。最常用的是指數(shù)退溫函數(shù)：

tk+1=

tk

為退溫速率，0<

<l，

大小可以不斷變化。2.3.2模擬退火算法的計算機(jī)實現(xiàn)70步驟8：外循環(huán)終止準(zhǔn)那么〔算法終止準(zhǔn)那么〕用于決定算法何時結(jié)束。設(shè)置溫度終值te是一種簡單的方法，SA算法的收斂性理論中要求te趨于零，這顯然不實際。通常的做法包括：設(shè)置終止溫度的閾值；設(shè)置外循環(huán)迭代次數(shù)；算法搜索到的最優(yōu)值連續(xù)假設(shè)干步保持不變；檢驗系統(tǒng)熵是否穩(wěn)定。2.3.2模擬退火算法的計算機(jī)實現(xiàn)712.3.3模擬退火算法求解TSP問題模擬退火算法編碼最常用策略：路徑編碼直接采用城市在路徑中的位置來構(gòu)造用于優(yōu)化的狀態(tài)。例：九城市TSP問題，路徑：5-4-1-7-9-8-6-2-3路徑編碼：(541798623)72狀態(tài)產(chǎn)生函數(shù)對于基于路徑編碼的SA狀態(tài)產(chǎn)生函數(shù)操作，可設(shè)計為：互換操作逆序操作插入操作例：狀態(tài)為(541798623)，兩隨機(jī)位置為2，6互換操作結(jié)果：(581794623)逆序操作結(jié)果：(589714623)插入操作結(jié)果：(584179623)2.3.3模擬退火算法求解TSP問題73SA通過概率判斷來接受新狀態(tài)，在局部極小解處有時機(jī)跳出，并最終趨于全局最優(yōu)。理論上，初溫充分高、降溫足夠慢、每一溫度下抽樣足夠長、最終溫度趨于零時，算法以概率1收斂到全局最優(yōu)解。SA的參數(shù)選擇是一個難題，通常只能依據(jù)一定的啟發(fā)式準(zhǔn)那么或大量的實驗加以選取。2.3.4模擬退火算法的特點(diǎn)2.4群智能算法及其應(yīng)用2.4.1群智能算法概述2.4.2蟻群算法及應(yīng)用2.4.3粒子群算法及應(yīng)用2.4.4魚群算法及應(yīng)用2.4.5鳥群算法應(yīng)用2.4.6貓群算法及應(yīng)用742.4.1群智能算法概述一、生物群體的啟示二、群智能的概念三、群智能的意義和開展前景四、群智能算法與進(jìn)化計算的異同五、群智能算法的分類2.4.1群智能算法概述一、生物群體的啟示鳥群通過協(xié)作進(jìn)行捕食；魚聚集成群可以有效的逃避捕食者；房間偏僻角落里的蛋糕總會先被螞蟻發(fā)現(xiàn)；頭腦簡單的蜜蜂卻能構(gòu)造出世界上最完美的建筑物。76一、生物群體的啟示生物群中的每個個體只有簡單的信息處理能力和行為能力鳥群：飛行，捕食，避碰……昆蟲：爬行，覓食，產(chǎn)生信息素……群體中各個個體之間可以進(jìn)行信息交互。鳥群：視覺，聽覺，磁場……昆蟲：感知信息素……群體的能力要遠(yuǎn)遠(yuǎn)超出個體能力的簡單疊加。信息感知能力、分工協(xié)作能力、適應(yīng)生存能力2.4.1群智能算法概述772.4.1群智能算法的概述二、群智能〔SwarmIntelligence,SI〕的概念概念 把群居昆蟲的集體行為稱作“群智能〞〔“群體智能〞、“群集智能〞、“集群智能〞等〕特點(diǎn) 個體的行為很簡單，但當(dāng)它們一起協(xié)同工作時，卻能夠突現(xiàn)出非常復(fù)雜〔智能〕的行為特征。1.群智能概念的開展過程分子自動機(jī)系統(tǒng)中提出。分子自動機(jī)中的主體在一維或二維網(wǎng)格空間中與相鄰個體相互作用，從而實現(xiàn)自組織?！猙yBeni(貝尼)，Hackwood(哈克伍德)任何一種由昆蟲群體或其它動物社會行為機(jī)制而激發(fā)設(shè)計出的算法或分布式解決問題的策略均屬于群智能?！猙yBonabeau(博納博)、Dorigo(杜里戈)&Theraula無智能或簡單智能的主體通過任何形式的聚集協(xié)同而表現(xiàn)出智能行為的特性。 ——byBonabeau2.4.1群智能算法概述792.定義SI的五條根本原那么〔byMarkMillonas1994)ProximityPrinciple:群內(nèi)個體具有能執(zhí)行簡單的時間或空間上的評估和計算的能力。QualityPrinciple:群內(nèi)個體能對環(huán)境(包括群內(nèi)其它個體)的關(guān)鍵性因素的變化做出響應(yīng)。PrincipleofDiverseResponse:群內(nèi)不同個體對環(huán)境中的某一變化所表現(xiàn)出的響應(yīng)行為具有多樣性。2.4.1群智能算法概述802.定義SI的五條根本原那么〔byMarkMillonas1994)StabilityPrinciple:不是每次環(huán)境的變化都會導(dǎo)致整個群體的行為模式的改變。AdaptabilityPrinciple:環(huán)境所發(fā)生的變化中，假設(shè)出現(xiàn)群體值得付出代價的改變機(jī)遇，群體必須能夠改變其行為模式。2.4.1群智能算法概述81三、SI的意義和開展前景 群智能依靠的是概率搜索算法。雖然概率搜索算法通常要采用較多的評價函數(shù)，但與梯度法及傳統(tǒng)的演化算法相比，主要優(yōu)點(diǎn)為：無集中控制約束，不會因個別個體的故障影響整個問題的求解，確保了系統(tǒng)具備更強(qiáng)的魯棒性。以非直接的信息交流方式確保了系統(tǒng)的擴(kuò)展性。并行分布式算法模型，可充分利用多處理器。對問題定義的連續(xù)性無特殊要求。2.4.1群智能算法概述靈活性：群體可以適應(yīng)隨時變化的環(huán)境；自我組織：活動既不受中央控制，也不受局部監(jiān)管。易于實現(xiàn)算法中僅涉及各種根本的數(shù)學(xué)操作。數(shù)據(jù)處理過程對CPU和內(nèi)存的要求不高。只需要目標(biāo)函數(shù)的輸出值，不需要它的梯度信息。2.4.1群智能算法概述在沒有集中控制且不提供全局模型的前提下，群智能的思路為尋找復(fù)雜的分布式問題求解方案提供了根底。已完成的群智能理論和應(yīng)用方法研究證明群智能方法能夠有效解決大多數(shù)全局優(yōu)化問題群智能潛在的并行性和分布式特點(diǎn)為處理大量的、以數(shù)據(jù)庫形式存在的數(shù)據(jù)提供了技術(shù)保證。2.4.1群智能算法概述無論從理論研究還是應(yīng)用研究的角度分析，群智能理論及其應(yīng)用研究都是有重要學(xué)術(shù)意義和現(xiàn)實價值。群智能已成為有別于傳統(tǒng)人工智能中連接主義和符號主義的一種新的關(guān)于智能的描述方法。作為一種新興的演化計算技術(shù)，群智能已成為研究焦點(diǎn)，它與人工生命，特別是進(jìn)化策略以及遺傳算法有著極為特殊的關(guān)系。2.4.1群智能算法概述四、群智能算法與進(jìn)化計算的異同SI與EC的相同點(diǎn)都研究個體與群體的關(guān)系都存在個體之間的信息傳遞都是為了解決實際問題，而非單純的模擬自然現(xiàn)象都屬于隨機(jī)搜索算法SI與EC的不同點(diǎn)SI模擬的是個體之間的協(xié)同作用EC模擬的是適者生存的自然選擇機(jī)制。2.4.1群智能算法的概述2.4.1群智能算法的概述五、群智能算法的分類廣義的群智能算法包括：粒子群算法：模擬鳥群覓食行為蟻群算法：模擬蟻群覓食行為魚群算法：模擬魚群的覓食、聚群及追尾行為免疫算法：模擬生物免疫系統(tǒng)工作機(jī)理細(xì)菌覓食算法：模擬大腸桿菌覓食行為混合算法：多種群智能算法的結(jié)合一、蟻群算法起源二、蟻群算法的原理分析三、蟻群算法與TSP問題2.4.2蟻群算法及應(yīng)用2.4.2蟻群算法及應(yīng)用一、蟻群算法起源1992年，意大利學(xué)者Dorigo從生物進(jìn)化的機(jī)制中受到啟發(fā)，在其博士論文中提出螞蟻系統(tǒng)(AntSystem)，模擬自然界螞蟻搜索路徑的行為。隨后，Dorigo等人進(jìn)一步將螞蟻算法開展為一種通用的優(yōu)化技術(shù)----蟻群優(yōu)化(AntColonyOptimization,ACO)。從Dorigo在90年代最早提出AS，并將其應(yīng)用于解決TSP問題開始，根本的蟻群算法得到了不斷的開展和完善，并在其他許多實際優(yōu)化問題求解中進(jìn)一步得到了驗證。螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D點(diǎn)?？呻S機(jī)選擇的路線：ABD或ACD。設(shè)初始時每條路線分配一只螞蟻，每單位時間行走一步上圖為經(jīng)過9個時間單位時的情形：走ABD的螞蟻到達(dá)終點(diǎn)，而走ACD的螞蟻剛好走到C點(diǎn)，為一半路程。2.4.2蟻群算法及應(yīng)用簡化的螞蟻尋食過程：本圖為從開始算起，經(jīng)過18個時間單位時的情形：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A走ACD的螞蟻剛好走到D點(diǎn)。2.4.2蟻群算法及應(yīng)用簡化的螞蟻尋食過程：簡化的螞蟻尋食過程：設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個單位。36個時間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點(diǎn)取得了食物。ABD的路線往返了2趟，每一處的信息素為4個單位ACD的路線往返了1趟，每一處的信息素為2個單位信息素比值為2:1按信息素指導(dǎo)，蟻群在ABD路線上增派一只螞蟻(共2只)，ACD路線上仍然是一只螞蟻。2.4.2蟻群算法及應(yīng)用簡化的螞蟻尋食過程：72個時間單位后，兩條線路上的信息素單位積累為12和4，比值為3:1。假設(shè)按以上規(guī)那么繼續(xù)，蟻群在ABD路線上再增派一只螞蟻(共3只)，ACD路線上仍然是一只螞蟻。再36個時間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。假設(shè)繼續(xù)進(jìn)行，按信息素指導(dǎo)，最終所有螞蟻會放棄ACD路線，都選擇ABD路線，這就是正反響效應(yīng)。2.4.2蟻群算法及應(yīng)用 最初提出的AS有三種版本：Ant-density、Ant-quantity、Ant-cycle前兩種算法中，螞蟻在兩個位置節(jié)點(diǎn)間每移動一次后即更新信息素。Ant-cycle中，所有螞蟻都完成了自己的行程后，才對信息素進(jìn)行更新，而且每個螞蟻所釋放的信息素被表達(dá)為反映相應(yīng)行程質(zhì)量的函數(shù)。2.4.2蟻群算法及應(yīng)用與其它各種通用的啟發(fā)式算法相比，在不大于75城市的TSP中，AS的求解能力比較理想。但是當(dāng)問題規(guī)模擴(kuò)展時，AS的解題能力大幅度下降。AS改進(jìn)版共同點(diǎn)：增強(qiáng)螞蟻搜索過程中對最優(yōu)解的探索能力差異：搜索控制策略2.4.2蟻群算法及應(yīng)用其后的ACO研究工作主要都集中在AS性能的改進(jìn)方面。較較早的一種改進(jìn)是精英策略(ElitistStrategy)，其思想是：在算法開始后，對所有已發(fā)現(xiàn)的最好路徑給予額外增強(qiáng)，并將隨后與之對應(yīng)的行程記為Tgb(全局最優(yōu)行程)，當(dāng)進(jìn)行信息素更新時，對這些行程予以加權(quán)，同時將經(jīng)過這些行程的螞蟻記為“精英〞，從而增大較好行程的選擇時機(jī)。這種改進(jìn)型算法能以更快的速度獲得更好的解。但是假設(shè)選擇的精英過多，那么算法會由于較早收斂于局部次優(yōu)解，而導(dǎo)致搜索的過早停滯。2.4.2蟻群算法及應(yīng)用蟻群算法能夠用于解決大多數(shù)優(yōu)化問題或者能夠被轉(zhuǎn)化為優(yōu)化求解的問題，是一種有開展前景的算法。目前，其應(yīng)用領(lǐng)域已擴(kuò)展到多目標(biāo)優(yōu)化數(shù)據(jù)分類數(shù)據(jù)聚類模式識別生物系統(tǒng)建模流程規(guī)劃信號處理機(jī)器人控制決策支持仿真和系統(tǒng)辯識2.4.2蟻群算法及應(yīng)用二、蟻群算法的原理螞蟻尋食過程：尋找路徑時，在路徑上釋放出一種特殊的信息素。碰到?jīng)]有走過的路口，隨機(jī)挑選一條路徑，并釋放出與路徑長度有關(guān)的信息素。路徑越長，釋放的激素濃度越低。后來的螞蟻再次碰到這個路口的時候，選擇激素濃度較高路徑概率相對較大。正反響：最優(yōu)路徑上激素濃度越來越大，其它路徑上激素濃度隨時間的流逝而消減。最終整個蟻群找出最優(yōu)路徑。2.4.2蟻群算法及應(yīng)用2.4.2蟻群算法及應(yīng)用自然蟻群與人工蟻群算法：人工蟻群中把具有簡單功能的工作單元看作螞蟻。相似處：優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。區(qū)別：人工蟻群能記憶已訪問過的節(jié)點(diǎn)，在選擇下條路徑時是按一定算法規(guī)律有意識地尋找最短路徑。如，TSP問題中可預(yù)先知道當(dāng)前城市到下一個目的地的距離。2.4.2蟻群算法及應(yīng)用三、蟻群算法與TSP問題初始的蟻群算法是基于圖的蟻群算法(graph-basedantsystem，GBAS)，2000年由Gutjahr(古特雅爾)在FutureGenerationComputingSystems提出。TSP問題表示為N個城市的有向圖：G=(N,A)目標(biāo)函數(shù)w=(i1,i2,…,in)為城市1,2,…,n的一個排列(dij)n

n為城市間距離矩陣設(shè)m只螞蟻在圖的相鄰節(jié)點(diǎn)間移動，協(xié)作異步地得到解。螞蟻計算出下一步所有可達(dá)節(jié)點(diǎn)的一步轉(zhuǎn)移概率，并按此概率實現(xiàn)一步移動，依此往復(fù)。一步轉(zhuǎn)移概率由圖中每條邊上的兩類參數(shù)決定：信息素值、可見度(即先驗值)。信息素的更新有2種方式：揮發(fā)——所有路徑上信息素以一定比率減少增強(qiáng)——給評價值“好〞(有螞蟻走過)的邊增加信息素2.4.2蟻群算法及應(yīng)用STEP0

對n個城市的TSP問題，城市間的距離矩陣為：(dij)n

n給TSP圖中的每一條弧(i,j)賦信息素初值：

ij(0)=1/|A||A|：表示圖中弧(i,j)的數(shù)目，即矩陣(dij)n

n中不為零的數(shù)；設(shè)有m只螞蟻工作，都從同一城市i0出發(fā)當(dāng)前最好解是：w*=(1,2,…,n)目標(biāo)函數(shù)：2.4.2蟻群算法及應(yīng)用STEP1(外循環(huán))假設(shè)滿足算法停止規(guī)那么，停止計算，輸出計算得到的最好解給定外循環(huán)的最大數(shù)目，說明有足夠的螞蟻工作；當(dāng)前最優(yōu)解連續(xù)K次相同而停止，K是給定的整數(shù)，表示算法已收斂；給定優(yōu)化問題的下界和誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時，算法終止。否那么使螞蟻s(1sm)從起點(diǎn)i0出發(fā)，用L(s)表示螞蟻s行走的城市集合，初始L(s)為空集。2.4.2蟻群算法及應(yīng)用STEP2(內(nèi)循環(huán))按螞蟻1sm的順序分別計算在城市i，假設(shè)L(s)=N或{l|(i,l)A,lL(s)}=，完成螞蟻s的計算。否那么，假設(shè)T={l|(i,l)A,lL(s)}-{i0}，以概率 到達(dá)j，L(s)=L(s){j}，il=j假設(shè)L(s)N且T=，那么到達(dá)i0， L(s)=L(s){i0}，il=i0 重復(fù)STEP22.4.2蟻群算法及