1、第十二章 模擬退火算法與人工免疫算法簡介,本章對目前常用的幾種智能優(yōu)化計算算法作簡單介紹，以使讀者對它們有個基本認識。內(nèi)容包括神經(jīng)網(wǎng)絡(luò)、遺傳算法、模擬退火算法和神經(jīng)網(wǎng)絡(luò)混合優(yōu)化學(xué)習(xí)策略。,12.1 模擬退火算法,模擬退火算法(simulated annealing,簡稱SA)的思想最早是由Metropolis等(1953)提出的，1983年Kirkpatrick等將其用于組合優(yōu)化。SA算法是基于Monte Carlo迭代求解策略的一種隨機尋優(yōu)算法，其出發(fā)點是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。,模擬退火算法,模擬退火算法在某一初溫下，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳

2、特性在解空間中隨機尋找目標函數(shù)的全局最優(yōu)解，即在局部優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)解。模擬退火算法是一種通用的優(yōu)化算法，目前已在工程中得到了廣泛應(yīng)用。,模擬退火算法,12.1.1 物理退火過程和Metropolis準則 簡單而言，物理退火過程由以下三部分組成： 加溫過程。其目的是增強粒子的熱運動，使其偏離平衡位置。當(dāng)溫度足夠高時，固體將溶解為液體，從而消除系統(tǒng)原先可能存在的非均勻態(tài)，使隨后進行的冷卻過程以某一平衡態(tài)為起點。溶解過程與系統(tǒng)的熵增過程聯(lián)系，系統(tǒng)能量也隨溫度的升高而增大。,模擬退火算法,等溫過程。物理學(xué)的知識告訴我們，對于與周圍環(huán)境交換熱量而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變

3、化總是朝自由能減少的方向進行，當(dāng)自由能達到最小時，系統(tǒng)達到平衡態(tài)。 冷卻過程。目的是使粒子的熱運動減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。,模擬退火算法,Metropolis等在1953年提出了重要性采樣法，即以概率接受新狀態(tài)。具體而言，在溫度t,由當(dāng)前狀態(tài)i產(chǎn)生新狀態(tài)j，兩者的能量分別為 ，若 則接受新狀態(tài)j為當(dāng)前狀態(tài)；否則，若概率 大于 區(qū)間內(nèi)的隨機數(shù)則仍舊接受新狀態(tài)j為當(dāng)前狀態(tài)，若不成立則保留i為當(dāng)前狀態(tài)，其中k為Boltzmann常數(shù)。,模擬退火算法,這種重要性采樣過程在高溫下可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)，而在低溫下基本只接受與當(dāng)前能量差較小的新狀態(tài)，而且當(dāng)溫度

4、趨于零時，就不能接受比當(dāng)前狀態(tài)能量高的新狀態(tài)。這種接受準則通常稱為Metropolis準則。,模擬退火算法,12.1.2 模擬退火算法的基本思想和步驟 1983年Kirkpatrick等意識到組合優(yōu)化與物理退火的相似性，并受到Metropolis準則的啟迪，提出了模擬退火算法。模擬退火算法是基于Monte Carlo 迭代求解策略的一種隨機尋優(yōu)算法，其出發(fā)點是基于物理退火過程與組合優(yōu)化之間的相似性，SA由某一較高初溫開始，利用具有概率突跳特性的Metropolis抽樣策略在解空間中進行隨機搜索，伴隨溫度的不斷下降重復(fù)抽樣過程，最終得到問題的全局最優(yōu)解。,模擬退火算法,標準模擬退火算法的一般步驟

5、可描述如下： 給定初溫 ，隨機產(chǎn)生初始狀態(tài) ，令 ； Repeat: Repeat 產(chǎn)生新狀態(tài) ；,模擬退火算法,Until 抽樣穩(wěn)定準則滿足； 退溫 ，并令 ； Until 算法終止準則滿足； 輸出算法搜索結(jié)果。,模擬退火算法,12.1.3 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)定 從算法流程上看，模擬退火算法包括三函數(shù)兩準則，即狀態(tài)產(chǎn)生函數(shù)、狀態(tài)接受函數(shù)、溫度更新函數(shù)、內(nèi)循環(huán)終止準則和外循環(huán)終止準則，這些環(huán)節(jié)的設(shè)計將決定SA算法的優(yōu)化性能。此外，初溫的選擇對SA算法性能也有很大影響。,模擬退火算法,狀態(tài)產(chǎn)生函數(shù) 設(shè)計狀態(tài)產(chǎn)生函數(shù)（鄰域函數(shù)）的出發(fā)點應(yīng)該是盡可能保證產(chǎn)生的候選解遍布全部的解空間。通常

