基于遗传算法的机器人路径规划MATLAB源码

遗传算法详解（含MATLAB代码）Python遗传算法框架使用实例（一）使用Geatpy实现句子匹配在前面几篇文章中，我们已经介绍了高性能Python遗传和进化算法框架——Geatpy的使用。

本篇就一个案例进行展开讲述：pip install geatpy更新至Geatpy2的方法：pip install --upgrade --user geatpy查看版本号，在Python中执行：import geatpyprint(geatpy.__version__)我们都听过“无限猴子定理”，说的是有无限只猴子用无限的时间会产生特定的文章。

在无限猴子定理中，我们“假定”猴子们是没有像人类那样“智能”的，而且“假定”猴子不会自我学习。

因此，这些猴子需要“无限的时间"。

而在遗传算法中，由于采用的是启发式的进化搜索，因此不需要”无限的时间“就可以完成类似的工作。

当然，需要产生的文章篇幅越长，那么就需要越久的时间才能完成。

下面以产生"T om is a little boy, isn't he? Yes he is, he is a good and smart child and he is always ready to help others, all in all we all like him very much."的句子为例，讲述如何利用Geatpy实现句子的搜索。

之前的文章中我们已经讲述过如何使用Geatpy的进化算法框架实现遗传算法编程。

这里就直接用框架。

