第7章 計算智能

2023/10/131第7章計算智能2023/10/132內(nèi)容7.1人工免疫算法7.2蟻群算法7.3粒子群算法7.4模擬退火算法2023/10/1337.1人工免疫算法7.1.1自然免疫系統(tǒng)7.1.2人工免疫算法7.1.3人工免疫算法的應用2023/10/1347.1.1自然免疫系統(tǒng)（1）免疫是指肌體對感染具有抵抗能力而不患疫病或傳染病。生物免疫系統(tǒng)是一個由眾多組織、細胞與分子等構(gòu)成的復雜系統(tǒng)，它由免疫活性分子、免疫細胞、免疫組織和器官組成。具有識別機制，能夠從人體自體細胞（被感染的細胞）或自體分子和外因感染的微組織中檢測并消除病毒等病原體。

2023/10/1357.1.1自然免疫系統(tǒng)（2）免疫系統(tǒng)的主要功能有以下三個方面：1.免疫防御：指機體排斥外源性抗原異物的能力。這是機體藉以自凈、不受外來物質(zhì)干擾和保持物種純潔的生理機制。2.免疫自穩(wěn)：指機體識別和清除自身衰老殘損的組織、細胞的能力，這是機體藉以維持正常內(nèi)環(huán)境穩(wěn)定的重要機制。3.免疫監(jiān)視：指機體殺傷和清除異常突變細胞的能力，機體藉以監(jiān)視和抑制惡性腫瘤在體內(nèi)生長。免疫監(jiān)視功能低下，則機體易患惡性腫瘤。2023/10/1367.1.2人工免疫算法（1）目前主要存在兩種類型的免疫算法：一種是基于免疫學原理的免疫算法；一種是與遺傳算法等其他計算智能融合的免疫遺傳和進化算法。人工免疫算法模型主要考慮三個方面：抗原、抗體的形式抗原與抗體以及抗體與抗體之間相互作用機制整個系統(tǒng)的構(gòu)造2023/10/1377.1.2人工免疫算法（2）人工免疫算法的步驟：步1識別抗原。免疫系統(tǒng)確認抗原入侵；步2產(chǎn)生初始抗體群體。激活記憶細胞產(chǎn)生抗體，清除以前出現(xiàn)過的抗原，從包含最優(yōu)抗體（最優(yōu)解）數(shù)據(jù)庫中選擇出來一些抗體。初始抗體群體也可以隨機產(chǎn)生或依據(jù)先驗知識產(chǎn)生；步3抗體評價。抗體與抗原接觸，然后，計算抗原和抗體之間的親和力，對抗體進行評價；步4產(chǎn)生記憶。在記憶庫規(guī)模范圍內(nèi)，將群體中優(yōu)良抗體存入記憶庫。與抗原有最大親和力的抗體加給記憶細胞。由于記憶細胞數(shù)目有限，新產(chǎn)生的與抗原具有更高親和力的抗體替換較低親和力的抗體；2023/10/1387.1.2人工免疫算法（3）步5結(jié)束判斷。依據(jù)問題所確定的結(jié)束條件，判斷記憶庫中的抗體是否滿足要求，滿足，則結(jié)束。步6抗體的親和力成熟。對抗體群體進行克隆選擇和超變異操作，改變?nèi)后w中的抗體，使群體在保持多樣性的情況下與抗原更好地匹配；步7群體控制及新抗體群體產(chǎn)生，即抗體的死亡和產(chǎn)生。在群體規(guī)模的范圍內(nèi)，對抗體群體與記憶庫中的抗體進行評價，依據(jù)群體規(guī)模參數(shù)將刺激度最差的一部分抗體刪除，形成新一代抗體群體。高親和力抗體受到促進，高密度抗體受到抑制。轉(zhuǎn)步3。2023/10/1397.1.2人工免疫算法（4）免疫算法中一個關鍵問題是對抗體的評價，評價取決于四個因素抗體與抗原的匹配度抗體間的相互刺激作用抑制作用抗體的獎勵2023/10/13107.1.3人工免疫算法的應用

