遗传算法及蚂蚁算法作业.doc
word题目1：z=2-exp-(x2+y2), x,y-5,+5Î，求函数最小值1用遗传算法来做：第一步：确定决策变量与其约束条件s.t. -5<=x<=5第二步：建立优化模型第三步：确定编码方法，用长度为50位的二进制编码串来表示决策变量x第四步：确定解码方法第五步：确定个体评价方法个体的适应度取为每次迭代的最小值的绝对值加上目标函数值，即第六步：确定参数此题种群规模n=30,迭代次数ger=200,交叉概率pc=0.65,变异概率代码：clear all;close all;clc;tic;n=30;ger=200;pc=0.65;pm=0.05;% 生成初始种群v=init_population(n,50); N,L=size(v);disp(sprintf('Number of generations:%d',ger);disp(sprintf('Population size:%d',N);disp(sprintf('Crossover probability:%.3f',pc);disp(sprintf('Mutation probability:%.3f',pm);% 待优化问题xmin=-5;xmax=5;ymin=-5;ymax=5;f='-(2-exp(-(x.2+y.2)'x,y=meshgrid(xmin:0.1:xmax,ymin:0.1:ymax);vxp=x;vyp=y;vzp=eval(f);figure(1);mesh(vxp,vyp,-vzp);hold on;grid on;% 计算适应度，并画出初始种群图形x=decode(v(:,1:25),xmin,xmax);y=decode(v(:,26:50),ymin,ymax);fit=eval(f);plot3(x,y,-fit,'k*');title('(a)染色体的初始位置');xlabel('x');ylabel('y');zlabel('f(x,y)');% 迭代前的初始化vmfit=;vx=;it=1; % 迭代计数器% 开始进化while it<=ger % Reproduction(Bi-classist Selection) vtemp=roulette(v,fit); % Crossover v=crossover(vtemp,pc); % Mutation M=rand(N,L)<=pm; %M(1,:)=zeros(1,L); v=v-2.*(v.*M)+M; % Results x=decode(v(:,1:25),xmin,xmax); y=decode(v(:,26:50),ymin,ymax); fit=eval(f); sol,indb=max(fit); % 每次迭代中最优目标函数值 v(1,:)=v(indb,:); fit_mean=mean(fit); % 每次迭代中目标函数值的平均值 vx=vx sol; vmfit=vmfit fit_mean; it=it+1;end% 最后结果disp(sprintf('n'); %空一行% 显示最优解与最优值disp(sprintf('Maximum foundx,f(x):%.4f,%.4f,%.4f',x(indb),y(indb),-sol);% 图形显示最优结果figure(2);mesh(vxp,vyp,-vzp);hold on;grid on;plot3(x,y,-fit,'r*');title('染色体的最终位置');xlabel('x');ylabel('y');zlabel('f(x,y)');% 图形显示最优与平均函数值变化趋势figure(3);plot(-vx);%title('最优,平均函数值变化趋势');xlabel('Generations');ylabel('f(x)');hold on;plot(-vmfit,'r');hold off;runtime=toc运行结果：Maximum foundx,f(x):0.0033,0.0017,1.00002用蚁群算法来做代码:% Ant main programclear all;close all;clc;tic;Ant=100;Ger=50;xmin=-5;xmax=5;ymin=-5;ymax=5;tcl=0.05;f='-(2-exp(-(x.2+y.2)' % 待优化的目标函数x,y=meshgrid(xmin:tcl:xmax,ymin:tcl:ymax);vxp=x;vyp=y;vzp=eval(f);figure(1);mesh(vxp,vyp,-vzp);hold on;% 初始化蚂蚁位置for i=1:Ant X(i,1)=(xmin+(xmax-xmin)*rand(1); X(i,2)=(ymin+(ymax-ymin)*rand(1); % T0-信息素,函数值越大,信息素浓度越大T0(i)=exp(-(X(i,1).2+X(i,2).2)-2;endplot3(X(:,1),X(:,2),-T0,'k*');hold on;grid on;title('蚂蚁的初始分布位置');xlabel('x');ylabel('y');zlabel('f(x,y)');% 开始寻优for i_ger=1:Ger P0=0.2; % P0-全局转移选择因子 P=0.8; % P -信息素蒸发系数 lamda=1/i_ger; % 转移步长参数 T_Best(i_ger),BestIndex=max(T0); for j_g=1:Ant % 求取全局转移概率 r=T0(BestIndex)-T0(j_g); Prob(i_ger,j_g)=r/T0(BestIndex); end for j_g_tr=1:Ant if Prob(i_ger,j_g_tr)<P0 temp1=X(j_g_tr,1)+(2*rand(1)-1)*lamda; temp2=X(j_g_tr,2)+(2*rand(1)-1)*lamda; else temp1=X(j_g_tr,1)+(xmax-xmin)*(rand(1)-0.5); temp2=X(j_g_tr,2)+(ymax-ymin)*(rand(1)-0.5); end if temp1<xmin temp1=xmin; end if temp1>xmax temp1=xmax; end if temp2<ymin temp2=ymin; end if temp2>ymax temp2=ymax; end if -(2-exp(-(temp1.2+temp2.2)>-(2-exp(-(X(j_g_tr,1).2+X(j_g_tr,2).2) X(j_g_tr,1)=temp1; X(j_g_tr,2)=temp2; end end %信息素更新 for t_t=1:AntT0(t_t)=(1-P)*T0(t_t)-(2-exp(-(X(t_t,1).2+X(t_t,2).2); end c_iter,i_iter=max(T0); maxpoint_iter=X(i_iter,1),X(i_iter,2); max_local(i_ger)=-(2-exp(-(X(i_iter,1).2+X(i_iter,2).2); %将每代全局最优解存到max_global矩阵中 if i_ger>=2 if max_local(i_ger)>max_global(i_ger-1) max_global(i_ger)=max_local(i_ger); else max_global(i_ger)=max_global(i_ger-1); end else max_global(i_ger)=max_local(i_ger); endend% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %figure(2);mesh(vxp,vyp,-vzp);hold on;x=X(:,1);y=X(:,2);plot3(x,y,-eval(f),'b*');hold on;grid on;title('蚂蚁的最终分布位置');xlabel('x');ylabel('y');zlabel('f(x,y)');figure(3);plot(1:Ger,-max_global,'b-')hold on;title('最优函数值变化趋势');xlabel('iteration');ylabel('f(x)');grid on;c_max,i_max=max(T0);maxpoint=X(i_max,1),X(i_max,2)maxvalue=-(2-exp(-(X(i_max,1).2+X(i_max,2).2)runtime=toc结果：题目2：利用蚁群算法求下面加权有向图中从A到G的最短路：解：第一步：初始化N只蚂蚁，也就是N条道路第二步：初始化运行参数，开始迭代第三步：在迭代步数X围之内，计算转移概率，如果小于全局转移概率就进展小X围的搜索，否如此就进展大X围的搜索第四步：更新信息素，记录状态，准备进展下一次迭代第五步：转第三步第六步：输出结果代码：function shortroad_ant_main% Ant main programclear all;close all;clc;%清屏tic;%计时开始Ant=50;Ger=100;%运行参数初始化power=0 5 3 100 100 100 100 100 100 100 100 100 100 100 100 100; 100 0 100 1 3 6 100 100 100 100 100 100 100 100 100 100; 100 100 0 100 8 7 6 100 100 100 100 100 100 100 100 100; 100 100 100 0 100 100 100 6 8 100 100 100 100 100 100 100; 100 100 100 100 0 100 100 3 5 100 100 100 100 100 100 100; 100 100 100 100 100 0 100 100 3 3 100 100 100 100 100 100; 100 100 100 100 100 100 0 100 8 4 100 100 100 100 100 100; 100 100 100 100 100 100 100 0 100 100 2 2 100 100 100 100; 100 100 100 100 100 100 100 100 0 100 100 1 2 100 100 100; 100 100 100 100 100 100 100 100 100 0 100 3 3 100 100 100; 100 100 100 100 100 100 100 100 100 100 0 100 100 3 5 100; 100 100 100 100 100 100 100 100 100 100 100 0 100 5 2 100; 100 100 100 100 100 100 100 100 100 100 100 100 0 6 6 100; 100 100 100 100 100 100 100 100 100 100 100 100 100 0 100 4; 100 100 100 100 100 100 100 100 100 100 100 100 100 100 0 3; 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 0;PM PN=size(power);% 初始化蚂蚁位置v=init_population(Ant,PN);v(:,1)=1;v(:,PN)=1;%始点和终点纳入路径%把距离当信息素浓度fit=short_road_fun(v,power);%距离越小越好，所以要和信息素浓度相对应。T0 = max(fit)-fit;% 画出图形figure(1);grid on;hold on;plot(fit,'k*');title('(a)蚂蚁的初始位置');xlabel('x');ylabel('f(x)');% 初始化vmfit=;vx=;P0=0.2; % P0-全局转移选择因子P=0.8; % P -信息素蒸发系数%C=;% 开始寻优for i_ger=1:Ger lamda=1/i_ger; % 转移步长参数 T_Best(i_ger),BestIndex=max(T0);%最大信息素浓度 for j_g=1:Ant % 求取全局转移概率 r=T0(BestIndex)-T0(j_g);%与最优的蚂蚁的距离 Prob(i_ger,j_g)=r/T0(BestIndex);%应该以多大的速率向它靠拢 end for j_g_tr=1:Ant if Prob(i_ger,j_g_tr)<P0 %局部转移-小动作转移 M=rand(1,PN)<lamda; temp=v(j_g_tr,:)-2.*(v(j_g_tr,:).*M)+M; else %全局转移-大步伐转移 M=rand(1,PN)<P0; temp=v(j_g_tr,:)-2.*(v(j_g_tr,:).*M)+M; end %始点和终点重新参加。即不能在移动过程中发生改变。 temp(:,1)=1;temp(:,end)=1; if short_road_fun(temp,power)<short_road_fun(v(j_g_tr,:),power) %记录 v(j_g_tr,:)=temp; end end %信息素更新，准备下一次迭代 fit=short_road_fun(v,power); T0 = (1-P)*T0+(max(fit)-fit);%信息素蒸发 sol,indb=min(fit); v(1,:)=v(indb,:);%记录本次迭代的状态 media=mean(fit); vx=vx sol; vmfit=vmfit media;end% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 最后结果disp(sprintf('n'); %空一行% 显示最优解与最优值disp(sprintf('Shortroad is %s',num2str(find(v(indb,:);%num2str数据转换成字符。disp(sprintf('Mininum is %d',sol);v(indb,:)% 图形显示最优结果figure(2);grid on;hold on;plot(fit,'r*');title('蚂蚁的最终位置');xlabel('x');ylabel('f(x)');% 图形显示最优与平均函数值变化趋势figure(3);plot(vx);title('最优,平均函数值变化趋势');xlabel('Generations');ylabel('f(x)');hold on;plot(vmfit,'r');hold off;runtime=toc%时间完毕end%function fit=short_road_fun(v,power)vm vn=size(v);fit=zeros(vm,1);%记录每一条路径的距离for i=1:vm I=find(v(i,:)=1);%寻找在路径上的点 Im,In=size(I); for j=1:In-1 fit(i)=fit(i)+power(I(j),I(j+1);%求路径的距离 endendend%Function init_populationfunction v=init_population(n1,s1)v=round(rand(n1,s1);%初始化所有的蚂蚁end运行结果：Shortroad is 1 2 5 8 12 15 16Mininum is 1827 / 27
