万字长文了解免疫算法原理 及求解复杂约束问题(源码实现)
免疫算法理論
??????生物免疫系統是-一個復雜的自適應系統。免疫系統能夠識別出病原體,具有學習、記憶和模式識別能力,因此可以借鑒其信息處理機制來解決科學和工程問題。免疫算法正是基于生物免疫系統識別外部病原體并產生抗體對抗病原體的學習機制而提出的,由此誕生了基于免疫原理的智能優化方法研究這一新的研究方向。
生物免疫系統
?????? 傳統免疫是指機體抗感染的防御能力,而現代免疫則指機體免疫系統識別和排除抗原性異物,從而維持機體生理平衡和穩定的功能。免疫是機體的一種生理反應,當病原體(即抗原)進入人體時,這些抗原將刺激免疫細胞(淋巴B細胞、T細胞)產生一種抵抗該病原生物的特殊蛋白質- --抗體。抗體能將該病原生物消滅,并在將病原生物消滅之后,仍存留在人體內。當同樣的病原生物再次侵入人體時,該病原生物就會很快地被體內存留的抗體消滅。
免疫
?????? 免疫是指機體對自身和異體識別與響應過程中產生的生物學效應的總和,正常情況下是一種維持機體循環穩定的生理性功能。生物機體識別異體抗原,對其產生免疫響應并清除;機體對自身抗原不產生免疫響應。
抗原
??????抗原是一種能夠刺激機體產生免疫應答并能與應答產物結合的物質。它不是免疫系統的有機組成部分,但它是啟動免疫應答的始動因素。
抗體
??????抗體是一種能夠進行特異識別和清除抗原的免疫分子,其中具有抗細菌和抗毒素免疫功能的球蛋白物質,故抗體也稱免疫球蛋白分子,它是由B細胞分化成的漿細胞所產生的。
T細胞和B細胞
??????T細胞和B細胞是淋巴細胞的主要組成部分。B細胞受到抗原刺激后,可增殖分化為大量漿細胞,而漿細胞具有合成和分泌抗體的功能。但是,B細胞不能識別大多數抗原,必須借助能識別抗原的輔助性T細胞來輔助B細胞活化,產生抗體。
生物免疫系統原理
??????生物免疫系統是由免疫分子、免疫組織和免疫細胞組成的復雜系統。這些組成免疫系統的組織和器官分布在人體各處,用來完成各種免疫防衛功能,它們就是人們熟知的淋巴器官和淋巴組織。
免疫算法基本概念
??????免疫算法是受生物免疫系統的啟發而推出的一種新型的智能搜索算法。它是一種確定性和隨機性選擇相結合并具有“勘探”與“開采”能力的啟發式隨機搜索算法。免疫算法將優化問題中待優化的問題對應免疫應答中的抗原,可行解對應抗體(B細胞),可行解質量對應免疫細胞與抗原的親和度。如此則可以將優化問題的尋優過程與生物免疫系統識別抗原并實現抗體進化的過程對應起來,將生物免疫應答中的進化過程抽象為數學上的進化尋優過程,形成一種智能優化算法。
??????免疫算法是對生物免疫系統機理抽象而得的,算法中的許多概念和算子與免疫系統中的概念和免疫機理存在著對應關系。免疫算法與生物免疫系統概念的對應關系如表4.1所示。由于抗體是由B細胞產生的,在免疫算法中對抗體和B細胞不做區分,都對應為優化問題的可行解。
免疫算法的特點
??????免疫算法是受免疫學啟發,模擬生物免疫系統功能和原理來解決復雜問題的自適應智能系統,它保留了生物免疫系統所具有的若干特,包括:
??????(1)全局搜索能力。模仿免疫應答過程提出的免疫算法是一 種具有全局搜索能力的優化算法,免疫算法在對優質抗體鄰域進行局部搜索的同時利用變異算子和種群刷新算子不斷產生新個體,探索可行解區間的新區域,保證算法在完整的可行解區間進行搜索,具有全局收斂性能。
??????(2)多樣性保持機制。免疫算法借鑒了生物免疫系統的多樣性保持機制,對抗體進行濃度計算,并將濃度計算的結果作為評價抗體個體優劣的-一個重要標準;它使濃度高的抗體被抑制,保證抗體種群具有很好的多樣性,這也是保證算法全局收斂性能的一個重要方面。
??????(3)魯棒性強。基于生物免疫機理的免疫算法不針對特定問題,而且不強調算法參數設置和初始解的質量,利用其啟發式的智能搜索機制,即使起步于劣質解種群,最終也可以搜索到問題的全局最優解,對問題和初始解的依賴性不強,具有很強的適應性和魯棒性。
??????(4)并行分布式搜索機制。免疫算法不需要集中控制,可以實現并行處理。而且,免疫算法的優化進程是一種多進程的并行優化,在探求問題最優解的同時可以得到問題的多個次優解,即除找到問題的最佳解決方案外,還會得到若干較好的備選方案,尤其適合于多模態的優化問題。
免疫算法算子
??????與遺傳算法等其他智能優化算法類似,免疫算法的進化尋優過程也是通過算子來實現的。免疫算法的算子包括:親和度評價算子、抗體濃度評價算子、激勵度計算算子、免疫選擇算子、克隆算子、變異算子、克隆抑制算子和種群刷新算子等。由于算法的編碼方式可能為實數編碼、離散編碼等,不同編碼方式下的算法算子會有所不同
親和度評價算子
??????親和度表征免疫細胞與抗原的結合強度,與遺傳算法中的適應度類似。親和度評價算子通常是一個函數aff(x): S∈R,其中S為問題的可行解區間,R為實數域。函數的輸入為一個抗體個體(可行解),輸出即為親和度評價結果。親和度的評價與問題具體相關,針對不同的優化問題,應該在理解問題實質的前提下,根據問題的特點定義親和度評價函數。通常函數優化問題可以用函數值或對函數值的簡單處理(如取倒數、相反數等)作為親和度評價,而對于組合優化問題或應用中更為復雜的優化問題,則需要具體問題具體分析。
抗體濃度評價算子
??????抗體濃度表征抗體種群的多樣性好壞。抗體濃度過高意味著種群中非常類似的個體大量存在,則尋優搜索會集中于可行解區間的一一個區域,不利于全局優化。因此優化算法中應對濃度過高的個體進行抑制,保證個體的多樣性。
??????抗體濃度通常定義為:濃度越低值越大
??????進行抗體濃度評價的–個前提是抗體間親和度的定義。免疫中經常提到的親和度為抗體對抗原的親和度,實際上抗體和抗體之間也存在著親和度的概念,它代表了兩個抗體個體之間的相似程度。抗體間親和度的計算方法主要包括基于抗體和抗原親和度的計算方法、基于歐氏距離的計算方法、基于海明距離的計算方法、基于信息熵的計算方法等。
??????對于實數編碼的算法,抗體間親和度通常可以通過抗體向量之間的歐氏距離來計算:
??????對于基于離散編碼的算法,衡量抗體_抗體親和度最直接的方法就是利用抗體串的海明距離:
激勵度計算算子
??????抗體激勵度是對抗體質量的最終評價結果,需要綜合考慮抗體親和度和抗體濃度,通常親和度大(目標函數值好)、濃度低的抗體會得到較大的激勵度(即優秀)。抗體激勵度的計算通
常可以利用抗體親和度和抗體濃度的評價結果進行簡單的數學運算得到,如:
免疫選擇算子
??????免疫選擇算子根據抗體的激勵度確定選擇哪些抗體進入克隆選擇操作。在抗體群中激勵度高的抗體個體具有更好的質量,更有可能被選中進行克隆選擇操作,在搜索空間中更有搜索價值。
克隆算子
??????克隆算子將免疫選擇算子選中的抗體個體進行復制。,
變異算子
??????變異算子對克隆算子得到的抗體克隆結果進行變異操作,以產生親和度突變,實現局部搜索。變異算子是免疫算法中產生有潛力的新抗體、實現區域搜索的重要算子,它對算法的性能有很大影響。變異算子也和算法的編碼方式相關,實數編碼的算法和離散編碼的算法采用不同的變異算子。
克隆抑制算子
??????克隆抑制算子用于對經過變異后的克隆體進行再選擇,抑制親和度低的抗體,保留親和度高的抗體進入新的抗體種群。在克隆抑制的過程中,克隆算子操作的源抗體與克隆體經變異算子作用后得到的臨時抗體群共同組成-一個合,克隆抑制操作將保留此集合中親和度最高的抗體,抑制其他抗體。由于克隆變異算子操作的源抗體是種群中的優質抗體,而克隆抑制算子操作的臨時抗體集合中又包含了父代的源抗體,因此在免疫算法的算子操作中隱含了最優個體保留機制。
種群刷新算子
??????種群刷新算子用于對種群中激勵度較低的抗體進行刷新,從抗體種群中刪除這些抗體并以隨機生成的新抗體替代,有利于保持抗體的多樣性,實現全局搜索,探索新的可行解空間區域。
免疫算法流程
免疫算法算例
算例1
??????求函數f(x,y)= 5sin(x)+x2+y的最小值,其中x的取值范圍為[-4, 4],y的取值范圍為[-_4,4]。這是一個有多個局部極值的函數。
matlab求解
%%%%%%%%%%%%%%%%%免疫算法求函數極值%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%%%%%% clear all; %清除所有變量 close all; %清圖 clc; %清屏 D=2; %免疫個體維數 NP=50; %免疫個體數目 Xs=4; %取值上限 Xx=-4; %取值下限 G=200; %最大免疫代數 pm=0.7; %變異概率 alfa=2; %激勵度系數 belta=1; %激勵度系數 detas=0.2; %相似度閾值 gen=0; %免疫代數 Ncl=5; %克隆個數 deta0=0.5*Xs; %鄰域范圍初值 %%%%%%%%%%%%%%%%%%%%%%%初始種群%%%%%%%%%%%%%%%%%%%%%%%% f=rand(D,NP)*(Xs-Xx)+Xx; for np=1:NPMSLL(np)=func2(f(:,np)); end %%%%%%%%%%%%%%%%%計算個體濃度和激勵度%%%%%%%%%%%%%%%%%%% for np=1:NPfor j=1:NP nd(j)=sum(sqrt((f(:,np)-f(:,j)).^2));if nd(j)<detasnd(j)=1;elsend(j)=0;endendND(np)=sum(nd)/NP; end MSLL = alfa*MSLL- belta*ND; %%%%%%%%%%%%%%%%%%%激勵度按升序排列%%%%%%%%%%%%%%%%%%%%%% [SortMSLL,Index]=sort(MSLL); Sortf=f(:,Index); %%%%%%%%%%%%%%%%%%%%%%%%免疫循環%%%%%%%%%%%%%%%%%%%%%%%% while gen<Gfor i=1:NP/2%%%%%%%%選激勵度前NP/2個體進行免疫操作%%%%%%%%%%%a=Sortf(:,i);Na=repmat(a,1,Ncl);deta=deta0/gen;for j=1:Nclfor ii=1:D%%%%%%%%%%%%%%%%%變異%%%%%%%%%%%%%%%%%%%if rand<pmNa(ii,j)=Na(ii,j)+(rand-0.5)*deta;end%%%%%%%%%%%%%%邊界條件處理%%%%%%%%%%%%%%%if (Na(ii,j)>Xs) | (Na(ii,j)<Xx)Na(ii,j)=rand * (Xs-Xx)+Xx;endendendNa(:,1)=Sortf(:,i); %保留克隆源個體%%%%%%%%%%克隆抑制,保留親和度最高的個體%%%%%%%%%%for j=1:NclNaMSLL(j)=func2(Na(:,j));end[NaSortMSLL,Index]=sort(NaMSLL);aMSLL(i)=NaSortMSLL(1);NaSortf=Na(:,Index);af(:,i)=NaSortf(:,1);end %%%%%%%%%%%%%%%%%%%%免疫種群激勵度%%%%%%%%%%%%%%%%%%%for np=1:NP/2for j=1:NP/2nda(j)=sum(sqrt((af(:,np)-af(:,j)).^2)); if nda(j)<detasnda(j)=1;elsenda(j)=0;endendaND(np)=sum(nda)/NP/2;endaMSLL = alfa*aMSLL- belta*aND;%%%%%%%%%%%%%%%%%%%%%%%種群刷新%%%%%%%%%%%%%%%%%%%%%%%bf=rand(D,NP/2)*(Xs-Xx)+Xx;for np=1:NP/2bMSLL(np)=func2(bf(:,np));end%%%%%%%%%%%%%%%%%%%新生成種群激勵度%%%%%%%%%%%%%%%%%%%%for np=1:NP/2for j=1:NP/2ndc(j)=sum(sqrt((bf(:,np)-bf(:,j)).^2));if ndc(j)<detasndc(j)=1;elsendc(j)=0;endendbND(np)=sum(ndc)/NP/2;endbMSLL = alfa*bMSLL- belta*bND;%%%%%%%%%%%%%%免疫種群與新生種群合并%%%%%%%%%%%%%%%%%%%f1=[af,bf];MSLL1=[aMSLL,bMSLL];[SortMSLL,Index]=sort(MSLL1);Sortf=f1(:,Index);gen=gen+1;trace(gen)=func2(Sortf(:,1)); end %%%%%%%%%%%%%%%%%%%%%%%輸出優化結果%%%%%%%%%%%%%%%%%%%%%%%% Bestf=Sortf(:,1); %最優變量 trace(end); %最優值 figure,plot(trace) xlabel('迭代次數') ylabel('目標函數值') title('親和度進化曲線')%%%%%%%%%%%%%%%%%%%%%%%%%親和度函數%%%%%%%%%%%%%%%%%%%%%% function value=func2(x) value=5*sin(x(1)*x(2))+x(1)*x(1)+x(2)*x(2); endpython求解
import numpy as np import pandas as pd from tqdm import tqdm#進度條設置 import matplotlib.pyplot as plt from pylab import * import matplotlib; matplotlib.use('TkAgg') mpl.rcParams['font.sans-serif'] = ['SimHei'] mpl.rcParams['axes.unicode_minus'] = False####################初始化參數################### D=2 #免疫個體維數 NP=50 #免疫個體數目 Xs=4 #取值上限 Xx=-4 #取值下限 G=200 #最大免疫代數 pm=0.7 #變異概率 alfa=2 #激勵度系數 belta=1 #激勵度系數 detas=0.2 #相似度閾值 gen=0 #免疫代數 Ncl=5 #克隆個數 deta0=0.5*Xs #鄰域范圍初值###目標函數 def calc_f(X):value = 5*np.sin(X[0]*X[1]) +(X[0] * X[0] + X[1] * X[1])return value##############計算個體濃度和激勵度########## def motivation(x,num):ND = np.zeros((num,1)) #臨時數組nd = np.zeros((num,1)) #濃度for i in range(num):for j in range(num):tmp = np.sqrt(np.sum((x[i, :] - x[j, :]) ** 2))if (tmp > detas):ND[i,0] = 0else:ND[i,0] = 1nd[i,0] = np.sum(ND) / num## 激勵度MSLL = np.zeros((num,1))for i in range(num):tmp = calc_f(x[i])MSLL[i,0] = tmpmtv = alfa * MSLL - belta * ndreturn mtv#################免疫算法####################種群初始化 f=np.random.random((NP,D))*(Xs-Xx)+Xx #shape(50, 2)MSLL=np.zeros((NP,1)) #存儲當代種群激勵度值#統一術語:親和度值最高=激勵度值最低 ##計算初始種群親和度值(激勵度值) for i in range(NP):MSLL[i]=calc_f(f[i])###激勵度按升序排序 Index=np.argsort(MSLL,axis=0) Index=Index[:,0] Sortf=f[Index] #shape(50, 2)af=np.zeros((np.int(NP/2),D))#存儲變異后的個體trace=[] #記錄迭代激勵度最優值 #########免疫循環############ for gen in tqdm(range(G)):#遍歷每一次迭代for i in range(np.int(NP/2)):#遍歷前一半樣本#選激勵度前NP/2個體進行免疫操作a = Sortf[i]#當前個體 .shape(2,)a=a.reshape(-1,2)Na = np.tile(a,(Ncl,1)) #對當前個體進行克隆 Na.shape=(5, 2)deta = deta0 / (gen+1) #剛開始迭代時,deta較大,隨著迭代次數變多,deta減少for j in range(Ncl):#遍歷每一個克隆樣本for ii in range(D):#遍歷每一個維度################變異####if np.random.random()<pm:#以一定概率進行變異Na[j,ii]=Na[j,ii]+(np.random.random()-0.5)*deta #元素=元素+加一個很小的隨機數#邊界條件處理if Na[j,ii]>Xs or Na[j,ii]<Xx:#如果在上下限范圍外Na[j, ii]=np.random.uniform(Xx,Xs,1)#保留克隆源個體Na[0,:]=Sortf[i]#####克隆抑制,保留親和度最高的個體NaMSLL = np.zeros((Ncl, 1)) # 存儲變異種群激勵度值for j in range(Ncl): # 遍歷每一個克隆樣本NaMSLL[j]=calc_f(Na[j])Index = np.argsort(NaMSLL, axis=0)#激勵度按升序排序Index = Index[:, 0]NaSortf=Na[Index] #排序后的種群af[i]=NaSortf[0] #取最優#print(af.shape)#(25, 2)####免疫種群(克隆變異部分的)激勵度aMSLL=motivation(af,af.shape[0])#print(aMSLL.shape)#(25, 1)###種群刷新,產生一半新生群體bf = np.random.random((np.int(NP/2),D))*(Xs-Xx)+Xx #bf.shape=(25, 2)bMSLL=motivation(bf,bf.shape[0])#新生種群的激勵度 bMsLL.shape=(25, 1)#########免疫種群與新生種群合并#############f1 = np.concatenate((af,bf),axis=0) # 合并的種群 f1.shape=(50, 2)MSLL1=np.concatenate((aMSLL,bMSLL),axis=0) # 合并種群激勵度值 MSLL1.shape=(50, 1)Index = np.argsort(MSLL1, axis=0)Index = Index[:, 0]Sortf = f1[Index] # shape(50, 2)trace.append(calc_f(f1[0]))#記錄最優個體的激勵度值############輸出優化結果 Bestf=Sortf[0,:] #最優變量 print('最優變量',Bestf) print('最優值',trace[-1] ) #最優值plt.plot(trace) plt.title('迭代曲線') plt.show()免疫算法求解復雜約束問題
求解方法
- 一開始設計編碼規則時,讓解編碼就只可能在可行區域內。典型的例子是算法做實數函數的優化,會給出 upper bound和lower bound,然后無論怎樣的個體,解碼后都在這兩個bound之間 。
- 設計合理的變異算子,使得滿足這些算子本身的特性的前提下,還讓算子運算后的個體也在可行域內。此方法 例子見TSP求解。
- 罰函數法。萬能方法。但罰函數太多或太嚴格,會導致效果很差。懲罰系數較大,族群會更加集中在可行域中,而不鼓勵向不可行域探索。當懲罰系數過大,容易使算法收斂于局部最優;懲罰系數較小,族群會更積極在不可行域中進行大量探索,一定程度上能幫助尋找全局最優,但也有浪費算力的風險。當懲罰系數過小,算法可能會收斂于不可行解。
- 在變異/交叉之后加入一個判斷語句,判斷是否滿足約束條件,如果不滿足,有兩個策略:超出邊界的放到邊界上。或者超出邊界的,重新初始化。
注意事項
??????在優化算法中,每一步迭代都會更新個體和群體,雖然可以將有約束問題轉換為無約束問題進行迭代求解,但是問題的解xi依然存在不滿足約束條件的情況,因此需要編制一些規則來比較兩個粒子的優劣,規則如下:
- 如果兩個粒子xi和xj都可行,則比較其適應度函數f(xi)和f(xj),值小的粒子為優。
- 當兩個粒子xi和xj都不可行,則比較懲罰項P(xi)和P(xj),違背約束程度小的粒子更優。
- 當粒子xi可行而粒子xj不可行,選可行解。
?????問題
流程圖
此流程圖是我自己的求解思路
python 版求解
import numpy as np import pandas as pd from tqdm import tqdm#進度條設置 import matplotlib.pyplot as plt from pylab import * import matplotlib; matplotlib.use('TkAgg') mpl.rcParams['font.sans-serif'] = ['SimHei'] mpl.rcParams['axes.unicode_minus'] = False####################初始化參數################### D=2 #免疫個體維數 NP=50 #免疫個體數目 G=50 #最大免疫代數 pm=0.7 #變異概率 alfa=2 #激勵度系數 belta=1 #激勵度系數 detas=0.2 #相似度閾值 gen=0 #免疫代數 Ncl=5 #克隆個數 deta0=0.5*2 #鄰域范圍初值########################這里定義一些參數,分別是計算激勵度函數和計算約束懲罰項函數############def calc_f(X):"""計算個體的目標函數值,X 的維度是 size * 2 """a = 10pi = np.pix = X[0]y = X[1]return 2 * a + x ** 2 - a * np.cos(2 * pi * x) + y ** 2 - a * np.cos(2 * 3.14 * y)def calc_e(X):"""計算個體的目懲罰項,X 的維度是 size * 2 """ee = 0"""計算第一個約束的懲罰項"""e1 = X[0] + X[1] - 6ee += max(0, e1)"""計算第二個約束的懲罰項"""e2 = 3 * X[0] - 2 * X[1] - 5ee += max(0, e2)return ee########################這里定義一些免疫算法相關的函數#############統一術語:激勵度最低=親和度最高#計算個體濃度和激勵度## def motivation(x,num):"""param x:群體param num:群體個數return : alfa*(目標函數值+懲罰項)-belta*濃度 .其中的目標函數值為最小化問題"""ND = np.zeros((num,1)) #臨時數組nd = np.zeros((num,1)) #濃度for i in range(num):for j in range(num):tmp = np.sqrt(np.sum((x[i, :] - x[j, :]) ** 2))if (tmp > detas):ND[i,0] = 0else:ND[i,0] = 1nd[i,0] = np.sum(ND) / num #濃度## 激勵度MSLL = np.zeros((num,1)) #MSLL存儲 群體激勵度。激勵度=目標函數值+懲罰項for i in range(num):tmp = calc_f(x[i])#目標函數值ee=calc_e(x[i]) #懲罰項MSLL[i,0] = tmp+ee #激勵度=目標函數值+懲罰項mtv = alfa * MSLL - belta * ndreturn mtv#alfa*(目標函數值+懲罰項)-belta*濃度#免疫操作函數:克隆、變異、變異抑制 def variation(Sortf):"""param Sortf:按親和度大小排序后的群體return :af 經過克隆、變異、變異抑制后的群體"""af = np.zeros((np.int(NP / 2), D)) # 存儲變異后的個體for i in range(np.int(NP / 2)): # 遍歷前一半個體# 選激勵度前NP/2個體進行免疫操作a = Sortf[i] # 當前個體 .shape(D,)a = a.reshape(-1, D) #(-1,維度D)Na = np.tile(a, (Ncl, 1)) # 對當前個體進行克隆 Na.shape=(Ncl, D)deta = deta0 / (gen + 1) # 剛開始迭代時,deta較大,隨著迭代次數變多,deta減少for j in range(Ncl):#遍歷每一個克隆樣本for ii in range(D):#遍歷每一個維度################變異####if np.random.random()<pm:#以一定概率進行變異Na[j,ii]=Na[j,ii]+(np.random.random()-0.5)*deta #元素=元素+加一個很小的隨機數# x邊界條件處理if Na[j, 0] > 2 or Na[j, 0] < 1: # 如果在上下限范圍外Na[j, 0] = np.random.uniform(1, 2, 1)#y邊界條件處理if Na[j, 1] > 0 or Na[j, 1] < -1: # 如果在上下限范圍外Na[j, 1] = np.random.uniform(-1, 0, 1)# 保留克隆源個體Na[0, :] = Sortf[i]#####克隆抑制,保留親和度最高(激勵度最低)的個體NaMSLL = np.zeros((Ncl, 1)) # 存儲變異種群激勵度值for j in range(Ncl): # 遍歷每一個克隆樣本NaMSLL[j]=calc_f(Na[j])+calc_e(Na[j]) #目標函數值+懲罰項Index = np.argsort(NaMSLL, axis=0) # 激勵度按升序排序Index = Index[:, 0]NaSortf = Na[Index] # 排序后的種群af[i] = NaSortf[0] # 取最優return af #免疫操作:創建新生種群 def refresh():"""創建一般新生種群并返回"""bf = np.random.random((np.int(NP / 2), D))##邊界條件處理for j in range(bf.shape[0]):#遍歷每一個個體#x邊界條件處理if bf[j, 0] > 2 or bf[j, 0] < 1: # 如果在上下限范圍外bf[j, 0] = np.random.uniform(1, 2, 1)#y邊界條件處理if bf[j, 1] > 0 or bf[j, 1] < -1: # 如果在上下限范圍外bf[j, 1] = np.random.uniform(-1, 0, 1)return bf#############這里定義懲罰項帶來的子代與父代的選擇函數 #子代和父輩之間的選擇操作 def update_best(parent,parent_fitness,parent_e,child,child_fitness,child_e):"""判:param parent: 父輩個體:param parent_fitness:父輩適應度值:param parent_e :父輩懲罰項:param child: 子代個體:param child_fitness 子代適應度值:param child_e :子代懲罰項:return: 父輩 和子代中較優者、適應度、懲罰項"""# 規則1,如果 parent 和 child 都沒有違反約束,則取適應度小的if parent_e <= 0.0000001 and child_e <= 0.0000001:if parent_fitness <= child_fitness:return parent,parent_fitness,parent_eelse:return child,child_fitness,child_e# 規則2,如果child違反約束而parent沒有違反約束,則取parentif parent_e < 0.0000001 and child_e >= 0.0000001:return parent,parent_fitness,parent_e# 規則3,如果parent違反約束而child沒有違反約束,則取childif parent_e >= 0.0000001 and child_e < 0.0000001:return child,child_fitness,child_e# 規則4,如果兩個都違反約束,則取適應度值小的if parent_fitness <= child_fitness:return parent,parent_fitness,parent_eelse:return child,child_fitness,child_e########################免疫算法流程開始數###############1.種群初始化 f=np.random.random((NP,D)) #shape(50, 2) MSLL=np.zeros((NP,1)) #存儲當代種群親和值##2.計算初始種群激勵度值(親和度值) for i in range(NP):MSLL[i]=calc_f(f[i])+calc_e(f[i])###3.激勵度按升序排序 Index=np.argsort(MSLL,axis=0) Index=Index[:,0] Sortf=f[Index] #shape(50, 2) #排序后的初始群體###4.免疫循環 trace=[] #記錄迭代激勵度最優值 for gen in tqdm(range(G)):#遍歷每一次迭代af=variation(Sortf)# 選擇一半個體 進行克隆、變異、變異抑制aMSLL = motivation(af, af.shape[0]) #計算上一步得到的群體(親和度) 激勵度=alfa*(目標函數值+懲罰項)-belta*濃度 shape=(25,1)bf=refresh()#創建一半新生種群#bf.shape=(25, 2)bMSLL = motivation(bf, bf.shape[0]) # 新生種群的激勵度 bMsLL.shape=(25, 1)# ##########種群刷新:免疫種群與新生種群合并##f1 = np.concatenate((af, bf), axis=0) # 合并的種群 f1.shape=(50, 2) f1為子代MSLL1 = np.concatenate((aMSLL, bMSLL), axis=0) # 合并種群激勵度值 MSLL1.shape=(50, 1)# 更新群體#Sortf為父代群體parentfitness= motivation(Sortf, Sortf.shape[0]) #父代親和度#子代和父代的選擇,首先選對的for j in range(NP):#遍歷每一個個體parent=Sortf[j]#父親parent_fitness=parentfitness[j]#父親親和度parent_ee=calc_e(parent) #父親懲罰項child=f1[j]#兒子child_fitness=MSLL1[j]#兒子親和度child_ee=calc_e(child)#兒子懲罰項f1[j],child_fitness1,child_ee1=update_best(parent, parent_fitness, parent_ee,child, child_fitness,child_ee)#得到子代與父代選擇更新后的群體f1MSLL2=motivation(f1, f1.shape[0])#種群激勵度值 MSLL2.shape=(50, 1)Index = np.argsort(MSLL2, axis=0)Index = Index[:, 0]Sortf = f1[Index] # shape(50, 2)trace.append(calc_f(f1[0])) # 記錄最優個體的激勵度值############輸出優化結果 Bestf=Sortf[0,:] #最優變量 print('最優變量',Bestf) print('最優值',trace[-1] ) #最優值 print('懲罰項',calc_e(Bestf))plt.plot(trace) plt.title('迭代曲線') plt.show()這題我以前用粒子群、遺傳、差分 求過(見以前博客)。算法來的值為1.5.免疫算法算出來的為1。 可以看出在實數編碼中,免疫算法比哪幾種算法強。
離散編碼免疫算法見:
離散免疫算法求解旅行商問題(源碼實現)
二進制編碼免疫算法見:
免疫算法(二進制)算例(源碼實現)
作者:電氣-余登武
總結
以上是生活随笔為你收集整理的万字长文了解免疫算法原理 及求解复杂约束问题(源码实现)的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 地暖机安全隐患大吗?
- 下一篇: 笑笑家用A地砖90块。如果改用B地砖需要