計(jì)算群體智能

計(jì)算群體智能1、優(yōu)化方法遺傳算法概述傳統(tǒng)的優(yōu)化方法（局部?jī)?yōu)化）共軛梯度法、擬牛頓法、單純形方法全局優(yōu)化方法

GA、漫步法（RandomWalk）、模擬退火法

第2頁(yè),共102頁(yè)，2024年2月25日，星期天2、遺傳算法優(yōu)點(diǎn)

遺傳算法（GA）模擬自然選擇和自然遺傳過(guò)程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個(gè)體，利用遺傳算子(選擇、交叉和變異)對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過(guò)程，直到滿足某種收斂指標(biāo)為止。其遺傳進(jìn)化操作過(guò)程簡(jiǎn)單，容易理解。

第3頁(yè),共102頁(yè)，2024年2月25日，星期天遺傳算法基本原理1、基本思想

模擬自然界優(yōu)勝劣汰的進(jìn)化現(xiàn)象，把搜索空間映射為遺傳空間，把可能的解編碼成一個(gè)向量——染色體，向量的每個(gè)元素稱為基因。通過(guò)不斷計(jì)算各染色體的適應(yīng)值，選擇最好的染色體，獲得最優(yōu)解。2、遺傳算法的基本運(yùn)算⑴選擇運(yùn)算⑵交換操作⑶變異第4頁(yè),共102頁(yè)，2024年2月25日，星期天選擇運(yùn)算

從舊的種群中選擇適應(yīng)度高的染色體，放入匹配集（緩沖區(qū)），為以后染色體交換、變異，產(chǎn)生新的染色體作準(zhǔn)備。選擇方法——適應(yīng)度比例法（轉(zhuǎn)輪法）某染色體被選的概率：Pcxi為種群中第i個(gè)染色體，f(xi)為第i個(gè)染色體的適應(yīng)度值。第5頁(yè),共102頁(yè)，2024年2月25日，星期天具體步驟1）計(jì)算各染色體適應(yīng)度值2）累計(jì)所有染色體適應(yīng)度值，記錄中間累加值S-mid和最后累加值sum=∑f(xi)3）產(chǎn)生一個(gè)隨機(jī)數(shù)N，0〈N〈sum4）選擇對(duì)應(yīng)中間累加值S-mid的第一個(gè)染色體進(jìn)入交換集5）重復(fù)（3）和（4），直到獲得足夠的染色體。第6頁(yè),共102頁(yè)，2024年2月25日，星期天舉例：

⒈具有6個(gè)染色體的二進(jìn)制編碼、適應(yīng)度值、Pc累計(jì)值。

染色體的適應(yīng)度和所占的比例用轉(zhuǎn)輪方法進(jìn)行選擇第7頁(yè),共102頁(yè)，2024年2月25日，星期天染色體被選的概率染色體編號(hào)12345678910適應(yīng)度8217721211737被選概率0.10.020.220.090.020.160.140.090.030.09適應(yīng)度累計(jì)8

10

2734364859666976被選的染色體個(gè)數(shù)隨機(jī)數(shù)2349761312757所選染色體號(hào)碼37103137第8頁(yè),共102頁(yè)，2024年2月25日，星期天交換操作

方法:隨機(jī)選擇二個(gè)染色體(雙親染色體),隨機(jī)指定一點(diǎn)或多點(diǎn),進(jìn)行交換,可得二個(gè)新的染色體(子輩染色體).新的子輩染色體:A’

11010001

B’

