简单说几句

1. 简单说几句，算法的基本逻辑请看其他文章，很多，不介绍。本文旨在提供一份python代码供各位后来学习者多一些资料理解学习GA，同时对于那些只需简单使用GA解决路径规划的人提供一个并不麻烦的途径。
2. 注意，非路径规划，非栅格图模型的，本文代码99.99%无法运行！
3. 考虑到随机生成的初代路径解的效果非常非常不好，难以生成看上去像那么回事儿的路径。因此，本GA的初代解来源基本ACO算法的初代解。
4. 本文所提供GA理论上只要ACO能生成初代解，那就一定能成功运行，无视地图尺寸。当然，效果稳定性不保证。
5. 通常来说，初代解的质量将直接影响GA的迭代速度以及收敛解，因此，本文GA的效果不等价真正的GA算法效果。
6. 本文GA选择算子直接用的竞标赛选择法；交叉算子采用的是单点交叉法，即在两条路径的任一相同交点处断开并交叉；变异算子主要是通过将随机位置的节点进行删除，并判断新路径是否最优，择优保留来实现的。

python代码

0.预安装库

pip install numpy pandas pygame matplotlib   #四个库
pip install lddya==5.0.1     #作者的自用库，里面有一些工具下文会用到

1.调用模版

from lddya.Algorithm.Heuristic import ACO,GA    #导入ACO,GA算法
from lddya.Draw import ShanGeTu,IterationGraph    #导入栅格图、迭代图的绘制模块
from lddya.Map import Map   #导入地图文件读取模块
m = Map()    
m.load_map_file('map.txt')    # 读取地图文件
aco = ACO(map_data=m.data,start=[0,0],end=[19,19],max_iter = 1)    #设置迭代次数为1，以获得ACO生成的初代解
aco.run()                     # ACO迭代运行
ga = GA(map_data=m.data
             ,chroms_list=aco.success_way_list.copy()  #将蚁群算法得到的初代路径赋值给遗传算法的初代
             ,population = 100
             ,max_iter=50
            )                  #实例化一个GA算法
ga.run()                       #GA迭代运行
sfig = ShanGeTu(map_data = m.data)       # 初始化栅格图绘制模块
sfig.draw_way(ga.way_data_best)   # 绘制路径信息，路径数据由ga.way_data_best提供。
sfig.save('123.jpg')                   #保存栅格图数据为'123.jpg'
dfig = IterationGraph(data_list= [ga.generation_aver,ga.generation_best],   #绘制数据: 每代平均、每代最优路径信息
                    style_list=['--r','-.g'],    # 线型 (规则同plt.plot()中的线型规则)
                    legend_list=['每代平均','每代最优'],  # 图例 (可选参数，可以不写)
                    xlabel='迭代次数',           # x轴标签，默认“x”
                    ylabel= '路径长度'           # y轴标签，默认“y”
                    )                 # 初始化迭代图绘制模块        
dfig.save('321.jpg')                     #迭代图保存为321.jpg

2.地图文件

下面为某地图文件内容，数字位置与栅格图的黑白栅格一一对应。

PS: 注意，Map.data本质上是基于numpy的0-1矩阵。

00000000000000000000
00000000000000000000
00000000000000000000
00010010000000000000
00001100011001100000
00010100110000000000
00000000110000000000
00000000000000000000
00010010000010110000
00010010000110110000
00000010000100100000
00100000000000100000
01100111000100000000
01000111111100000000
00000100000110001001
00000000000100001001
00000000011000001101
00001111000000000100
00000100000000000000
00110000001100000000

3.栅格图+迭代图

下图所示的栅格图即为上文的栅格数据文件对应的图，左上角栅格坐标为[0,0]，向下y增大，向右x增大。所以右下角为[19,19]。

下图就是算法的迭代图。

3.GA类

如果你只是想使用GA解决问题，下面的内容就不用看了，效果不好就调参或者改进吧。考虑存在朋友仅想阅读代码，这里我附一下GA的代码供学习参考。