把自定义问题类和执行脚本编写在下面的"main.py”文件中：# -*- coding: utf-8 -*-import numpy as npimport geatpy as eaclass MyProblem(ea.Problem): # 继承Problem父类def __init__(self):name = 'MyProblem' # 初始化name（函数名称，可以随意设置） # 定义需要匹配的句子strs = 'Tom is a little boy, isn't he? Yes he is, he is a good and smart child and he is always ready to help others, all in all we all like him very much.'self.words = []for c in strs:self.words.append(ord(c)) # 把字符串转成ASCII码M = 1 # 初始化M（目标维数）maxormins = [1] # 初始化maxormins（目标最小最大化标记列表，1：最小化该目标；-1：最大化该目标）Dim = len(self.words) # 初始化Dim（决策变量维数）varTypes = [1] * Dim # 初始化varTypes（决策变量的类型，元素为0表示对应的变量是连续的；1表示是离散的）lb = [32] * Dim # 决策变量下界ub = [122] * Dim # 决策变量上界lbin = [1] * Dim # 决策变量下边界ubin = [1] * Dim # 决策变量上边界# 调用父类构造方法完成实例化ea.Problem.__init__(self, name, M, maxormins, Dim, varTypes, lb, ub, lbin, ubin)def aimFunc(self, pop): # 目标函数Vars = pop.Phen # 得到决策变量矩阵diff = np.sum((Vars - self.words)**2, 1)pop.ObjV = np.array([diff]).T # 把求得的目标函数值赋值给种群pop的ObjV执行脚本if __name__ == "__main__":"""================================实例化问题对象============================="""problem = MyProblem() # 生成问题对象"""==================================种群设置================================"""Encoding = 'RI' # 编码方式NIND = 50 # 种群规模Field = ea.crtfld(Encoding, problem.varTypes, problem.ranges,problem.borders) # 创建区域描述器population = ea.Population(Encoding, Field, NIND) # 实例化种群对象（此时种群还没被初始化，仅仅是完成种群对象的实例化）"""================================算法参数设置=============================="""myAlgorithm = ea.soea_DE_rand_1_L_templet(problem, population) # 实例化一个算法模板对象myAlgorithm.MAXGEN = 2000 # 最大进化代数"""===========================调用算法模板进行种群进化========================="""[population, obj_trace, var_trace] = myAlgorithm.run() # 执行算法模板population.save() # 把最后一代种群的信息保存到文件中# 输出结果best_gen = np.argmin(obj_trace[:, 1]) # 记录最优种群是在哪一代best_ObjV = obj_trace[best_gen, 1]print('最优的目标函数值为：%s'%(best_ObjV))print('有效进化代数：%s'%(obj_trace.shape[0]))print('最优的一代是第 %s 代'%(best_gen + 1))print('评价次数：%s'%(myAlgorithm.evalsNum))print('时间已过 %s 秒'%(myAlgorithm.passTime))for num in var_trace[best_gen, :]:print(chr(int(num)), end = '')上述代码中首先定义了一个问题类MyProblem，然后调用Geatpy内置的soea_DE_rand_1_L_templet算法模板，它实现的是差分进化算法DE-rand-1-L，详见源码：运行结果如下：种群信息导出完毕。

硕士生考查课程考试试卷考试科目：考生姓名：考生学号：学院：专业：考生成绩：任课老师(签名)考试日期：年月日午时至时《MATLAB 教程》试题：A 、利用MATLAB 设计遗传算法程序，寻找下图11个端点最短路径，其中没有连接端点表示没有路径。

要求设计遗传算法对该问题求解。

ae h kB 、设计遗传算法求解f (x)极小值，具体表达式如下：321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =⎧=⎪⎨⎪-≤≤=⎩∑ 要求必须使用m 函数方式设计程序。

C 、利用MATLAB 编程实现：三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是如何乘船渡河的大权掌握在商人手中，商人们怎样才能安全渡河？D 、结合自己的研究方向选择合适的问题，利用MATLAB 进行实验。

以上四题任选一题进行实验，并写出实验报告。

选择题目：B 、设计遗传算法求解f (x)极小值，具体表达式如下：321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =⎧=⎪⎨⎪-≤≤=⎩∑ 要求必须使用m 函数方式设计程序。

一、问题分析（10分）这是一个简单的三元函数求最小值的函数优化问题，可以利用遗传算法来指导性搜索最小值。

实验要求必须以matlab 为工具，利用遗传算法对问题进行求解。

在本实验中，要求我们用M 函数自行设计遗传算法，通过遗传算法基本原理，选择、交叉、变异等操作进行指导性邻域搜索，得到最优解。

二、实验原理与数学模型（20分）（1）试验原理：用遗传算法求解函数优化问题，遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。

其采纳了自然进化模型，从代表问题可能潜在解集的一个种群开始，种群由经过基因编码的一定数目的个体组成。

每个个体实际上是染色体带有特征的实体；初始种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的解：在每一代，概据问题域中个体的适应度大小挑选个体；并借助遗传算子进行组合交叉和主客观变异，产生出代表新的解集的种群。

1 遗传算法的原理1.1 遗传算法的基本思想遗传算法（genetic algorithms，GA）是一种基于自然选择和基因遗传学原理，借鉴了生物进化优胜劣汰的自然选择机理和生物界繁衍进化的基因重组、突变的遗传机制的全局自适应概率搜索算法。

遗传算法是从一组随机产生的初始解（种群）开始，这个种群由经过基因编码的一定数量的个体组成，每个个体实际上是染色体带有特征的实体。

染色体作为遗传物质的主要载体，其内部表现（即基因型）是某种基因组合，它决定了个体的外部表现。

因此，从一开始就需要实现从表现型到基因型的映射，即编码工作。

初始种群产生后，按照优胜劣汰的原理，逐代演化产生出越来越好的近似解。

在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。

这个过程将导致种群像自然进化一样，后代种群比前代更加适应环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。

计算开始时，将实际问题的变量进行编码形成染色体，随机产生一定数目的个体，即种群，并计算每个个体的适应度值，然后通过终止条件判断该初始解是否是最优解，若是则停止计算输出结果，若不是则通过遗传算子操作产生新的一代种群，回到计算群体中每个个体的适应度值的部分，然后转到终止条件判断。

这一过程循环执行，直到满足优化准则，最终产生问题的最优解。

图1-1给出了遗传算法的基本过程。

1.2 遗传算法的特点1.2.1 遗传算法的优点遗传算法具有十分强的鲁棒性，比起传统优化方法，遗传算法有如下优点：1. 遗传算法以控制变量的编码作为运算对象。

传统的优化算法往往直接利用控制变量的实际值的本身来进行优化运算，但遗传算法不是直接以控制变量的值，而是以控制变量的特定形式的编码为运算对象。

这种对控制变量的编码处理方式，可以模仿自然界中生物的遗传和进化等机理，也使得我们可以方便地处理各种变量和应用遗传操作算子。

2. 遗传算法具有内在的本质并行性。

基于遗传算法的机器人路径规划MATLAB源代码基本思路是：取各障碍物顶点连线的中点为路径点，相互连接各路径点，将机器人移动的起点和终点限制在各路径点上，利用最短路径算法来求网络图的最短路径，找到从起点P1到终点Pn的最短路径。

上述算法使用了连接线中点的条件，因此不是整个规划空间的最优路径，然后利用遗传算法对找到的最短路径各个路径点Pi (i=1,2,…n)调整，让各路径点在相应障碍物端点连线上滑动，利用Pi= Pi1+ti×(Pi2-Pi1)（ti∈[0,1] i=1,2,…n）即可确定相应的Pi，即为新的路径点，连接此路径点为最优路径。

function [L1,XY1,L2,XY2]=JQRLJGH(XX,YY)%% 基于Dijkstra和遗传算法的机器人路径规划% GreenSim团队——专业级算法设计&代写程序% 欢迎访问GreenSim团队主页→/greensim%输入参数在函数体内部定义%输出参数为% L1 由Dijkstra算法得出的最短路径长度% XY1 由Dijkstra算法得出的最短路径经过节点的坐标% L2 由遗传算法得出的最短路径长度% XY2 由遗传算法得出的最短路径经过节点的坐标%程序输出的图片有% Fig1 环境地图（包括：边界、障碍物、障碍物顶点之间的连线、Dijkstra的网络图结构）% Fig2 由Dijkstra算法得到的最短路径% Fig3 由遗传算法得到的最短路径% Fig4 遗传算法的收敛曲线（迄今为止找到的最优解、种群平均适应值）%% 画Fig1figure(1);PlotGraph;title('地形图及网络拓扑结构')PD=inf*ones(26,26);for i=1:26for j=1:26if D(i,j)==1x1=XY(i,5);y1=XY(i,6);x2=XY(j,5);y2=XY(j,6);dist=((x1-x2)^2+(y1-y2)^2)^0.5;PD(i,j)=dist;endendend%% 调用最短路算法求最短路s=1;%出发点t=26;%目标点[L,R]=ZuiDuanLu(PD,s,t);L1=L(end);XY1=XY(R,5:6);%% 绘制由最短路算法得到的最短路径figure(2);PlotGraph;hold onfor i=1:(length(R)-1)x1=XY1(i,1);y1=XY1(i,2);x2=XY1(i+1,1);y2=XY1(i+1,2);plot([x1,x2],[y1,y2],'k');hold onendtitle('由Dijkstra算法得到的初始路径')%% 使用遗传算法进一步寻找最短路%第一步：变量初始化M=50;%进化代数设置N=20;%种群规模设置Pm=0.3;%变异概率设置LC1=zeros(1,M);LC2=zeros(1,M);Yp=L1;%第二步：随机产生初始种群X1=XY(R,1);Y1=XY(R,2);X2=XY(R,3);Y2=XY(R,4);for i=1:Nfarm{i}=rand(1,aaa);end% 以下是进化迭代过程counter=0;%设置迭代计数器while counter<M%停止条件为达到最大迭代次数%% 第三步：交叉%交叉采用双亲双子单点交叉newfarm=cell(1,2*N);%用于存储子代的细胞结构Ser=randperm(N);%两两随机配对的配对表A=farm{Ser(1)};%取出父代AB=farm{Ser(2)};%取出父代BP0=unidrnd(aaa-1);%随机选择交叉点a=[A(:,1:P0),B(:,(P0+1):end)];%产生子代ab=[B(:,1:P0),A(:,(P0+1):end)];%产生子代bnewfarm{2*N-1}=a;%加入子代种群newfarm{2*N}=b;for i=1:(N-1)A=farm{Ser(i)};B=farm{Ser(i+1)};newfarm{2*i}=b;endFARM=[farm,newfarm];%新旧种群合并%% 第四步：选择复制SER=randperm(2*N);FITNESS=zeros(1,2*N);fitness=zeros(1,N);for i=1:(2*N)PP=FARM{i};FITNESS(i)=MinFun(PP,X1,X2,Y1,Y2);%调用目标函数endfor i=1:Nf1=FITNESS(SER(2*i-1));f2=FITNESS(SER(2*i));if f1<=f2elsefarm{i}=FARM{SER(2*i)};fitness(i)=FITNESS(SER(2*i));endend%记录最佳个体和收敛曲线minfitness=min(fitness);meanfitness=mean(fitness);if minfitness<Yppos=find(fitness==minfitness);Xp=farm{pos(1)};Yp=minfitness;endif counter==10PPP=[0.5,Xp,0.5]';PPPP=1-PPP;X=PPP.*X1+PPPP.*X2;Y=PPP.*Y1+PPPP.*Y2;XY2=[X,Y];figure(3)PlotGraph;hold onfor i=1:(length(R)-1)x1=XY2(i,1);y1=XY2(i,2);x2=XY2(i+1,1);y2=XY2(i+1,2);plot([x1,x2],[y1,y2],'k');hold onendtitle('遗传算法第10代')hold onfor i=1:(length(R)-1)x1=XY1(i,1);y1=XY1(i,2);x2=XY1(i+1,1);y2=XY1(i+1,2);plot([x1,x2],[y1,y2],'k','LineWidth',1);hold onendendif counter==20PPP=[0.5,Xp,0.5]';PPPP=1-PPP;X=PPP.*X1+PPPP.*X2;Y=PPP.*Y1+PPPP.*Y2;XY2=[X,Y];figure(4)PlotGraph;hold onfor i=1:(length(R)-1)x1=XY2(i,1);y2=XY2(i+1,2);plot([x1,x2],[y1,y2],'k');hold onendtitle('遗传算法第20代')hold onx1=XY1(i,1);y1=XY1(i,2);x2=XY1(i+1,1);y2=XY1(i+1,2);plot([x1,x2],[y1,y2],'k','LineWidth',1);hold onendendif counter==30PPP=[0.5,Xp,0.5]';PPPP=1-PPP;X=PPP.*X1+PPPP.*X2;Y=PPP.*Y1+PPPP.*Y2;XY2=[X,Y];figure(5)PlotGraph;hold onfor i=1:(length(R)-1)x1=XY2(i,1);y1=XY2(i,2);x2=XY2(i+1,1);y2=XY2(i+1,2);plot([x1,x2],[y1,y2],'k');hold onendtitle('遗传算法第30代')hold onfor i=1:(length(R)-1)x1=XY1(i,1);y2=XY1(i+1,2);plot([x1,x2],[y1,y2],'k','LineWidth',1);hold onendendif counter==40PPP=[0.5,Xp,0.5]';PPPP=1-PPP;X=PPP.*X1+PPPP.*X2;Y=PPP.*Y1+PPPP.*Y2;XY2=[X,Y];figure(6)PlotGraph;hold onx1=XY2(i,1);y1=XY2(i,2);x2=XY2(i+1,1);y2=XY2(i+1,2);plot([x1,x2],[y1,y2],'k');hold onendtitle('遗传算法第40代')hold onfor i=1:(length(R)-1)x1=XY1(i,1);y1=XY1(i,2);x2=XY1(i+1,1);y2=XY1(i+1,2);plot([x1,x2],[y1,y2],'k','LineWidth',1);hold onendendif counter==50PPP=[0.5,Xp,0.5]';PPPP=1-PPP;X=PPP.*X1+PPPP.*X2;Y=PPP.*Y1+PPPP.*Y2;XY2=[X,Y];figure(7)PlotGraph;hold onfor i=1:(length(R)-1)x1=XY2(i,1);y1=XY2(i,2);x2=XY2(i+1,1);y2=XY2(i+1,2);plot([x1,x2],[y1,y2],'k');hold onendtitle('遗传算法第50代')hold onfor i=1:(length(R)-1)x1=XY1(i,1);y1=XY1(i,2);x2=XY1(i+1,1);y2=XY1(i+1,2);plot([x1,x2],[y1,y2],'k','LineWidth',1);hold onendendLC2(counter+1)=Yp;LC1(counter+1)=meanfitness;%% 第五步：变异for i=1:Nif Pm>rand&&pos(1)~=iAA=farm{i};AA(POS)=rand;farm{i}=AA;endendcounter=counter+1;disp(counter);end%% 输出遗传算法的优化结果PPP=[0.5,Xp,0.5]';PPPP=1-PPP;X=PPP.*X1+PPPP.*X2;Y=PPP.*Y1+PPPP.*Y2;XY2=[X,Y];L2=Yp;%% 绘制Fig3figure(8)PlotGraph;hold onhold onfor i=1:(length(R)-1)x1=XY1(i,1);y1=XY1(i,2);x2=XY1(i+1,1);y2=XY1(i+1,2);plot([x1,x2],[y1,y2],'k','LineWidth',1);hold onendfor i=1:(length(R)-1)x1=XY2(i,1);y1=XY2(i,2);x2=XY2(i+1,1);y2=XY2(i+1,2);plot([x1,x2],[y1,y2],'k');hold onendtitle('遗传算法最终结果')figure(9)PlotGraph;hold onfor i=1:(length(R)-1)x1=XY1(i,1);y1=XY1(i,2);x2=XY1(i+1,1);y2=XY1(i+1,2);plot([x1,x2],[y1,y2],'k','LineWidth',1);hold onendhold onfor i=1:(length(R)-1)x1=XY2(i,1);y1=XY2(i,2);x2=XY2(i+1,1);y2=XY2(i+1,2);plot([x1,x2],[y1,y2],'k','LineWidth',2);hold onendtitle('遗传算法优化前后结果比较')%% 绘制Fig4figure(10);plot(LC1);hold onplot(LC2);xlabel('迭代次数');title('收敛曲线');源代码运行结果展示。