01011110第9頁(yè),共102頁(yè)，2024年2月25日，星期天變異模擬生物在自然界環(huán)境變化,引起基因的突變.在染色體二進(jìn)制編碼中,1變成0;或0變成1.突變產(chǎn)生染色體的多樣性,避免進(jìn)化中早期成熟,陷入局部極值點(diǎn),突變的概率很低.第10頁(yè),共102頁(yè)，2024年2月25日，星期天GA流程第11頁(yè),共102頁(yè)，2024年2月25日，星期天簡(jiǎn)單遺傳算法（GA）的基本參數(shù)①種群規(guī)模P:參與進(jìn)化的染色體總數(shù).②代溝G:二代之間不相同的染色體數(shù)目,無(wú)重疊G=1;有重疊0<G<1③選擇方法:轉(zhuǎn)輪法,精英選擇法,競(jìng)爭(zhēng)法.④交換率:Pc一般為60~100%.⑤變異率:Pm一般為0.1~10%第12頁(yè),共102頁(yè)，2024年2月25日，星期天實(shí)例1、產(chǎn)生初始種群00011000000101111001000000010110011101001010101010（8）（5）（2）（10）（7）1110010110100101101111000000011001110100000101001（12）（5）（19）（10）（14）2、計(jì)算適應(yīng)度第13頁(yè),共102頁(yè)，2024年2月25日，星期天3、選擇個(gè)體染色體適應(yīng)度選擇概率累積概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488＋5＋2＋10＋7＋12＋5＋19＋10＋140.0869570.05434858＋5＋2＋10＋7＋12＋5＋19＋10＋140.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174第14頁(yè),共102頁(yè)，2024年2月25日，星期天3、選擇個(gè)體染色體適應(yīng)度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.000000第15頁(yè),共102頁(yè)，2024年2月25日，星期天3、選擇在0～1之間產(chǎn)生一個(gè)隨機(jī)數(shù)：0.5459290.7845670.4469300.5078930.2911980.7163400.2709010.3714350.854641個(gè)體染色體適應(yīng)度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0869570.0543480.1413040.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.2717390.3478260.4782610.5326090.7391300.8478261.0000000.163043淘淘汰第16頁(yè),共102頁(yè)，2024年2月25日，星期天4、交叉000110000011100101101100000001100111010010101010101110010110100101101110011101001100000001000101001100011000001110010110110000000110011101000001111010000001011011110000101101011011110000100111010000011001110100110000000110101010001010010011第17頁(yè),共102頁(yè)，2024年2月25日，星期天5、變異0001100000111001011011000000011001110100101010101011100101101001011011110000000110011101000001010011000111101000000101101111000010110101101111000010011101000001100111010011000000011010101000101001001100011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100110001111010000001011011110000101101011011110000100101010000011001110100110000000110101010001010010011第18頁(yè),共102頁(yè)，2024年2月25日，星期天6、至下一代，適應(yīng)度計(jì)算→選擇→交叉→變異，直至滿足終止條件。第19頁(yè),共102頁(yè)，2024年2月25日，星期天遺傳算法的應(yīng)用及一些問(wèn)題1、遺傳算法的應(yīng)用領(lǐng)域（1）組合優(yōu)化（2）函數(shù)優(yōu)化（3）自動(dòng)控制（4）生產(chǎn)調(diào)度（5）圖像處理（6）機(jī)器學(xué)習(xí)（7）人工生命（8）數(shù)據(jù)挖掘2、遺傳算法在應(yīng)用中的一些問(wèn)題1）知識(shí)的編碼

二進(jìn)制和十進(jìn)制的比較：二進(jìn)制有更多圖式和更大的搜索范圍；十進(jìn)制更接近于實(shí)際操作。第20頁(yè),共102頁(yè)，2024年2月25日，星期天

2）適應(yīng)度函數(shù)

適應(yīng)度函數(shù)值必須非負(fù)，根據(jù)情況做適當(dāng)?shù)奶幚怼?/p>

第21頁(yè),共102頁(yè)，2024年2月25日，星期天如圖第22頁(yè),共102頁(yè)，2024年2月25日，星期天3）全局最優(yōu)和收斂性。

根據(jù)圖式定理，對(duì)于具有“欺騙性”函數(shù)，GA有可能落入局部最優(yōu)點(diǎn)。舉例：3位欺騙函數(shù)第23頁(yè),共102頁(yè)，2024年2月25日，星期天4.2粒子群算法第24頁(yè),共102頁(yè)，2024年2月25日，星期天

粒子群優(yōu)化算法（PSO）是一種進(jìn)化計(jì)算技術(shù)（evolutionarycomputation）,由Eberhart博士和kennedy博士于1995年提出(KennedyJ，EberhartR．

Particleswarmoptimization．ProceedingsoftheIEEEInternationalConferenceonNeuralNetworks．1995．1942~1948.)。源于對(duì)鳥(niǎo)群捕食的行為研究。粒子群優(yōu)化算法的基本思想是通過(guò)群體中個(gè)體之間的協(xié)作和信息共享來(lái)尋找最優(yōu)解．

PSO的優(yōu)勢(shì)在于簡(jiǎn)單容易實(shí)現(xiàn)并且沒(méi)有許多參數(shù)的調(diào)節(jié)。目前已被廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制以及其他遺傳算法的應(yīng)用領(lǐng)域。

第25頁(yè),共102頁(yè)，2024年2月25日，星期天設(shè)想這樣一個(gè)場(chǎng)景：一群鳥(niǎo)在隨機(jī)的搜索食物。在這個(gè)區(qū)域里只有一塊食物，所有的鳥(niǎo)都不知道食物在那。但是它們知道自己當(dāng)前的位置距離食物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略是什么？最簡(jiǎn)單有效的就是搜尋目前離食物最近的鳥(niǎo)的周圍區(qū)域。第26頁(yè),共102頁(yè)，2024年2月25日，星期天

抽象：鳥(niǎo)被抽象為沒(méi)有質(zhì)量和體積的微粒(點(diǎn))，并延伸到N維空間，粒子I在N維空間的位置表示為矢量Xi＝(x1，x2，…，xN)，飛行速度表示為矢量Vi＝(v1，v2，…，vN)．每個(gè)粒子都有一個(gè)由目標(biāo)函數(shù)決定的適應(yīng)值(fitnessvalue)，并且知道自己到目前為止發(fā)現(xiàn)的最好位置(pbest)和現(xiàn)在的位置Xi．這個(gè)可以看作是粒子自己的飛行經(jīng)驗(yàn)．除此之外，每個(gè)粒子還知道到目前為止整個(gè)群體中所有粒子發(fā)現(xiàn)的最好位置(gbest)(gbest是pbest中的最好值)．這個(gè)可以看作是粒子同伴的經(jīng)驗(yàn)．粒子就是通過(guò)自己的經(jīng)驗(yàn)和同伴中最好的經(jīng)驗(yàn)來(lái)決定下一步的運(yùn)動(dòng)。

