引入精英主义的遗传算法MATLAB程序实现.doc

人工智能作业

题 目： 引入精英主义的遗传算法MATLAB程序实现

姓 名： 林俊杰

学 号： 130120052

学 院： 电气工程与自动化学院

专 业： 控制理论与控制工程

年 级： 2013 级

指导教师： 李玉蓉

2014 年 1月 8 日

一、基本遗传算法
遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了 达尔文的进化论和孟德尔的遗传学说。基本遗传算法的步骤有：①初始群体的产生 ②个体编码 ③适应度汁算 ④选择运算 ⑤交叉运算 ⑥变异运算。
二、引入精英主义的基本遗传算法
精英主义(Elitist Strategy)是基本遗传算法的一种优化。为了防止进化过程中产生的最优解被交叉和变异所破坏，可以将每一代中的最优解原封不动的复制到下一代中。引入精英主义的遗传算法具有收敛速度快、最优解寻求稳定、有较好的稳定性。可通过引入精英个数的比例来控制整体的收敛速度，个数越多收敛越快，但过多的精英个数可能会造成算法的局部收敛，反而得到不良结果。
三、基本遗传算法程序运行结果与说明
测试程序采用了Rosenbrock函数，该函数有两个局部极大点和，其中后者为全局最大点。如图1、2、3所示为基本遗传算法在运行过程中，对最优解的跟踪曲线。可以看出未改进的基本遗传算法最优解跟踪曲线呈现出震荡，不稳定。甚至在整个寻求过程都无法找到最后的最优解，这样的遗传算法性能根本无法满足工程及应用要求。如图4所示基本遗传算法在某一代找到了最优解后，该最优解由于在轮盘选择中未被选中，所以很快的算法失去了该最有解，致使整个求解过程震荡，无结果。

图1 图2

图3 图4
三、引入精英主义的遗传算法程序运行结果与说明
引入精英主义后，很好的解决了该问题。如图5、6、7、8所示最优解寻求曲线快速的收敛到最优解，整个曲线平整无波动。具有较好的收敛速度、稳定性。明显克服了基本遗传算法的震荡不稳定。而且在数次运行过程中找出最优解的概率明显增加，但仍然存在不能求的最优解的情况。出现不能求解情况是待改进的地方。

图5 图6

图7 图8

四、总结
通过遗传算法程序的编写，熟悉了遗传算法的工作原理。通过引入精英主义对基本遗传算法进行了改进，解决了基本遗传算法的不稳定性、波动性、收敛速度慢的缺点。但在最优解求解的成功率上改进不是很大，有待将来改进。
五、程序附录
clc;
clear;
popsize=20; %群体大小
chromlength=20; %单个个体长度
pc=0.8; %交叉概率
pm=0.08; %变异概率
global tracenum; %全局变量用于每代中的最大值跟踪
tracenum=1;
global maxtrace;
pop=initpop(popsize,chromlength); %随机产生初始群体
for i=1:600 %600为进化代数
[objvalue]=calobjvalue(pop); %计算目标函数
fitvalue=calfitvalue(objvalue); %计算群体中每个个体的适应度
[newpop]=selection(pop,fitvalue); %选择复制
%objvalue
pop=newpop; %种群更新
[newpop]=crossover(pop,pc); %交叉
pop=newpop;%种群更新
[newpop]=mutation(pop,pm); %变异
pop=newpop;%种群更新
end
[objvalue]=calobjvalue(pop); %计算目标函数
fitvalue=calfitvalue(objvalue); %计算群体中每个个体的适应度
[newpop]=selection(pop,fitvalue); %复制
pop=newpop;%种群更新
******************************************************************************
[objvalue]=calobjvalue(pop)%计算目标函数
x = 1:601;%绘制最大值跟踪图
figure(1);
subplot(1,1,1);
plot(x,maxtrace,'r-o');
%title('加入精英主义的遗传算法最优解跟踪图');
title('基本遗传算法最优解跟踪图');
*************************
function bestindividual=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
global maxtrace;%全局变量声明
global tracenum;%全局变量声明
maxtrace(tracenum)=bestfit;%用于最大适应度跟踪
tracenum=tracenum+1;
*******************************************************************************
function fitvalue=calfitvalue(objvalue)%计算个体的适应度
global Cmin;%全局变量声明
Cmin=0;%适应度最小值
[px,py]=size(objvalue);
for i=1:px
if objvalue(i)+Cmin>0%如果函数值小于0，则适应度为0.否则为函数值
temp=Cmin+objvalue(i);
else
temp=0.0;
end
fitvalue(i)=temp;
end
fitvalue=fitvalue';
******************************************************************************
function [objvalue]=calobjvalue(pop)%函数值计算
temp1=decodechrom(pop,1,10); %将pop每行1到10的元素转化成十进制数
temp2=decodechrom(pop,11,10);%将pop每行11到20的元素转化成十进制数
x1=temp1.*(4.096/1023)-2.048;%将数据转换为原范围数据
x2=temp2.*(4.096/1023)-2.048;%将数据转换为原范围数据
objvalue=100.*(x1.*x1-x2).*(x1.*x1-x2)+(1-x1).*(1-x1);%计算函数值
*********************************************************
function [newpop]=crossover(pop,pc)%交叉过程
[px,py]=size(pop);%求得种群矩阵维数
newpop=ones(size(pop));
x=[1:px];%定义x变量存放交叉顺序
x=x(randperm(numel(x)));%随机产生交叉顺序
for i=1:2:px-1%种群循环交叉
if(rand 2)%进行基因互换
newpop(x(i),:)=[pop(x(i),1:(cpoint-1)),pop(x(i+1),cpoint:py)];
newpop(x(i+1),:)=[pop(x(i+1),1:(cpoint-1)),pop(x(i),cpoint:py)];
else
newpop(x(i),:)=pop(x(i),:);
newpop(x(i+1),:)=pop(x(i+1),:);
end
else%不满足交叉概率，直接复制到下一代
newpop(x(i),:)=pop(x(i),:);
newpop(x(i+1),:)=pop(x(i+1),:);
end
end
******************
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的每行之和
*******************************************************************************
function pop2=decodechrom(pop,spoint,length)%将个体中的不同参数分离，并转换为十进制
pop1=pop(:,spoint:spoint+length-1);
pop2=decodebinary(pop1);
*******************************************************************************
function pop=initpop(popsize,chromlength)%随机产生种群
pop=round(rand(popsize,chromlength));
***
function [newpop]=mutation(pop,pm)%变异过程
[px,py]=size(pop);%计算种群矩阵维数
newpop=ones(size(pop));
for i=1:px%循环对每个个体变异
if(randnt=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
pop(i,:)=newpop(i,:);
end
else
newpop(i,:)=pop(i,:);
end
end
**************************************************************
function [newpop]=selection(pop,fitvalue)%选择复制过程
totalfit=sum(fitvalue); %求适应值之和
b=best(pop,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))