1 简介近年来, 路径规划一直是机器人学中的研究热 点之一.它研究的目的是在有障碍物的环境中, 为机 器人寻找从起始点到目标点并且能够避开障碍物的 合理 、有效的路径.其中涉及到环境信息的获取 、环 境的表示 、路径执行、知识的获取等 .国内外已有不 少学者对移动机器人路径规划问题作了深入研究, 并提出了多种路径规划方法.例如, 可视图法[ 1-2] 、图 搜索法 、人工势场法[ 3] 等.但这些方法的搜索空间比 较大, 存在组合爆炸的问题, 难以满足实时搜索的要 求, 或者存在局部极小值问题, 使规划失败. 遗传算法由于具有算法鲁棒 、灵活, 在种群中搜 索不易落入局部最小点等优点[ 4] , 近几年被广泛采 用, 但它在实际应用过程中也可能会产生早熟现象、 局部寻优能力差等问题 .而模拟退火算法却具有较 强的局部搜索能力, 所以使用遗传算法与模拟退火 相结合的方法, 是解决上述问题的有效途径.本文中 将这两个算法结合构成遗传模拟退火算法, 它兼备 了很强的全局和局部搜索能力的优点, 在变量数目 较大时尤其突出.2 部分代码%%%%%%模拟退火遗传算法(SAGA)%%%%%%%%%%% clear %%%设置超参数 p_crs 0.7; %交叉概率 p_mut 0.1; %变异概率 ratio 0.5; %选择操作中父辈的比例 pop_num 5000; %种群规模 chrom_len 7; %染色体长度这里代表路线的点数 iteration 40; T0 100; %初始温度 A 0.8; %退火速度 % 一个个体就是一条路线 [x,y]popinit(pop_num,chrom_len); %产生初始种群 fitsaga_fitness(x,y, T0); %计算种群适应度 [bestx0,besty0,fit0]best(x,y,fit); d0 0; %初始路径长度 for j1:1:size(bestx0,2)-1 d0 d0 sqrt((bestx0(1,j1)-bestx0(1,j)).^2 ... (besty0(1,j1)-besty0(1,j)).^2); %该个体即路线的路径长度 end for i1:1:iteration %设置进化代数 [Parentx,Parenty]select(x, y, fit, ratio); %选择 [Kidx,Kidy]crossover(Parentx,Parenty,p_crs); %交叉 [Kidx,Kidy]mutation(Kidx,Kidy,p_mut); %变异 x [Parentx; Kidx]; % 得到新的种群 y [Parentx; Kidy]; x(:,chrom_len)1.5; % 保留终点 y(:,chrom_len)8.9; T T0 * A^(i-1); % 当前温度 fit saga_fitness(x,y,T); % 计算进化后的适应度 [bestx,besty,bestfit]best(x,y,fit); %选择每一代中的最佳个体 route_x(i,:)bestx; %保存该最佳个体 route_y(i,:)besty; route_fit(i)bestfit; for j1:1:size(bestx,2)-1 dd(j)sqrt((bestx(1,j1)-bestx(1,j)).^2 ... (besty(1,j1)-besty(1,j)).^2); %该个体即路线的路径长度 end d(i) sum(dd); %有问题 fprintf(%dth 代进化完成...\n, i) % plot(bestx,besty,r-); end route_fit [fit0, route_fit]; %加上初始种群中最优个体 route_x [bestx0; route_x]; route_y [bestx0; route_y]; d [d0, d]; [final_fit,idx]max(route_fit); %所有代中的的最佳路线 final_routexroute_x(idx,:); final_routeyroute_y(idx,:); final_distance min(d) %最佳路径长度 %画图可视化路线、进化过程 % start point xs0; ys0; % Destination xt1.5; yt8.9; %obstacle xobs[1.5 4.0 1.2]; yobs[6.5 3.0 1.5]; robs[1.5 1.0 0.8]; thetalinspace(0,2*pi,100); max_area 0; for k1:numel(xobs) fill(xobs(k)robs(k)*cos(theta),yobs(k)robs(k)*sin(theta),[0.5 0.7 0.8]); % 后一个参数表示RGB值 text(xobs(k), yobs(k), num2str(k)) hold on; end plot(xs,ys,bs,MarkerSize,12,MarkerFaceColor,y); plot(xt,yt,kp,MarkerSize,16,MarkerFaceColor,g); grid on; hold on; %%画出最短路径的路线 plot(final_routex,final_routey,r*-, linewidth, 1.5); legend(障碍物1,障碍物2,障碍物3,起点, 终点, 最短路线) set(gca,FontSize,16); hold off; % 进化过程中适应度曲线 figure, % plot(0:1:size(route_fit,2)-1, route_fit, linewidth, 1.2) plot(d, linewidth, 1.2) % ylim([0.08,0.1]) title([变异率,num2str(p_mut),,交叉率, num2str(p_crs), 的进化曲线]); legend(最短路径长度值, Location, northeast); set(gca,FontSize,16); d_saga d; save(d_saga); load(d_saga.mat); figure, plot(d, linewidth, 1.2), hold on, plot(d_saga, linewidth, 1.2); title([变异率,num2str(p_mut),,交叉率, num2str(p_crs), 的进化曲线]); legend(SAGA最优路径值, GA最优路径值, Location, northeast); set(gca,FontSize,16);3 仿真结果4 参考文献[1]周明, 孙树栋, 彭炎午. 基于遗传模拟退火算法的机器人路径规划[J]. 航空学报, 1998, 19(1):3.博主简介擅长智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真有科研问题可私信交流。部分理论引用网络文献若有侵权联系博主删除。