精华内容
下载资源
问答
  • 遗传算法路径规划

    2019-06-25 18:32:02
    使用遗传算法实现路径规划,地图使用bmp文件,可以自己指定或者使用画图软件编写
  • 本代码主要利用MATLAB工具实现MATLAB——遗传算法路径规划,简单明了,易于理解
  • 里面包括基于栅格的遗传算法的的介绍及机器人路径规划程序,希望对你们有用
  • 用于带障碍的路径规划仿真及可视化,引入了geatpy 进化算法作为示例,可引入其它方法对比其目标函数值。
  • 算法学习之遗传算法路径规划(python代码实现)

    千次阅读 多人点赞 2020-05-22 15:47:45
    遗传算法学习——使用python做路径规划一、引言二、算法伪代码三、算法流程以及代码实现1、地图创建四、代码工程文档 一、引言   机器人控制过程中,路径规划是其中重要的一环。因此本文采用遗传算法对机器人移动...

    一、引言

      机器人控制过程中,路径规划是其中重要的一环。因此本文采用遗传算法对机器人移动时的路径进行优化,最终选取出一条最优路径。采用栅格图法为机器人移动的地图进行建模,并根据遗传算法机理,在python上仿真实现了最优路径的选取。
      在查阅资料时发现遗传算法做路径规划仿真大多采用matlab软件,而python实现的例子几乎没有。再加上本人正好在学习python,就参考matlab代码做了python的仿真。
    本文重点参考文献链接:基于遗传算法的移动机器人路径规划,在此感谢链接作者。

    二、算法伪代码

      算法伪代码如下:
        step1:建立地图
        step2:初始化种群
        step3:计算个体的适应度值
        step4:选择适应度合适的个体进入下一代
        step5:交叉
        step6:变异
        step7:更新种群,若出现最优路径或达到迭代次数,则转至step8,否则转step3
        step8:输出最优的个体作为最优解
      本文会按照算法的伪代码一步一步讲解。

    三、算法流程以及代码实现

    1、地图创建

      本文采取栅格图法创建地图空间,便于确定直角坐标系。
      如图1所示,图中共有25个栅格,每个栅格表示一段路径,其中黑色方块表示的是障碍物,白色方块表示的是自由栅格,即可行走。
      以图中为例,在构建栅格地图时,首先以地图左下角第一个栅格为坐标原点建立直角坐标系。因此每一个栅格可以用(x,y)的坐标形式表示,比如左下角第一个栅格可以表示为(1,1)。并且从左下角开始每一个栅格进行编号N,编号从0开始,设定编号0为起点,24为终点。说明下,这种编号方式就是遗传算法中的编码操作,会使相对复杂的问题结构,变得简单。比如现在以坐标形式表示一条从(1,1)到(5,5)的路径:(1,1)->(2,2)->(3,2)->(4,2)->(4,3)->(5,4)->(5,5)。这种方法在编程中需要使用二维数组来存放这么一条路径,但通过编码之后,这样的路径可以简化为:(0,6,7,8,13,19,24),只需要一个向量便可以表示。其中坐标和编码之间的转换关系为:
    x=N/col+1x = N/col+1
    y=N%col+1y = N\%col+1

    其中col为栅格图的列数,N为编码,x,y分别为横纵坐标,也可读作x行y列(需要注意,行数从下往上数,列数从左往右数)。
    图1 栅格图编码
      以上方法以一种通用的方法,本案例代码中由于使用python编程,构建地图用的是列表的方式,因此行数从上往下,列数从左往右,并且由于列表的索引从0开始,因此坐标原点也是用的(0,0)如下图所示,光标选中的左上角元素坐标为(0,0),编码为0,编码从左往右一次是0,1,2…直到右下角的99。
    带有障碍的栅格地图
      python实现画栅格地图的代码如下:

    import random
    class Map():
        '''
        :param:地图类
        :param:使用时需要传入行列两个参数 再实例化
        '''
    
        def __init__(self,row,col):
            '''
            :param:row::行
            :param:col::列
            '''
            self.data = []
            self.row = row
            self.col = col
        def map_init(self):
            self.data = [[0 for i in range(self.col)] for j in range(self.row)]
            # for i in range(self.row):
            #     for j in range(self.col):
            #         print(self.data[i][j],end=' ')
            #     print('')
        def map_Obstacle(self,num):
            '''
            :param:num:地图障碍物数量
            :return:返回包含障碍物的地图数据
            '''
            self.num = num
            for i in range(self.num):#生成小于等于num个障碍
                self.data[random.randint(0,self.row-1)][random.randint(0,self.col-1)] = 1
            if self.data[0][0] == 1:        #判断顶点位置是否是障碍  若是 修改成可通行
                self.data[0][0] = 0
    
            if self.data[self.row-1][0] == 1:
                self.data[self.row-1][0] = 0
    
            if self.data[0][self.col-1] == 1:
                self.data[0][self.col - 1] = 0
    
            if self.data[self.row-1][self.col - 1] == 1:
                self.data[self.row - 1][self.col - 1] = 0
            for i in range(self.row):       #显示出来
                for j in range(self.col):
                    print(self.data[i][j],end=' ')
                print('')
            return self.data
    

      使用时代码如下:

    map = Map(10,10)#10行 10列
    map.map_init()#生成初始的10行10列 的0矩阵
    arr = map.map_Obstacle(20)#这里传入的参数是在10*10 的0矩阵上随机生成20个障碍物,因为是随机生成,实际的障碍物数量<=20 返回带有障碍的数据给arr 
    

    到这里,已经生成了一个带有障碍的栅格地图,现在进行step2

    2、种群初始化

      种群的概念是个体的集合。在这之前需说明遗传算法是从问题解的编码组开始,而非单个解开始搜索。即种群的每一个个体都是当前问题的一个可行解,使用遗传算法的过程,是从这些可行解(个体)中找出最优解(适应度最强的个体)。对于本文来讲,种群的初始化就是找到若干组可以从起点到达终点的路径,每一组路径就是一个个体,种群的大小就是个体的数量。遗传算法求解最优路径过程中,种群的初始化是一个难点,也是最难的一步,既要保证路径的可行性,还要保证路径的连续性(即不能跳跃行走)。在遗传算法路径规划中,种群的初始化过程是最重要的,也是最难的。下面开始介绍本文用到的方法。
      本文实现种群初始化分为两步,第一步为找到一条间断的路径,即从栅格图的每一行中随机取出一个不是障碍物的元素。比如在图1中取(0,6,10,16,24),在每一行中都取了一个元素,并且这些元素都是自由栅格。第二步为将间断的路径连续化,在这步中,需要先从路径的第一个栅格判断此条路径与之相邻的下一个栅格是否为连续,判断公式为:
    D=Max{abs(x1x2),abs(y1y2)}D = Max\{abs(x1-x2),abs(y1-y2)\}
    若D=1,则说明路径连续,反之不连续。对于不连续的两个坐标,采用中点法计算两个栅格的中点栅格,公式如下:
    中点法插点
    其中(X_new,Y_new)是新插入栅格的坐标。
     1.若新栅格为障碍物栅格:则以上下左右(这个顺序可以任意,也可以改为8个方向搜索)顺序取新栅格的相邻栅格,并判断此栅格是否已经在路径中。
      a).若此栅格为无障碍栅格且不在路径中则插入路径中;
      b).若遍历上下左右四个栅格后没有满足条件的栅格则删除这条路径;
     2.若新栅格为无障碍物栅格,则插入两个到不连续栅格中间。
     3.继续判断新插入的栅格和新插入的栅格的前一个栅格是否连续,若不连续则循环以上步骤,直到两个栅格连续。当两个栅格连续后取下一个栅格,循环以上步骤,直到整条路径连续。
     4.按照以上步骤生成了一条初始路径之后,会出现走回头路的现象,比如按照图1生成了以下一条路径:(0,6,1,2,6,7,8,13,19,24)可以看出,6号这个节点一共走了两次,这样的话这条路径就会有冗余部分,也就是我认为的走了回头路。这种情况下,为了使算法加快收敛速度,就要保证初始种群比较优良,也就是初始的路径长度就短,那么就有必要滤除这段重复的路段,这里专门设计了一个滤除一段路径中两个相同元素之间内容的算法。代码在我的另一篇博文里面,这里附上链接:python实现将列表中重复元素之间的内容全部滤除
      这里初始化种群的步骤十分繁琐,因此直接上初始化代码,代码上有详细注释,代码如下:

    #step2 初始化种群 也是最难的一步
    class Population():
        def __init__(self,row,col,num,NP):
            self.row = row
            self.col = col
            self.num = num
            self.NP = NP
            self.p_start = 0  # 起始点序号  10进制编码
            self.p_end = self.row * self.col - 1  # 终点序号 10进制编码
            self.xs = (self.p_start) // (self.col)  # 行
            self.ys = (self.p_start) % (self.col)  # 列
            self.xe = (self.p_end) // (self.col)  # 终点所在的行
            self.ye = (self.p_end) % (self.col)
            self.map_start = Map(self.row, self.col)  # Map的实例化 主函数中可以不再初始化地图
            self.map_start.map_init()  # map初始化 生成0矩阵
            self.map = self.map_start.map_Obstacle(self.num)  # 生成带障碍的map
    
            self.can = []  # 这个列表存放整个地图中不是障碍物的点的坐标 按行搜索
            self.popu = [[0 for i in range(self.col)]
                         for j in range(self.NP)]  # 种群的列表,包含NP个间断可行解,即从起点到终点的路径
            # self.popu = []#存放可行解  可行路径
            self.end_popu = []	#存放最终的连续NP条路径
    
        def Population_Init(self):
            '''
            :return:返回NP条连续可行解  即初始路径
            '''
            for i in range(self.NP):       #添加NP条路径
                j = 0
                for xk in range(0,self.row):  #多少行
                    self.can = []             #清空can列表   用来缓存当前行的可行点
                    for yk in range(0,self.col):   #从起点0 开始的列开始搜寻到终点的列  也就是此行中的自由点
                        num = (yk) + (xk) * self.col
                        if self.map_start.data[xk][yk] == 0:
                            self.can.append(num)
                    # print(self.can,'自由点\n')
                    length = len(self.can)     #此行的长度  随机生成指针取出坐标
                    # print(length)
                    self.popu[i][j] = (self.can[random.randint(0,length-1)])
                    j += 1#j从1 开始  是因为 0 的元素时起点编号
                self.popu[i][0] = self.p_start  # 每一行的第一个元素设置为起点序号
                self.popu[i][-1] = self.p_end
    
                temp = self.Generate_Continuous_Path(self.popu[i])#将返回的一条路经 添加进end中
                if temp != []:      #将返回的空列表路径滤除
                    temp = fiter.fiter(temp)    #滤除重复节点路径
                    self.end_popu.append(temp)
                # print(self.end_popu, end='\n')
            # print('测试1',self.popu,end='\n')
            return self.end_popu
        # @staticmethod
        def Generate_Continuous_Path(self,old_popu):#生成连续的路径个体
            '''
            :param old_popu: 未进行连续化的一条路径
            :return:        返回已经连续化的一条路径
            '''
            self.new_popu = old_popu    #传进来的参数就是一行的数组  一条路径
            self.flag = 0
            self.lengh = len(self.new_popu)  #先将第一条路经的长度取出来
            i = 0
            # print("lengh =",self.lengh )
            while i!= self.lengh-1:       #i 不等于 当前行的长度减去1  从0计数  这里有问题 待修改
                x_now = (self.new_popu[i]) // (self.col)  # 行 解码  算出此条路经的第i个元素的直角坐标
                y_now = (self.new_popu[i]) % (self.col)  # 列
                x_next =  (self.new_popu[i+1]) // (self.col) #计算此条路经中下一个点的坐标
                y_next =  (self.new_popu[i+1]) % (self.col)
                #最大迭代次数
                max_iteration = 0
    
                #判断下一个点与当前点的坐标是否连续 等于1 为连续
                while max(abs(x_next - x_now), abs(y_next - y_now)) != 1:
                    x_insert = math.ceil((x_next + x_now) // 2)      #行
                    y_insert = math.ceil((y_next + y_now) // 2) #ceil向上取整数     #列
                    # print("x_insert = ",x_insert,"\ty_insert = ",y_insert)
                    flag1 = 0
    
                    if self.map_start.data[x_insert][y_insert] == 0:  #插入的这个坐标为0 可走
                        num_insert = (y_insert) + (x_insert) * self.col #计算出插入坐标的编码
                        self.new_popu.insert(i+1,num_insert)
                        # print(self.new_popu)
                        # print(num_insert)
                    else:#插入的栅格为障碍  判断插入的栅格上下左右是否为障碍,以及是否在路径中,若不是障碍且不在路径中,就插入
                        #判断下方
                        if (x_insert + 1 < self.row)and flag1 == 0:       #保证坐标是在地图上的
                            if ((self.map_start.data[x_insert+1][y_insert] == 0)#下方不是障碍物
                                and (((y_insert) + (x_insert+1) * self.col) not in self.new_popu)):#编号不在已知路径中
                                num_insert = (y_insert) + (x_insert+1) * self.col  #计算下方的编号
                                self.new_popu.insert(i + 1, num_insert) #插入编号
                                flag1 = 1       #设置标志位 避免下面重复插入
    
                                # print('下方插入',num_insert)
                        #判断右方
                        if (y_insert + 1 < self.col)and flag1 == 0:  # 保证坐标是在地图上的 并且前面没有插入
                            if ((self.map_start.data[x_insert][y_insert+1] == 0)#右方不是障碍物
                                and (((y_insert+1) + (x_insert) * self.col) not in self.new_popu)):#编号不在已知路径中
                                num_insert = (y_insert+1) + (x_insert) * self.col  #计算右方的编号
                                self.new_popu.insert(i + 1, num_insert) #插入编号
                                flag1 = 1  # 设置标志位 避免下面重复插入
                                # print('右方插入',num_insert)
                        #判断上方
                        if (x_insert - 1 > 0) and flag1 == 0:  # 保证坐标是在地图上的
                            if ((self.map_start.data[x_insert-1][y_insert] == 0)#右方不是障碍物
                                and (((y_insert) + (x_insert-1) * self.col) not in self.new_popu)):#编号不在已知路径中
                                num_insert = (y_insert) + (x_insert-1) * self.col  #计算右方的编号
                                self.new_popu.insert(i + 1, num_insert) #插入编号
                                flag1 = 1  # 设置标志位 避免下面重复插入
                                # print('上方插入',num_insert)
                        #判断左方
                        if (y_insert - 1 > 0)and flag1 == 0:  # 保证坐标是在地图上的
                            if ((self.map_start.data[x_insert][y_insert-1] == 0)#右方不是障碍物
                                and (((y_insert-1) + (x_insert) * self.col) not in self.new_popu)):#编号不在已知路径中
                                num_insert = (y_insert-1) + (x_insert) * self.col  #计算右方的编号
                                self.new_popu.insert(i + 1, num_insert) #插入编号
                                flag1 = 1  # 设置标志位 避免下面重复插入
                                # print('左方插入',num_insert)
                        if flag1 == 0:  #如果前面没有插入新点  说明这条路径不对 删除
                            self.new_popu = []
                            break
                    x_next = num_insert//self.col
                    y_next = num_insert%self.col
                    # x_next = x_insert
                    # y_next = y_insert
                    max_iteration += 1#迭代次数+1
                    if max_iteration > 20:
                        self.new_popu = []  #超出迭代次数 说明此条路经可能无法进行连续   删除路径
                        break
                if self.new_popu == []:
                    break
                self.lengh = len(self.new_popu)
                i = i+1
            # print(self.new_popu,'连续')
            return  self.new_popu#返回的是一条路径
    

      这里需要注意的是,在种群初始化对象的__init__方法中已经初始化了地图数据,因此主函数只需要对种群初始化对象实例化就行,使用方法如下:

    population = Population(10,10,20,100)   #实例化对象 并生成初始带随机障碍的地图
    popu = population.Population_Init()  #种群初始化  得到np条初始可行路径
    

    小结

      种群初始化是最难的一步,因为需要判断的地方非常多,比如连续化路径时,还要判断是否超出了地图边界,因为地图是列表数据,一旦超出索引,程序就会报错。还有许多需要注意的地方,这些在程序中都有注释,此外前文提到如果插入的点是障碍物,那么就在其上下左右四个方向搜寻自由点,其实也可以改为在其周围8个方向搜寻自由点,毕竟对角线的方向也是可以走的。
      然而出现的问题还是有的,使用中点插值法使路径连续化会产生一些错误,有的时候会穿过障碍行驶。针对这个问题,在下一步计算适应度函数的过程中,使用了惩罚函数来惩罚这些穿越障碍物的路径,但这个问题是这种方法本身的局限,靠惩罚函数是不能彻底解决的。因此在一些文献中,初始化种群还会采用RRT随机树的方法,这个在之后会改进。
      到这里初始化种群结束,进行下一步,计算适应度函数。

    3、适者生存之适应度函数

      这里就进入到了达尔文进化论的范畴了,其实并没有那么玄乎.适应度函数就是衡量一个问题的解是否是最优的标准,比如一个适应度函数:
    f(x)=x2+1f(x) = x^2+1
      要求f(x)的值取得最小时,x的值是最优的,那么f(x)就是适应度函数的值,x取得每一个值都是适应度函数的解,问题就是这个解是不是最优的。归根到底,遗传算法其实就是解决这样一个问题的方法。
      而本文选取的适应度函数标准为使得路径最短。代码中给定相邻的栅格图为1个单位长度,则对角的长度为1.4(根号2)。其实除了路径最短这一标准外,还有路径平滑度,机器人能耗等标准,由于能力有限,故本文只采用路径最短作为标准。
      根据以上的解释,求适应度函数值就可以理解为求一条路径从起点到终点的距离。代码如下:

    #step3 计算适应度函数
    def calvalue(popu,col):
        '''
        :param popu: 传入种群信息
        :param col: 这个参数是地图的列数 ,因为要解码用到
        :return: 返回的是每一条路径长度组成的列表
        '''
        hang = len(popu)#计算行
        value = [] #存放计算出来的路径长度值
        for i in range(hang):#从第0行开始 到最后一行
            value.append(0)
            single_popu = popu[i] #把当前行的元素赋给 single_popu 之后操作
            single_lengh = len(single_popu)#将当前行的长度拿出来
            for j in range(single_lengh-1):#从第一个元素计算到倒数第一个元素
                x_now = (single_popu[j]) // (col)  # 行 解码  算出此条路经的第i个元素的直角坐标
                y_now = (single_popu[j]) % (col)  # 列
                x_next = (single_popu[j + 1]) // (col)  # 计算此条路经中下一个点的坐标
                y_next = (single_popu[j + 1]) % (col)
                if abs(x_now - x_next) + abs(y_now - y_next) == 1:#路径上下左右连续 不是对角的 则路径长度为1
                    value[i] = value[i]+1
                elif max(abs(x_now - x_next),abs(y_now - y_next))>=2:#惩罚函数 若跳跃或者穿过障碍
                    value[i] = value[i] + 100
                else:
                    value[i] = value[i]+1.4  #对角长度为根号2  即1.4
        return value
    

    小结

      在计算适应度值的时候,传入的种群路径有的其实并不连续,因为跨过了障碍,因此在函数中用以下代码进行惩罚:

    elif max(abs(x_now - x_next),abs(y_now - y_next))>=2:#惩罚函数 若跳跃或者穿过障碍
    	value[i] = value[i] + 100
    

    就是将路径长度直接加长,这样的话在下一步"选择"操作中就大概率的会将这样的路径过滤掉,但不能保证全部过滤。

    4、物竞天择之选择

      这里就是根据适应度值进行选择比较优良的个体存活到下一代,也就是物竞天择。本文中采取了两种方法进行选择优良个体进入下一代。第一种方法是参考文献中所采用的轮盘赌方法;第二种方法是将适应度值从小到大排序,假设种群中强者的概率是50%,即0.5,并且认为强者都能存活(这里强者的概率其实就是对强者筛选过了),即都能进入下一代。那么剩下的50%就是弱者,而对于弱者,也有一个弱者存活概率比如0.3,之后采取随机存活的方式,产生一个0-1之间的随机小数,若0.3大于这个小数 ,那么认为可以存活,否则直接舍弃。存活下来的强者和弱者构成了一个新的种群,进行下一步的交叉操作。首先来看参考文献中的轮盘赌方法进行筛选下一代,代码如下:

    #step4 选择
    def selection(pop,value):
        '''
        :param pop:种群
        :param value:适应度值列表
        :return:返回新的种群
        '''
    
        ###原来的方法会丢失种群数量
        now_value=[]#做倒数后的适应度值列表
        P_value = []  #存放适应度值占总比概率的列表
        random_deci = []#存放随机的小数
        new_popu = []       #选择后的种群
        sum_value = 0   #存放适应度的总和  计算轮盘赌的概率
        lengh = len(pop)#首先计算种群有多少行,也就是有多少初始路径
        for i in range(lengh):
            new_popu.append([]) #原始种群有多少个个体  新的种群就有多少
        for i in value:     #由于适应度值是距离  将需要的就是距离最短的  因此求倒数来排序
            now_value.append(1/i)  #将适应度取倒数   倒数越小适应度越小,路径越长  就可以按概率抛弃
            sum_value += (1/i)
        for i in now_value:#将每一个适应度值取出来  做比例  得出每个适应度值的占比概率 存到列表中
            P_value.append(i/sum_value)
        P_value = np.cumsum(P_value)#累加和 并排序 从小到大
        for i in range(lengh):
            random_deci.append(random.random())#产生 i个随即小数 存到列表中
        random_deci = sorted(random_deci)#从小到大排序
        fitin = 0
        newin = 0
        while(newin<lengh): #遍历每一行
            if random_deci[newin] < P_value[fitin]:
                new_popu[newin] = pop[fitin]#这里的代码有点难理解
                newin += 1
            else:
                fitin += 1
        return new_popu
    

    再看第二种方法,代码如下:

    #step4 选择
    def selection(pop,value):
        '''
        :param pop:种群
        :param value:适应度值列表
        :return:返回新的种群
        '''
        ####原来的方法会丢失种群数量
        retain_rate = 0.6#适应度最优的保留几率
        random_rate = 0.3#适应度差的保留几率
        dict_my = dict(zip(value, pop))     #将路径距离和路径打包字典
    
        new_popu = []
        sort_dis = sorted(dict_my)   #将字典按照键排序  也就是按照距离短-长排序
        retain_lengh = int(len(pop)*retain_rate)      #适应度强的按照存活概率 保留下
        temp = sort_dis[:retain_lengh]      #缓存下保留的距离,待会将距离对应的字典值取出来
        # print(temp,'优秀保留')
        for i in sort_dis[retain_lengh:]:   #距离长的按照随机概率保留
            if random.random() < random_rate:
                temp.append(i)
        #temp现在存放的就是进入下一代的种群信息,他是距离信息,下一步通过字典将种群提取出来
        for i in temp:
            new_popu.append(dict_my[i]) #至此种群选取完
        return new_popu
    

    小结

      这两种方法都能够选取下一代的种群,但都会出现一个问题:在选择的过程中,种群的规模会慢慢变小,有时侯不等迭代结束,种群就所剩无几(即可行路径没剩几条了)虽然能够选出比较优的路径解,但总感觉哪里不对以及路径不是最优的,因此后续还要再查资料,解决这个问题。

    5、遗传学之交叉

      交叉的方法有许多种,由于这里采用十进制编码方式,因此单点交叉方法比较简单实用。
      代码中的思想为:给定一个交叉概率pc,然后再产生0-1之间的一个随机数,并和交叉概率pc比较,若pc大于这个随机小数,则进行交叉操作。
      交叉操作具体为:由于路径的不同而导致个体长度的不同,因此,选择相邻的两个个体,其交叉点的位置不一定相同,这里选取相同编码处进行交叉(起点和终点除外),以保证路径的连续性。具体的交叉操作是找出两条路径中所有相同的点,然后随机选择其中的一个点,将之后的路径进行交叉操作。比如一条连续路径为(0,6,7,8,13,18,23,24),另一条连续路径为(0,1,6,7,8,13,19,24),重复的序号(6,7,8,13),则随机选取一个序号,如13,将13后面的序号交叉,即可得到两条新的路径(0,6,7,8,13,19,24)和(0,1,6,7,8,13,18,23,24),其中(0,6,7,8,13,19,24)其实是肉眼看到的最优的路径,这就是交叉的操作。
    代码如下:

    #step5 交叉   拟采用单点交叉
    def cross(parents,pc):
        '''
        :param parents: 交叉的父类
        :param pc:   交叉概率
        :return:
        '''
        children = []  #首先创建一个子代 空列表 存放交叉后的种群
        single_popu_index_list = []#存放重复内容的指针
        lenparents = len(parents)  #先提取出父代的个数  因为要配对 奇数个的话会剩余一个
        parity = lenparents % 2 #计算出长度奇偶性  parity= 1 说明是奇数个  则需要把最后一条个体直接加上 不交叉
        for i in range(0,lenparents-1,2):       #每次取出两条个体 如果是奇数个则长度要减去 一  range函数不会取最后一个
            single_now_popu = parents[i]   #取出当前选中的两个父代中的第一个
            single_next_popu = parents[i+1]#取出当前选中的两个父代中的第二个
            children.append([]) #子代添加两行  稍后存取新的种群
            children.append([])
            index_content = list(set(single_now_popu).intersection(set(single_next_popu))) #第一条路经与第二条路经重复的内容
            num_rep = len(index_content)          #重复内容的个数
            if random.random() < pc and num_rep>=3:
                content = index_content[random.randint(0,num_rep-1)]   #随机选取一个重复的内容
                now_index = single_now_popu.index(content)  #重复内容在第一个父代中的索引
                next_index = single_next_popu.index(content)#重复内容在第二个父代中的索引
                children[i] = single_now_popu[0:now_index + 1] + single_next_popu[next_index + 1:]
                children[i+1] = single_next_popu[0:next_index + 1] + single_now_popu[now_index + 1:]
            else:
                children[i] = parents[i]
                children[i+1] = parents[i+1]
        if parity == 1:     #如果是个奇数  为了保证种群规模不变 需要加上最后一条
            children.append([]) #子代在添加一行
            children[-1] = parents[-1] #直接遗传给下一代
        return children
    

    这里如果pc概率小于随机小数,不进行交叉操作的话,就把原来的路径信息直接赋给下一代,因为要保证交叉操作不会减小种群规模。还有一点要注意,如果父代种群有奇数条路径,可以看到,代码中是每次选择相邻的两条路径进行交叉,只能交叉偶数个父代,那么最后会剩余一个父代没法交叉,这里就是直接遗传给下一代了。

        if parity == 1:     #如果是个奇数  为了保证种群规模不变 需要加上最后一条
            children.append([]) #子代在添加一行
            children[-1] = parents[-1] #直接遗传给下一代
    

    小结

      交叉操作是肯定不会减小种群的规模的,并且还会使种群多样化,在写这篇博客时,忽然想到,如果交叉时选择的父代是随机选择,指定交叉次数,会不会能使种群的规模达到我所指定的规模?还有一个之前就想到的问题,如果相同的元素除了起始点和交叉点之外大于等于2个,那么父代交叉完一次后,子代可能还会有重复的元素,子代是否能再次交叉一次?直至两个子代没有相同元素。这些操作能够使种群更加多样化,并且有可能解决种群规模在选择操作时减小的问题。这里记下,之后检验。

    6、遗传学之变异

      遗传学基因突变是指基因中的某一段发生变化,在此路径规划中的变异就是指一条路径的某一段发生了变化,在代码中的思想为:给定一个变异概率pm,然后产生0-1之间的一个随机数,并和变异概率pm比较,若pm大于随机小数则进行变异操作。
      变异方法是随机选取路径中除起点和终点以外的两个栅格,去除这两个栅格之间的路径,然后以这两个栅格为相邻点,使用初始化种群中的路径连续化步骤将这两个点进行连续操作。此时有可能无法产生连续的路径,则需要重新选择两个栅格执行以上操作,直到完成变异操作。这种重新生成的连续路径就是变异之后的连续路径。
    变异代码如下:

    #step6 变异
    def mutation(children,pm):
        '''
        :param children: 子代种群
        :param pm: 变异概率
        :return: 返回变异后的新种群
        '''
    
        row = len(children)   #子代有多少行   即多少条路经
        new_popu = []
        for i in range(row):#提取出来每一行
    
            single_popu = children[i]
            if random.random()<pm:#小于变异概率   就变异
                col = len(single_popu)#每一行的长度 即列数  也就是这条路径有多少节点
                first = random.randint(1,col-2) #随机选取两个指针
                second = random.randint(1,col-2)
                if first != second :    #判断两个指针是否相同  不相同的话把两个指针中间的部分删除 在进行连续化
                    #判断一下指针大小  便于切片
                    if(first<second):
                        single_popu = single_popu[0:first]+single_popu[second+1:]
                    else :
                        single_popu = single_popu[0:second] + single_popu[first+1:]
                temp = population.Generate_Continuous_Path(single_popu)#连续化
                if temp!= []:
                    new_popu.append(temp)
            else:       #不变异的话就将原来的个体直接赋值
                new_popu.append(single_popu)
        return new_popu
    

    小结

      额。。。这个代码贴上来之后,我好像发现了种群规模减小的原因了。原因就是:此时有可能无法产生连续的路径,则需要重新选择两个栅格执行以上操作,直到完成变异操作。这句话我在程序中忽略了,对于无法生成路径的变异个体,我直接舍弃了,所以会导致变异丢失种群数量。在程序中应该判断如下:

    if temp == []:#路径为空,说明没有生成连续路径
    	'''
    	这段里面应该在进行循环变异知道变异成功
    	'''
    	pass
    

    7、更新种群以及输出结果

      至此,选择、交叉、变异全部完成,种群更新完毕。若没有出现最优路径或者超出迭代次数,则继续进行之前的操作。若是出现最优路径或迭代完毕则从种群中找到适应度值最小的个体进行输出,并将栅格地图中的编码用’*‘代替。画出清晰的路径图。
    这段代码在主函数中呈现:

    if __name__ == '__main__':
        print('原始地图')
        population = Population(10,10,20,100)   #实例化对象 并生成初始带随机障碍的地图
    
        popu = population.Population_Init()  #种群初始化  得到np条初始可行路径
        # print(popu,'连续路径')#打印出np条可行路径
    
        for i in range(200):    #迭代200代
            lastpopu = popu #上次的种群先保存起来
            value = calvalue(popu,population.col) #计算适应度值
            # print(value,'适应度值')#打印出np条路径的适应度值
    
            new = selection(popu,value)#选择 按适应度返回新的种群
            # print(new,'新种群')
            # value = calvalue(new,population.col) #计算适应度值
            # print(value,'新种群适应度值')#打印出np条路径的适应度值
            child = cross(new,0.8)  #交叉  产生子代
            # print(child,'交叉子代')
            # value = calvalue(child,population.col) #计算适应度值
            # print(value,'子代适应度值')#打印出np条路径的适应度值
            popu = mutation(child,0.8)#变异 产生子代 并更新原始种群
    
            if popu == []:  #如果本次的种群成空了  则把上次的种群信息拿出来,并迭代结束
                popu = lastpopu
                break
            # print('第',i,'次迭代后的种群为:',popu)
        if popu == []:  #迭代完成后先判断 若迭代完成了 但是种群路径还是空 说明可能是没有路径
            print('无路径')
        else:
            value = calvalue(popu,population.col) #计算适应度值
            minnum = value[0]
            for i in range(len(value)):#找出最小的适应度函数值
                if value[i] < minnum:#小于最小适应度  则替代
                    minnum = value[i]
            popu = popu[value.index(minnum)]#取出最小的适应度值的个体
    
            for i in popu:
                x = (i) // (population.map_start.col)  # 行 解码  算出此条路经的第i个元素的直角坐标
                y = (i) % (population.map_start.col)  # 列
                population.map_start.data[x][y] = '*'   #将路径用*表示
            print('\n规划地图')
            for i in range(population.map_start.row):   #显示路径
                for j in range(population.map_start.col):
                    print(population.map_start.data[i][j],end=' ')
                print('')
            print('最短路径值为:',minnum)
            print('最短路径为:',popu)
    

    结果如下图,上面的数组为生成的带障碍的原始地图,下面的为规划好路径的地图,最后输出最优路径的路径长度以及路径编码号。
    结果图

    四、代码工程文档

      理论再多,不如直接上可以用的代码,下面的代码为整体的工程代码,直接可Ctrl+C->Ctrl+V运行:

    # -*- coding: UTF-8 -*-
    '''*******************************
    @ 开发人员:Mr.Zs
    @ 开发时间:2020/5/18 19:22
    @ 开发环境:PyCharm
    @ 项目名称:算法类总工程->遗传算法路径规划V1.0.py
    ******************************'''
    import random   #生成随机整数
    import numpy as np #生成随机小数
    import math #用于计算除法 取整等运算
    print(r'''
    遗传算法是对参数集合的编码而非针对参数本身开始进化
    遗传算法是从问题解的编码组开始,而非单个解开始搜索
    
    step1:建立地图
    step2:初始化种群(随机生成若干条从起点能够到达终点的路径(可行解),每一条可行路径为一个个体)
    step3:计算个体的适应度值
    step4:选择适应度合适的个体进入下一代
    step5:交叉
    step6:变异
    step7:更新种群,若没有出现最优个体,则转至step3
    step8:输出最优的个体作为最优解
    参考文献:https://blog.csdn.net/qq_40870689/article/details/86916910?ops_request_misc=&request_id=&biz_id=102&utm_term=%E9%81%97%E4%BC%A0%E7%AE%97%E6%B3%95%E8%B7%AF%E5%BE%84%E8%A7%84%E5%88%92&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-1-86916910
    ''')
    
    #这个对象专门滤除路径中的回头路
    class Fiter:
        def __init__(self):
            self.b = 1  # 标志位
    
        def function(self, a):  # 定义一个函数
            for i in a:  # 遍历列表中的内容
                a = a[a.index(i) + 1:]  # 把当前内容索引的后面的内容剪切下来  因为前面的已经比对过了
                if i in a:  # 如果当前内容与后面有重复
                    return i, 1  # 返回当前重复的内容 以及标志位1
                else:  # 没有重复就不用管  继续for循环
                    pass
            return 0, 0  # 全部遍历完  没有重复的就返回0 这里返回两个0 是因为返回的数量要保持一致
    
        def fiter(self, a):
            while (self.b == 1):  # 标志位一直是 1  则说明有重复的内容
                (i, self.b) = self.function(a)  # 此时接受函数接收 返回值 i是重复的内容 b是标志位
                c = [j for j, x in enumerate(a) if x == i]  # 将重复内容的索引全部添加进c列表中
                a = a[0:c[0]] + a[c[-1]:]  # a列表切片在重组
            return a
    fiter = Fiter()#实例化对象
    #将地图上的点抽象话,可以用x表示横坐标 y表示纵坐标
    class Point:
        def __init__(self, x, y):
            self.x = x
            self.y = y
    
        def __eq__(self, other): #函数重载  #判断两个坐标  的  值 是否一样
            if((self.x == other.x )and (self.y == other.y)):
                return  True
            else:
                return False
        def __ne__(self, other):
            pass
    
    #step1
    class Map():
        '''
        :param:地图类
        :param:使用时需要传入行列两个参数 再实例化
        '''
    
        def __init__(self,row,col):
            '''
            :param:row::行
            :param:col::列
            '''
            self.start_point = Point(0,0)
            self.end_point = Point(row-1,col-1)
            self.data = []
            self.row = row
            self.col = col
        def map_init(self):
            '''
            :param:创建栅格地图row行*col列 的矩阵
            '''
            self.data = [[0 for i in range(self.col)] for j in range(self.row)]
            # for i in range(self.row):
            #     for j in range(self.col):
            #         print(self.data[i][j],end=' ')
            #     print('')
        def map_Obstacle(self,num):
            '''
            :param:num:地图障碍物数量
            :return:返回包含障碍物的地图数据
            '''
            self.num = num
            for i in range(self.num):#生成小于等于num个障碍
                self.data[random.randint(0,self.row-1)][random.randint(0,self.col-1)] = 1
            if self.data[0][0] == 1:        #判断顶点位置是否是障碍  若是 修改成可通行
                self.data[0][0] = 0
    
            if self.data[self.row-1][0] == 1:
                self.data[self.row-1][0] = 0
    
            if self.data[0][self.col-1] == 1:
                self.data[0][self.col - 1] = 0
    
            if self.data[self.row-1][self.col - 1] == 1:
                self.data[self.row - 1][self.col - 1] = 0
            for i in range(self.row):       #显示出来
                for j in range(self.col):
                    print(self.data[i][j],end=' ')
                print('')
            return self.data
    #step2 初始化种群 也是最难的一步
    class Population():
        def __init__(self,row,col,num,NP):
            self.row = row
            self.col = col
            self.num = num
            self.NP = NP
            self.p_start = 0  # 起始点序号  10进制编码
            self.p_end = self.row * self.col - 1  # 终点序号 10进制编码
            self.xs = (self.p_start) // (self.col)  # 行
            self.ys = (self.p_start) % (self.col)  # 列
            self.xe = (self.p_end) // (self.col)  # 终点所在的行
            self.ye = (self.p_end) % (self.col)
            self.map_start = Map(self.row, self.col)  # Map的实例化 主函数中可以不再初始化地图
            self.map_start.map_init()  # map初始化 生成0矩阵
            self.map = self.map_start.map_Obstacle(self.num)  # 生成带障碍的map
    
            self.can = []  # 这个列表存放整个地图中不是障碍物的点的坐标 按行搜索
            self.popu = [[0 for i in range(self.col)]
                         for j in range(self.NP)]  # 种群的列表,包含NP个间断可行解,即从起点到终点的路径
            # self.popu = []#存放可行解  可行路径
            self.end_popu = []
    
        def Population_Init(self):
            '''
            :return:无返回值,作用是找出NP条不连续可行解
            '''
    
    
            for i in range(self.NP):       #添加NP条路径
                j = 0
                for xk in range(0,self.row):  #多少行
                    self.can = []             #清空can列表   用来缓存当前行的可行点
                    for yk in range(0,self.col):   #从起点0 开始的列开始搜寻到终点的列  也就是此行中的自由点
                        num = (yk) + (xk) * self.col
                        if self.map_start.data[xk][yk] == 0:
                            self.can.append(num)
                    # print(self.can,'自由点\n')
                    length = len(self.can)     #此行的长度  随机生成指针取出坐标
                    # print(length)
                    self.popu[i][j] = (self.can[random.randint(0,length-1)])
                    j += 1#j从1 开始  是因为 0 的元素时起点编号
                self.popu[i][0] = self.p_start  # 每一行的第一个元素设置为起点序号
                self.popu[i][-1] = self.p_end
    
                temp = self.Generate_Continuous_Path(self.popu[i])#将返回的一条路经 添加进end中
                if temp != []:      #将返回的空列表路径滤除
                    temp = fiter.fiter(temp)    #滤除重复节点路径
                    self.end_popu.append(temp)
                # print(self.end_popu, end='\n')
            # print('测试1',self.popu,end='\n')
            return self.end_popu
        # @staticmethod
        def Generate_Continuous_Path(self,old_popu):#生成连续的路径个体
            '''
            :param old_popu: 未进行连续化的一条路径
            :return:        无返回                   # 已经连续化的一条路径
            '''
            self.new_popu = old_popu    #传进来的参数就是一行的数组  一条路径
            self.flag = 0
            self.lengh = len(self.new_popu)  #先将第一条路经的长度取出来
            i = 0
            # print("lengh =",self.lengh )
            while i!= self.lengh-1:       #i 不等于 当前行的长度减去1  从0计数  这里有问题 待修改
                x_now = (self.new_popu[i]) // (self.col)  # 行 解码  算出此条路经的第i个元素的直角坐标
                y_now = (self.new_popu[i]) % (self.col)  # 列
                x_next =  (self.new_popu[i+1]) // (self.col) #计算此条路经中下一个点的坐标
                y_next =  (self.new_popu[i+1]) % (self.col)
                #最大迭代次数
                max_iteration = 0
    
                #判断下一个点与当前点的坐标是否连续 等于1 为连续
                while max(abs(x_next - x_now), abs(y_next - y_now)) != 1:
                    x_insert = math.ceil((x_next + x_now) // 2)      #行
                    y_insert = math.ceil((y_next + y_now) // 2) #ceil向上取整数     #列
                    # print("x_insert = ",x_insert,"\ty_insert = ",y_insert)
                    flag1 = 0
    
                    if self.map_start.data[x_insert][y_insert] == 0:  #插入的这个坐标为0 可走
                        num_insert = (y_insert) + (x_insert) * self.col #计算出插入坐标的编码
                        self.new_popu.insert(i+1,num_insert)
                        # print(self.new_popu)
                        # print(num_insert)
                    else:#插入的栅格为障碍  判断插入的栅格上下左右是否为障碍,以及是否在路径中,若不是障碍且不在路径中,就插入
                        #判断下方
                        if (x_insert + 1 < self.row)and flag1 == 0:       #保证坐标是在地图上的
                            if ((self.map_start.data[x_insert+1][y_insert] == 0)#下方不是障碍物
                                and (((y_insert) + (x_insert+1) * self.col) not in self.new_popu)):#编号不在已知路径中
                                num_insert = (y_insert) + (x_insert+1) * self.col  #计算下方的编号
                                self.new_popu.insert(i + 1, num_insert) #插入编号
                                flag1 = 1       #设置标志位 避免下面重复插入
    
                                # print('下方插入',num_insert)
                        #判断右方
                        if (y_insert + 1 < self.col)and flag1 == 0:  # 保证坐标是在地图上的 并且前面没有插入
                            if ((self.map_start.data[x_insert][y_insert+1] == 0)#右方不是障碍物
                                and (((y_insert+1) + (x_insert) * self.col) not in self.new_popu)):#编号不在已知路径中
                                num_insert = (y_insert+1) + (x_insert) * self.col  #计算右方的编号
                                self.new_popu.insert(i + 1, num_insert) #插入编号
                                flag1 = 1  # 设置标志位 避免下面重复插入
                                # print('右方插入',num_insert)
                        #判断上方
                        if (x_insert - 1 > 0) and flag1 == 0:  # 保证坐标是在地图上的
                            if ((self.map_start.data[x_insert-1][y_insert] == 0)#右方不是障碍物
                                and (((y_insert) + (x_insert-1) * self.col) not in self.new_popu)):#编号不在已知路径中
                                num_insert = (y_insert) + (x_insert-1) * self.col  #计算右方的编号
                                self.new_popu.insert(i + 1, num_insert) #插入编号
                                flag1 = 1  # 设置标志位 避免下面重复插入
                                # print('上方插入',num_insert)
                        #判断左方
                        if (y_insert - 1 > 0)and flag1 == 0:  # 保证坐标是在地图上的
                            if ((self.map_start.data[x_insert][y_insert-1] == 0)#右方不是障碍物
                                and (((y_insert-1) + (x_insert) * self.col) not in self.new_popu)):#编号不在已知路径中
                                num_insert = (y_insert-1) + (x_insert) * self.col  #计算右方的编号
                                self.new_popu.insert(i + 1, num_insert) #插入编号
                                flag1 = 1  # 设置标志位 避免下面重复插入
                                # print('左方插入',num_insert)
                        if flag1 == 0:  #如果前面没有插入新点  说明这条路径不对 删除
                            self.new_popu = []
                            break
                    x_next = num_insert//self.col
                    y_next = num_insert%self.col
                    # x_next = x_insert
                    # y_next = y_insert
                    max_iteration += 1#迭代次数+1
                    if max_iteration > 20:
                        self.new_popu = []  #超出迭代次数 说明此条路经可能无法进行连续   删除路径
                        break
                if self.new_popu == []:
                    break
                self.lengh = len(self.new_popu)
                i = i+1
            # print(self.new_popu,'连续')
            return  self.new_popu#返回的是一条路径
    #step3 计算适应度函数
    def calvalue(popu,col):
        '''
        :param popu: 传入种群信息
        :param col: 这个参数是地图的列数 ,因为要解码用到
        :return:    返回的是每一条路径长度组成的列表
        '''
        hang = len(popu)#计算行
        value = [] #存放计算出来的路径长度值
        for i in range(hang):#从第0行开始 到最后一行
            value.append(0)
            single_popu = popu[i] #把当前行的元素赋给 single_popu 之后操作
            single_lengh = len(single_popu)#将当前行的长度拿出来
            for j in range(single_lengh-1):#从第一个元素计算到倒数第一个元素
                x_now = (single_popu[j]) // (col)  # 行 解码  算出此条路经的第i个元素的直角坐标
                y_now = (single_popu[j]) % (col)  # 列
                x_next = (single_popu[j + 1]) // (col)  # 计算此条路经中下一个点的坐标
                y_next = (single_popu[j + 1]) % (col)
                if abs(x_now - x_next) + abs(y_now - y_next) == 1:#路径上下左右连续 不是对角的 则路径长度为1
                    value[i] = value[i]+1
                elif max(abs(x_now - x_next),abs(y_now - y_next))>=2:#惩罚函数 若跳跃或者穿过障碍
                    value[i] = value[i] + 100
                else:
                    value[i] = value[i]+1.4  #对角长度为根号2  即1.4
        return value
    #step4 选择
    def selection(pop,value):
        '''
        :param pop:种群
        :param value:适应度值列表
        :return:返回新的种群
        '''
    
        ###原来的方法会丢失种群数量
        now_value=[]#做倒数后的适应度值列表
        P_value = []  #存放适应度值占总比概率的列表
        random_deci = []#存放随机的小数
        new_popu = []       #选择后的种群
        sum_value = 0   #存放适应度的总和  计算轮盘赌的概率
        lengh = len(pop)#首先计算种群有多少行,也就是有多少初始路径
        for i in range(lengh):
            new_popu.append([]) #原始种群有多少个个体  新的种群就有多少
        for i in value:     #由于适应度值是距离  将需要的就是距离最短的  因此求倒数来排序
            now_value.append(1/i)  #将适应度取倒数   倒数越小适应度越小,路径越长  就可以按概率抛弃
            sum_value += (1/i)
        for i in now_value:#将每一个适应度值取出来  做比例  得出每个适应度值的占比概率 存到列表中
            P_value.append(i/sum_value)
        P_value = np.cumsum(P_value)#累加和 并排序 从小到大
        for i in range(lengh):
            random_deci.append(random.random())#产生 i个随即小数 存到列表中
        random_deci = sorted(random_deci)#从小到大排序
        fitin = 0
        newin = 0
        while(newin<lengh): #遍历每一行
            if random_deci[newin] < P_value[fitin]:
                new_popu[newin] = pop[fitin]
                newin += 1
            else:
                fitin += 1
        return new_popu
        # ####原来的方法会丢失种群数量
        # retain_rate = 0.6#适应度最优的保留几率
        # random_rate = 0.3#适应度差的保留几率
        # dict_my = dict(zip(value, pop))     #将路径距离和路径打包字典
        #
        # new_popu = []
        # sort_dis = sorted(dict_my)   #将字典按照键排序  也就是按照距离短-长排序
        # retain_lengh = int(len(pop)*retain_rate)      #适应度强的按照存活概率 保留下
        # temp = sort_dis[:retain_lengh]      #缓存下保留的距离,待会将距离对应的字典值取出来
        # # print(temp,'优秀保留')
        # for i in sort_dis[retain_lengh:]:   #距离长的按照随机概率保留
        #     if random.random() < random_rate:
        #         temp.append(i)
        # #temp现在存放的就是进入下一代的种群信息,他是距离信息,下一步通过字典将种群提取出来
        # for i in temp:
        #     new_popu.append(dict_my[i]) #至此种群选取完
        # return new_popu
    #step5 交叉   拟采用单点交叉
    def cross(parents,pc):
        '''
        :param parents: 交叉的父类
        :param pc:   交叉概率
        :return:
        '''
        children = []  #首先创建一个子代 空列表 存放交叉后的种群
        single_popu_index_list = []#存放重复内容的指针
        lenparents = len(parents)  #先提取出父代的个数  因为要配对 奇数个的话会剩余一个
        parity = lenparents % 2 #计算出长度奇偶性  parity= 1 说明是奇数个  则需要把最后一条个体直接加上 不交叉
        for i in range(0,lenparents-1,2):       #每次取出两条个体 如果是奇数个则长度要减去 一  range函数不会取最后一个
            single_now_popu = parents[i]   #取出当前选中的两个父代中的第一个
            single_next_popu = parents[i+1]#取出当前选中的两个父代中的第二个
            children.append([]) #子代添加两行  稍后存取新的种群
            children.append([])
            index_content = list(set(single_now_popu).intersection(set(single_next_popu))) #第一条路经与第二条路经重复的内容
            num_rep = len(index_content)          #重复内容的个数
            if random.random() < pc and num_rep>=3:
                content = index_content[random.randint(0,num_rep-1)]   #随机选取一个重复的内容
                now_index = single_now_popu.index(content)  #重复内容在第一个父代中的索引
                next_index = single_next_popu.index(content)#重复内容在第二个父代中的索引
                children[i] = single_now_popu[0:now_index + 1] + single_next_popu[next_index + 1:]
                children[i+1] = single_next_popu[0:next_index + 1] + single_now_popu[now_index + 1:]
            else:
                children[i] = parents[i]
                children[i+1] = parents[i+1]
        if parity == 1:     #如果是个奇数  为了保证种群规模不变 需要加上最后一条
            children.append([]) #子代在添加一行
            children[-1] = parents[-1]
        return children
    #step6 变异
    def mutation(children,pm):
        '''
        :param children: 子代种群
        :param pm: 变异概率
        :return: 返回变异后的新种群
        '''
    
        row = len(children)   #子代有多少行   即多少条路经
        new_popu = []
        for i in range(row):#提取出来每一行
    
            single_popu = children[i]
            if random.random()<pm:#小于变异概率   就变异
                col = len(single_popu)#每一行的长度 即列数  也就是这条路径有多少节点
                first = random.randint(1,col-2) #随机选取两个指针
                second = random.randint(1,col-2)
                if first != second :    #判断两个指针是否相同  不相同的话把两个指针中间的部分删除 在进行连续化
                    #判断一下指针大小  便于切片
                    if(first<second):
                        single_popu = single_popu[0:first]+single_popu[second+1:]
                    else :
                        single_popu = single_popu[0:second] + single_popu[first+1:]
                temp = population.Generate_Continuous_Path(single_popu)#连续化
                if temp!= []:
                    new_popu.append(temp)
            else:       #不变异的话就将原来的个体直接赋值
                new_popu.append(single_popu)
        return new_popu
    if __name__ == '__main__':
        print('原始地图')
        population = Population(10,10,20,100)   #实例化对象 并生成初始带随机障碍的地图
    
        popu = population.Population_Init()  #种群初始化  得到np条初始可行路径
        # print(popu,'连续路径')#打印出np条可行路径
    
        for i in range(200):    #迭代200代
            lastpopu = popu #上次的种群先保存起来
            value = calvalue(popu,population.col) #计算适应度值
            # print(value,'适应度值')#打印出np条路径的适应度值
    
            new = selection(popu,value)#选择 按适应度返回新的种群
            # print(new,'新种群')
            # value = calvalue(new,population.col) #计算适应度值
            # print(value,'新种群适应度值')#打印出np条路径的适应度值
            child = cross(new,0.8)  #交叉  产生子代
            # print(child,'交叉子代')
            # value = calvalue(child,population.col) #计算适应度值
            # print(value,'子代适应度值')#打印出np条路径的适应度值
            popu = mutation(child,0.8)#变异 产生子代 并更新原始种群
    
            if popu == []:  #如果本次的种群成空了  则把上次的种群信息拿出来,并迭代结束
                popu = lastpopu
                break
            # print('第',i,'次迭代后的种群为:',popu)
        if popu == []:  #迭代完成后先判断 若迭代完成了 但是种群路径还是空 说明可能是没有路径
            print('无路径')
        else:
            value = calvalue(popu,population.col) #计算适应度值
            minnum = value[0]
            for i in range(len(value)):#找出最小的适应度函数值
                if value[i] < minnum:#小于最小适应度  则替代
                    minnum = value[i]
            popu = popu[value.index(minnum)]#取出最小的适应度值的个体
    
            for i in popu:
                x = (i) // (population.map_start.col)  # 行 解码  算出此条路经的第i个元素的直角坐标
                y = (i) % (population.map_start.col)  # 列
                population.map_start.data[x][y] = '*'   #将路径用*表示
            print('\n规划地图')
            for i in range(population.map_start.row):   #显示路径
                for j in range(population.map_start.col):
                    print(population.map_start.data[i][j],end=' ')
                print('')
            print('最短路径值为:',minnum)
            print('最短路径为:',popu)
    

    结束语

      代码还有个待改进的地方,有时候明明有路径,但是却会输出“无路径”,可能是与路径连续化这个代码有关系

    问题解决

    1、解决种群规模随迭代次数增加而减小的问题

      解决方法与上文猜测一致,将变异操作的代码改为如下所示即可:

    #step6 变异
    def mutation(children,pm):
        '''
        :param children: 子代种群
        :param pm: 变异概率
        :return: 返回变异后的新种群
        '''
    
        row = len(children)   #子代有多少行   即多少条路经
        new_popu = []
        for i in range(row):#提取出来每一行
            temp = [] #定义一个缓存路径的空列表
            while(temp == []): #在这里加入死循环,一直等待变异成功
                single_popu = children[i]
                if random.random()<pm:#小于变异概率   就变异
                    col = len(single_popu)#每一行的长度 即列数  也就是这条路径有多少节点
                    first = random.randint(1,col-2) #随机选取两个指针
                    second = random.randint(1,col-2)
                    if first != second :    #判断两个指针是否相同  不相同的话把两个指针中间的部分删除 在进行连续化
                        #判断一下指针大小  便于切片
                        if(first<second):
                            single_popu = single_popu[0:first]+single_popu[second+1:]
                        else :
                            single_popu = single_popu[0:second] + single_popu[first+1:]
                    temp = population.Generate_Continuous_Path(single_popu)#连续化
                    if temp!= []:
                        new_popu.append(temp)
    
                else:       #不变异的话就将原来的个体直接赋值
                    new_popu.append(single_popu)
        return new_popu
    
    展开全文
  • 本发明涉及工业机器人应用领域,尤其是基于遗传算法和五次多项式插值的机器人路径规划方法,适用于六自由度工业机器人在焊接、喷涂、工装夹具及自动化作业等领域范畴。背景技术:随着自动化技术的发展,工业机器人在...

    本发明涉及工业机器人应用领域,尤其是基于遗传算法和五次多项式插值的机器人路径规划方法,适用于六自由度工业机器人在焊接、喷涂、工装夹具及自动化作业等领域范畴。

    背景技术:

    随着自动化技术的发展,工业机器人在制造业中的地位越来越显著。为进一步提高机器人工作效率,保证产品质量,对机器人轨迹规划深入研究一直是热点问题。传统工业机器人大多是通过固定示教再现的手段来执行任务的,首先要进行机器人路径规划,还要再接着进行运动规划。这很大程度上依赖工程师的经验水平,并且会随着工作量的增多而变得难以操作。

    技术实现要素:

    针对上述技术问题,本发明提供一种基于遗传算法和五次多项式插值的机器人路径规划方法,通过数学模型与计算机运算的结合,使得路径规划与运动规划快速到位,从而提高机器人轨迹规划效率,缩短规划步骤与时间。

    为实现上述目的,本发明采用下述技术方案:

    基于遗传算法和五次多项式插值的机器人路径规划方法,根据机器人DH参数建立机器人模型,确认工作任务点,求解关节角,同步使用遗传算法规划机器人任务点的执行顺序以及使用五次多项式插值规划相邻任务点之间关节运动规律,最后直接输出运动最优路径以及各机械臂运动规律图。

    进一步地,使用遗传算法对机器人任务点执行顺序的规划,包括以下步骤:

    步骤1,按照DH参数建立机器人运动学模型;

    步骤2,将机器人任务空间离散化为具体的位姿矩阵Ti,记录笛卡尔空间坐标vi=(xi,yi,zi);

    步骤3,按机器人逆解公式求得各位姿矩阵Ti对应的关节角θi;

    步骤4,对任务点进行自然数序列编码1-n,计算任意两任务点之间的距离,该距离矩阵如下:

    步骤5,拟定遍历所有任务点之间的距离之和为评价函数L,如下:

    其中,s为任务点编码顺序;

    步骤6,使用遗传算法优化任务点顺序;

    步骤7,从最终种群中挑选出适应度值最大的个体,记录其基因值作为最优序列S。

    进一步地,步骤6中使用遗传算法优化任务点顺序,包括以下步骤:

    步骤61,初始化种群,随机产生个体数为M的种群,各个体按照进行乱序n全排列,设定总迭代次数C;

    步骤62,计算每一个个体的适应度值;

    Fitness=1/LS (3)

    步骤63,对适应度值进行排序,删除适应度值低的个体,代替适应度高的个体,保持种群规模;

    步骤64,随机选两个个体,任意交换其中两段基因的值,检测重复基因并进行对应修改,直到基因无冲突,保持种群规模;

    步骤65,随机选取部分个体,任意交换其中两个位置的基因值,保持种群规模,同时执行迭代次数C=C-1;

    步骤66,重复执行步骤6,直到达到预定迭代次数C为0。

    进一步地,使用五次多项式插值对相邻任务点之间关节运动规律的规划,包括以下步骤:

    步骤8,建立五次多项式模型,如下:

    θ(t)=a0+a1t+a2t2+a3t3+a4t4+a5t5 (4)

    其中,t为时间,a为多项式系数,θ为关节角向量,t0和tf为关节插值的首末时间点;

    步骤9,根据步骤7中所得优化序列S,顺次取得S序列中i号和i+1(i≧1)号任务点对应的关节坐标向量,作为一组关节插值的节点;

    步骤10,根据相关型号的六自由度机器人关节运动参数要求,设置包括角速度及角加速度的约束条件,使用Matlab软件计算出各关节角插值后的角度,同时执行i=i+1;

    步骤11,重复执行步骤3直至插值完毕S序列中最后两个任务点元素,生成整个序列的所有关节角运动规律图。

    有益效果:

    本发明根据机器人DH参数建立数学模型;将机器人工作任务点的位姿矩阵Ti离散出来;对位姿矩阵Ti进行逆解求得对应的qi;通过遗传算法优化任务点的作业顺序;通过五次多项式插值优化相邻点运动规律,得到运动规律曲线图;因此,本发明可以帮助工程师快速规划机器人工作顺序以及运动规律,延长设备寿命,节约工作调试时间。

    附图说明

    图1是本发明的流程图;

    图2是本发明一实施例的的机器人空间任务点示意图;

    图3是本发明一实施例的的遗传算法规划的机器人空间路径图;

    图4是本发明一实施例的的遗传算法收敛图;

    图5是本发明一实施例的机器人空间一段位移图;

    图6是本发明一实施例的机器人空间二段位移图;

    图7是本发明一实施例的机器人空间一段角速度图;

    图8是本发明一实施例的机器人空间二段角速度图;

    图9是本发明一实施例的机器人空间一段角加速度图;

    图10是本发明一实施例的机器人空间二段角加速度图。

    具体实施方式

    下面结合附图和实施例对本发明进一步说明。

    本实施例提出一种六自由度机器人路径规划方法,如图1所示,本例型号为puma560,DH参数如下表1:

    表1 puma560DH参数

    步骤1,将机器人15个任务空间点离散化,如图2所示,对应具体的位姿矩阵为Ti,Ti的位置向量为vi=(xi,yi,zi),(i=1,2,3…15);

    拟定遍历15个任务空间点之间的距离之和L,其中s为15个任务空间点编码顺序:

    步骤2,产生初始种群M=50,迭代次数C=500,每个个体由15个基因乱序全排列而成,设置交叉概率为0.5,变异概率为0.2。

    步骤3,计算各个体的适应度值,并且按照从大到小的顺序排列,依据“轮盘赌”法则,复制适应度值大的个体到下一代,淘汰适应度值小的个体,保持种群规模。

    Fitness=1/LS (2)

    步骤4,随机选两个个体,任意交换其中两段基因的值,检测重复基因并进行对应修改,直到基因无冲突,保持种群规模。

    步骤5,随机选取部分个体,任意交换其中两个位置的基因值,保持种群规模,同时执行迭代总次数自减1。

    步骤6,重复执行步骤3至步骤5,直至达到总迭代次数为0,如图3、4所示,退出遗传算法寻优程序,得到优化序列S。

    步骤7,按照DH参数对各个Ti进行逆解求得对应的关节角θi。这里取三个位姿点作为代表。通过机器人逆解求得各关节角如下:

    将θP1、θ、P2、θP3的各个关节角值带入五次多项式中,设置角速度0.05rad/s-2,角加速度为0,其中θP2的末值为θP3的初值。

    θ(t)=a0+a1t+a2t2+a3t3+a4t4+a5t5 (3)

    步骤8,重复执行步骤7,直至插值完毕S序列中最后一组关节角,使用Matlab绘制出各关节运动规律曲线图,如图5-10所示。

    对本发明保护范围的限制,所属领域技术人员应该明白,在本发明的技术方案的基础上,本领域技术人员不需要付出创造性劳动即可做出的各种修改或变形仍在本发明的保护范围以内。

    展开全文
  • 探讨了一种改进的基于遗传算法的静态环境下机器人全局路径规划方法的可行性。该方法通过障碍物的数量来动态确定所需的路径点数(基因),使得它能更广泛地应用于不同环境,最后对结果进行修正。仿真实验表明了该方法...
  • //A*算法找寻路径 list path = astar.GetPath(start, end, false); //打印 for (auto &p : path) cout (' << p->x ,' << p->y )' ; system("pause"); return 0; } 测试结果 检验 附:...

    f70c3e8243e55116e0977649fd7d3b3e.png

    A star.h

    首先放完整版代码:

    #include <vector>

    #include <list>

    using namespace std;

    const int kCost1 = 10; //直移一格消耗

    const int kCost2 = 14; //斜移一格消耗

    struct Point

    {

    int x, y; //点坐标,这里为了方便按照C++的数组来计算,x代表横排,y代表竖列

    int F, G, H; //F=G+H

    Point *parent; //parent的坐标,这里没有用指针,从而简化代码

    /*Point(int _x, int _y) :x(_x), y(_y), F(0), G(0), H(0), parent(NULL)

    {

    }*/

    Point(int _x, int _y)//变量初始化

    {

    x = _x;

    y = _y;

    F = 0;

    G = 0;

    H = 0;

    parent = NULL;

    }

    };

    class Astar

    {

    public:

    void InitAstar(vector<vector<int>> &_maze);

    list<Point *> GetPath(Point &startPoint, Point &endPoint, bool isIgnoreCorner);

    private:

    Point *findPath(Point &startPoint, Point &endPoint, bool isIgnoreCorner);

    vector<Point *> getSurroundPoints(const Point *point, bool isIgnoreCorner) const;

    bool isCanreach(const Point *point, const Point *target, bool isIgnoreCorner) const; //判断某点是否可以用于下一步判断

    Point *isInList(const list<Point *> &list, const Point *point) const; //判断开启/关闭列表中是否包含某点

    Point *getLeastFpoint(); //从开启列表中返回F值最小的节点

    //计算FGH值

    int calcG(Point *temp_start, Point *point);

    int calcH(Point *point, Point *end);

    int calcF(Point *point);

    private:

    vector<std::vector<int>> maze;

    list<Point *> openList; //开启列表

    list<Point *> closeList; //关闭列表

    };

    void Astar::InitAstar(std::vector<std::vector<int>> &_maze)

    {

    maze = _maze;

    }

    int Astar::calcG(Point *temp_start, Point *point)

    {

    int extraG = (abs(point->x - temp_start->x) + abs(point->y - temp_start->y)) == 1 ? kCost1 : kCost2;

    int parentG = point->parent == NULL ? 0 : point->parent->G; //如果是初始节点,则其父节点是空

    return parentG + extraG;

    }

    int Astar::calcH(Point *point, Point *end)

    {

    //用简单的欧几里得距离计算H,这个H的计算是关键,还有很多算法,没深入研究^_^

    //return sqrt((double)(end->x - point->x)*(double)(end->x - point->x) + (double)(end->y - point->y)*(double)(end->y - point->y))*kCost1;

    return ((end->x - point->x) + end->y - point->y)*kCost1;

    }

    int Astar::calcF(Point *point)

    {

    return point->G + point->H;

    }

    Point *Astar::getLeastFpoint()

    {

    if (!openList.empty())

    {

    auto resPoint = openList.front();

    for (auto &point : openList)

    if (point->F<resPoint->F)

    resPoint = point;

    return resPoint;

    }

    return NULL;

    }

    Point *Astar::findPath(Point &startPoint, Point &endPoint, bool isIgnoreCorner)

    {

    openList.push_back(new Point(startPoint.x, startPoint.y)); //置入起点,拷贝开辟一个节点,内外隔离

    while (!openList.empty())

    {

    auto curPoint = getLeastFpoint(); //找到F值最小的点

    openList.remove(curPoint); //从开启列表中删除

    closeList.push_back(curPoint); //放到关闭列表

    //1,找到当前周围八个格中可以通过的格子

    auto surroundPoints = getSurroundPoints(curPoint, isIgnoreCorner);

    for (auto &target : surroundPoints)

    {

    //2,对某一个格子,如果它不在开启列表中,加入到开启列表,设置当前格为其父节点,计算F G H

    if (!isInList(openList, target))

    {

    target->parent = curPoint;

    target->G = calcG(curPoint, target);

    target->H = calcH(target, &endPoint);

    target->F = calcF(target);

    openList.push_back(target);

    }

    //3,对某一个格子,它在开启列表中,计算G值, 如果比原来的大, 就什么都不做, 否则设置它的父节点为当前点,并更新G和F

    else

    {

    int tempG = calcG(curPoint, target);

    if (tempG<target->G)

    {

    target->parent = curPoint;

    target->G = tempG;

    target->F = calcF(target);

    }

    }

    Point *resPoint = isInList(openList, &endPoint);

    if (resPoint)

    return resPoint; //返回列表里的节点指针,不要用原来传入的endpoint指针,因为发生了深拷贝

    }

    }

    return NULL;

    }

    std::list<Point *> Astar::GetPath(Point &startPoint, Point &endPoint, bool isIgnoreCorner)

    {

    Point *result = findPath(startPoint, endPoint, isIgnoreCorner);

    list<Point *> path;

    //返回路径,如果没找到路径,返回空链表

    while (result)

    {

    path.push_front(result);

    result = result->parent;

    }

    // 清空临时开闭列表,防止重复执行GetPath导致结果异常

    openList.clear();

    closeList.clear();

    return path;

    }

    Point *Astar::isInList(const std::list<Point *> &list, const Point *point) const

    {

    //判断某个节点是否在列表中,这里不能比较指针,因为每次加入列表是新开辟的节点,只能比较坐标

    for (auto p : list)

    if (p->x == point->x&&p->y == point->y)

    return p;

    return NULL;

    }

    bool Astar::isCanreach(const Point *point, const Point *target, bool isIgnoreCorner) const

    {

    if (target->x<0 || target->x>maze.size() - 1

    || target->y<0 || target->y>maze[0].size() - 1

    || maze[target->x][target->y] == 1

    || target->x == point->x&&target->y == point->y

    || isInList(closeList, target)) //如果点与当前节点重合、超出地图、是障碍物、或者在关闭列表中,返回false

    return false;

    else

    {

    if (abs(point->x - target->x) + abs(point->y - target->y) == 1) //非斜角可以

    return true;

    else

    {

    //斜对角要判断是否绊住

    if (maze[point->x][target->y] == 0 && maze[target->x][point->y] == 0)

    return true;

    else

    return isIgnoreCorner;

    }

    }

    }

    vector<Point *> Astar::getSurroundPoints(const Point *point, bool isIgnoreCorner) const

    {

    vector<Point *> surroundPoints;

    for (int x = point->x - 1; x <= point->x + 1; x++)

    for (int y = point->y - 1; y <= point->y + 1; y++)

    if (isCanreach(point, new Point(x, y), isIgnoreCorner))

    surroundPoints.push_back(new Point(x, y));

    return surroundPoints;

    }

    测试 main.cpp

    #include <math.h>

    #include<iostream>

    #include "A star .h"

    using namespace std;

    int main()

    {

    //初始化地图,用二维矩阵代表地图,1表示障碍物,0表示可通

    vector<vector<int>> maze = {

    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },

    { 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1 },

    { 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1 },

    { 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1 },

    { 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1 },

    { 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1 },

    { 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1 },

    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    };

    Astar astar;

    astar.InitAstar(maze);

    //设置起始和结束点

    Point start(1, 1);

    Point end(6, 10);

    //A*算法找寻路径

    list<Point *> path = astar.GetPath(start, end, false);

    //打印

    for (auto &p : path)

    cout << '(' << p->x << ',' << p->y << ')' << endl;

    system("pause");

    return 0;

    }

    测试结果

    16e514ad43b480d37cc5121f082d6bc4.png

    检验

    4b32eb3e1d04c0266bcf770aa985c3e3.png

    aad8e81bd81ed5ec4a60cea2e4f79745.png

    附:

    http://qiao.github.io/PathFinding.js/visualqiao.github.io

    讲解

    首先定义一个结构体:

    e090f47f88aad2632dbca325d86efe80.png

    这个结构体就表示一个栅格,其中包括坐标(x,y),每一个栅格都有的FGH,G表示从起点到当前节点的路程,H表示当前节点到终点的预估。还包括父节点,也是Point类型的。在结构体里面对其初始化。

    接下来定义一个类:

    7bae88119b1394d674db52f4cad9b090.png

    类中声明了10种函数,以及3个变量,意义见注释。

    第一种函数InitAstar:

    13a0d84fdbd0e1b49f3f218ea4471cff.png

    这个函数把地形矩阵传给Astar类中的maze二维向量,用于导航。

    第二种函数用来计算从temp_start作为父节点这条路走过来的G值:

    03c381bf07666bbb7d4b920e44957c8e.png

    第三种函数计算H,这里我用的是曼哈顿距离,也可以用欧式距离:

    90e09624ea4a83be10a791eb6c60cd9c.png

    第四种计算节点的F:

    9bedba37c2e7f6df4a5a4cc09dffa1b3.png

    接下来的这个函数用于搜索openlist中F值最小的节点:

    b06a689ec2cc8bfd13be638f1131110f.png

    第六种函数用来判断某一个节点是否处于openlist或者closelist中,返会list中的这个重复的节点,没有重复的就返回空节点:

    7d338a87d4d12bebb2ffb042ee8261a0.png

    第七种函数用来看目标节点是否可以作为下一个搜索的中心点:

    cca6e287e908e5e4ca550b8d88b648bc.png

    首先,目标节点若是不在地图中,或是目标节点是一个障碍物,或是目标点与当前节点重合,亦或是目标点已经在close链表中(考察过了),都表示这个点不在考察范围内。非上述情况,看目标点与当前点是否是斜角,如果不是,是否考虑corner都可以考察。这里说一下考虑corner的意义,如果考虑corner,那么斜着走时候两边不能有障碍物。如果两边都是0(没有障碍物),那么就可以考察,否则就看是否考虑corner,考虑就不能走这条路。

    第八种函数用来把周围可选的点提取出来:

    c72a42f0a086a60614a33341212c912e.png

    原理很简单:遍历周围8个周围点加上自身,把可考察的点放入一个向量中返回。

    接下来就进行寻路函数:

    b2da1064aac70cc305a9540c1b548205.png

    流程就是:先把起点放入openlist中,然后每次在open list中找最小F值,把它从openlist拿到closelist中,表示这个节点已经考察过了,然后对这个点周围的点进行考察,不在openlist,就先计算FGH值后加进去;如果已经在了,就更新FGH,更新父节点。一直更新下去,直到终点出现在openlist中就找到了。这时返回找到的点,否则返回空节点。

    接下来把找到的路径存在一个链表中:

    f19a9975f0a9b160175877717b712cfc.png

    从终点开始,每次把它的父节点插入链表头,直到父节点为空,这样我们就得到了路径坐标。

    展开全文
  • 本文为大家分享了Python遗传算法解决最大流问题,供大家参考,具体内容如下Generate_matrixdef Generate_matrix(x,y):import numpy as npimport randomreturn np.ceil(np.array([random.random()*10 for i in range...

    本文为大家分享了Python遗传算法解决最大流问题,供大家参考,具体内容如下

    Generate_matrix

    def Generate_matrix(x,y):

    import numpy as np

    import random

    return np.ceil(np.array([random.random()*10 for i in range(x*y)]).reshape(x,y))

    Max_road

    def Max_road(A,degree,start):

    import random

    import numpy as np

    import copy

    def change(M,number,start): # number 控制变异程度 start 控制变异量

    x , y = M.shape

    for i in range(start,x):

    Line = zip(range(len(M[i])),M[i])

    index_0 = [t[0] for t in Line if t[1]==0] # 获取 0 所对应的下标

    index_1 = [t[0] for t in Line if t[1]==1] # 获取 1 所对应的下标

    M[i][random.sample(index_0,number)[0]]=1 # 随机改变序列中 number 个值 0->1

    M[i][random.sample(index_1,number)[0]]=0 # 随机改变序列中 number 个值 1->0

    return M

    x,y = A.shape

    n=x

    generation = y

    #初始化一个有 n 中情况的解决方案矩阵

    init_solve = np.zeros([n,x+y-2])

    init=[1]*(x-1)+[0]*(y-1)

    for i in range(n) :

    random.shuffle(init)

    init_solve[i,:] = init # 1 表示向下走 0 表示向右走

    solve = copy.copy(init_solve)

    for loop in range(generation):

    Sum = [A[0,0]]*n # 用于记录每一种方案的总流量

    for i in range(n):

    j=0;k=0;

    for m in solve[i,:]:

    if m==1:

    k=k+1

    else:

    j=j+1

    Sum[i] = Sum[i] + A[k,j]

    Sum_index = zip(range(len(Sum)),Sum)

    sort_sum_index = sorted(Sum_index,key = lambda d : d[1] , reverse =True) # 将 方案 按照流量总和排序

    Max = sort_sum_index[0][1] # 最大流量

    #print Max

    solve_index_half = [a[0] for a in sort_sum_index[:n/2]] # 保留排序后方案的一半

    solve = np.concatenate([solve[solve_index_half],solve[solve_index_half]]) # 将保留的一半方案 进行复制 ,复制部分用于变异

    change(solve,int((x+y-2)*degree)+1 ,start) # 变异

    return solve[0] , Max

    Draw_road

    def Draw_road(road,A):

    import pylab as plt

    import seaborn

    seaborn.set()

    x , y =A.shape

    # 将下移和右移映射到绘图坐标上

    Road = [(1,x)] # 初始坐标

    j=1;k=x;

    for m in road:

    if m==1:

    k=k-1

    else:

    j=j+1

    Road.append((j,k))

    # print Road

    for i in range(len(road)):

    plt.plot([Road[i][0],Road[i+1][0]],[Road[i][1],Road[i+1][1]])

    实际运行的例子

    In [119]: A = Generate_matrix(4,6)

    In [120]: A

    Out[120]:

    array([[ 10., 1., 7., 10., 8., 8.],

    [ 4., 8., 8., 4., 8., 2.],

    [ 9., 8., 8., 3., 9., 8.],

    [ 7., 2., 5., 9., 3., 8.]])

    In [121]: road , M=Max_road(A,0.1,2)

    In [122]: Draw_road(road,A)

    22d736d7c730cef946a42831f3a73a6d.png

    较大规模的情况

    In [105]: A = Generate_matrix(40,60)

    In [106]: road , M=Max_road(A,0.1,4)

    In [107]: road

    Out[107]:

    array([ 0., 0., 0., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0.,

    1., 0., 0., 0., 1., 0., 0., 1., 0., 1., 1., 1., 1.,

    1., 0., 0., 0., 0., 0., 1., 0., 0., 1., 0., 0., 0.,

    1., 0., 0., 0., 1., 0., 1., 0., 0., 1., 0., 0., 1.,

    0., 0., 0., 1., 0., 0., 1., 1., 1., 1., 0., 0., 0.,

    0., 0., 0., 1., 0., 1., 1., 1., 1., 0., 1., 0., 1.,

    1., 1., 0., 1., 0., 1., 0., 1., 0., 1., 0., 0., 1.,

    0., 1., 0., 0., 1., 0., 1.])

    In [108]: Draw_road(road,A)

    e74c7127857de697f9fddb76c4433edb.png

    In [109]: A = generate_Matrix(100,200)

    In [110]: road , M=Max_road(A,0.1,10)

    In [111]: draw_road(road,A)

    31d64b9edb8a186f1a7e4d12fdab184d.png

    以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。

    展开全文
  • 第一篇文章,记录学习的过程~``` python#产生自然数列表a=range(5) #这样是错误的a=list(range(5)) #正确的是这样的,加一个list#产生数值全部为0的一维数组,与matlab中类似from numpy import *in:b=zeros(5) #产生...
  • fit =[]31 32 #路径 33 paths =[]34 #最优路径 35 #迭代次数 36 ITERATION_COUNT = 100 37 #38 direction_arr = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]39 40 41 defis_valid...
  • 1.学习理解机器人路径规划算法,重点研究遗传算法和蚁群算法。 2.对典型的二维场景采用栅格法进行matlab建模。 3.用matlab对遗传算法,蚁群算法仿真,比较不同算法的优缺点,确定有效的路径规划求解算法。 所以就...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 398
精华内容 159
关键字:

遗传算法路径规划