第27頁(yè),共102頁(yè)，2024年2月25日，星期天PSO初始化為一群隨機(jī)粒子(隨機(jī)解)。然后通過(guò)迭代找到最優(yōu)解。在每一次的迭代中，粒子通過(guò)跟蹤兩個(gè)“極值”(pbest,gbest)來(lái)更新自己。在找到這兩個(gè)最優(yōu)值后，粒子通過(guò)下面的公式來(lái)更新自己的速度和位置。(1)式(2)式在式(1)、(2)中，i＝1，2，…，M，M是該群體中粒子的總數(shù)。第28頁(yè),共102頁(yè)，2024年2月25日，星期天Vi

是粒子的速度；pbest和gbest如前定義；rand()是介于（0、1）之間的隨機(jī)數(shù)；Xi是粒子的當(dāng)前位置。c1和c2是學(xué)習(xí)因子，通常取c1＝c2＝2在每一維，粒子都有一個(gè)最大限制速度Vmax，如果某一維的速度超過(guò)設(shè)定的Vmax，那么這一維的速度就被限定為Vmax。（Vmax

>0）從社會(huì)學(xué)的角度來(lái)看，公式(1)的第一部分稱為記憶項(xiàng)，表示上次速度大小和方向的影響；公式第二部分稱為自身認(rèn)知項(xiàng)，是從當(dāng)前點(diǎn)指向粒子自身最好點(diǎn)的一個(gè)矢量，表示粒子的動(dòng)作來(lái)源于自己經(jīng)驗(yàn)的部分；公式的第三部分稱為群體認(rèn)知項(xiàng)，是一個(gè)從當(dāng)前點(diǎn)指向種群最好點(diǎn)的矢量，反映了粒子間的協(xié)同合作和知識(shí)共享。粒子就是通過(guò)自己的經(jīng)驗(yàn)和同伴中最好的經(jīng)驗(yàn)來(lái)決定下一步的運(yùn)動(dòng)。第29頁(yè),共102頁(yè)，2024年2月25日，星期天1998年shi等人在進(jìn)化計(jì)算的國(guó)際會(huì)議上發(fā)表了一篇論文《Amodifiedparticleswarmoptimizer》對(duì)前面的公式(1)進(jìn)行了修正。引入慣性權(quán)重因子。（3）式非負(fù)，稱為慣性因子。公式(2)和(3)被視為標(biāo)準(zhǔn)pso算法。第30頁(yè),共102頁(yè)，2024年2月25日，星期天標(biāo)準(zhǔn)PSO算法的流程：Step1:初始化一群微粒(群體規(guī)模為m)，包括隨機(jī)位置和速度；Step2:評(píng)價(jià)每個(gè)微粒的適應(yīng)度；Step3:對(duì)每個(gè)微粒，將其適應(yīng)值與其經(jīng)過(guò)的最好位置pbest作比較，如果較好，則將其作為當(dāng)前的最好位置pbest;Step4:對(duì)每個(gè)微粒，將其適應(yīng)值與其經(jīng)過(guò)的最好位置gbest作比較，如果較好，則將其作為當(dāng)前的最好位置gbest;Step5:根據(jù)(2)、(3)式調(diào)整微粒速度和位置；Step6：未達(dá)到結(jié)束條件則轉(zhuǎn)Step2。迭代終止條件根據(jù)具體問(wèn)題一般選最大迭代次數(shù)或(和)微粒群迄今為止搜索到的最優(yōu)位置滿足預(yù)定最小適應(yīng)閾值。第31頁(yè),共102頁(yè)，2024年2月25日，星期天方程(2)和(3)中pbest和gbest分別表示微粒群的局部和全局最優(yōu)位置，當(dāng)C1＝0時(shí)，則粒子沒(méi)有了認(rèn)知能力，變?yōu)橹挥猩鐣?huì)的模型(social-only):被稱為全局PSO算法.粒子有擴(kuò)展搜索空間的能力，具有較快的收斂速度，但由于缺少局部搜索，對(duì)于復(fù)雜問(wèn)題比標(biāo)準(zhǔn)PSO更易陷入局部最優(yōu)。當(dāng)C2＝0時(shí)，則粒子之間沒(méi)有社會(huì)信息，模型變?yōu)橹挥姓J(rèn)知(cognition-only)模型：被稱為局部PSO算法。由于個(gè)體之間沒(méi)有信息的交流，整個(gè)群體相當(dāng)于多個(gè)粒子進(jìn)行盲目的隨機(jī)搜索，收斂速度慢，因而得到最優(yōu)解的可能性小。第32頁(yè),共102頁(yè)，2024年2月25日，星期天參數(shù)有：群體規(guī)模m，慣性因子，學(xué)習(xí)因子c1和c2最大速度Vmax，迭代次數(shù)Gk。群體規(guī)模m一般取20～40，對(duì)較難或特定類別的問(wèn)題可以取到100～200。最大速度Vmax決定當(dāng)前位置與最好位置之間的區(qū)域的分辨率(或精度)。如果太快，則粒子有可能越過(guò)極小點(diǎn);如果太慢，則粒子不能在局部極小點(diǎn)之外進(jìn)行足夠的探索，會(huì)陷入到局部極值區(qū)域內(nèi)。這種限制可以達(dá)到防止計(jì)算溢出、決定問(wèn)題空間搜索的粒度的目的。參數(shù)分析第33頁(yè),共102頁(yè)，2024年2月25日，星期天權(quán)重因子：包括慣性因子和學(xué)習(xí)因子c1和c2。使粒子保持著運(yùn)動(dòng)慣性，使其具有擴(kuò)展搜索空間的趨勢(shì)，有能力探索新的區(qū)域。C1和c2代表將每個(gè)粒子推向Pbest和gbest位置的統(tǒng)計(jì)加速項(xiàng)的權(quán)值。較低的值允許粒子在被拉回之前可以在目標(biāo)區(qū)域外徘徊，較高的值導(dǎo)致粒子突然地沖向或越過(guò)目標(biāo)區(qū)域。

