Rumia's blog

​ 大致流程图如下:

st=>start: 确定实际问题参数
code=>operation: 对参数集进行编码
init=>operation: 初始化群体P(t)
judge=>operation: 评价群体
con=>condition: 满足停止规则
mutation=>operation: 遗传操作以及产生新一代群体
end=>end: 结束
st->code->init->judge->con
con(yes)->end
con(no)(bottom)->mutation
mutation->init->judge

以求函数$f(x)=9\sin{5x}+8\cos{4x}$ 的最大值为例,讲解遗传算法的过程

初始化(编码)

popsize表示群体大小,chromlength表示染色体长度(二进制数的长度),长度大小取决于变量的二进制编码的长度。

function pop=initpop(popsize,chromlength)
pop=round(rand(popsize,chromlength));
end

目标函数值

1.二进制转化为十进制数

function pop2=decodebinary(pop)
[px,py]=size(pop);
% 求pop的行数和列数
for i=1:py
pop1(:,i)=2.^(py-i)*pop(:,i);
end
pop2=sum(pop1,2);
%求pop1的每行之和
end

2.二进制编码转化为十进制数,spoint表示待解码的二进制串的起始位置。

%将二进制编码转换成十进制
function pop2=decodechrom(pop,spoint,length)
pop1=pop(:,spoint:spoint+length-1);
pop2=popdecodebinary(pop1);
end

3.计算目标函数值

function [objvalue]=calobjvalue(pop)
temp1=decodechrom(pop,1,10);
x=temp1*10/1023;
objvalue=10*sin(5*x)+7*cos(4*x);
end

计算个体适应值

%计算个体适应值
funciton fitvalue=calfitvalue(objvalue)
global Cmin;
Cmin=0;
[px,py]=size(objvalue);
for i=1:px
	if objvalue(i)+Cmin>0
		temp=Cmin+objvalue(i);
	else
		temp=0.0;
	end
	fitvalue(i)=temp;
end
fitvalue=fitvalue'

选择复制

选择或者说复制操作是决定那些个体可以进入下一代,程序中采用赌轮盘选择法选择,此方法较易实现。根据方程 $p_i=\frac{f_i}{\sum{f_i}}$, 选择步骤如下

1.在第 t 代,计算 $\sum{f_i}$ 和$p_i$

2.产生{0,1}的随机数rand(),求s=rand(·)*$\sum{f_i}$

3.求$\sum_{i=1}^{k}{fi}\geq s$中最小的k,则第k个个体被选中

4.进行N次(2)、(3)操作,得到N个个体,成为第 $t=t+1$ 代种群

%选择复制
function [newpop]=selection(pop,fitvalue)
totalfit=sum(fitvalue);
fitvalue=fitvalue/totalfit;
fitvalue=cumsum(fitvalue);
[px,py]=size(pop);
ms=sort(rand(px,1));
fitin=1;
newin=1;;
while newin<=px
	if(ms(newin))<fitvalue(fitin)
		newpop(newin)=pop(fitin);
		newin=newin+1;
	else
		fitin=fitin+1;
	end
end

交叉

%交叉
function [newpop]=crossover(pop,pc)
[px,py]=size(pop);
newpop=ones(size(pop));
for i=1:2:px-1
	if(rand<pc)
		cpoint=round(rand*py);
		newpop(i,:)=[pop(i,1:cpoint),pop(i+1,cpoint+1:py)];
		newpop(i+1,:)=[pop(i+1,1:cpoint),pop(i,cpoint+1:py)];
	else
		newpop(i,:)=pop(i);
		newpop(i+1,:)=pop(i+1);
	end
end

变异

function [newpop]=mutation(pop,pm)
[px,py]=size(pop);
newpop=ones(size(pop));
for i=1:px
	if(rand<px)
		mpoint=round(rand*py);
		if mpoint<=0
			mpoint=1;
		end
		newpop(i)=pop(i);
		if any(newpop(i,mpoint))==0
			newpop(i,mpoint)=1;
		else
			newpop(i,mpoint)=0;
		end
	else
		newpop(i)=pop(i);
	end
end

求出群体中最大适应值及其个体

function [bestindividual,bestfit]=best(pop,fitvalue)
[px,py]=size(pop);
bestindividual=pop(1,:);
bestfit=fitvalue(1);
for i=2:px
	if fitvalue(i)>bestfit
		bestindividual=pop(i,:);
		bestfit=fitvalue(i);
	end
end

main()

clear all
clc
popsize=20;								%群体大小
chromlength=10;							%字符串长度(个体长度)
pc=0.7;									%交叉概率
pm=0.005								%变异概率
pop=initpop(popsize,chromlength);	  	%随机产生初始群体
for i=1:20
	[objvalue]=calobjvalue(pop);	 	%计算目标函数
	fitvalue=calfitvalue(objvalue);	 	%计算群体中每个个体的适应度
	[newpop]=selection(pop,fitvalue);	%复制
	[newpop]=crossover(pop,pc);			%交叉
	[newpop]=mutation(pop,pc);			%变异
[bestindividual,bestfit]=best(pop,fitvalue);%求出群体中适应值最大的个体及其适应值
y(i)=max(bestfit);
n(i)=i;
pop5=bestindividual;
x(i)=decodechrom(pop5,1,chromlength)*10/1023;
pop=newpop;
end
fplot('9*sin(5*x)+8*cos(4*x)',[0 15]);
hold on
plot(x,y,'r*')
hold off

tips

遗传算法有四个参数需要提前设定,一般在一下范围内进行设置。

  1. 群体大小 :20~100(太小会出现近亲交配,产生病态基因)
  2. 遗传算法的终止进化代数:100~500(太小不容易收敛,太大有可能过于早熟不可能再收敛,继续进化无意义)
  3. 交叉概率:0.4~0.99
  4. 变异概率:0.0001~0.1 (太大容易错失最优个体,太小不能有效更新种群)

下一part讲matlab自带的遗传算法工具箱,这个明白大致原理即可。

###