6、，狀態(tài)產(chǎn)生函數(shù)由兩部分組成，即產(chǎn)生候選解的方式和候選解產(chǎn)生的概率分布。,模擬退火算法,狀態(tài)接受函數(shù) 狀態(tài)接受函數(shù)一般以概率的方式給出，不同接受函數(shù)的差別主要在于接受概率的形式不同。設(shè)計狀態(tài)接受概率，應(yīng)該遵循以下原則： 在固定溫度下，接受使目標函數(shù)值下降的候選解的概率要大于使目標值上升的候選解的概率；,模擬退火算法,隨溫度的下降，接受使目標函數(shù)值上升的解的概率要逐漸減小； 當(dāng)溫度趨于零時，只能接受目標函數(shù)值下降的解。 狀態(tài)接受函數(shù)的引入是SA算法實現(xiàn)全局搜索的最關(guān)鍵的因素，SA算法中通常采用min1,exp(-C/t)作為狀態(tài)接受函數(shù)。,模擬退火算法,初溫 初始溫度、溫度更新函數(shù)、內(nèi)循環(huán)終止準則

7、和外循環(huán)終止準則通常被稱為退火歷程(annealing schedule)。實驗表明，初溫越大，獲得高質(zhì)量解的幾率越大，但花費的計算時間將增加。因此，初溫的確定應(yīng)折衷考慮優(yōu)化質(zhì)量和優(yōu)化效率，常用方法包括：,模擬退火算法,均勻抽樣一組狀態(tài)，以各狀態(tài)目標值的方差為初溫。 隨機產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標值差 ，然后依據(jù)差值，利用一定的函數(shù)確定初溫。譬如 ,其中 為初始接受概率 利用經(jīng)驗公式給出。,模擬退火算法,溫度更新函數(shù) 溫度更新函數(shù)，即溫度的下降方式，用于在外循環(huán)中修改溫度值。 目前，最常用的溫度更新函數(shù)為指數(shù)退溫函數(shù)，即，其中且其大小可以不斷變化。,模擬退火算法,內(nèi)循環(huán)終止準則 內(nèi)

8、循環(huán)終止準則，或稱Metropolis抽樣穩(wěn)定準則，用于決定在各溫度下產(chǎn)生候選解的數(shù)目。在非時齊SA算法理論中，由于在每個溫度下只產(chǎn)生一個或少量候選解，所以不存在選擇內(nèi)循環(huán)終止準則的問題。,模擬退火算法,而在時齊SA算法理論中，收斂條件要求在每個溫度下產(chǎn)生候選解的數(shù)目趨于無窮大，以使相應(yīng)的馬氏鏈達到平穩(wěn)概率分布，顯然在實際應(yīng)用算法時這是無法實現(xiàn)的。常用的抽樣準則包括： 檢驗?zāi)繕撕瘮?shù)的均值是否穩(wěn)定； 連續(xù)若干步的目標值變化較??； 按一定的步數(shù)抽樣。,模擬退火算法,外循環(huán)終止準則 外循環(huán)終止準則，即算法終止準則，用于決定算法何時結(jié)束。設(shè)置溫度終值是一種簡單的方法。SA算法的收斂性理論中要求溫度終值

9、趨于零，這顯然不合實際。通常的做法是：,模擬退火算法,設(shè)置終止溫度的閾值； 設(shè)置外循環(huán)迭代次數(shù)； 算法收斂到的最優(yōu)值連續(xù)若干步保持不變； 檢驗系統(tǒng)熵是否穩(wěn)定。,12.1.4 神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略,鑒于GA、SA的全局優(yōu)化特性和通用性，即優(yōu)化過程無需導(dǎo)數(shù)信息，我們可以基于實數(shù)編碼構(gòu)造BPSA、BPGA混合優(yōu)化學(xué)習(xí)策略，以提高前向網(wǎng)絡(luò)學(xué)習(xí)的速度、精度，特別是避免陷入局部極小的能力。,12.1.4 神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略,4.1 BPSA混合學(xué)習(xí)策略 在BPSA混合學(xué)習(xí)策略中，采用以BP為主框架，并在學(xué)習(xí)過程中引入SA策略。這樣做，既利用了基于梯度下降的有指導(dǎo)學(xué)習(xí)來提高局部搜索性能