如果令c1＝c2＝0，粒子將一直以當(dāng)前速度的飛行，直到邊界。很難找到最優(yōu)解。如果＝0，則速度只取決于當(dāng)前位置和歷史最好位置，速度本身沒(méi)有記憶性。假設(shè)一個(gè)粒子處在全局最好位置，它將保持靜止，其他粒子則飛向它的最好位置和全局最好位置的加權(quán)中心。粒子將收縮到當(dāng)前全局最好位置。在加上第一部分后，粒子有擴(kuò)展搜索空間的趨勢(shì)，這也使得w的作用表現(xiàn)為針對(duì)不同的搜索問(wèn)題，調(diào)整算法的全局和局部搜索能力的平衡。較大時(shí)，具有較強(qiáng)的全局搜索能力；較小時(shí)，具有較強(qiáng)的局部搜索能力。第34頁(yè),共102頁(yè)，2024年2月25日，星期天基本PSO是用于實(shí)值連續(xù)空間，然而許多實(shí)際問(wèn)題是組合優(yōu)化問(wèn)題，因而提出離散形式的PSO。速度和位置更新式為：thenelse其中：為sigmoid函數(shù)離散二進(jìn)制PSO第35頁(yè),共102頁(yè)，2024年2月25日，星期天4.3模擬退火算法

第36頁(yè),共102頁(yè)，2024年2月25日，星期天4.3.1模擬退火算法及模型

算法的提出

模擬退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。算法的目的解決NP復(fù)雜性問(wèn)題；克服優(yōu)化過(guò)程陷入局部極??；克服初值依賴性。4.3.1.1物理退火過(guò)程第37頁(yè),共102頁(yè)，2024年2月25日，星期天物理退火過(guò)程

什么是退火：退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。第38頁(yè),共102頁(yè)，2024年2月25日，星期天物理退火過(guò)程

加溫過(guò)程——增強(qiáng)粒子的熱運(yùn)動(dòng)，消除系統(tǒng)原先可能存在的非均勻態(tài)；等溫過(guò)程——對(duì)于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡態(tài)；冷卻過(guò)程——使粒子熱運(yùn)動(dòng)減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。第39頁(yè),共102頁(yè)，2024年2月25日，星期天數(shù)學(xué)表述

在溫度T，分子停留在狀態(tài)r滿足Boltzmann概率分布第40頁(yè),共102頁(yè)，2024年2月25日，星期天數(shù)學(xué)表述在同一個(gè)溫度T，選定兩個(gè)能量E1<E2，有在同一個(gè)溫度，分子停留在能量小的狀態(tài)的概率比停留在能量大的狀態(tài)的概率要大。<1>0第41頁(yè),共102頁(yè)，2024年2月25日，星期天數(shù)學(xué)表述

若|D|為狀態(tài)空間D中狀態(tài)的個(gè)數(shù)，D0是具有最低能量的狀態(tài)集合：當(dāng)溫度很高時(shí)，每個(gè)狀態(tài)概率基本相同，接近平均值1/|D|；狀態(tài)空間存在超過(guò)兩個(gè)不同能量時(shí)，具有最低能量狀態(tài)的概率超出平均值1/|D|；當(dāng)溫度趨于0時(shí)，分子停留在最低能量狀態(tài)的概率趨于1。能量最低狀態(tài)非能量最低狀態(tài)第42頁(yè),共102頁(yè)，2024年2月25日，星期天Metropolis準(zhǔn)則（1953）——以概率接受新?tīng)顟B(tài)固體在恒定溫度下達(dá)到熱平衡的過(guò)程可以用MonteCarlo方法（計(jì)算機(jī)隨機(jī)模擬方法）加以模擬，雖然該方法簡(jiǎn)單，但必須大量采樣才能得到比較精確的結(jié)果，計(jì)算量很大。第43頁(yè),共102頁(yè)，2024年2月25日，星期天若在溫度T，當(dāng)前狀態(tài)i→新?tīng)顟B(tài)j

