遗传算法及蚂蚁算法作业.docx
《遗传算法及蚂蚁算法作业.docx》由会员分享，可在线阅读，更多相关《遗传算法及蚂蚁算法作业.docx（14页珍藏版）》请在冰点文库上搜索。
遗传算法及蚂蚁算法作业
（1）用遗传算法来做：
第一步：
确定决策变量及其约束条件
s.t.-5<=x<=5
第二步：
建立优化模型
第三步：
确定编码方法，用长度为50位的二进制编码串来表示决策变量x
第四步：
确定解码方法
第五步：
确定个体评价方法
个体的适应度取为每次迭代的最小值的绝对值加上目标函数值，即
第六步：
确定参数
本题种群规模n=30,迭代次数ger=200,交叉概率pc=0.65,变异概率pm=0.05
代码：
clearall;
closeall;
clc;
tic;
n=30;
ger=200;
pc=0.65;
pm=0.05;
%生成初始种群
v=init_population（n,50）;
[N,L]=size（v）;
disp（sprintf（'Numberofgenerations:
%d',ger））;
disp（sprintf（'Populationsize:
%d',N））;
disp（sprintf（'Crossoverprobability:
%.3f',pc））;
disp（sprintf（'Mutationprobability:
%.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）;
holdon;
gridon;
%计算适应度，并画出初始种群图形
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;%迭代计数器
%开始进化
whileit<=ger
%Reproduction（Bi-classistSelection）
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=[vxsol];
vmfit=[vmfitfit_mean];
it=it+1;
end
%%%%最后结果
disp（sprintf（'\n'））;%空一行
%显示最优解及最优值
disp（sprintf（'Maximumfound[x,f（x）]:
[%.4f,%.4f,%.4f]',x（indb）,y（indb）,-sol））;
%图形显示最优结果
figure
（2）;
mesh（vxp,vyp,-vzp）;
holdon;
gridon;
plot3（x,y,-fit,'r*'）;
title（'染色体的最终位置'）;
xlabel（'x'）;
ylabel（'y'）;
zlabel（'f（x,y）'）;
%图形显示最优及平均函数值变化趋势
figure（3）;
plot（-vx）;
%title（'最优,平均函数值变化趋势'）;
xlabel（'Generations'）;
ylabel（'f（x）'）;
holdon;
plot（-vmfit,'r'）;
holdoff;
runtime=toc
运行结果：
Maximumfound[x,f（x）]:
[0.0033,0.0017,1.0000]
（2）用蚁群算法来做
代码:
%Antmainprogram
clearall;
closeall;
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）;
holdon;
%初始化蚂蚁位置
fori=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;
end
plot3（X（:
1）,X（:
2）,-T0,'k*'）;
holdon;
gridon;
title（'蚂蚁的初始分布位置'）;
xlabel（'x'）;
ylabel（'y'）;
zlabel（'f（x,y）'）;
%开始寻优
fori_ger=1:
Ger
P0=0.2;%P0----全局转移选择因子
P=0.8;%P----信息素蒸发系数
lamda=1/i_ger;%转移步长参数
[T_Best（i_ger）,BestIndex]=max（T0）;
forj_g=1:
Ant%求取全局转移概率
r=T0（BestIndex）-T0（j_g）;
Prob（i_ger,j_g）=r/T0（BestIndex）;
end
forj_g_tr=1:
Ant
ifProb（i_ger,j_g_tr）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
iftemp1temp1=xmin;
end
iftemp1>xmax
temp1=xmax;
end
iftemp2temp2=ymin;
end
iftemp2>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
%信息素更新
fort_t=1:
Ant
T0（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矩阵中
ifi_ger>=2
ifmax_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）;
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
figure
（2）;
mesh（vxp,vyp,-vzp）;
holdon;
x=X（:
1）;
y=X（:
2）;
plot3（x,y,-eval（f）,'b*'）;
holdon;
gridon;
title（'蚂蚁的最终分布位置'）;
xlabel（'x'）;
ylabel（'y'）;
zlabel（'f（x,y）'）;
figure（3）;
plot（1:
Ger,-max_global,'b-'）
holdon;
title（'最优函数值变化趋势'）;
xlabel（'iteration'）;
ylabel（'f（x）'）;
gridon;
[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
结果：
maxvalue=1.0000
题目2：
利用蚁群算法求下面加权有向图中从A到G的最短路：
解：
第一步：
初始化N只蚂蚁，也就是N条道路
第二步：
初始化运行参数，开始迭代
第三步：
在迭代步数范围之内，计算转移概率，如果小于全局转移概率就进行小范围的搜索，否则就进行大范围的搜索
第四步：
更新信息素，记录状态，准备进行下一次迭代
第五步：
转第三步
第六步：
输出结果
代码：
functionshortroad_ant_main
%Antmainprogram
clearall;closeall;clc;%清屏
tic;%计时开始
Ant=50;Ger=100;%运行参数初始化
power=[053100100100100100100100100100100100100100;
1000100136100100100100100100100100100100;
1001000100876100100100100100100100100100;
100100100010010010068100100100100100100100;
100100100100010010035100100100100100100100;
100100100100100010010033100100100100100100;
100100100100100100010084100100100100100100;
100100100100100100100010010022100100100100;
100100100100100100100100010010012100100100;
100100100100100100100100100010033100100100;
100100100100100100100100100100010010035100;
100100100100100100100100100100100010052100;
100100100100100100100100100100100100066100;
10010010010010010010010010010010010010001004;
10010010010010010010010010010010010010010003;
1001001001001001001001001001001001001001001000];
[PMPN]=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）;gridon;holdon;
plot（fit,'k*'）;
title（'（a）蚂蚁的初始位置'）;
xlabel（'x'）;ylabel（'f（x）'）;
%初始化
vmfit=[];vx=[];
P0=0.2;%P0----全局转移选择因子
P=0.8;%P----信息素蒸发系数
%C=[];
%开始寻优
fori_ger=1:
Ger
lamda=1/i_ger;%转移步长参数
[T_Best（i_ger）,BestIndex]=max（T0）;%最大信息素浓度
forj_g=1:
Ant%求取全局转移概率
r=T0（BestIndex）-T0（j_g）;%与最佳的蚂蚁的距离
Prob（i_ger,j_g）=r/T0（BestIndex）;%应该以多大的速率向它靠拢
end
forj_g_tr=1:
Ant
ifProb（i_ger,j_g_tr）%局部转移----小动作转移
M=rand（1,PN）temp=v（j_g_tr,:
）-2.*（v（j_g_tr,:
）.*M）+M;
else
%全局转移----大步伐转移
M=rand（1,PN）temp=v（j_g_tr,:
）-2.*（v（j_g_tr,:
）.*M）+M;
end
%始点和终点重新加入。
即不能在移动过程中发生改变。
temp（:
1）=1;temp（:
end）=1;
ifshort_road_fun（temp,power））,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=[vxsol];
vmfit=[vmfitmedia];
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%最后结果
disp（sprintf（'\n'））;%空一行
%显示最优解及最优值
disp（sprintf（'Shortroadis%s',num2str（find（v（indb,:
）））））;%num2str数据转换成字符。
disp（sprintf（'Mininumis%d',sol））;
v（indb,:
）
%图形显示最优结果
figure
（2）;gridon;holdon;
plot（fit,'r*'）;
title（'蚂蚁的最终位置'）;
xlabel（'x'）;
ylabel（'f（x）'）;
%图形显示最优及平均函数值变化趋势
figure（3）;
plot（vx）;
title（'最优,平均函数值变化趋势'）;
xlabel（'Generations'）;ylabel（'f（x）'）;
holdon;plot（vmfit,'r'）;holdoff;
runtime=toc%时间结束
end
%%
functionfit=short_road_fun（v,power）
[vmvn]=size（v）;
fit=zeros（vm,1）;%记录每一条路径的距离
fori=1:
vm
I=find（v（i,:
）==1）;%寻找在路径上的点
[Im,In]=size（I）;
forj=1:
In-1
fit（i）=fit（i）+power（I（j）,I（j+1））;%求路径的距离
end
end
end
%%
%Functioninit_population
functionv=init_population（n1,s1）
v=round（rand（n1,s1））;%初始化所有的蚂蚁
end
运行结果：
Shortroadis1258121516
Mininumis18
升级会员 