10、，也利用了SA的概率突跳性來實現(xiàn)最終的全局收斂，從而可提高學(xué)習(xí)速度和精度。 BP-SA混合學(xué)習(xí)策略的算法步驟如下：,神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略, 隨機產(chǎn)生初始權(quán)值 ，確定初溫 ，令 利用BP計算 。 利用SA進行搜索： 利用SA狀態(tài)產(chǎn)生函數(shù)產(chǎn)生新權(quán)值 ， ，其中 為隨機擾動。,神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略, 計算 的目標函數(shù)值與 的目標函數(shù)值之差 。 計算接受概率 。 若 ，則取 ；否則 保持不變。,神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略,(4) 利用退溫函數(shù) 進行退溫，其中 為退溫速率。 若 對應(yīng)的目標函數(shù)滿足要求精度 ，則終止算法并輸出結(jié)果；否則，令 ，轉(zhuǎn)步驟。,神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策

11、略,4.2 BPGA混合學(xué)習(xí)策略 神經(jīng)網(wǎng)絡(luò)的連接權(quán)包含著神經(jīng)網(wǎng)絡(luò)系統(tǒng)的全部知識。反向傳播的BP神經(jīng)網(wǎng)絡(luò)(back propagation network)的學(xué)習(xí)算法是基于梯度下降的，因而具有以下缺點：網(wǎng)絡(luò)訓(xùn)練速度慢、容易陷入局部極小值、全局搜索能力差等。而遺傳算法的搜索遍及整個解空間，因此容易得到全局最優(yōu)解，而且遺傳算法不要求目標函數(shù)連續(xù)、可微，甚至不要求目標函數(shù)有顯函數(shù)的形式，只要求問題可計算。,神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略,因此，將擅長全局搜索的遺傳算法和局部尋優(yōu)能力較強的BP算法結(jié)合起來，可以避免陷入局部極小值，提高算法收斂速度，很快找到問題的全局最優(yōu)解。 BP算法和遺傳算法結(jié)合訓(xùn)練神

12、經(jīng)網(wǎng)絡(luò)權(quán)重的主要步驟為：,神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略,(1) 以神經(jīng)網(wǎng)絡(luò)節(jié)點之間的連接權(quán)重和節(jié)點的閾值為參數(shù)，采用實數(shù)編碼。采用三層神經(jīng)網(wǎng)絡(luò)，設(shè)輸入節(jié)點數(shù)為p，輸出節(jié)點數(shù)為q，隱層節(jié)點數(shù)為r，則編碼長度n為： （10-4-1）,神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略,(2)設(shè)定神經(jīng)網(wǎng)絡(luò)節(jié)點連接權(quán)重的取值范圍 ,產(chǎn)生相應(yīng)范圍的均勻分布隨機數(shù)賦給基因值，產(chǎn)生初始群體； (3)對群體中個體進行評價。將個體解碼賦值給相應(yīng)的連接權(quán)(包括節(jié)點閾值)，引入學(xué)習(xí)樣本計算出學(xué)習(xí)誤差E，個體的適應(yīng)度定義為： . （10-4-2）,神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略,(4)對群體中的個體執(zhí)行遺傳操作： 選擇操作。采用比例選

13、擇算子，若群體規(guī)模為M，則適應(yīng)度為的個體被選中進入下一代的概率為： . （10-4-3）,神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略, 交叉操作。由于采用實數(shù)編碼，故選擇算術(shù)交叉算子。父代中的個體 和 以交叉概率 進行交叉操作，可產(chǎn)生的子代個體為： （10-4-4） 和 （10-4-5） 其中a為參數(shù) 。,神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略, 變異操作。 采用均勻變異算子。個體 的各個基因位以變異概率 發(fā)生變異，即按概率用 區(qū)間中的均勻分布隨機數(shù)代替原有值。 引入最優(yōu)保留策略。,神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略, 判斷滿足遺傳算法操作終止條件否？不滿足則轉(zhuǎn)步驟。否則轉(zhuǎn)步驟。 將遺傳算法搜索的最優(yōu)個體解碼，賦值給