若Ej<Ei，則接受j為當(dāng)前狀態(tài)；否則，若概率p=exp[-(Ej-Ei)/kBT]大于[0,1)區(qū)間的隨機(jī)數(shù)，則仍接受狀態(tài)j

為當(dāng)前狀態(tài)；若不成立則保留狀態(tài)i

為當(dāng)前狀態(tài)。第44頁(yè),共102頁(yè)，2024年2月25日，星期天p=exp[-(Ej-Ei)/kBT]

在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新?tīng)顟B(tài)；在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新?tīng)顟B(tài)。第45頁(yè),共102頁(yè)，2024年2月25日，星期天相似性比較

組合優(yōu)化問(wèn)題金屬物體解粒子狀態(tài)最優(yōu)解能量最低的狀態(tài)設(shè)定初溫熔解過(guò)程Metropolis抽樣過(guò)程等溫過(guò)程控制參數(shù)的下降冷卻目標(biāo)函數(shù)能量第46頁(yè),共102頁(yè)，2024年2月25日，星期天基本步驟

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

RepeatRepeat

產(chǎn)生新?tīng)顟B(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é)果。第47頁(yè),共102頁(yè)，2024年2月25日，星期天影響優(yōu)化結(jié)果的主要因素

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

RepeatRepeat

產(chǎn)生新?tīng)顟B(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)則初始溫度第48頁(yè),共102頁(yè)，2024年2月25日，星期天4.3.2模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)原則

產(chǎn)生的候選解應(yīng)遍布全部解空間方法

在當(dāng)前狀態(tài)的鄰域結(jié)構(gòu)內(nèi)以一定概率方式（均勻分布、正態(tài)分布、指數(shù)分布等）產(chǎn)生4.3.2.1狀態(tài)產(chǎn)生函數(shù)第49頁(yè),共102頁(yè)，2024年2月25日，星期天原則

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

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

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

具體形式對(duì)算法影響不大一般采用min[1,exp(-?C/t)]4.3.2.2狀態(tài)接受函數(shù)第50頁(yè),共102頁(yè)，2024年2月25日，星期天收斂性分析

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

初溫越大，獲得高質(zhì)量解的機(jī)率越大，但花費(fèi)較多的計(jì)算時(shí)間；4.3.2.3初溫第51頁(yè),共102頁(yè)，2024年2月25日，星期天方法

（1）均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值得方差為初溫；（2）隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差，根據(jù)差值，利用一定的函數(shù)確定初溫；（3）利用經(jīng)驗(yàn)公式。第52頁(yè),共102頁(yè)，2024年2月25日，星期天時(shí)齊算法的溫度下降函數(shù)

（1），α越接近1溫度下降越慢，且其大小可以不斷變化；（2），其中t0為起始溫度，K為算法溫度下降的總次數(shù)。4.3.2.4溫度更新函數(shù)第53頁(yè),共102頁(yè)，2024年2月25日，星期天非時(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ù)抽樣。4.3.2.5內(nèi)循環(huán)終止準(zhǔn)則第54頁(yè),共102頁(yè)，2024年2月25日，星期天常用方法

（1）設(shè)置終止溫度的閾值；（2）設(shè)置外循環(huán)迭代次數(shù)；（3）算法搜索到的最優(yōu)值連續(xù)若干步保持不變；（4）概率分析方法。4.3.2.6外循環(huán)終止準(zhǔn)則第55頁(yè),共102頁(yè)，2024年2月25日，星期天4.3.3模擬退火算法的改進(jìn)模擬退火算法的優(yōu)點(diǎn)

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

由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此優(yōu)化過(guò)程較長(zhǎng)。4.3.3.1模擬退火算法的優(yōu)缺點(diǎn)第56頁(yè),共102頁(yè)，2024年2月25日，星期天改進(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)則。4.3.3.2改進(jìn)內(nèi)容第57頁(yè),共102頁(yè)，2024年2月25日，星期天改進(jìn)的方式

（1）增加升溫或重升溫過(guò)程，避免陷入局部極小；（2）增加記憶功能（記憶“Bestsofar”狀態(tài)）；（3）增加補(bǔ)充搜索過(guò)程（以最優(yōu)結(jié)果為初始解）；（4）對(duì)每一當(dāng)前狀態(tài)，采用多次搜索策略，以概率接受區(qū)域內(nèi)的最優(yōu)狀態(tài)；（5）結(jié)合其它搜索機(jī)制的算法；（6）上述各方法的綜合。第58頁(yè),共102頁(yè)，2024年2月25日，星期天4.3.4模擬退火算法的實(shí)現(xiàn)與應(yīng)用算法流程

30城市TSP問(wèn)題（d*=423.741byDBFogel）

第59頁(yè),共102頁(yè)，2024年2月25日，星期天初始溫度的計(jì)算

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

第60頁(yè),共102頁(yè)，2024年2月25日，星期天狀態(tài)產(chǎn)生函數(shù)的設(shè)計(jì)（1）互換操作，隨機(jī)交換兩個(gè)城市的順序；（2）逆序操作，兩個(gè)隨機(jī)位置間的城市逆序；（3）插入操作，隨機(jī)選擇某點(diǎn)插入某隨機(jī)位置。283591467283591467283591467281593467283419567235981467第61頁(yè),共102頁(yè)，2024年2月25日，星期天參數(shù)設(shè)定

