DE算法
DE(Differential Evolution)
差分進化算法是一種新興的進化計算技術。它是由Storn等人于1995年提出的，和其它演化算法一樣，DE是一種模擬生物進化的隨機模型，通過反復迭代，使得那些適應環境的個體被保存了下來。但相比于進化算法，DE保留了基于種群的全局搜索策略，采用實數編碼、基于差分的簡單變異操作和一對一的競爭生存策略，降低了遺傳操作的復雜性。
關鍵理念：初為GA的變種，后自稱一派
和GA，EP，ES不同，DE不是生物學啟發的。
個體表示：
一般用實數編碼，(x1,x2,…,xn)就是它的個體表達形式。
接下來介紹DE算法的各個部分：
父代個體選擇：
基向量選擇：一般有三種選擇方式，１．隨機從種群中選擇一個個體。２．選擇當前種群最好的個體。３．選擇當前個體（DE的處理一般是對種群分個處理）。 產生差向量：一般可以產生１個或２個差向量，從種群中隨機選取兩個或多個個體相減產生。
重組：
產生實驗向量：選擇當前要更新的個體與變異向量交叉重組。隨機產生一個概率值當它小于重組閾值時將變異向量賦給試驗向量否則將當前個體賦給試驗向量 產生變異向量：可以是當前基向量，或者是當前個體。需要保持試驗向量至少有一維是來自變異向量的。
變異：
變異這部分有專門的公式：
當然理論上來說步長因子需要保持兩性，如果設為整個種群同一個值在實驗中似乎影響也不大。
存活選擇：
當前子代如果好于父代，則存活。
有了這些東西我們就可以編出相應的代碼：
function [answer,best]=DE(fun)
global popnum ubound lbound dim F cost times
best=inf;
answer=zeros(times,cost/popnum);
for i=1:timesX=initpop();thebest=inf;for j=1:cost/popnumfor k=1:popnum[BV,DV]=PS(X);TV=variant(X(k,:),BV,DV);X(k,:)=selecsur(X(k,:),TV);endanswer(i,j)=thebest;if thebest<bestbest=thebest;endend
endfunction X=initpop()
X=unifrnd(lbound,ubound,popnum,dim);
endfunction [BV,DV]=PS(X) %父代選擇
BV=X(unidrnd(popnum),:); %隨機選取一個個體作為基向量
DV=diff(X(randperm(popnum,3),:)); %隨機生成兩個差向量
end function TV=variant(X,BV,DV) %變異
MV=BV+F*mean(DV);
TV=zeros(1,dim);
flag=0;
for i1=1:dimif rand()<0.8TV(i1)=MV(i1);flag=1;elseTV(i1)=X(i1);endif flag==0n=unidrnd(dim);TV(n)=MV(n);end
end
endfunction f=fit(X) %適應值函數f=fun(X);
end function luck=selecsur(X,newX) %生存選擇
new=fit(newX);
old=fit(X);
if new<oldgood=new;luck=newX;
elsegood=old;luck=X;
end
if good<thebestthebest=good;
end
end
end
測試branin函數:
global popnum ubound lbound vs dim cost times F
popnum=50; %種群數量
ubound=15; %個體維度大小上限
lbound=-5; %個體維度大小下限
F=0.7 %統一的步長
vs=0.3; %變異強度臨界值
dim=2; %個體維度大小
cost=20000; %計算代價
times=30; %重復計算次數
fun=@(x)(x(2)-(5.1/(4*pi^2))*x(1)^2+5*x(1)/pi-6)^2+10*(1-1/(8*pi))*cos(x(1))+10;
[answer,best]=DE(fun) %best為DE找到的最優值，answer為每次計算得到的最好結果變化矩陣
plt(answer);
function plt(answer) %繪制L曲線圖
hisbest=reshape(answer',1,size(answer,1)*size(answer,2));
hisbest(1)=max(hisbest);
for k=2:length(hisbest)if hisbest(k)>hisbest(k-1)hisbest(k)=hisbest(k-1);end
end
for t=2:length(hisbest)hisbest(t)=(hisbest(t)+hisbest(t-1)*(t-1))/t;
end
plot(log(hisbest));
hold on
end
結果如下：
總結
