一、要求
1.利用matlab实现遗传算法和蚁群算法，解决相关问题
2.体会两种算法的具体作用
二、原理
（1）遗传算法：
不断循环，直到寻找出一个解
1. 检查每个染色体，看它解决问题的性能怎样，并相应地为它分配一个适应性分 数。
2. 从当前群体选出两个成员。选出的概率与染色体的适应性成正比，适应分数越 高，被选中的概率越大。常用的方法就是轮赌选择法(roulette wheel selection)。
3. 按照预先设定的杂交率(crossover rate),从每个选中染色体的一个随机确定的点 上进行杂交。
4. 按照预定的变异率(mutation rate),通过对被选染色体的位的循环，把相应的位进 行翻转。
5. 重复步骤 2，3，4，直到新的群体被创建出来。 结束循环
结束循环。
在matlab中可以通过工具箱optimtool利用GUI实现遗传算法，
（2）蚁群算法：
原理：
1、蚂蚁在路径上释放信息素。
2、碰到还没走过的路口，就随机挑选一条路走。同时，释放与路径长度有关的信息素。
3、信息素浓度与路径长度成反比。后来的蚂蚁再次碰到该路口时，就选择信息素浓度较高路径。
4、最优路径上的信息素浓度越来越大。
5、最终蚁群找到最优寻食路径。
步骤：
1.选择从初始点下一步可以到达的节点，根据每个节点的信息素求出前往每个节点的概率，并利用轮盘算法选取下一步的初始点。
pijk=[τij(t)]a*[ηij]βkϵ{N-tabμk}[τij(t)]a*[ηij]β0,
其中，τij(t)
为析取图中弧（i,j）上
的信息素的浓度；ηij为
与弧（i,j）相关联
的启发式信息；α、β分别
为τij(t)、ηij的权重
参数。
2.更新路径以及路程长度。
3.重复1、2过程，直到蚂蚁到达终点或者无路可走。
4.重复1、2、3，直到某一代m只蚂蚁迭代结束。
5.更新信息素矩阵，其中没有到达的蚂蚁不计算在内。
τijt+1=1-ρ*τijt+Δτij
Δτijt=QLk(t), 蚂蚁k经过i,j0, 蚂蚁k不经过i,j
（6）重复（1）~（5），直至第n代蚂蚁迭代结束。
三、过程及结果
3.1.遗传算法的GUI实现
利用GUI实现用遗传算法求解函数
fx,y=1-0.1*(sinx2+y2-0.1)/(x2+y2)
的适应值。
创建遗传算法适应度函数：
图1 适应度函数
打开遗传算法GUI界面设置参数并运行：
图2 遗传算法GUI
结果如下：
图3 遗传算法运行结果
可以看出，本轮迭代最佳适应值为0.988461而平均适应值为0.993128
3.2.蚁群算法在路径规划中的应用
实验需要我们给出机器人在避开障碍物的前提下通过地图的最优路径。
输入0和1组成的矩阵表示地图，0表示可通过，1表示障碍物，地图布局如下：
图4 地图布局
算法实现代码如下：
function main()
G=[0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
0 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
0 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0;
0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0;
0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0;
0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0;
0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0;
1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0;
1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 0;
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0;
0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0;];
MM=size(G,1);
Tau=ones(MM*MM,MM*MM);
Tau=8.*Tau;
K=200;
M=80;
S=1;
E=MM*MM;
Alpha=1;
Beta=8;
Rho=0.4;
Q=1;
mink1=inf;
mink=0;
min1=0;
D=G2D(G);
N=size(D,1);
a=1;
Ex=a*(mod(E,MM)-0.5);
if Ex==-0.5
Ex=MM-0.5;
end
Ey=a*(MM+0.5-ceil(E/MM));
Eta=zeros(N);
for i=1:N
ix=a*(mod(i,MM)-0.5);
if ix==-0.5
ix=MM-0.5;
end
iy=a*(MM+0.5-ceil(i/MM));
if i~=E
Eta(i)=1/((ix-Ex)^2+(iy-Ey)^2-0.5);
else
Eta(i)=100;
end
end
ROUTES=cell(K,M);
PL=zeros(K,M);
for k = 1:K
for m = 1:M
W=S;
Path=S;
PLkm=0;
TABUkm=ones(N);
TABUkm(S)=0;
DD=D;
DW=DD(W,:);
DW1=find(DW);
for j=1:length(DW1)
if TABUkm(DW1(j))==0
DW(DW(j))=0;
end
end
LJD=find(DW);
Len_LJD=length(LJD);
while W~=E&&Len_LJD>=1
PP=zeros(Len_LJD);
for i=1:Len_LJD
PP(i)=(Tau(W,LJD(i))^Alpha)*((Eta(LJD(i)))^Beta);
end
sumpp=sum(PP);
PP=PP/sumpp;
Pcum(1)=PP(1);
for i=2:Len_LJD
Pcum(i)=Pcum(i-1)+PP(i);
end
Select=find(Pcum>=rand);
to_visit=LJD(Select(1));
Path=[Path,to_visit];
PLkm=PLkm+DD(W,to_visit);
W=to_visit;
for kk=1:N
if TABUkm(kk)==0
DD(W,kk)=0;
DD(kk,W)=0;
end
end
TABUkm(W)=0;
DW=DD(W,:);
DW1=find(DW);
for j=1:length(DW1)
if TABUkm(DW1(j))==0
DW(j)=0;
end
end
LJD=find(DW);
Len_LJD=length(LJD);
end
ROUTES{k,m}=Path;
if Path(end)==E
PL(k,m)=PLkm;
if PLkm<mink1
mink=k;min1=m;mink1=PLkm;
end
else
PL(k,m)=0;
end
end
Delta_Tau=zeros(N,N);
for m=1:M
if PL(k,m)
ROUT=ROUTES{k,m};
TS=length(ROUT)-1;
PL_km=PL(k,m);
for s=1:TS
x=ROUT(s);
y=ROUT(s+1);
Delta_Tau(x,y)=Delta_Tau(x,y)+Q/PL_km;
Delta_Tau(y,x)=Delta_Tau(y,x)+Q/PL_km;
end
end
end
Tau=(1-Rho).*Tau+Delta_Tau;
end
plotif=1;
if plotif==1
minPL=zeros(K);
for i=1:K
PLK=PL(i,:);
Nonzero=find(PLK);
PLKPLK=PLK(Nonzero);
minPL(i)=min(PLKPLK);
end
figure(1)
plot(minPL)
hold on
grid on
title('�������߱仯����')
xlabel('��������')
ylabel('��ѷ������')
figure(2)
axis([0,MM,0,MM])
for i = 1:MM
for j= 1:MM
if G(i,j)==1
x1=j-1;y1=MM-i;
x2=j;y2=MM-i;
x3=j;y3=MM-i+1;
x4=j-1;y4=MM-i+1;
fill([x1,x2,x3,x4],[y1,y2,y3,y4],[0.2,0.2,0.2]);
hold on
else
x1=j-1;y1=MM-i;
x2=j;y2=MM-i;
x3=j;y3=MM-i+1;
x4=j-1;y4=MM-i+1;
fill([x1,x2,x3,x4],[y1,y2,y3,y4],[1,1,1]);
hold on
end
end
end
hold on
title('�������˶��켣');
xlabel('����x');
ylabel('����y');
ROUT=ROUTES{mink,min1};
LENROUT=length(ROUT);
Rx=ROUT;
Ry=ROUT;
for ii=1:LENROUT
Rx(ii)=a*(mod(ROUT(ii),MM)-0.5);
if Rx(ii)==-0.5
Rx(ii)=MM-0.5;
end
Ry(ii)=a*(MM+0.5-ceil(ROUT(ii)/MM));
end
plot(Rx,Ry)
end
plotif2=0;
if plotif2==1
figure(3)
axis([0,MM,0,MM])
for i=1:MM
for j=1:MM
if G(i,j)==1
x1=j-1;y1=MM-i;
x2=j;y2=MM-i;
x3=j;y3=MM-i+1;
x4=j-1;y4=MM-i+1;
fill([x1,x2,x3,x4],[y1,y2,y3,y4],[0.2,0.2,0.2]);
hold on
else
x1=j-1;y1=MM-i;
x2=j;y2=MM-i;
x3=j;y3=MM-i+1;
x4=j-1;y4=MM-i+1;
fill([x1,x2,x3,x4],[y1,y2,y3,y4],[1,1,1]);
hold on
end
end
end
for k=1:K
PLK=PL(k,:);
minPLK=min(PLK);
pos=find(PLK==minPLK);
m=pos(1);
ROUT=ROUTES{k,m};
LENROUT=length(ROUT);
Rx=ROUT;
Ry=ROUT;
for ii=1:LENROUT
Rx(ii)=a*(mod(ROUT(ii),MM)-0.5);
if Rx(ii)==-0.5
Rx(ii)=MM-0.5;
end
Ry(ii)=a*(MM+0.5-ceil(ROUT(ii)/MM));
end
plot(Rx,Ry)
hold on
end
end
function D=G2D(G)
l=size(G,1);
D=zeros(l*l,l*l);
for i=1:l
for j=1:l
if G(i,j)==0
for m=1:l
for n=1:l
if G(m,n)==0
im=abs(i-m);jn=abs(j-n);
if im+jn==1||(im==1&&jn==1)
D((i-1)*l+j,(m-1)*l+n)=(im+jn)^0.5;
end
end
end
end
end
end
end
运行上述代码后结果如下：
图5 收敛曲线变化趋势
从图中可以看出迭代次数在30到40次之间时，最小路径长度逐渐收敛于38左右
图6 机器人运动轨迹
分析轨迹可知，机器人避开了所有的障碍，成功通过地图
四、总结
对于遗传算法我们可以直接利用matlab自带的GUI实现遗传算法的编程，并且可以发现每一次运行所求解的适应值都可能会有所不同，这是由于遗传算法是近似优化算法，它的每个解不能保证全局最优。在蚁群算法求解最优路径的实验中，通过编程的方式，选取最短路径作为优化原则并利用轮盘算法迭代寻找最优路线，可以看到蚁群算法中信息素等相关参数的具体影响。路径规划也是自主机器人移动导航的一项关键技术。
![[Linux]文件系统](https://img-blog.csdnimg.cn/direct/1b5be787563442f2ac787f808f542cff.png#pic_center)