截止溫度tf=0.01;

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

內(nèi)循環(huán)次數(shù)L=200*CityNum;第62頁(yè),共102頁(yè)，2024年2月25日，星期天運(yùn)行過(guò)程

第63頁(yè),共102頁(yè)，2024年2月25日，星期天運(yùn)行過(guò)程

第64頁(yè),共102頁(yè)，2024年2月25日，星期天運(yùn)行過(guò)程

第65頁(yè),共102頁(yè)，2024年2月25日，星期天運(yùn)行過(guò)程

第66頁(yè),共102頁(yè)，2024年2月25日，星期天運(yùn)行過(guò)程

第67頁(yè),共102頁(yè)，2024年2月25日，星期天運(yùn)行結(jié)果

第68頁(yè),共102頁(yè)，2024年2月25日，星期天4.4蟻群算法

第69頁(yè),共102頁(yè)，2024年2月25日，星期天4.4.1蟻群優(yōu)化算法起源20世紀(jì)90年代意大利學(xué)者M(jìn)．Dorigo，V．Maniezzo，A．Colorni等從生物進(jìn)化的機(jī)制中受到啟發(fā)，通過(guò)模擬自然界螞蟻搜索路徑的行為，提出來(lái)一種新型的模擬進(jìn)化算法——

蟻群算法，是群智能理論研究領(lǐng)域的一種主要算法。用該方法求解TSP問(wèn)題、分配問(wèn)題、job-shop調(diào)度問(wèn)題，取得了較好的試驗(yàn)結(jié)果．雖然研究時(shí)間不長(zhǎng)，但是現(xiàn)在的研究顯示出，蟻群算法在求解復(fù)雜優(yōu)化問(wèn)題（特別是離散優(yōu)化問(wèn)題）方面有一定優(yōu)勢(shì)，表明它是一種有發(fā)展前景的算法．第70頁(yè),共102頁(yè)，2024年2月25日，星期天4.4.2蟻群優(yōu)化算法應(yīng)用領(lǐng)域這種方法能夠被用于解決大多數(shù)優(yōu)化問(wèn)題或者能夠轉(zhuǎn)化為優(yōu)化求解的問(wèn)題?，F(xiàn)在其應(yīng)用領(lǐng)域已擴(kuò)展到多目標(biāo)優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識(shí)別、電信管理、生物系統(tǒng)建模、流程規(guī)劃、信號(hào)處理、機(jī)器人控制、決策支持以及仿真和系統(tǒng)辯識(shí)等方面，群智能理論和方法為解決這類應(yīng)用問(wèn)題提供了新的途徑。第71頁(yè),共102頁(yè)，2024年2月25日，星期天4.4.3蟻群優(yōu)化算法研究現(xiàn)狀90年代Dorigo最早提出了蟻群優(yōu)化算法---螞蟻系統(tǒng)（AntSystem,AS）并將其應(yīng)用于解決計(jì)算機(jī)算法學(xué)中經(jīng)典的旅行商問(wèn)題（TSP）。從螞蟻系統(tǒng)開(kāi)始，基本的蟻群算法得到了不斷的發(fā)展和完善，并在TSP以及許多實(shí)際優(yōu)化問(wèn)題求解中進(jìn)一步得到了驗(yàn)證。這些AS改進(jìn)版本的一個(gè)共同點(diǎn)就是增強(qiáng)了螞蟻搜索過(guò)程中對(duì)最優(yōu)解的探索能力，它們之間的差異僅在于搜索控制策略方面。而且，取得了最佳結(jié)果的ACO是通過(guò)引入局部搜索算法實(shí)現(xiàn)的，這實(shí)際上是一些結(jié)合了標(biāo)準(zhǔn)局域搜索算法的混合型概率搜索算法，有利于提高蟻群各級(jí)系統(tǒng)在優(yōu)化問(wèn)題中的求解質(zhì)量。第72頁(yè),共102頁(yè)，2024年2月25日，星期天4.4.4蟻群算法原理蟻群算法是對(duì)自然界螞蟻的尋徑方式進(jìn)行模似而得出的一種仿生算法。螞蟻在運(yùn)動(dòng)過(guò)程中，能夠在它所經(jīng)過(guò)的路徑上留下一種稱之為外激素(pheromone)的物質(zhì)進(jìn)行信息傳遞，而且螞蟻在運(yùn)動(dòng)過(guò)程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過(guò)的螞蟻越多，則后來(lái)者選擇該路徑的概率就越大。為了說(shuō)明蟻群算法的原理，先簡(jiǎn)要介紹一下螞蟻搜尋食物的具體過(guò)程。在蟻群尋找食物時(shí)，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因?yàn)槲浵佋趯ふ衣窂綍r(shí)會(huì)在路徑上釋放出一種特殊的信息素。當(dāng)它們碰到一個(gè)還沒(méi)有走過(guò)的路口時(shí)．就隨機(jī)地挑選一條路徑前行。與此同時(shí)釋放出與路徑長(zhǎng)度有關(guān)的信息素。路徑越長(zhǎng)，釋放的激索濃度越低.當(dāng)后來(lái)的螞蟻再次碰到這個(gè)路口的時(shí)候．選擇激素濃度較高路徑概率就會(huì)相對(duì)較大。這樣形成一個(gè)正反饋。最優(yōu)路徑上的激索濃度越來(lái)越大．而其它的路徑上激素濃度卻會(huì)隨著時(shí)間的流逝而消減。最終整個(gè)蟻群會(huì)找出最優(yōu)路徑。第73頁(yè),共102頁(yè)，2024年2月25日，星期天4.4.4.1簡(jiǎn)化的螞蟻尋食過(guò)程螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D點(diǎn)，可能隨機(jī)選擇路線ABD或ACD。假設(shè)初始時(shí)每條分配路線一只螞蟻，每個(gè)時(shí)間單位行走一步，本圖為經(jīng)過(guò)9個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)，而走ACD的螞蟻剛好走到C點(diǎn)，為一半路程。第74頁(yè),共102頁(yè)，2024年2月25日，星期天本圖為從開(kāi)始算起，經(jīng)過(guò)18個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。第75頁(yè),共102頁(yè)，2024年2月25日，星期天假設(shè)螞蟻每經(jīng)過(guò)一處所留下的信息素為一個(gè)單位，則經(jīng)過(guò)36個(gè)時(shí)間單位后，所有開(kāi)始一起出發(fā)的螞蟻都經(jīng)過(guò)不同路徑從D點(diǎn)取得了食物，此時(shí)ABD的路線往返了2趟，每一處的信息素為4個(gè)單位，而ACD的路線往返了一趟，每一處的信息素為2個(gè)單位，其比值為2：1。尋找食物的過(guò)程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經(jīng)過(guò)36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為12和4，比值為3：1。若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過(guò)36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會(huì)放棄ACD路線，而都選擇ABD路線。第76頁(yè),共102頁(yè)，2024年2月25日，星期天4.4.4.2自然蟻群與人工蟻群算法基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問(wèn)題，可以構(gòu)造人工蟻群，來(lái)解決最優(yōu)化問(wèn)題，如TSP問(wèn)題。人工蟻群中把具有簡(jiǎn)單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)。同時(shí)，人工蟻群再選擇下一條路徑的時(shí)候是按一定算法規(guī)律有意識(shí)地尋找最短路徑，而不是盲目的。例如在TSP問(wèn)題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。第77頁(yè),共102頁(yè)，2024年2月25日，星期天下面以TSP問(wèn)題為例說(shuō)明基本蟻群算法模型。TSP問(wèn)題表示為一個(gè)N個(gè)城市的有向圖G=（N，A），其中 城市之間距離目標(biāo)函數(shù)為其中，，為城市1,2，…n的一個(gè)排列，。第78頁(yè),共102頁(yè)，2024年2月25日，星期天其中： 表示邊（i，j）上的信息素濃度； 是啟發(fā)信息，d是城市i和j之間的距離；

