当前位置:首页 » 《随便一记》 » 正文

遗传算法解决tsp问题(基于python)

15 人参与  2023年05月05日 10:04  分类 : 《随便一记》  评论

点击全文阅读


目录

1.遗传算法简要介绍

2.tsp问题简要介绍

3.遗传算法解决tsp问题的几个特殊点

4.源码

1.遗传算法简要介绍

        简单来说,遗传算法是用于解决最优化问题的一种搜索算法。其核心基于自然界种群进化的规律,即初始种群进行交配,在基因层面上,其中会发生交叉互换、基因突变等变异,产生新一批的种群,在种群不断繁衍的过程中,“适者生存,不适者灭亡”,更符合环境要求的个体的基因保留下来的可能性更大,不适应环境的个体的基因往往不会延续下去。漫长的时间后,会筛选出一批最适应环境的种群。

        基于此,当我们在解决最优化问题时,采取上述思想,将问题的解看作是“个体”,这些个体组成一个抽象的“种群”,这些解被映射成为相应的编码,于是我们就能得到由各种编码组成的“种群”。这些编码可以进行片段的交叉互换,或者其中某些数字发生“基因突变”,从而进行种群的更新。那么如何筛选更合适的个体呢?根据实际的需要与限制,我们基于编码,通过特定的函数,计算出每个个体的“适应度”,适应度更大的个体的基因(编码)被选中并保留下来的概率更大。这样经过上百次迭代后,就能得到一个接近最优解的一个种群。

        详细的介绍大家可以参照这篇文章遗传算法详解 附python代码实现_重学CS的博客-CSDN博客_python遗传算法 ,文章作者将一般公式的最优化讲解到令人发指的详细与通俗易懂。如果能将这篇文章掌握,基本上可以通过遗传算法,求任何公式(n元n次方程)的最值。其中的内涵是将解从十进制数字映射成为二进制串,这其中的编码与解码过程很重要。

        在这里就不展开叙述更多细节了,上面那篇文章讲的很清楚,本篇重点在于解决tsp问题。

