計算群體智能

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

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

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

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

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

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

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

⒈具有6個染色體的二進制編碼、適應度值、Pc累計值。

染色體的適應度和所占的比例用轉輪方法進行選擇第7頁,共102頁，2024年2月25日，星期天染色體被選的概率染色體編號12345678910適應度8217721211737被選概率0.10.020.220.090.020.160.140.090.030.09適應度累計8

10

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

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

11010001

B’

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

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

2）適應度函數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

算法的提出

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

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

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

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

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

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

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

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

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

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

給定初溫t=t0，隨機產(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)定準則滿足；退溫tk+1=update(tk)并令k=k+1；

Until算法終止準則滿足；輸出算法搜索結果。第47頁,共102頁，2024年2月25日，星期天影響優(yōu)化結果的主要因素

給定初溫t=t0，隨機產(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)定準則滿足；退溫tk+1=update(tk)并令k=k+1；

Until算法終止準則滿足；輸出算法搜索結果。三函數(shù)兩準則初始溫度第48頁,共102頁，2024年2月25日，星期天4.3.2模擬退火算法關鍵參數(shù)和操作的設計原則

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

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

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

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

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

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

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

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

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

（1），α越接近1溫度下降越慢，且其大小可以不斷變化；（2），其中t0為起始溫度，K為算法溫度下降的總次數(shù)。4.3.2.4溫度更新函數(shù)第53頁,共102頁，2024年2月25日，星期天非時齊模擬退火算法

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

（1）檢驗目標函數(shù)的均值是否穩(wěn)定；（2）連續(xù)若干步的目標值變化較小；（3）按一定的步數(shù)抽樣。4.3.2.5內(nèi)循環(huán)終止準則第54頁,共102頁，2024年2月25日，星期天常用方法

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

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

由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此優(yōu)化過程較長。4.3.3.1模擬退火算法的優(yōu)缺點第56頁,共102頁，2024年2月25日，星期天改進的可行方案

（1）設計合適的狀態(tài)產(chǎn)生函數(shù)；（2）設計高效的退火歷程；（3）避免狀態(tài)的迂回搜索；（4）采用并行搜索結構；（5）避免陷入局部極小，改進對溫度的控制方式；（6）選擇合適的初始狀態(tài)；（7）設計合適的算法終止準則。4.3.3.2改進內(nèi)容第57頁,共102頁，2024年2月25日，星期天改進的方式

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

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

第59頁,共102頁，2024年2月25日，星期天初始溫度的計算

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

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

截止溫度tf=0.01;

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

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

第63頁,共102頁，2024年2月25日，星期天運行過程

第64頁,共102頁，2024年2月25日，星期天運行過程

第65頁,共102頁，2024年2月25日，星期天運行過程

第66頁,共102頁，2024年2月25日，星期天運行過程

第67頁,共102頁，2024年2月25日，星期天運行結果

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

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

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

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

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

將j置入禁忌表,螞蟻轉移到j;

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

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

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

第84頁,共102頁，2024年2月25日，星期天4.5.1免疫算法的生物學基礎

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

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

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

生物的免疫功能主要是由參與免疫反應的細胞或由其構成的器官來完成的；

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

特異性免疫反應（SpecificImmunity）

非特異性免疫反應（NonspecificImmunity）；

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

動態(tài)平衡的網(wǎng)絡結構

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

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

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

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

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

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

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