一、遗传算法及栅格地图简介
1.1 引言
1.2 遗传算法理论
1.2.1 遗传算法的生物学基础
1.2.2 遗传算法的理论基础
1.2.3 遗传算法的基本概念
1.2.4 标准的遗传算法
1.2.5 遗传算法的特点
1.2.6 遗传算法的改进方向
1.3 遗传算法流程
1.4 关键参数说明
2 栅格地图
2.1 栅格法应用背景
路径规划时首先要获取环境信息， 建立环境地图， 合理的环境表示有利于建立规划方法和选择合适的搜索算法，最终实现较少的时间开销而规划出较为满意的路径。一般使用栅格法在静态环境下建立环境地图。
2.2 栅格法实质
将AGV的工作环境进行单元分割， 将其用大小相等的方块表示出来，这样栅格大小的选取是影响规划算法性能的一个很重要的因素。栅格较小的话，由栅格地图所表示的环境信息将会非常清晰，但由于需要存储较多的信息，会增大存储开销，同时干扰信号也会随之增加，规划速度会相应降低，实时性得不到保证；反之，由于信息存储量少，抗干扰能力有所增强，规划速随之增快，但环境信息划分会变得较为模糊，不利于有效路径的规划。在描述环境信息时障碍物所在区域在栅格地图中呈现为黑色，地图矩阵中标为1，可自由通行区域在栅格地图中呈现为白色，地图矩阵中标为0。路径规划的目的就是在建立好的环境地图中找到一条最优的可通行路径，所以使用栅格法建立环境地图时，栅格大小的合理设定非常关键。
2.3 10乘10的静态环境地图
10乘10的静态环境地图代码
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%建立环境地图%%%%%%%%%%%%%%%%%%%%%%%%%%%%function DrawMap(map)n = size(map);step = 1;a = 0 : step :n(1);b = 0 : step :n(2);figure(1)axis([0 n(2) 0 n(1)]); %设置地图横纵尺寸set(gca,'xtick',b,'ytick',a,'GridLineStyle','-',...'xGrid','on','yGrid','on');hold onr = 1;for(i=1:n(1)) %设置障碍物的左下角点的x,y坐标for(j=1:n(2))if(map(i,j)==1)p(r,1)=j-1;p(r,2)=i-1;fill([p(r,1) p(r,1) + step p(r,1) + step p(r,1)],...[p(r,2) p(r,2) p(r,2) + step p(r,2) + step ],'k');r=r+1;hold onendendend%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%栅格数字标识%%%%%%%%%%%%%%%%%%%%%%%%%%%%x_text = 1:1:n(1)*n(2); %产生所需数值.for i = 1:1:n(1)*n(2)[row,col] = ind2sub([n(2),n(1)],i);text(row-0.9,col-0.5,num2str(x_text(i)),'FontSize',8,'Color','0.7 0.7 0.7');endhold onaxis square
建立环境矩阵，1代表黑色栅格，0代表白色栅格，调用以上程序，即可得到上述环境地图。
map=[0 0 0 1 0 0 1 0 0 0;1 0 0 0 0 1 1 0 0 0;0 0 1 0 0 0 1 1 0 0;0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 1 0 0 1 0;1 0 0 0 0 1 1 0 0 0;0 0 0 1 0 0 0 0 0 0;1 1 1 0 0 0 1 0 0 0;0 0 0 0 0 1 1 0 0 0;0 0 0 0 0 1 1 0 0 0;];DrawMap(map); %得到环境地图
2.4 栅格地图中障碍栅格处路径约束
移动体栅格环境中多采用八方向的移动方式，此移动方式在完全可通行区域不存在运行安全问题，当
移动体周围存在障碍栅格时此移动方式可能会发生与障碍物栅格的碰撞问题，为解决此问题加入约束
条件，当在分别与障碍物栅格水平方向和垂直方向的可行栅格两栅格之间通行时，禁止移动体采用对
角式移动方式。
约束条件的加入，实质是改变栅格地图的邻接矩阵，将障碍栅格(数字为“1”的矩阵元素)的对角栅格
设为不可达， 即将对角栅格的距离值改为无穷大。其实现MATLAB代码如下：
代码：
%约束移动体在障碍栅格对角运动%通过优化邻接矩阵实现%%%%%%%%%%%%%%%%%% 约束移动体移动方式 %%%%%%%%%%%%%%%%%function W=OPW(map,W)% map 地图矩阵 % W 邻接矩阵n = size(map);num = n(1)*n(2);for(j=1:n(1))for(z=1:n(2))if(map(j,z)==1)if(j==1) %若障碍物在第一行if(z==1)%若障碍物为第一行的第一个W(j+1,j+n(2)*j)=Inf;W(j+n(2)*j,j+1)=Inf;elseif(z==n(2)) %若障碍物为第一行的最后一个W(n(2)-1,n(2)+n(1)*j)=Inf;W(n(2)+n(1)*j,n(2)-1)=Inf;else%若障碍物为第一行的其他W(z-1,z+j*n(2))=Inf;W(z+j*n(2),z-1)=Inf;W(z+1,z+j*n(2))=Inf;W(z+j*n(2),z+1)=Inf;endendendif(j==n(1))%若障碍物在最后一行if(z==1)%若障碍物为最后一行的第一个W(z+n(2)*(j-2),z+n(2)*(j-1)+1)=Inf;W(z+n(2)*(j-1)+1,z+n(2)*(j-2))=Inf;elseif(z==n(2)) %若障碍物为最后一行的最后一个W(n(1)*n(2)-1,(n(1)-1)*n(2))=Inf;W((n(1)-1)*n(2),n(1)*n(2)-1)=Inf;else %若障碍物为最后一行的其他W((j-2)*n(2)+z,(j-1)*n(2)+z-1)=Inf;W((j-1)*n(2)+z-1,(j-2)*n(2)+z)=Inf;W((j-2)*n(2)+z,(j-1)*n(2)+z+1)=Inf;W((j-1)*n(2)+z+1,(j-2)*n(2)+z)=Inf;endendendif(z==1) if(j~=1&&j~=n(1)) %若障碍物在第一列非边缘位置 W(z+(j-2)*n(2),z+1+(j-1)*n(2))=Inf;W(z+1+(j-1)*n(2),z+(j-2)*n(2))=Inf;W(z+1+(j-1)*n(2),z+j*n(2))=Inf;W(z+j*n(2),z+1+(j-1)*n(2))=Inf;endendif(z==n(2))if(j~=1&&j~=n(1)) %若障碍物在最后一列非边缘位置 W((j+1)*n(2),j*n(2)-1)=Inf;W(j*n(2)-1,(j+1)*n(2))=Inf;W(j*n(2)-1,(j-1)*n(2))=Inf;W((j-1)*n(2),j*n(2)-1)=Inf;endendif(j~=1&&j~=n(1)&&z~=1&&z~=n(2)) %若障碍物在非边缘位置W(z+(j-1)*n(2)-1,z+j*n(2))=Inf;W(z+j*n(2),z+(j-1)*n(2)-1)=Inf;W(z+j*n(2),z+(j-1)*n(2)+1)=Inf;W(z+(j-1)*n(2)+1,z+j*n(2))=Inf;W(z+(j-1)*n(2)-1,z+(j-2)*n(2))=Inf;W(z+(j-2)*n(2),z+(j-1)*n(2)-1)=Inf;W(z+(j-2)*n(2),z+(j-1)*n(2)+1)=Inf;W(z+(j-1)*n(2)+1,z+(j-2)*n(2))=Inf;endendendendend
2.5 栅格法案例
下面以Djkstra算法为例， 其实现如下：
map=[0 0 0 1 0 0 1 0 0 0;1 0 0 0 0 1 1 0 0 0;0 0 1 0 0 0 1 1 0 0;0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 1 0 0 1 0;1 0 0 0 0 1 1 0 0 0;0 0 0 1 0 0 0 0 0 0;1 1 1 0 0 0 1 0 0 0;0 0 0 0 0 1 1 0 0 0;0 0 0 0 0 1 1 0 0 0;];%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%建立环境矩阵map%%%%%%%%%%%%%%%%%%%%%%%%%%%%%DrawMap(map); %得到环境地图W=G2D(map); %得到环境地图的邻接矩阵W(W==0)=Inf; %邻接矩阵数值处理W=OPW(map,W); %优化邻接矩阵[distance,path]=dijkstra(W,1,100);%设置起始栅格，得到最短路径距离以及栅格路径[x,y]=Get_xy(distance,path,map); %得到栅格相应的x，y坐标Plot(distance,x,y); %画出路径
运行结果如下：
其中函数程序：
DrawMap(map) 详见建立栅格地图
W=G2D(map) ； 详见建立邻接矩阵
[distance， path] =dijkstra(W， 1， 100) 详见Djk stra算法
[x， y] =Get_xy(distance， path， map) ；
Plot(distance， x， y) ；
二、部分源代码
clc;clear all;clear all;close all;t=23; %过程点个数=t－1s=500;%种群规模pc=0.90; %交叉概率pm=0.20; %变异概率pop=zeros(s,t);for i=1:spop(i,1:t-1)=randperm(t-1);endfor k=1:1:2000 %进化代次数kif mod(k,10)==1kendpop=qiujuli(pop);c=15;%选择淘汰个数pop=select(pop,c);p=rand;if p>=pcpop=cross(pop);endif p>=pmpop=mutate(pop);endendpopmin(pop(:,t))J=pop(:,t);fi=1./J;[Oderfi,Indexfi]=sort(fi); %安排fi从小到大BestS=pop(Indexfi(s),:); %使BestS=E(m),m即是属于max(fi)的IndexfiI=BestS;x=[2 3 6 10 14 17 22 20 23 25 30 28 25 21 29 16 18 15 9 11 6 5 ];y=[5 26 14 29 27 24 28 22 26 30 30 17 13 15 4 13 3 1 6 2 2 7];for i=1:1:t-1x1(i)=x(I(i));y1(i)=y(I(i));endx(t)=x(I(1));y(t)=y(I(1));a = [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 11 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 0 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 11 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 11 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 01 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 01 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 01 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 01 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 11 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 11 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1];%31*31栅格b = a;b(end+1,end+1) = 0;colormap([0 0 0;1 1 1]),pcolor(b)axis image xy;%绘制栅格图hold on;figure(1);plot(x,y,'-or');
三、运行结果
四、matlab版本及参考文献
1 matlab版本
a
2 参考文献
《智能优化算法及其MATLAB实例（第2版）》包子阳 余继周 杨杉著 电子工业出版社