14、神經(jīng)網(wǎng)絡(luò)權(quán)重(包括節(jié)點閾值)，繼續(xù)采用BP算法優(yōu)化神經(jīng)網(wǎng)絡(luò)的權(quán)重和閾值。,神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略,4.3 GASA混合學(xué)習(xí)策略 采用三層前饋網(wǎng)絡(luò)，GA和SA結(jié)合訓(xùn)練神經(jīng)網(wǎng)絡(luò)權(quán)重的步驟如下： 給定模擬退火初溫 ，令 ； 以神經(jīng)網(wǎng)絡(luò)節(jié)點之間的連接權(quán)重和節(jié)點的閾值為參數(shù)，采用實數(shù)編碼。采用三層神經(jīng)網(wǎng)絡(luò)，設(shè)輸入節(jié)點數(shù)為p，輸出節(jié)點數(shù)為q，隱層節(jié)點數(shù)為r，則編碼長度n為：,神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略,（10-4-6） 設(shè)定神經(jīng)網(wǎng)絡(luò)節(jié)點連接權(quán)重的取值范圍 ，產(chǎn)生相應(yīng)范圍的均勻分布隨機數(shù)賦給基因值，產(chǎn)生初始群體； 對群體中個體進行評價。將個體解碼賦值給相應(yīng)的連接權(quán)(包括節(jié)點閾值)，引入學(xué)習(xí)樣本計

15、算出學(xué)習(xí)誤差E，個體的適應(yīng)度定義為： . （10-4-7）,神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略, 對群體中的個體執(zhí)行遺傳操作： 選擇操作。采用比例選擇算子，若群體規(guī)模為M，則適應(yīng)度為 的個體 被選中進入下一代的概率為： . （10-4-8）,神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略, 交叉操作。由于采用實數(shù)編碼，故選擇算術(shù)交叉算子。父代中的個體 和 以交叉概率 進行交叉操作，可產(chǎn)生的子代個體為： （10-4-9） 和 （10-4-10） 其中a為參數(shù) 。,神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略, 變異操作。采用均勻變異算子。個體 的各個基因位以變異概率 發(fā)生變異，即按概率 用區(qū)間 中的均勻分布隨機數(shù)代替原有值。 引

16、入最優(yōu)保留策略。 對群體中每一個個體引入模擬退火操作：,神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略, 利用SA狀態(tài)產(chǎn)生函數(shù)產(chǎn)生新基因值 ， ，其中 為隨機擾動。 計算 的目標函數(shù)值與 的目標函數(shù)值之差 。 計算接受概率 。,神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略, 若 ，則取 ；否則 保持不變。 引入最優(yōu)保留策略。 利用退溫函數(shù) 進行退溫，其中 為退溫速率。,神經(jīng)網(wǎng)絡(luò)權(quán)值的混合優(yōu)化學(xué)習(xí)策略, 判斷滿足遺傳算法操作終止條件否？不滿足則轉(zhuǎn)步驟。否則轉(zhuǎn)步驟。 將遺傳算法搜索的最優(yōu)個體解碼，賦值給神經(jīng)網(wǎng)絡(luò)權(quán)重(包括節(jié)點閾值)。,二、人工免疫系統(tǒng),引言,1,2,免疫算法,3,典型的人工免疫系統(tǒng)ARTIS,4,基本免疫方法,

17、引言,人工免疫系統(tǒng)作為人工智能領(lǐng)域的重要分支，同神經(jīng)網(wǎng)絡(luò)及遺傳算法一樣也是智能信息處理的重要手段，已經(jīng)受到越來越多的關(guān)注。 它通過類似于生物免疫系統(tǒng)的機能，構(gòu)造具有動態(tài)性和自適應(yīng)性的信息防御體系，以此來抵制外部無用、有害信息的侵入，從而保證接受信息的有效性與無害性。,背景,在生物科學(xué)領(lǐng)域，人們對進化、遺傳和免疫等自然 現(xiàn)象已經(jīng)進行了廣泛而深入的研究 ； 進化算法是建立在模仿生物遺傳與自然選擇基礎(chǔ)上的一種并行優(yōu)化算法，其性能優(yōu)異、應(yīng)用廣泛； 進化算子在為每個個體提供了進化機會的同時，也無可避免地產(chǎn)生了退化的可能； 大多數(shù)待求問題有可以利用的先驗知識或特征信息，故可以利用這些信息來抑制進化過程中的

