多種群遺傳算法可以解決傳統遺傳算法存在的早熟收斂問題,多種群遺傳算法MPGA在标準遺傳算法SGA的基礎上主要引入了以下概念:
(1)突破SGA僅靠單個群體進行遺傳進化的架構,引入多個種群同時進行優化搜尋;不同的種群賦以不同的控制參數,實作不同的搜尋目的。
(2)各個種群之間通過移民算子進行聯系,實作多種群的協同進化;最優解的擷取是多個種群協同進化的綜合結果。
(3)通過人工選擇算子儲存各種群每個進化代中的最有個體,并作為判斷算法收斂的依據。
MPGA的算法結構示意圖:
下面,我們以一個具體問題為例,使用英國謝菲爾德大學的遺傳算法工具箱求解。
求複雜二進制函數的最值:
求解結果如圖:
圖2 标準遺傳算法運作5次的進化過程圖
求解結果如圖:
圖3 多種群遺傳算法運作5次的進化過程圖
從圖2可見,5次得到的優化結果均不同,标準遺傳算法很不穩定,而且在接近500代的時候任然未穩定下來,說明最優解還有上升的可能。對于這種複雜的函數優化,使用标準的遺傳算法已經很難得到最優解了。
從圖3可見,多種群遺傳算法運作5次的結果完全一緻,說明多種群遺傳算法穩定性很好,而且穩定性很好,而且使用的遺傳代數很小,最大不超過60代,可見,多種群遺傳算法的收斂速度快,适合複雜問題的優化。
參考文獻:
[1]葉在福,單淵達.基于多種群遺傳算法的輸電系統擴充規劃[J].電力系統自動化,2000(05):24-27,35.
[2]餘健明,吳海峰,楊文宇.基于改進多種群遺傳算法的配電網規劃[J].電網技術,2005,29(07):36-40,55.
[3]郝翔,李人厚.适用于複雜函數優化的多群體遺傳算法[J].控制與決策,1998,17(03):184-188.
[4]周文彬,蔡永銘,陳華豔.實值多種群遺傳算法求解動态規劃問題[J].控制工程,2007,5(14):103-104,124.
[5]陳曦,王希誠.一種改進的多種群遺傳算法[J].遼甯科技大學學報,2009,32(2):160-163.
matlab代碼:
%% 多種群遺傳算法
clear;
clc
close all
NIND=40; %個體數目
NVAR=2; %變量的維數
PRECI=20; %變量的二進制位數
GGAP=0.9; %代溝
MP=10; %種群數目
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); %建立初始種群
end
pc=0.7+(0.9-0.7)*rand(MP,1); %在【0.7,0.9】範圍内随機産生交叉機率
pm=0.001+(0.05-0.001)*rand(MP,1); %在【0.001,0.05】範圍内随機産生變異機率
gen=0; %初始遺傳代數
gen0=0; %初始保持代數
MAXGEN=10; %最優個體最少保持代數
maxY=0; %最優值
for i=1:MP
ObjV{i}=ObjectFunction(bs2rv(Chrom{i}, FieldD));%計算各初始種群個體的目标函數值
end
MaxObjV=zeros(MP,1); %記錄精華種群
MaxChrom=zeros(MP,PRECI*NVAR); %記錄精華種群的編碼
while gen0<=MAXGEN
gen=gen+1; %遺傳代數加1
for i=1:MP
FitnV{i}=ranking(-ObjV{i}); % 各種群的适應度
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)); % 計算子代目标函數值
[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); %找出精華種群中最優的個體
if YY(gen)>maxY %判斷目前優化值是否與前一次優化值相同
maxY=YY(gen); %更新最優值
gen0=0;
else
gen0=gen0+1; %最優值保持次數加1
end
end
%% 進化過程圖
plot(1:gen,YY)
xlabel('進化代數')
ylabel('最優解變化')
title('進化過程')
xlim([1,gen])
%% 輸出最優解
[Y,I]=max(MaxObjV); %找出精華種群中最優的個體
X=(bs2rv(MaxChrom(I,:), FieldD)); %最優個體的解碼解
disp(['最優值為:',num2str(Y)])
disp(['對應的自變量取值:',num2str(X)])