1.計算機安全：自然免疫系統(tǒng)本身就是一個分布的、具有自適應性和自學習能力的生物入侵檢測系統(tǒng)，它在抵抗病毒和細菌等病原體的入侵方面擔當著與計算機入侵檢測系統(tǒng)類似的任務。2.故障診斷：將免疫機理設計用于軟件或硬件系統(tǒng)的故障診斷的算法或模型，并用現(xiàn)代計算機系統(tǒng)編程實現(xiàn)3.智能優(yōu)化：在函數(shù)優(yōu)化、組合優(yōu)化、調(diào)度問題等方面得到應用并取得了很好的效果。4.數(shù)據(jù)挖掘：采用人工免疫模型的數(shù)據(jù)挖掘任務目前主要集中在數(shù)據(jù)聚類分析、數(shù)據(jù)濃縮、歸類任務等方面。2023/10/13117.2蟻群算法7.2.1螞蟻系統(tǒng)的原理7.2.2蟻群算法模型7.2.3蟻群算法的應用2023/10/13127.2.1螞蟻系統(tǒng)的原理多里科用圖形描述了螞蟻系統(tǒng)的原理：2023/10/13137.2.2蟻群算法模型（1）人工螞蟻與真實螞蟻的相似之處：（1）人工螞蟻也具有信息素釋放和揮發(fā)機制，并且通過信息素進行間接的通訊。（2）人工螞蟻也利用正反饋機制，以信息素作為反（3）人工螞蟻也是采用概率機制進行狀態(tài)轉(zhuǎn)移（4）人工螞蟻也是一個相互合作的個體。2023/10/13147.2.2蟻群算法模型（2）求解旅行商問題的蟻群算法步驟：步1

初始化：設螞蟻個數(shù)m，最大進化代數(shù)NCmax，當前進化代數(shù)NC=0，時間t=0，每條邊（兩個城市間）上的信息素濃度將m個螞蟻隨機地置于n個城市上。步2

禁忌表中的索引。將螞蟻k的起點城市加入到禁忌表中tabuk；步3如果禁忌表不滿，則：s=s+1；對每只螞蟻k，計算轉(zhuǎn)移概率，使用輪盤賭方法選擇下一個要到的城市；螞蟻k移到城市j，并將城市j加入到tabuk中；2023/10/13157.2.2蟻群算法模型（3）步4

（1）對每只螞蟻，計算螞蟻k走過的周游長度Lk；更新當前的最優(yōu)路徑。（2）對每條邊，若螞蟻k在本次周游中經(jīng)過lij，則更新邊lij的信息素：步5

對每條邊，計算信息素量：步6

t=t+1，NC=NC+1。并對每條信息度增加濃度為0;步7如果NC<NCmax，且沒出現(xiàn)停滯現(xiàn)象，則清空所有禁忌表，轉(zhuǎn)步2，否則，輸出最優(yōu)路徑，算法終止。2023/10/13167.2.3蟻群算法的應用（1）靜態(tài)組合優(yōu)化問題，如：經(jīng)典旅行商問題（TSP，0-1背包問題（O-1KP），二次分配問題（QAP），車間任務調(diào)度問題（JSP），車輛路徑問題（VRP），圖著色問題（GCP），有序排列問題（SOP）等等。（2）動態(tài)組合優(yōu)化問題，動態(tài)問題被定義為一些量的函數(shù)，這些量的值由隱含系統(tǒng)動態(tài)設置，因此，問題在運行時間內(nèi)是變化的，而優(yōu)化算法需在線適應不斷變化的環(huán)境。如網(wǎng)絡路由問題等。蟻群算法的具體應用也可以分為路由、分配、調(diào)度、子集、機器學習、網(wǎng)絡路由等類型的問題2023/10/13177.3粒子群算法7.3.1粒子群系統(tǒng)7.3.2粒子群算法模型7.3.3粒子群算法的應用2023/10/13187.3.1粒子群系統(tǒng)粒子群算法是對粒子群系統(tǒng)的模擬，主要是模擬鳥群的捕食行為。一群鳥在隨機地搜索食物，它們通過與同伴間的相互通信確定尋找食物的最短路徑。這是一種基于鄰域原理的找到食物的最簡單、有效的策略，即搜尋目前離食物最近的鳥的鄰域。依靠群體中個體之間的交互作用，通過像近鄰學習和歷史學習，達到對解進行優(yōu)化的目的。2023/10/13197.3.2粒子群算法模型（1）基本的粒子群算法步驟：步1初始化：t=0，對每個微粒pi，在允許范圍內(nèi)隨機設置其初始位置xi(t)和速度vi(t)，每個微粒pi的pBesti設為其初始位置適應值，pBesti中的最好值設為gBest；步2評價每個微粒的適應值τ(xi(t))；步3對每個微粒pi，如果τ(xi(t))

<pBesti

，則pBesti=τ(xi(t))，xpBesti

=xi(t)；步4對每個微粒pi，如果τ(xi(t))

<gBes