遗传算法实例简介

1、为了更好地应用遗传算法(GA , 现将举个简单的例子,一起来熟悉下 GA 的操作,大家可以在 matlab 下运行下列程序来验证,谢谢!如求下列函数的最大值f(x=10*sin(5x+7*cos(4x x 0,10一、初始化 (编码 initpop.m 函数的功能是实现群体的初始化, popsize 表示群体的大小, chromlength 表示染色体的长度 (二值数的长度 ,长度大小取决于变量的二进制编码的长度 (在本例中取 10位 。遗传算法子程序%Name: initpop.m%初始化function pop=initpop(popsize,chromlengthpop=round(ra

2、nd(popsize,chromlength;% rand随机产生每个单元为 0,1 行数为 popsize ,列数为 chromlength 的矩阵,% roud对矩阵的每个单元进行圆整。这样产生的初始种群。二、计算目标函数值1、将二进制数转化为十进制数 (1遗传算法子程序%Name: decodebinary.m%产生 2n 2(n-1 . 1 的行向量,然后求和,将二进制转化为十进制function pop2=decodebinary(poppx,py=size(pop; %求 pop 行和例数for i=1:pypop1(:,i=2.(py-1.*pop(:,i;py=py-1;end

3、pop2=sum(pop1,2; %求 pop1的每行之和2、将二进制编码转化为十进制数 (2decodechrom.m 函数的功能是将染色体 (或二进制编码 转换为十进制,参数 spoint 表示待解码的二进 制串的起始位置。 (对于多个变量而言,如有两个变量,采用 20为表示,每个变量 10为,则第一个变量 从 1开始,另一个变量从 11开始。本例为 1 ,参数 1ength 表示所截取的长度(本例为 10 。遗传算法子程序%Name: decodechrom.m%将二进制编码转换成十进制function pop2=decodechrom(pop,spoint,lengthpop1=pop

4、(:,spoint:spoint+length-1;pop2=decodebinary(pop1;3、计算目标函数值calobjvalue.m 函数的功能是实现目标函数的计算,其公式采用本文示例仿真,可根据不同优化问题予以 修改。遗传算法子程序%Name: calobjvalue.m%实现目标函数的计算function objvalue=calobjvalue(poptemp1=decodechrom(pop,1,10; %将 pop 每行转化成十进制数x=temp1*10/1023; %将二值域 中的数转化为变量域 的数objvalue=10*sin(5*x+7*cos(4*x;%计算目标函

5、数值三、计算个体的适应值%遗传算法子程序%Name:calfitvalue.m%计算个体的适应值function fitvalue=calfitvalue(objvalueglobal Cmin;Cmin=0;px,py=size(objvalue;for i=1:pxif objvalue(i+Cmin>0temp=Cmin+objvalue(i;elsetemp=0.0;endfitvalue(i=temp;endfitvalue=fitvalue'四、选择复制选择或复制操作是决定哪些个体可以进入下一代。程序中采用赌轮盘选择法选择,这种方法较易实现。 根据方程 pi=fi/f

6、i=fi/fsum ,选择步骤:1 在第 t 代,由(1式计算 fsum 和 pi2 产生 0,1 的随机数 rand( .,求 s=rand( .*fsum3 求 fis 中最小的 k ,则第 k 个个体被选中4 进行 N 次 2 、 3操作,得到 N 个个体,成为第 t=t+1 代种群%遗传算法子程序%Name: selection.m%选择复制function newpop=selection(pop,fitvaluetotalfit=sum(fitvalue; %求适应值之和fitvalue=fitvalue/totalfit; %单个个体被选择的概率fitvalue=cumsum(f

7、itvalue; %如 fitvalue=1 2 3 4,则 cumsum(fitvalue=1 3 6 10px,py=size(pop;ms=sort(rand(px,1; %从小到大排列fitin=1;newin=1;while newin<=pxif(ms(newin<fitvalue(fitinnewpop(newin,:=pop(fitin,:;newin=newin+1;elsefitin=fitin+1;endend五、交叉交叉 (crossover,群体中的每个个体之间都以一定的概率 pc 交叉,即两个个体从各自字符串的某一位 置(一般是随机确定开始互相交换,这类

8、似生物进化过程中的基因分裂与重组。例如,假设 2个父代个 体 x1, x2为:x1=0100110x2=1010001从每个个体的第 3位开始交叉,交又后得到 2个新的子代个体 y1, y2分别为:y1=0100001y2=1010110这样 2个子代个体就分别具有了 2个父代个体的某些特征。 利用交又我们有可能由父代个体在子代组合成 具有更高适合度的个体。事实上交又是遗传算法区别于其它传统优化方法的主要特点之一。%遗传算法子程序%Name: crossover.m%交叉function newpop=crossover(pop,pcpx,py=size(pop;newpop=ones(siz

9、e(pop;for i=1:2:px-1if(rand<pccpoint=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;elsenewpop(i,:=pop(i,:;newpop(i+1,:=pop(i+1,:;endend六、变异变异 (mutation, 基因的突变普遍存在于生物的进化过程中。 变异是指父代中的每个个体的每一位都以概 率 pm 翻转,即由 “1” 变为 “0” ,或由 “0” 变为 “1” 。遗传算法

10、的变异特性可以使求解过程随机地搜索到解 可能存在的整个空间,因此可以在一定程度上求得全局最优解。%遗传算法子程序%Name: mutation.m%变异function newpop=mutation(pop,pmpx,py=size(pop;newpop=ones(size(pop;for i=1:pxif(rand<pmmpoint=round(rand*py;if mpoint<=0mpoint=1;endnewpop(i,:=pop(i,:;if any(newpop(i,mpoint=0newpop(i,mpoint=1;elsenewpop(i,mpoint=0;end

11、elsenewpop(i,:=pop(i,:;endend七、求出群体中最大得适应值及其个体%遗传算法子程序%Name: best.m%求出群体中适应值最大的值function bestindividual,bestfit=best(pop,fitvaluepx,py=size(pop;bestindividual=pop(1,:;bestfit=fitvalue(1;for i=2:pxif fitvalue(i>bestfitbestindividual=pop(i,:;bestfit=fitvalue(i;endend八、主程序%遗传算法主程序%Name:genmain05.mcl

12、earclfpopsize=20; %群体大小chromlength=10; %字符串长度(个体长度 pc=0.6; %交叉概率pm=0.001; %变异概率pop=initpop(popsize,chromlength; %随机产生初始群体for i=1:20 %20为迭代次数objvalue=calobjvalue(pop; %计算目标函数fitvalue=calfitvalue(objvalue; %计算群体中每个个体的适应度newpop=selection(pop,fitvalue; %复制newpop=crossover(pop,pc; %交叉newpop=mutation(pop,

13、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;endfplot('10*sin(5*x+7*cos(4*x',0 10hold onplot(x,y,'r*'hold off222222222222222222222222222222222222222222222222222222222

14、2222Matlab 遗传算法的移动机器人路径规划程序, 高手过 来帮忙%起点(0, 0,终点(9, 9障碍点 op 为(6, 4,(5, 7安全范围半径为 r=0.5产生两个基因 m,n ,分别代表两个点,个位数为横坐标,十位数为纵坐标 % %目标函数 %functionsol,val=gaFeval(sol,optionsm=sol(:,1;n=sol(:,2;x1=rem(m,10;y1=fix(m,10;x2=rem(n,10;y2=fix(n,10;g1=(m-64(m-57(n-64(n-57; %罚函数 使产生的点不在障碍物内 % if g1=0val=1/(sqrt(x12+y

15、12+sqrt(x1-x22+(y1-y22+sqrt(x2-92+(y2-9 2;%适应度函数为路径长度的倒数 %elseval=1/(sqrt(x12+y12+sqrt(x1-x22+(y1-y22+sqrt(x2-92+(y2-9 2-20;%主函数 %bounds=ones(2,1*1,98function pop=initializega(20,bounds,'gaFeval','roulette' plot(trace(:,1,trace(:,3,'r-'hold onplot(trace(:,1,trace(:,2,'b*&

16、#39;xlabel('Generation'ylabel('Fittness'legend('解的变化 ',' 种群平均值的变化 ' 333333333333333333333333333333333333333333333333333333基于遗传算法的机器人路径规划 MA TLAB 源码算法的思路如下:取各障碍物顶点连线的中点为路径点, 相互连接各路径点, 将机器人移动 的起点和终点限制在各路径点上, 利用 Dijkstra 算法来求网络图的最短路径, 找到从起点 P1到终点 Pn 的最短路径,由于上述算法使用了连接线中点的

17、条件,不是整个规划空间的最优 路径, 然后利用遗传算法对找到的最短路径各个路径点 Pi (i=1,2, n 调整, 让各路径点在相 应障碍物端点连线上滑动,利用 Pi= Pi1+ti×(Pi2-Pi1(ti 0,1 i=1,2, n 即可确定相应的 Pi ,即为新的路径点,连接此路径点为最优路径。function L1,XY1,L2,XY2=JQRLJGH(XX,YY% 基于 Dijkstra 和遗传算法的机器人路径规划演示程序% GreenSim团队原创作品,转载请注明% GreenSim团队长期从事算法设计、代写程序等业务%输入参数在函数体内部定义%输出参数为% L1 由 Dij

18、kstra 算法得出的最短路径长度% XY1 由 Dijkstra 算法得出的最短路径经过节点的坐标% L2 由遗传算法得出的最短路径长度% XY2 由遗传算法得出的最短路径经过节点的坐标%程序输出的图片有% Fig1 环境地图(包括:边界、障碍物、障碍物顶点之间的连线、 Dijkstra 的网络图结构 % Fig2 由 Dijkstra 算法得到的最短路径% Fig3 由遗传算法得到的最短路径% Fig4 遗传算法的收敛曲线(迄今为止找到的最优解、种群平均适应值% 画 Fig1figure(1;PlotGraph;title('地形图及网络拓扑结构 'PD=inf*ones(

19、26,26;for j=1:26if D(i,j=1x1=XY(i,5;y1=XY(i,6;x2=XY(j,5;y2=XY(j,6;dist=(x1-x22+(y1-y220.5;PD(i,j=dist;endendend% 调用最短路算法求最短路s=1;%出发点t=26;%目标点L,R=ZuiDuanLu(PD,s,t;L1=L(end;XY1=XY(R,5:6;% 绘制由最短路算法得到的最短路径 figure(2;PlotGraph;hold onfor i=1:(length(R-1x1=XY1(i,1;y1=XY1(i,2;x2=XY1(i+1,1;y2=XY1(i+1,2;plot(

20、x1,x2,y1,y2,'k'hold onendtitle('由 Dijkstra 算法得到的初始路径 ' % 使用遗传算法进一步寻找最短路 %第一步:变量初始化M=50;%进化代数设置N=20;%种群规模设置Pm=0.3;%变异概率设置LC1=zeros(1,M;LC2=zeros(1,M;Yp=L1;%第二步:随机产生初始种群X1=XY(R,1;Y1=XY(R,2;X2=XY(R,3;Y2=XY(R,4;farmi=rand(1,aaa;end% 以下是进化迭代过程counter=0;%设置迭代计数器while counter % 第三步:交叉%交叉采用双

21、亲双子单点交叉newfarm=cell(1,2*N;%用于存储子代的细胞结构 Ser=randperm(N;%两两随机配对的配对表A=farmSer(1;%取出父代 AB=farmSer(2;%取出父代 BP0=unidrnd(aaa-1;%随机选择交叉点a=A(:,1:P0,B(:,(P0+1:end;%产生子代 ab=B(:,1:P0,A(:,(P0+1:end;%产生子代 bnewfarm2*N-1=a;%加入子代种群newfarm2*N=b;for i=1:(N-1A=farmSer(i;B=farmSer(i+1;newfarm2*i=b;endFARM=farm,newfarm;%

22、新旧种群合并% 第四步:选择复制SER=randperm(2*N;FITNESS=zeros(1,2*N;fitness=zeros(1,N;for i=1:(2*NPP=FARMi;FITNESS(i=MinFun(PP,X1,X2,Y1,Y2;%调用目标函数 endfor i=1:Nf1=FITNESS(SER(2*i-1;f2=FITNESS(SER(2*i;if f1<=f2elsefarmi=FARMSER(2*i;fitness(i=FITNESS(SER(2*i;endend%记录最佳个体和收敛曲线minfitness=min(fitness;meanfitness=mea

23、n(fitness;if minfitness pos=find(fitness=minfitness;Xp=farmpos(1;Yp=minfitness;endif counter=10PPP=0.5,Xp,0.5'PPPP=1-PPP;X=PPP.*X1+PPPP.*X2;Y=PPP.*Y1+PPPP.*Y2;XY2=X,Y;figure(3PlotGraph;hold onfor i=1:(length(R-1x1=XY2(i,1;y1=XY2(i,2;x2=XY2(i+1,1;y2=XY2(i+1,2;plot(x1,x2,y1,y2,'k'hold onen

24、dtitle('遗传算法第 10代 'hold onfor i=1:(length(R-1x1=XY1(i,1;y1=XY1(i,2;x2=XY1(i+1,1;y2=XY1(i+1,2;plot(x1,x2,y1,y2,'k','LineWidth',1; hold onendendif counter=20PPP=0.5,Xp,0.5'PPPP=1-PPP;X=PPP.*X1+PPPP.*X2;Y=PPP.*Y1+PPPP.*Y2;XY2=X,Y;figure(4PlotGraph;hold onfor i=1:(length(R-1x

25、1=XY2(i,1;y2=XY2(i+1,2;plot(x1,x2,y1,y2,'k'hold onendtitle('遗传算法第 20代 'hold onfor i=1:(length(R-1x1=XY1(i,1;y1=XY1(i,2;x2=XY1(i+1,1;y2=XY1(i+1,2;plot(x1,x2,y1,y2,'k','LineWidth',1; hold onendendif counter=30PPP=0.5,Xp,0.5'PPPP=1-PPP;X=PPP.*X1+PPPP.*X2;Y=PPP.*Y1+PP

26、PP.*Y2;XY2=X,Y;figure(5PlotGraph;hold onfor i=1:(length(R-1x1=XY2(i,1;y1=XY2(i,2;x2=XY2(i+1,1;y2=XY2(i+1,2;plot(x1,x2,y1,y2,'k'hold onendtitle('遗传算法第 30代 'hold onfor i=1:(length(R-1x1=XY1(i,1;y2=XY1(i+1,2;plot(x1,x2,y1,y2,'k','LineWidth',1; hold onendendif counter=40P

27、PP=0.5,Xp,0.5'PPPP=1-PPP;X=PPP.*X1+PPPP.*X2;Y=PPP.*Y1+PPPP.*Y2;XY2=X,Y;figure(6 PlotGraph; hold on for i=1:(length(R-1 x1=XY2(i,1; y1=XY2(i,2; x2=XY2(i+1,1; y2=XY2(i+1,2; plot(x1,x2,y1,y2,'k' hold on end title('遗传算法第 40 代' hold on for i=1:(length(R-1 x1=XY1(i,1; y1=XY1(i,2; x2=XY

28、1(i+1,1; y2=XY1(i+1,2; plot(x1,x2,y1,y2,'k','LineWidth',1; hold on end end if counter=50 PPP=0.5,Xp,0.5' PPPP=1-PPP; X=PPP.*X1+PPPP.*X2; Y=PPP.*Y1+PPPP.*Y2; XY2=X,Y; figure(7 PlotGraph; hold on for i=1:(length(R-1 x1=XY2(i,1; y1=XY2(i,2; x2=XY2(i+1,1; y2=XY2(i+1,2; plot(x1,x2,y1,y2,'k' hold on end title('遗传算法第 50 代' hold on for i=1:(length(R-1 x1=XY1(i,1; y1=XY1(i,2; x2=XY1(i+1,1; y2=XY1(i+1,2; plot(x1,x2,y1,y2,'k','LineWidth',1; hold on end end LC2(counter+1=Yp; LC1(counter+1=meanfitness; % 第五步：变异 for i=1