采用栅格对机器人的工作空间进行划分，再利用优化算法对机器人路径优化，是采用智能算法求最优路径的一个经典问题。目前，采用蚁群算法在栅格地图上进行路径优化取得比较好的效果，而利用遗传算法在栅格地图上进行路径优化在算法显得更加难以实现。
利用遗传算法处理栅格地图的机器人路径规划的难点主要包括：1保证路径不间断，2保证路径不穿过障碍。
用遗传算法解决优化问题时的步骤是固定的，就是种群初始化，选择，交叉，变异，适应度计算这样，那么下面我就说一下遗传算法求栅格地图中机器人路径规划在每个步骤的问题、难点以及解决办法。
1、种群初始化
首先要知道遗传算法种群初始化的定义。遗传算法种群初始化是生成一定种群数量的个体，每个个体是一个可行解。这里要注意是可行解，对于该问题也就是说是一个可行路径，也就是说应该是一个从路径起点到路径终点的，且不经过障碍的路径。怎样进行初始化种群得到可行路径是遗传算法求栅格路径的第一个难点也是最大难点。
方法
路径初始化可以分为两步：第一步生成必经节点路径，什么是必经节点路径？举个例子，比如对于10*10的栅格，从左下角编号1到右上角编号100的路径必经过第2行的一个点，第3行一个点……第9行的一个点，这是很显然的，那么我们在第二行的自由栅格中随机取一个节点、第3行的自由栅格中取一个节点……第9行自由栅格取一个节点，那么这就行程了一个必经点路径，当然这个路径也是间断的。所以需要第二步，第二步就是连接这些间断节点，而这个问题是该算法中最难的问题，因为在连接路径中，太难绕开障碍了，而且如果你绕开了障碍物，会发现失去了方向连不回来了。因此，在连接节点中采用中点连接法，但是中点，要取得有技巧，可在中点处取4或3个栅格，然后在这些栅格中找到自由栅格，等概率选择，如果有最坏得情形，这些中点处栅格全都是障碍，则在这些栅格中等概率选择一个作为路径一点，因此该方法保证了路径的连续性，但也有可能存在经过障碍的路径，而这种障碍的路径可以在适应度函数中进行惩罚。
上述初始化路径的两步结束后，进行简化路径操作，即如果路径中有两个相同的节点，则去掉相同节点之间的一段，这个很容易理解。
至此初始化路径结束，你已经成功了一大步！
2、选择
选择和遗传算法的选择是一样的，无需特殊改动，就是根据适应度进行选择。
3、交叉
交叉采用重复点交叉，这个也比较好理解，比如一条路径为[1 12 13 242536 45 56 ]，另一条路径为[ 1 142535 46 56]，这两条路径有一个公共节点25，进行交叉变成[1 12 13 242535 46 56]和[1 142536 45 56].
4、变异
变异的方法使用随机生成选择两个节点，并去掉这两个节点之间的路径，之后采用上述的中带你插入方法生成连续路径。
5、适应度计算
适应度计算路径长度和穿过障碍的个数，求和即可，这个比较间断不多说，下面展示一下我写的程序的效果。
% 基于遗传算法的栅格法机器人路径规划clc;clear allclose all;% 输入数据,即栅格地图G= [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0; 0 1 1 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0; 0 0 0 0 0 0 1 1 1 0 0 1 1 1 0 1 0 0 0 0; 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 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 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 0 1 1 0 0 0 0 0 0; 0 1 1 1 0 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 0 0 0 0 0; 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0; 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0; 0 0 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0; 0 0 1 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0; 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0; 0 0 1 1 1 0 1 1 0 0 0 0 0 0 1 0 0 1 1 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0];p_start = 0; % 起始序号p_end =399; % 终止序号NP = 200;% 种群数量max_gen = 2000; % 最大进化代数pc = 0.5;% 交叉概率pm = 0.5;% 变异概率a = 1; % 路径长度比重b = 7; % 路径顺滑度比重%init_path = [];z = 1;new_pop1 = {}; % 元包类型路径[y, x] = size(G);% 起点所在列(从左到右编号1.2.3...)xs = mod(p_start, x) + 1;% 起点所在行(从上到下编号行1.2.3...)ys = fix(p_start / x) + 1;% 终点所在列、行xe = mod(p_end, x) + 1;ye = fix(p_end / x) + 1;% 种群初始化step1，必经节点,从起始点所在行开始往上，在每行中挑选一个自由栅格，构成必经节点pass_num = ye - ys + 1;pop = zeros(NP, pass_num);min_value=1000;for i = 1 : NP pop(i, 1) = p_start; j = 1; % 除去起点和终点 for yk = ys+1 : ye-1 j = j + 1; % 每一行的可行点 can = []; for xk = 1 : x % 栅格序号 no = (xk - 1) + (yk - 1) * x; if G(yk, xk) == 0% 把点加入can矩阵中can = [can no]; end end can_num = length(can); % 产生随机整数 index = randi(can_num); % 为每一行加一个可行点 pop(i, j) = can(index); end pop(i, end) = p_end; %pop % 种群初始化step2将上述必经节点联结成无间断路径 single_new_pop = generate_continuous_path(pop(i, :), G, x); %init_path = [init_path, single_new_pop]; if ~isempty(single_new_pop) new_pop1(z, 1) = {single_new_pop}; z = z + 1; endend% 计算初始化种群的适应度% 计算路径长度path_value = cal_path_value(new_pop1, x);% 计算路径平滑度path_smooth = cal_path_smooth(new_pop1, x);fit_value = a .* path_value .^ -1 + b .* path_smooth .^ -1;mean_path_value = zeros(1, max_gen);min_path_value = zeros(1, max_gen);% 循环迭代操作for i = 1 : max_gen % 选择操作 new_pop2 = selection(new_pop1, fit_value); % 交叉操作 new_pop2 = crossover(new_pop2, pc); % 变异操作 new_pop2 = mutation(new_pop2, pm, G, x); % 更新种群 new_pop1 = new_pop2; % 计算适应度值 % 计算路径长度 path_value = cal_path_value(new_pop1, x); % 计算路径平滑度 path_smooth = cal_path_smooth(new_pop1, x); fit_value = a .* path_value .^ -1 + b .* path_smooth .^ -1; mean_path_value(1, i) = mean(path_value); [~, m] = max(fit_value); if min(path_value) min_value=min(path_value); min_path_value(1, i) = min(path_value); else min_path_value(1, i) = min_value; endend% 画每次迭代平均路径长度和最优路径长度图figure(1)plot(1:max_gen, mean_path_value, 'r')hold on;title(['a = ', num2str(a)', '，b = ',num2str(b)','的优化曲线图']);xlabel('迭代次数');ylabel('路径长度');plot(1:max_gen, min_path_value, 'b')legend('平均路径长度', '最优路径长度');min_path_value(1, end)% 在地图上画路径[~, min_index] = max(fit_value);min_path = new_pop1{min_index, 1};figure(2)hold on;title(['a = ', num2str(a)', '，b = ',num2str(b)','遗传算法机器人运动轨迹']);xlabel('坐标x');ylabel('坐标y');DrawMap(G);[~, min_path_num] = size(min_path);for i = 1:min_path_num % 路径点所在列(从左到右编号1.2.3...) x_min_path(1, i) = mod(min_path(1, i), x) + 1; % 路径点所在行(从上到下编号行1.2.3...) y_min_path(1, i) = fix(min_path(1, i) / x) + 1;endhold on;plot(x_min_path,y_min_path,'r')