18、退化現(xiàn)象； 生物免疫理論為改進原有算法的性能，建立集進化與免疫機制于一體的新型全局并行算法奠定了基礎(chǔ)。,一門新興的研究領(lǐng)域,Farmer等人在1986年首先在工程領(lǐng)域提出免疫概念； Varela等人受免疫網(wǎng)絡(luò)學(xué)說的啟發(fā)，提出并進而完善免疫網(wǎng)絡(luò)模型。,人工免疫網(wǎng)絡(luò)模型,獨特型免疫網(wǎng)絡(luò)（Jerne）； 互聯(lián)耦合免疫網(wǎng)絡(luò)（Ishiguro）； 免疫反應(yīng)網(wǎng)絡(luò)（Mitsumoto）； 對稱網(wǎng)絡(luò)（Hoffmann）； 多值免疫網(wǎng)絡(luò)（Tang）.,免疫學(xué)習(xí)算法,反面選擇算法（Forrest）； 免疫學(xué)習(xí)算法（Hunt 基于免疫系統(tǒng)中的其他特殊機制抽象出的算法，例如克隆選擇算法; 與遺傳算法等其他計算智能融合

19、產(chǎn)生的新算法，例如免疫遺傳算法。,免疫算法的一般步驟,Y,N,免疫算法,(1)識別抗原：免疫系統(tǒng)確認抗原入侵。 (2)產(chǎn)生初始抗體群體：激活記憶細胞產(chǎn)生抗體，清除以前出現(xiàn)過的抗原，從包含最優(yōu)抗體(最優(yōu)解)的數(shù)據(jù)庫中選擇出來一些抗體。 (3)計算親和力：計算抗體和抗原之間的親和力。 (4)記憶細胞分化：與抗原有最大親和力的抗體加給記憶細胞。由于記憶細胞數(shù)目有限，新產(chǎn)生的與抗原具有更高親和力的抗體替換較低親和力的抗體。 (5)抗體促進和抑制：高親和力抗體受到促進，高密度抗體受到抑制。通常通過計算抗體存活的期望值來實施。 (6)抗體產(chǎn)生:對未知抗原的響應(yīng)，產(chǎn)生新淋巴細胞,免疫算法,陰性選擇算法,Pr

20、ocedure Begin 隨機生成大量的候選檢測器(即免疫細胞) /*初始化*/ While一個給定大小的檢測器集合還沒有被產(chǎn)生do/*耐受*/ Begin 計算出每一個自體元素和一個候選檢測器之間的親和力; If這個候選的檢測器識別出了自體集合中的任何一個元素Then這個檢測器就要被消除掉; Else把這個檢測器放入檢測器集合里面; /*該檢測器成熟*/ 利用經(jīng)過耐受的檢測器集合，檢測系統(tǒng)以找出變種; End; End.,常見免疫算法,克隆選擇算法,Begin 隨機生成一個屬性串(免疫細胞)的群體 While收斂標準沒有滿足do Begin While not所有抗原搜索完畢do;*/初始化*/ Begin 選擇那些與抗原具有更高親和力的細胞;*/選擇*/ 生成免疫細胞的副本:越高親和力的細胞擁有更多的副本;*/再生*/ 根據(jù)它們的親和力進行變異:親和力越高，變異越小;*/遺傳變異*/ End.End.End.,免疫算法,免疫遺傳算法,隨機創(chuàng)建抗體和抗原的群體; 抗體和抗原匹配; 根據(jù)抗體的親和力對抗體做評價; 用標準遺傳算法進化抗體。 這個模型使免疫系統(tǒng)能夠通過學(xué)習(xí)，知道哪些抗體對抗原的識別有幫助。,常見免疫算法,免疫系統(tǒng)與一般免疫算法之間的比較,免