α和β反映了信息素與啟發(fā)信息的相對(duì)重要性； 表示螞蟻k已經(jīng)訪問(wèn)過(guò)的城市列表。當(dāng)所有螞蟻完成周游后，按以下公式進(jìn)行信息素更新。首先將m只螞蟻隨機(jī)放置在n個(gè)城市，位于城市i的第k只螞蟻選擇下一個(gè)城市j的概率為:第79頁(yè),共102頁(yè)，2024年2月25日，星期天其中：ρ為小于1的常數(shù)，表示信息的持久性。其中：Q為常數(shù)；lk表示第k只螞蟻在本次迭代中走過(guò)的路徑，Lk為路徑長(zhǎng)度。第80頁(yè),共102頁(yè)，2024年2月25日，星期天求解TSP算法步驟⑴初始化隨機(jī)放置螞蟻，為每只螞蟻建立禁忌表tabuk，將初始節(jié)點(diǎn)置入禁忌表中;⑵迭代過(guò)程k=1whilek=<ItCountdo(執(zhí)行迭代)fori=1tomdo(對(duì)m只螞蟻循環(huán))forj=1ton-1do(對(duì)n個(gè)城市循環(huán))

根據(jù)式(1)，采用輪盤(pán)賭方法在窗口外選擇下一個(gè)城市j;

將j置入禁忌表,螞蟻轉(zhuǎn)移到j(luò);

endforendfor計(jì)算每只螞蟻的路徑長(zhǎng)度;根據(jù)式(2)更新所有螞蟻路徑上的信息量;k=k+1;endwhile⑶輸出結(jié)果,結(jié)束算法.第81頁(yè),共102頁(yè)，2024年2月25日，星期天蟻群的規(guī)模和停止規(guī)則一、蟻群大小一般情況下蟻群中螞蟻的個(gè)數(shù)不超過(guò)TSP圖中節(jié)點(diǎn)的個(gè)數(shù)。二、終止條件

1給定一個(gè)外循環(huán)的最大數(shù)目；

