????????以下內(nèi)容大部分來(lái)源于《MATLAB智能算法30個(gè)案例分析》，僅為學(xué)習(xí)交流所用。
1 理論基礎(chǔ)
1.1 遺傳算法早熟問題
????????遺傳算法是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來(lái)的高度并行、隨機(jī)、自適應(yīng)的全局優(yōu)化概率搜索算法。由于優(yōu)化時(shí)不依賴于梯度，具有很強(qiáng)的魯棒性和全局搜索能力，因此，被廣泛應(yīng)用于機(jī)器學(xué)習(xí)、模式識(shí)別、數(shù)學(xué)規(guī)劃等領(lǐng)域。然而，隨著遺傳算法的廣泛應(yīng)用以及研究的深入，其諸多缺陷與不足也暴露出來(lái)，例如，早熟收斂問題。
????????未成熟收斂是遺傳算法中不可忽視的現(xiàn)象，主要表現(xiàn)在群體中的所有個(gè)體都趨于同一狀態(tài)而停止進(jìn)化，算法最終不能給出令人滿意的解。未成熟收斂的發(fā)生主要和下列幾個(gè)方面有關(guān)：
????????(1)選擇操作是根據(jù)當(dāng)前群體中個(gè)體的適應(yīng)度值所決定的概率進(jìn)行的，當(dāng)群體中存在個(gè)別超常個(gè)體時(shí)(該個(gè)體的適應(yīng)度比其他個(gè)體高得多),該個(gè)體在選擇算子作用下將會(huì)多次被選中，下一代群體很快被該個(gè)體所控制，群體中失去競(jìng)爭(zhēng)性，從而導(dǎo)致群體停滯不前。
????????(2)交叉和變異操作發(fā)生的頻度是受交叉概率Pe和變異概率Pm控制的。Pe和Pm的恰當(dāng)設(shè)定涉及遺傳算法全局搜索和局部搜索能力的均衡，進(jìn)化搜索的最終結(jié)果對(duì)Pe、Pm的取值相當(dāng)敏感，不同的Pe、Pm取值很可能會(huì)導(dǎo)致不同的計(jì)算結(jié)果。
????????(3)群體規(guī)模對(duì)遺傳算法的優(yōu)化性能也有較大的影響。當(dāng)群體規(guī)模較小時(shí)，群體中多樣性程度低，個(gè)體之間競(jìng)爭(zhēng)性較弱，隨著進(jìn)化的進(jìn)行，群體很快趨于單一化，交叉操作產(chǎn)生新個(gè)體的作用漸趨消失，群體的更新只靠變異操作來(lái)維持，群體很快終止進(jìn)化；當(dāng)群體規(guī)模取值較大時(shí)，勢(shì)必造成計(jì)算量的增加，計(jì)算效率受到影響。
????????(4)遺傳算法常用的終止判據(jù)是，當(dāng)?shù)螖?shù)到達(dá)人為規(guī)定的最大遺傳代數(shù)時(shí)，則終止進(jìn)化。如迭代次數(shù)過少，進(jìn)化不充分，也會(huì)造成未成熟收斂。為克服未成熟收斂，許多學(xué)者對(duì)算法改進(jìn)進(jìn)行了一些有益的探索，特別對(duì)遺傳控制參數(shù)的設(shè)定，提出了自適應(yīng)的交叉和變異，并獲得了一些有益的結(jié)論。但是，遺傳算法的未成熟收斂與上述諸多因素有關(guān)，在應(yīng)用遺傳算法解決實(shí)際問題時(shí)，控制參數(shù)如何設(shè)定，遺傳算子如何設(shè)計(jì)往往是根據(jù)實(shí)際問題試探性地給出，不恰當(dāng)?shù)脑O(shè)定會(huì)在很大程度上影響算法的性能。
1.2 多種群遺傳算法概述
????????針對(duì)遺傳算法所存在的上述問題，一種多種群遺傳算法(multiple population GA, MPGA)可以用來(lái)取代常規(guī)的標(biāo)準(zhǔn)遺傳算法(SGA)。MPGA在SGA的基礎(chǔ)上主要引入了以下幾個(gè)概念：
????????(1)突破SGA僅靠單個(gè)群體進(jìn)行遺傳進(jìn)化的框架，引入多個(gè)種群同時(shí)進(jìn)行優(yōu)化搜索；不同的種群賦以不同的控制參數(shù)，實(shí)現(xiàn)不同的搜索目的。
????????(2)各個(gè)種群之間通過移民算子進(jìn)行聯(lián)系，實(shí)現(xiàn)多種群的協(xié)同進(jìn)化；最優(yōu)解的獲取是多個(gè)種群協(xié)同進(jìn)化的綜合結(jié)果。
????????(3)通過人工選擇算子保存各種群每個(gè)進(jìn)化代中的最優(yōu)個(gè)體，并作為判斷算法收斂的依據(jù)。
????????圖7-1中，種群1～N的進(jìn)化機(jī)制都是常規(guī)的SGA,采用輪盤賭選擇、單點(diǎn)交叉和位點(diǎn)變異。
????????各種群取不同的控制參數(shù)。交叉概率Pe和變異概率Pm的取值決定了算法全局搜索和局部搜索能力的均衡。在SGA中，交叉算子是產(chǎn)生新個(gè)體的主要算子，它決定了遺傳算法全局搜索的能力；而變異算子只是產(chǎn)生新個(gè)體的輔助算子，它決定了遺傳算法的局部搜索能力。許多學(xué)者建議選擇較大的Pe(0.7～0.9)和較小的Pm(0.001～0.05)。但是Pe和Pm的取值方式還是有無(wú)數(shù)種，對(duì)于不同的選擇，優(yōu)化結(jié)果差異也是很大的。MPGA彌補(bǔ)了SGA的這一不足，通過多個(gè)設(shè)有不同控制參數(shù)的種群協(xié)同進(jìn)化，同時(shí)兼顧了算法的全局搜索和局部搜索。?
????????各種群是相對(duì)獨(dú)立的，相互之間通過移民算子聯(lián)系。移民算子將各種群在進(jìn)化過程中出現(xiàn)的最優(yōu)個(gè)體定期地(每隔一定的進(jìn)化代數(shù))引入其他的種群中，實(shí)現(xiàn)種群之間的信息交換。具體的操作規(guī)則是，將目標(biāo)種群中的最差個(gè)體用源種群的最優(yōu)個(gè)體代替。移民算子在MPGA中至關(guān)重要，如果沒有移民算子，各種群之間失去了聯(lián)系，MPGA將等同于用不同的控制參數(shù)進(jìn)行多次SGA計(jì)算，從而失去了MPGA的特色。
????????精華種群和其他種群有很大不同。在進(jìn)化的每一代，通過人工選擇算子選出其他種群的最優(yōu)個(gè)體放入精華種群加以保存。精華種群不進(jìn)行選擇、交叉、變異等遺傳操作，保證進(jìn)化過程中各種群產(chǎn)生的最優(yōu)個(gè)體不被破壞和丟失。同時(shí)，精華種群也是判斷算法終止的依據(jù)，這里采用最優(yōu)個(gè)體最少保持代數(shù)作為終止判據(jù)。這種判據(jù)充分利用了遺傳算法在進(jìn)化過程中的知識(shí)積累，較最大遺傳代數(shù)判據(jù)更為合理。
2 案例背景
2.1 問題描述
????????復(fù)雜二元函數(shù)求最值：
?????????matlab代碼及該函數(shù)的圖形如下。
x = linspace(0, 12.1, 200);
y = linspace(4.1, 5.8, 200);
[x, y] = meshgrid(x,y);
f = 21.5+x.*sin(4*pi*x)+y.*sin(20*pi*y);
figure;
surf(x,y,f);
colormap(gca, 'jet')
xlabel('x');
ylabel('y');
zlabel('f(x,y)');
title('函數(shù)圖像')
????????從圖7-2中可以看出，該非線性函數(shù)在給定范圍內(nèi)分布著許多局部極值，通常的尋優(yōu)算法極易陷入局部極值或在各局部極值間振蕩，比較適用于驗(yàn)證多種群遺傳算法的性能。
2.2 解題思路及步驟
????????圖7-1中的SGA流程圖這里不再贅述。本例SGA部分使用英國(guó)謝菲爾德大學(xué)推出的基于MATLAB的遺傳算法工具箱，具體的可以參考謝菲爾德大學(xué)的MATLAB遺傳算法工具箱。本例使用到的工具箱函數(shù)如表7-1所列。
3 MATLAB程序?qū)崿F(xiàn)
????????SGA部分直接使用英國(guó)謝菲爾德大學(xué)推出的基于MATLAB的遺傳算法工具箱，所以對(duì)應(yīng)的函數(shù)實(shí)現(xiàn)這里不做介紹，詳細(xì)的可以參考工具箱函數(shù)。下面詳細(xì)介紹移民算子和人工選擇算子的實(shí)現(xiàn)。
3.1 移民算子
????????移民算子函數(shù)名為immigrant,函數(shù)的輸入、輸出參數(shù)如表7-2所列。
????????具體函數(shù)代碼如下： ?文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-467331.html
function [Chrom,ObjV]=immigrant(Chrom,ObjV)
%% 移民算子
MP=length(Chrom);
for i=1:MP
[MaxO,maxI]=max(ObjV{i}); % 找出第i種群中最優(yōu)的個(gè)體
next_i=i+1; % 目標(biāo)種群（移民操作中）
if next_i>MP;next_i=mod(next_i,MP);end
[MinO,minI]=min(ObjV{next_i}); % 找出目標(biāo)種群中最劣的個(gè)體
%% 目標(biāo)種群最劣個(gè)體替換為源種群最優(yōu)個(gè)體
Chrom{next_i}(minI,:)=Chrom{i}(maxI,:);
ObjV{next_i}(minI)=ObjV{i}(maxI);
end
3.2 人工選擇算子
????????人工選擇算子函數(shù)名為EliteInduvidual,函數(shù)的輸入、輸出參數(shù)如表7-3所列。
????????具體函數(shù)代碼如下： ?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-467331.html
function [MaxObjV,MaxChrom]=EliteInduvidual(Chrom,ObjV,MaxObjV,MaxChrom)
%% 人工選擇算子
MP=length(Chrom); %種群數(shù)
for i=1:MP
[MaxO,maxI]=max(ObjV{i}); %找出第i種群中最優(yōu)個(gè)體
if MaxO>MaxObjV(i)
MaxObjV(i)=MaxO; %記錄各種群的精華個(gè)體
MaxChrom(i,:)=Chrom{i}(maxI,:); %記錄各種群精華個(gè)體的編碼
end
end
3.3 目標(biāo)函數(shù)
????????針對(duì)2.1節(jié)中提出的問題，寫出目標(biāo)函數(shù)，函數(shù)名為ObjectFunction。
function obj=ObjectFunction(X)
%% 待優(yōu)化的目標(biāo)函數(shù)
col=size(X,1);
for i=1:col
obj(i,1)=21.5+X(i,1)*sin(4*pi*X(i,1))+X(i,2)*sin(20*pi*X(i,2));
% obj(i,1)=exp(((X(i,1)-0.1)/0.8)^2)*(sin(5*pi*X(i,1)))^6;
end
3.4 標(biāo)準(zhǔn)遺傳算法主函數(shù)
????????先使用標(biāo)準(zhǔn)遺傳算法解決2.1節(jié)中的問題——復(fù)雜二元函數(shù)優(yōu)化。實(shí)現(xiàn)的主函數(shù)代碼如下：
%% 標(biāo)準(zhǔn)遺傳算法SGA
clear;
%clc
pc=0.7; % 交叉概率
pm=0.05; % 變異概率
%定義遺傳算法參數(shù)
NIND=40; %個(gè)體數(shù)目
MAXGEN=500; %最大遺傳代數(shù)
NVAR=2; %變量的維數(shù)
PRECI=20; %變量的二進(jìn)制位數(shù)
GGAP=0.9; %代溝
trace=zeros(MAXGEN,1); %記錄優(yōu)化軌跡
FieldD=[rep(PRECI,[1,NVAR]);[-3,4.1;12.1,5.8];rep([1;0;1;1],[1,NVAR])]; %建立區(qū)域描述器
Chrom=crtbp(NIND, NVAR*PRECI); %創(chuàng)建初始種群
gen=0; %代計(jì)數(shù)器
ObjV=ObjectFunction(bs2rv(Chrom, FieldD));%計(jì)算初始種群個(gè)體的目標(biāo)函數(shù)值
[maxY,I]=max(ObjV); %最優(yōu)值
X=bs2rv(Chrom, FieldD);
maxX=X(I,:);
while gen<MAXGEN %迭代
FitnV=ranking(-ObjV); %分配適應(yīng)度值(Assign fitness values)
SelCh=select('sus', Chrom, FitnV, GGAP); %選擇
SelCh=recombin('xovsp', SelCh, pc); %重組
SelCh=mut(SelCh,pm); %變異
ObjVSel=ObjectFunction(bs2rv(SelCh, FieldD)); %計(jì)算子代目標(biāo)函數(shù)值
[Chrom ObjV]=reins(Chrom, SelCh, 1, 1, ObjV, ObjVSel); %重插入
gen=gen+1; %代計(jì)數(shù)器增加
if maxY<max(ObjV)
[maxY,I]=max(ObjV);
X=bs2rv(Chrom, FieldD);
maxX=X(I,:);
end
trace(gen,1)=maxY;
end
%% 進(jìn)化過程圖
plot(1:gen,trace(:,1));
hold on
xlabel('進(jìn)化代數(shù)');
ylabel('最優(yōu)解變化');
title('SGA進(jìn)化過程');
%% 輸出最優(yōu)解
disp(['最優(yōu)值為：',num2str(maxY)]);
disp(['對(duì)應(yīng)的自變量取值：',num2str(maxX)]);
3.5 多種群遺傳算法主函數(shù)
????????使用多種群遺傳算法解決實(shí)現(xiàn)的主函數(shù)：
%%
%% 2、多種群遺傳算法
clear;
clc
NIND=40; %個(gè)體數(shù)目
NVAR=2; %變量的維數(shù)
PRECI=20; %變量的二進(jìn)制位數(shù)
GGAP=0.9; %代溝
MP=10; %種群數(shù)目
FieldD=[rep(PRECI,[1,NVAR]);[-3,4.1;12.1,5.8];rep([1;0;1;1],[1,NVAR])]; %譯碼矩陣
for i=1:MP
Chrom{i}=crtbp(NIND, NVAR*PRECI); %創(chuàng)建初始種群
end
pc=0.7+(0.9-0.7)*rand(MP,1); %在【0.7,0.9】范圍i內(nèi)隨機(jī)產(chǎn)生交叉概率
pm=0.001+(0.05-0.001)*rand(MP,1); %在【0.001,0.05】范圍內(nèi)隨機(jī)產(chǎn)生變異概率
gen=0; %初始遺傳代數(shù)
gen0=0; %初始保持代數(shù)
MAXGEN=10; %最優(yōu)個(gè)體最少保持代數(shù)
maxY=0; %最優(yōu)值
for i=1:MP
ObjV{i}=ObjectFunction(bs2rv(Chrom{i}, FieldD));%計(jì)算各初始種群個(gè)體的目標(biāo)函數(shù)值
end
MaxObjV=zeros(MP,1); %記錄精華種群
MaxChrom=zeros(MP,PRECI*NVAR); %記錄精華種群的編碼
while gen0<=MAXGEN
gen=gen+1; %遺傳代數(shù)加1
for i=1:MP
FitnV{i}=ranking(-ObjV{i}); % 各種群的適應(yīng)度
SelCh{i}=select('sus', Chrom{i}, FitnV{i},GGAP); % 選擇操作
SelCh{i}=recombin('xovsp',SelCh{i}, pc(i)); % 交叉操作
SelCh{i}=mut(SelCh{i},pm(i)); % 變異操作
ObjVSel=ObjectFunction(bs2rv(SelCh{i}, FieldD)); % 計(jì)算子代目標(biāo)函數(shù)值
[Chrom{i},ObjV{i}]=reins(Chrom{i},SelCh{i},1,1,ObjV{i},ObjVSel); %重插入操作
end
[Chrom,ObjV]=immigrant(Chrom,ObjV); % 移民操作
[MaxObjV,MaxChrom]=EliteInduvidual(Chrom,ObjV,MaxObjV,MaxChrom); % 人工選擇精華種群
YY(gen)=max(MaxObjV); %找出精華種群中最優(yōu)的個(gè)體
if YY(gen)>maxY %判斷當(dāng)前優(yōu)化值是否與前一次優(yōu)化值相同
maxY=YY(gen); %更新最優(yōu)值
gen0=0;
else
gen0=gen0+1; %最優(yōu)值保持次數(shù)加1
end
end
%% 進(jìn)化過程圖
plot(1:gen,YY);
xlabel('進(jìn)化代數(shù)')
ylabel('最優(yōu)解變化')
title('MPGA進(jìn)化過程')
%% 輸出最優(yōu)解
[Y,I]=max(MaxObjV); %找出精華種群中最優(yōu)的個(gè)體
X=(bs2rv(MaxChrom(I,:), FieldD)); %最優(yōu)個(gè)體的解碼解
disp(['最優(yōu)值為：',num2str(Y)])
disp(['對(duì)應(yīng)的自變量取值：',num2str(X)])4 結(jié)果分析
????????標(biāo)準(zhǔn)遺傳算法運(yùn)行5次得到的結(jié)果如下所示。
????????從結(jié)果可以看出，5次得到的優(yōu)化結(jié)果均不相同，標(biāo)準(zhǔn)遺傳算法很不穩(wěn)定，而且在接近500代的時(shí)候仍然未穩(wěn)定下來(lái)，說(shuō)明最優(yōu)解還有上升的可能。對(duì)于這種復(fù)雜的函數(shù)優(yōu)化，使用標(biāo)準(zhǔn)的遺傳算法已經(jīng)很難得到最優(yōu)解了。
????????多種群遺傳算法運(yùn)行5次得到的結(jié)果如下。
????????從結(jié)果可以看出，多種群遺傳算法運(yùn)行5次的結(jié)果完全一致，說(shuō)明多種群遺傳算法穩(wěn)定性很好，而且使用的遺傳代數(shù)都很小，最大的不超過70代?？梢?，多種群遺傳算法的收斂速度快，適合復(fù)雜問題的優(yōu)化。因?yàn)镸PGA中采用了多個(gè)種群同時(shí)對(duì)解空間進(jìn)行協(xié)同搜索，兼顧了算法的全局搜索和局
部搜索，計(jì)算結(jié)果對(duì)遺傳控制參數(shù)的敏感性大大降低，對(duì)克服未成熟收斂有顯著的效果。
5 延伸閱讀
????????在遺傳算法的基礎(chǔ)上，MPGA將SGA算法結(jié)構(gòu)進(jìn)行了擴(kuò)展，引入了多個(gè)種群同時(shí)對(duì)解空間進(jìn)行協(xié)同搜索，兼顧了算法全局搜索和局部搜索能力的均衡，大大降低了遺傳控制參數(shù)的不當(dāng)設(shè)定對(duì)規(guī)劃結(jié)果的影響，對(duì)抑制未成熟收斂的發(fā)生有明顯的效果。實(shí)際算例表明，MPGA用于復(fù)雜函數(shù)優(yōu)化是非常有效的。 2.1節(jié)中的問題是對(duì)二元函數(shù)的優(yōu)化，MPGA對(duì)于單元或者是其他任意元的函數(shù)優(yōu)化均可以實(shí)現(xiàn)，只是需要稍微做些修改即可。例如在[0,1]區(qū)間求最大值：
只需修改目標(biāo)函數(shù)和主函數(shù)中變量的維數(shù)和譯碼矩陣即可。
到了這里，關(guān)于(轉(zhuǎn)載)多種群遺傳算法的函數(shù)優(yōu)化算法(matlab實(shí)現(xiàn))的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