class GA():
    def __init__(self, map_data,chroms_list,population=50, max_iter = 100, cross_pro=0.95, mut_pro=0.15):
        '''
            Function
            --------
            初始化一个基本GA用于解决路径规划。

            Params
            ------
            map_data     : n*n-np.array  -> 尺寸为n*n的地图数据。\n
            chroms_list  : 
            population   : int -> 种群大小，默认为50。\n
            max_iter     : int -> 最大迭代次数，默认为50。\n
            cross_pro    : float -> 交叉概率，默认0.95。\n
            mut_pro      : float -> 变异概率，默认0.15。\n

            Return
            ------
            返回一个用于解决路径规划的GA实例。
            
        '''
        self.map_data = map_data   
        self.population = population   
        self.max_iter = max_iter
        self.cross_pro = cross_pro
        self.mut_pro = mut_pro
        self.chroms_list = chroms_list  # 初代染色体信息库, 初始化由外部提供
        self.child_list = []    #子代染色体信息库
        self.generation_aver = []   #记录每代评估值的平均值的列表
        self.generation_best = []   #记录每代评估值的最优值的列表
        self.global_best_value = 999  #全局已知最优评估值，默认为一个很大的数，999一般够用。
        self.way_data_best = []       #全局已知最优评估值对应的路径信息
        self.temporary = []   #临时变量，用来保存ACO生成的初代路径


    def eval_fun(self,way):
        '''
            Function
            --------
            染色体评估函数。

            Params
            ------
            way : n-list -> 一条包含n个节点信息的路径列表。如: [[0,0],[0,1],[1,2]...]

            Return
            ------
            length   : float -> 路径长度
        '''
        length = 0
        for j1 in range(len(way)-1):
            a1 = abs(way[j1][0]-way[j1+1][0])+abs(way[j1][1]-way[j1+1][1])
            if a1 == 2:
                length += 1.41421
            else:
                length += 1
        return length
    
    def run(self):
        '''
            Function
            --------
            函数运行主流程
        '''
        for i in range(self.max_iter):
            # Step 1：执行种群选择
            self.child_list = self.selection()
            self.evalution()
            # Step 2: 交叉 
            self.cross()
            # Step 3: 变异
            self.mutation()
            # Step 4: 子代并入父代中
            self.chroms_list = self.child_list.copy()
            print('iter ',i,':','平均值:',self.generation_aver[-1],'最优值:',self.generation_best[-1])
    
    def selection(self):
        '''
            Function:
            ---------
                选择算子。选择法则为竞标赛选择法。即每次随机选择3个个体出来竞争，最优秀的那个个体的染色体信息继承到下一代。
            
            Params:
            --------
                None

            Return:
            -------
                child_1:    list-list
                    子代的染色体信息
        '''
        chroms_1 = self.chroms_list.copy()
        child_1 = []
        for i in range(self.population):
            a_1 = []    # 3个选手
            b_1 = []    # 3个选手的成绩
            for j in range(3):
                a_1.append(np.random.randint(0,len(chroms_1)))
            for j in a_1:
                b_1.append(self.eval_fun(chroms_1[j]))
            c_1 = b_1.index(min(b_1))  # 最好的是第几个
            child_1.append(chroms_1[a_1[c_1]])  #最好者进入下一代
        return child_1


    def evalution(self):
        '''
            Function
            --------
            对child_list中的染色体进行评估
        '''
        e = []
        for i in self.child_list:
            e.append(self.eval_fun(i))
        self.generation_aver.append(sum(e)/len(e))
        self.generation_best.append(min(e))
        if min(e)<=self.global_best_value:
            self.global_best_value = min(e)
            k = e.index(min(e))
            self.way_data_best = self.child_list[k]

    def cross(self):
        '''
            Function
            --------
            交叉算子
        '''
        child_1 = []   # 参与交叉的个体
        for i in self.child_list:  #依据交叉概率挑选个体
            if np.random.random()<self.cross_pro:
                child_1.append(i)
        if len(child_1)%2 != 0:    #如果不是双数
            child_1.append(child_1[np.random.randint(0,len(child_1))])  #随机复制一个个体
        for i_1 in range(0,len(child_1),2):
            child_2 = child_1[i_1]       #交叉的第一个个体
            child_3 = child_1[i_1+1]     #交叉的第二个个体
            sames = []     #两条路径中，相同的节点的各自所在位置，放这里，留待后面交叉
            for k,i in enumerate(child_2[1:-1]):          # 找相同节点(除起点与终点)
                if i in child_3:
                    sames.append([k+1,child_3.index(i)])   # [index in child_2, index in child_3  ]
            if len(sames) != 0:
                a_1 = np.random.randint(0,len(sames))
                cut_1 = sames[a_1][0]
                cut_2 = sames[a_1][1]
                child_1[i_1] = child_2[:cut_1]+child_3[cut_2:]            #新的覆盖原染色体信息
                child_1[i_1+1] = child_3[:cut_2]+child_2[cut_1:]
        for i in child_1:                     #交叉后的染色体个体加入子代群集中
            self.child_list.append(i)

    def mutation(self):        
        '''
            Function
            --------
            变异算子
        '''
        child_1 = []   # 参与变异的个体
        for i in self.child_list:  #依据变异概率挑选个体
            if np.random.random()<self.mut_pro:
                child_1.append(i)
        for i in range(0,len(child_1)):
            child_2 = np.array(child_1[i])
            index = np.random.randint(low=1,high=len(child_2)-1)    #随机选择一个中间节点
            point_a,point_b,point_c = child_2[index-1:index+1+1]
            v1 = point_b-point_a
            v2 = point_c-point_b
            dot_product = np.dot(v1, v2)  #计算这两个向量的内积
            if dot_product <0 :          #如果两个向量之间的夹角为锐角，则必产生冗余
                del child_1[i][index]    #删除被选中的节点
            elif dot_product == 0:       #如果两个向量之间的夹角为直角，则需要进一步判断
                if 0 in v1:               #如果第一个向量是水平或者垂直的,则必存在冗余
                    del child_1[i][index]    #删除被选中的节点
                elif self.map_data[(point_a[0]+point_c[0])//2,(point_a[1]+point_c[1])//2]==0:                     #如果第一个向量是对角的,且point_a与point_b之间的节点为可通行，则可优化
                    child_1[i][index]  = [(point_a[0]+point_c[0])//2,(point_a[1]+point_c[1])//2]  #修改被选中的节点为中间节点

        for i in child_1:                     #交叉后的染色体个体加入子代群集中
            self.child_list.append(i)

最后，祝后来诸君学习顺利！