2當(dāng)前最優(yōu)解連續(xù)K次相同而停止，其中K是一個(gè)給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)。第82頁(yè),共102頁(yè)，2024年2月25日，星期天螞蟻算法的缺點(diǎn)螞蟻算法的缺點(diǎn)：1）收斂速度慢2）易于陷入局部最優(yōu)第83頁(yè),共102頁(yè)，2024年2月25日，星期天4.5人工免疫算法

第84頁(yè),共102頁(yè)，2024年2月25日，星期天4.5.1免疫算法的生物學(xué)基礎(chǔ)

免疫系統(tǒng)是哺乳動(dòng)物抵御外來(lái)有害物質(zhì)侵害的防御系統(tǒng)，動(dòng)物一生始終處于復(fù)雜多變的、充滿傷害的自然環(huán)境中，能夠平安無(wú)事、進(jìn)行正常的生命活動(dòng)，免疫系統(tǒng)在其中起著重要的作用。免疫是生物體的特異性生理反應(yīng),由具有免疫功能的器官、組織、細(xì)胞、免疫效應(yīng)分子及基因等組成。免疫系統(tǒng)通過(guò)分布在全身的不同種類的淋巴細(xì)胞識(shí)別和清除侵入生物體的抗原性異物。當(dāng)生物系統(tǒng)受到外界病毒侵害時(shí),便激活自身的免疫系統(tǒng),其目標(biāo)是盡可能保證整個(gè)生物系統(tǒng)的基本生理功能得到正常運(yùn)轉(zhuǎn)。第85頁(yè),共102頁(yè)，2024年2月25日，星期天4.5.2免疫算法的起源

在生物自然界中，免疫現(xiàn)象普遍存在，并對(duì)物種的生存與繁衍

發(fā)揮著重要的作用；

生物的免疫功能主要是由參與免疫反應(yīng)的細(xì)胞或由其構(gòu)成的器官來(lái)完成的；

生物免疫主要有兩種類型：

特異性免疫反應(yīng)（SpecificImmunity）

非特異性免疫反應(yīng)（NonspecificImmunity）；

生物免疫系統(tǒng)是通過(guò)自我識(shí)別、相互刺激與制約而構(gòu)成了一個(gè)

動(dòng)態(tài)平衡的網(wǎng)絡(luò)結(jié)構(gòu)

。第86頁(yè),共102頁(yè)，2024年2月25日，星期天4.5.3免疫算法的生物免疫機(jī)制第87頁(yè),共102頁(yè)，2024年2月25日，星期天4.5.4免疫算法的基本概念

抗原：在生命科學(xué)中，是指能夠刺激和誘導(dǎo)機(jī)體的免疫系統(tǒng)使其產(chǎn)生免疫應(yīng)答，并能與相應(yīng)的免疫應(yīng)答產(chǎn)物在體內(nèi)或體外發(fā)生特異性反應(yīng)的物質(zhì)。在我們的算法中，是指所有可能錯(cuò)誤的基因，即非最佳個(gè)體的基因。

抗體：在生命科學(xué)中，是指免疫系統(tǒng)受抗原刺激后，免疫細(xì)胞轉(zhuǎn)化為漿細(xì)胞并產(chǎn)生能與抗原發(fā)生特異性結(jié)合的免疫球蛋白，該免疫球蛋白即為抗體。第88頁(yè),共102頁(yè)，2024年2月25日，星期天

免疫疫苗：根據(jù)進(jìn)化環(huán)境或待求問(wèn)題的先驗(yàn)知識(shí)，所得到的對(duì)最佳個(gè)體基因的估計(jì)。

免疫調(diào)節(jié)：在免疫反應(yīng)過(guò)程中，大量的抗體的產(chǎn)生降低了抗原對(duì)免疫細(xì)胞的刺激，從而抑制抗體的分化和增殖，同時(shí)產(chǎn)生的抗體之間也存在著相互刺激和抑制的關(guān)系，這種抗原與抗體、抗體與抗體之間的相互制約關(guān)系使抗體免疫反應(yīng)維持一定的強(qiáng)度，保證機(jī)體的免疫平衡。第89頁(yè),共102頁(yè)，2024年2月25日，星期天

免疫記憶：指免疫系統(tǒng)將能與抗原發(fā)生反應(yīng)的抗體作為記憶細(xì)胞保存記憶下來(lái)，當(dāng)同類抗原再次侵入時(shí)，相應(yīng)的記憶細(xì)胞被激活而產(chǎn)生大量的抗體，縮短免疫反應(yīng)時(shí)間。

抗原識(shí)別：通過(guò)表達(dá)在抗原表面的表位和抗體分子表面的對(duì)位的化學(xué)基進(jìn)行相互匹配選擇完成識(shí)別，這種匹配過(guò)程也是一個(gè)不斷對(duì)抗原學(xué)習(xí)的過(guò)程，最終能選擇產(chǎn)生最適當(dāng)?shù)目贵w與抗原結(jié)合而排除抗原。第90頁(yè),共102頁(yè)，2024年2月25日，星期天4.5.5免疫算法的流程第91頁(yè)