2.tsp问题简要介绍

        根据百度百科的介绍,t旅行商问题,即TSP问题(Traveling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

3.遗传算法解决tsp问题的几个特殊点

这也是本篇的重点

3.1如何编码

首先要明白我们解的形式是什么,我们需要得到一条距离最短的路径。因此将这些城市编码(0、1、2........n),以10座城市为例,我们希望得到的解或许是3 5 4 8 6 7 9 0 2 1,因此,在遗传算法中,每个个体的形式就应该是10个不重复数字的排列。好消息是这样一来不需要进行二进制编码解码了。

 #初始化种群def generate_population(self):    path=np.array(range(self.num))    self.pop=[]    for i in range(self.size_pop):        x=path.copy()        np.random.shuffle(x)    #随机洗牌        self.pop.append(x)

3.2距离矩阵的建立

我们该如何评价一个解的适应度?显然我们希望每个个体的路径距离越小越好,所以我们需要先得到每座城市之间的距离,将其记录在一个矩阵当中,当后续需要求一条完整路径的距离时,任意两点的距离可以直接转化为坐标(比如说,(2,6))从这个矩阵中取出。

3.3交叉互换

如果直接确定一条染色体上的一个位置,将父本母本从这个位置开始直接交叉互换,这显然是不合理的,假如父本是 1 3 2 4,母本是 2 4 1 3,两者正好在中点切割进行交叉互换后的子代分别是1 3 1 3和 2 4 2 4,这显然是错误的!旅行商每座城市只能经过一次!所以在交换染色体片段的时候,必须要经过一个操作,就是去除重复碱基对。

TSP、MTSP问题遗传算法详细解读及python实现,这篇文章的博主给出了tsp问题遗传算法交叉互换的三种方式,这里我们选择第二种​

Order Crossover(顺序交叉)

​ 

3.4基因突变

在二进制编码的情况下,要想完成基因突变,只需要将选中的染色体随机替换掉一个碱基对即可。但是在tsp问题中,如果这样做,一定会导致被选中染色体碱基对的重复!因此我们需要做的是将被选中染色体的任意两碱基对进行互换,这样就避免了重复

3.5适应度计算

我们该如何评价一个个体的基因是否适合被遗传下来呢?这就需要计算个体的适应度,适应度越高的个体,被选择的概率就越大。在tsp问题中,我们希望一个个体的路径长度越短越好,即路径越短,适应度越大,在这里,采用文章基于遗传算法求解TSP问题(旅游路径规划,Python实现,超详细,可视化,结果分析中的适应度公式来计算适应度

fitness=\frac{1}{distance^{15}}
 

 适应度越大的个体被选中的可能性越大,用numpy.choice来实现

idx = np.random.choice(np.arange(self.size_pop), size=self.size_pop, replace=True,                       p=(self.fitness)/(fitness_sum) )

4.源码

import numpy as npclass TSP:    def __init__(self, citys, maxgen=500,                 size_pop=200, cross_rate=0.8,                 muta_rate=0.005                 ):        self.maxgen = maxgen            # 最大进化次数        self.size_pop = size_pop        # 种群大小(染色体个数)        self.cross_rate = cross_rate    # 交叉概率        self.muta_rate = muta_rate    # 变异概率        self.citys = citys       # 城市的坐标数据        self.num = citys.shape[0]    # 城市的个数(染色体长度)          #获得距离矩阵    def matrix_distance(self):        self.distance_m=np.zeros((self.num,self.num))        for i in range(self.num):            for j in range(self.num):                self.distance_m[i][j]=np.sqrt((self.citys[i][0]-self.citys[j][0])**2+(self.citys[i][1]-self.citys[j][1])**2)     #计算某条路径的距离    def get_total_distance(self,one_path):        distance=0        for i in range(self.num-1):            distance +=self.distance_m[one_path[i]][one_path[i+1]]        distance += self.distance_m[one_path[-1]][one_path[0]]        return distance     #初始化种群    def generate_population(self):        path=np.array(range(self.num))        self.pop=[]        for i in range(self.size_pop):            x=path.copy()            np.random.shuffle(x)    #随机洗牌            self.pop.append(x)            #交叉互换    def crossover(self):        self.new_pop=[]        for father in self.pop:            child=father   #初步让子代获得父本染色体            if np.random.rand()<self.cross_rate:                #随机选择一个染色体作为母本                mother_index = np.random.randint(0, self.size_pop)                mother=self.pop[mother_index]                  #确定切割点                     left = np.random.randint(0, self.num-2)                right = np.random.randint(left + 1, self.num-1)                mother=mother.tolist()                father=father.tolist()                #切割片段                gene = mother[left:right]                child1_c = father[right:]+father[:right]                child1 = child1_c.copy()                #去除重复基因                for o in gene:                    child1_c.remove(o)                child1[left:right] = gene                child1[right:] = child1_c[0:len(child1) - right]                child1[:left] = child1_c[(len(child1) - right):]                child=np.array(child1)             self.new_pop.append(child)        self.pop=self.new_pop    #变异    def mutation(self):        for i in range(self.size_pop):            if np.random.rand() < self.muta_rate:                child = self.pop[i]                u = np.random.randint(0,self.num - 2)                v = np.random.randint(u+1,self.num- 1)                child_x = child[u+1:v]                child_x=child_x[::-1]                        child = np.concatenate((child[0:u+1] , child_x , child[v:]))                self.pop[i]=child     #自然选择,种群根据适应度进行更新    def select(self):        #计算每条路径的长度,放入列表        self.dis=[]        for i in range(self.size_pop):            self.dis.append(self.get_total_distance(one_path=self.pop[i]))        #根据路径长度计算每个个体的适应度        self.fitness=[]        for i in range(self.size_pop):            self.fitness.append(1/(self.dis[i]**15))        #适应度总和        fitness_sum=0        for i in range(self.size_pop):            fitness_sum+=self.fitness[i]        #根据适应度进行选择,适应度大的被选择概率大        idx = np.random.choice(np.arange(self.size_pop), size=self.size_pop, replace=True,                           p=(self.fitness)/(fitness_sum) )        self.new_pop=[]        for i in idx:            self.new_pop.append(self.pop[i])        self.pop=self.new_pop             #输出当前种群中最优路径    def result_path(self):        self.index=np.argmax(self.fitness)        a="the shortest path is:"        for i in range(self.num-1):            a+=str(self.pop[self.index][i])            a+="-->"        a+=str(self.pop[self.index][-1])        print(a)        print("the total distance is",self.dis[self.index])        #主函数进行迭代def main(citys):        SL=TSP(citys)    SL.matrix_distance()    SL.generate_population()    for i in range (SL.maxgen):        SL.crossover()        SL.mutation()        SL.select()    SL.result_path()if __name__ == '__main__':    citys = np.array([[16.47, 96.10],[16.47, 94.44], [20.09, 92.54],                     [22.39, 93.37], [25.23, 97.24], [22.00, 96.05], [20.47, 97.02],                     [17.20, 96.29], [16.30, 97.38], [14.05, 98.12], [16.53, 97.38],                     [21.52, 95.59], [19.41, 97.13], [20.09, 92.55]])    main(citys)

结果分析

如果每一次迭代都输出结果,可以清楚地看到路径最终都收敛。事实上,每次收敛的结果与种群大小size_pop息息相关,一开始我将种群大小设置为 200,结果每次运行虽然收敛,但是得到的结果各不相同,基本上毫无关联,说明结果陷入了局部最优解,而非全局最优解。解决方法就是把size_pop设置为500,才使得结果误差较小,趋近于全局最优解。

事实上,要想使结果更直观,最好用坐标图使结果可视化,将路线显示出来。本文仅仅展示了数字结果,这样有两个问题,一是可能起始城市不同,如8 2 3 6 和 2 3 6 8,二是顺序不同,如8 2 3 6和 6 3 2 8,其实结果的路线本质是一样的,但直观看上去不利于结果统计。

参考文章:

http://t.csdn.cn/eJZmK

http://t.csdn.cn/0fYtK

http://t.csdn.cn/VFPLr

http://t.csdn.cn/2oWZt


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/60837.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1