模式識別與人工智能（基于MATLAB）（第2版）課件 11 免疫算法

免疫算法目錄

免疫算法產生和發展免疫算法理論免疫算法流程關鍵參數說明MATLAB仿真實例結論

一.免疫算法產生和發展

1958年澳大利亞學者Burnet率先提出與免疫算法（ImmuneAlgorithm，IA）相關的理論——克隆選擇原理。

1973年Jerne提出免疫系統的模型，他基于Burnet的克隆選擇學說，開創獨特型網絡理論，給出免疫系統的數學框架，并采用微分方程建模來仿真淋巴細胞的動態變化。

1986年Farmal等人基于免疫網絡學說理論構造出的免疫系統的動態模型，展示免疫系統與其他人工智能方法相結合的可能性，開創免疫系統研究的先河。二.免疫算法理論1.免疫算法概念免疫算法是受生物免疫系統的啟發而推出的一種新型的智能搜索算法。它是一種確定性和隨機性選擇相結合并具有“勘探”與“開采”能力的啟發式隨機搜索算法。免疫算法將優化問題中待優化的問題對應免疫應答中的抗原，可行解對應抗體（B細胞），可行解質量對應免疫細胞與抗原的親和度。如此則可以將優化問題的尋優過程與生物免疫系統識別抗原并實現抗體進化的過程對應起來，將生物免疫應答中的進化過程抽象為數學上的進化尋優過程，形成一種智能優化算法。二.免疫算法理論1.免疫算法概念免疫算法是對生物免疫系統機理抽象而得的，算法中的許多概念和算子與免疫系統中的概念和免疫機理存在著對應關系。免疫算法與生物免疫系統概念的對應關系如下表所示。生物免疫系統免疫算法抗原優化問題抗體（B細胞）優化問題的可行解親和度可行解的質量細胞活化免疫選擇細胞分化個體克隆親和度成熟變異克隆抑制克隆抑制動態維持平衡種群刷新二.免疫算法理論1.免疫算法概念根據上述的對應關系，模擬生物免疫應答的過程形成了用于優化計算的免疫算法。算法主要包含以下幾大模塊：（1）抗原識別與初始抗體產生。根據待優化問題的特點設計合適的抗體編碼規則，并在此編碼規則下利用問題的先驗知識產生初始抗體種群。（2）抗體評價。對抗體的質量進行評價，評價準則主要為抗體親和度和個體濃度，評價得出的優質抗體將進行進化免疫操作，劣質抗體將會被更新。（3）免疫操作。利用免疫選擇、克隆、變異、克隆抑制、種群刷新等算子模擬生物免疫應答中的各種免疫操作，形成基于生物免疫系統克隆選擇原理的進化規則和方法，實現對各種最優化問題的尋優搜索。二.免疫算法理論2.免疫算法特點免疫算法是受免疫學啟發，模擬生物免疫系統功能和原理來解決復雜問題的自適應智能系統，它保留了生物免疫系統所具有的若干特點，包括：全局搜索能力。多樣性保持機制。魯棒性強。并行分布式搜索機制。二.免疫算法理論3.免疫算法算子與遺傳算法等其他智能優化算法類似，免疫算法的進化尋優過程也是通過算子來實現的。免疫算法的算子包括：親和度評價算子、抗體濃度評價算子、激勵度計算算子、免疫選擇算子、克隆算子、變異算子、克隆抑制算子和種群刷新算子等。由于算法的編碼方式可能為實數編碼、離散編碼等，不同編碼方式下的算法算子也會有所不同。三.免疫算法流程目前還沒有統一的免疫算法及框圖，下面介紹一種含有多種免疫算子的算法流程，分為以下幾個步驟：（1）首先進行抗原識別，即理解待優化的問題，對問題進行可行性分析，提取先驗知識，構造出合適的親和度函數，并制定各種約束條件。（2）然后產生初始抗體群，通過編碼把問題的可行解表示成解空間中的抗體，在解的空間內隨機產生一個初始種群。（3）對種群中的每一個可行解進行親和度評價。（4）判斷是否滿足算法終止條件：如果滿足條件，則終止算法尋優過程，輸出計算結果；否則，繼續尋優運算。（5）計算抗體濃度和激勵度。三.免疫算法流程（6）進行免疫處理，包括免疫選擇、克隆、變異和克隆抑制。?免疫選擇：根據種群中抗體的親和度和濃度計算結果選擇優質抗體，使其活化；?克隆：對活化的抗體進行克隆復制，得到若干副本；?變異：對克隆得到的副本進行變異操作，使其發生親和度突變；?克隆抑制：對變異結果進行再選擇，抑制親和度低的抗體，保留親和度高的變異結果。（7）種群刷新，以隨機生成的新抗體替代種群中激勵度較低的抗體，形成新一代抗體，轉步驟（3）。三.免疫算法流程免疫算法運算流程如左圖所示。免疫算法中的進化操作是采用了基于免疫原理的進化算子實現的，如免疫選擇、克隆、變異等。而且算法中增加了抗體濃度和激勵度的計算，并將抗體濃度作為評價個體質量的一個標準，有利于保持個體多樣性，實現全局尋優。四.關鍵參數說明下面介紹一下免疫算法的主要參數，它在程序設計與調試中起著至關重要的作用。免疫算法主要包括以下關鍵參數：1．抗體種群大小NP抗體種群保留了免疫細胞的多樣性，從直觀上看，種群越大，免疫算法的全局搜索能力越好，但是算法每代的計算量也相應增大。在大多數問題中，NP取10～100較為合適，一般不超過200。2．免疫選擇比例免疫選擇的抗體的數量越多，將產生更多的克隆，其搜索能力越強，但是將增加每代的計算量。一般可以取抗體種群大小NP的10%～50%。四.關鍵參數說明3．抗體克隆擴增的倍數克隆的倍數決定了克隆擴增的細胞的數量，從而決定了算法的搜索能力，主要是局部搜索能力。克隆倍數數值越大，局部搜索能力越好，全局搜索能力也有一定提高，但是計算量也隨之增大，一般取5～10倍。4．種群刷新比例細胞的淘汰和更新是產生抗體多樣性的重要機制，因而對免疫算法的全局搜索能力產生重要影響。每代更新的抗體一般不超過抗體種群的50%。5．最大進化代數G最大進化代數G是表示免疫算法運行結束條件的一個參數，表示免疫算法運行到指定的進化代數之后就停止運行，并將當前群體中的最佳個體作為所求問題的最優解輸出。一般G取100～500。五.MATLAB仿真實例旅行商問題（TSP問題）。假設有一個旅行商人要拜訪全國31個省會城市，他需要選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發的城市。路徑的選擇要求是：所選路徑的路程為所有路徑之中的最小值。全國31個省會城市的坐標為[13042312；36391315；41772244；37121399；34881535；33261556；32381229；41961044；4312790；4386570；30071970；25621756；27881491；23811676；1332695；37151678；39182179；40612370；37802212；36762578；40292838；42632931；34291908；35072376；33942643；34393201；29353240；31403550；25452357；27782826；23702975]。五.MATLAB仿真實例%%%%%初始化%%%%%clearall;%清除所有變量closeall;%清圖clc;%清屏C=[13042312;36391315;41772244;37121399;34881535;33261556;32381229;41961044;4312790;4386570;30071970;25621756;27881491;23811676;1332695;37151678;39182179;40612370;37802212;36762578;40292838;42632931;34291908;35072376;33942643;34393201;29353240;31403550;25452357;27782826;23702975];%31個省會城市坐標N=size(C,1);%TSP問題的規模,即城市數目D=zeros(N);%任意兩個城市距離間隔矩陣%%%%%%求任意兩個城市距離間隔矩陣%%%%%fori=1:Nforj=1:ND(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;endendNP=200;%免疫個體數目G=1000;%最大免疫代數f=zeros(N,NP);%用于存儲種群fori=1:NPf(:,i)=randperm(N);%隨機生成初始種群endlen=zeros(NP,1);%存儲路徑長度fori=1:NPlen(i)=func3(D,f(:,i),N);%計算路徑長度end[Sortlen,Index]=sort(len);Sortf=f(:,Index);%種群個體排序gen=0;%免疫代數Ncl=10;%克隆個數1.MATLAB完整程序：五.MATLAB仿真實例%%%%%免疫循環%%%%%whilegen<Gfori=1:NP/2%%%%%選激勵度前NP/2個體進行免疫操作%%%%%a=Sortf(:,i);Ca=repmat(a,1,Ncl);forj=1:Nclp1=floor(1+N*rand());p2=floor(1+N*rand());whilep1==p2p1=floor(1+N*rand());p2=floor(1+N*rand());endtmp=Ca(p1,j);Ca(p1,j)=Ca(p2,j);Ca(p2,j)=tmp;endCa(:,1)=Sortf(:,i);%保留克隆源個體%%%%%克隆抑制，保留親和度最高的個體%%%%%forj=1:NclCalen(j)=func3(D,Ca(:,j),N);end[SortCalen,Index]=sort(Calen);SortCa=Ca(:,Index);af(:,i)=SortCa(:,1);alen(i)=SortCalen(1);end%%%%%種群刷新%%%%%fori=1:NP/2bf(:,i)=randperm(N);%隨機生成初始種群blen(i)=func3(D,bf(:,i),N);%計算路徑長度end%%%%%免疫種群與新種群合并%%%%%f=[af,bf];len=[alen,blen];[Sortlen,Index]=sort(len);Sortf=f(:,Index);

1.MATLAB完整程序：五.MATLAB仿真實例gen=gen+1;trace(gen)=Sortlen(1);end%%%%%輸出優化結果%%%%%Bestf=Sortf(:,1);%最優變量Bestlen=trace(end);%最優值figurefori=1:N-1plot([C(Bestf(i),1),C(Bestf(i+1),1)],[C(Bestf(i),2),C(Bestf(i+1),2)],'bo-');holdon;endplot([C(Bestf(N),1),C(Bestf(1),1)],[C(Bestf(N),2),C(Bestf(1),2)],'ro-');title(['優化最短距離:',num2str(