小程序开发定制人工智能 - 遗传算法解决TSP(旅行商问题) Python实现

小程序开发定制写在最前面

        小程序开发定制小程序开发定制小程序开发定制代码非原创！, 代码非原创！, 代码非原创！

小程序开发定制代码主体部分来自于B站up小程序开发定制主且有视频讲解，小程序开发定制我在阅读之后觉得up写得不错，小程序开发定制并在原代码的基础上用Echarts小程序开发定制完善了最后小程序开发定制数据可视化的部分。小程序开发定制以下是我对该算法做的图文 + 注释导读，小程序开发定制希望对看完视频还有不小程序开发定制理解的同学有所帮助。

        小程序开发定制附上原视频 ：

        源代码的GitHub地址:

      小程序开发定制为了更好的阅读，建议先去GitHub仓库clone源代码！！！ 

一.小程序开发定制数据结构分析

       为了更好的理解源代码，需对代码中使用到的两个类【individual】和【Ga】有一定的了解

1.individual类

        源码如下:

  1. class Individual:
  2.     def __init__(self, genes=None):
  3.         # 随机生成序列
  4.         if genes is None:
  5.             genes = [i for i in range(gene_len)]
  6.             random.shuffle(genes)
  7.         self.genes = genes
  8.         self.fitness = self.evaluate_fitness()
  9.  
  10.     # 适应度即以当前序列走完一个闭合曲线的路径之和
  11.     def evaluate_fitness(self):
  12.         # 计算个体适应度
  13.         fitness = 0.0
  14.         for i in range(gene_len - 1):
  15.             # 起始城市和目标城市
  16.             from_idx = self.genes[i]
  17.             to_idx = self.genes[i + 1]
  18.             fitness += city_dist_mat[from_idx, to_idx]
  19.         # 连接首尾【最后一个城市->起点城市】
  20.         fitness += city_dist_mat[self.genes[-1], self.genes[0]]
  21.         return fitness

              导读解析:

individual类：

代表了每一个迭代【Ga】中的【个体】
每个个体拥有如下【属性/特征】
        · 【genes】基因序列: TSP中抽象为一次路线规划
        · 【fitness】适应度 ：TSP中抽象为按路线规划完一次的路径之和
每个个体拥有如下【方法/能力】
        ·【evaluate_fitness】计算适应度: 根据个体的genes计算其适应度

        举例说明:

        

假设现有一个individual，其基因序列【genes】如下:

[2, 5, 9, 0, 8, 14, 4, 7, 11, 13, 12, 1, 3, 6, 10, 2]

其代表从 2号城市出发，依次经过 5号 ， 9号，0 号城市..，最终返回一号城市

附上用Echarts绘制的图片便于理解

该个体的fitness即：按照【genes】序列走往图上一圈后，所有线段的距离之和，

具体到图例就是各连线上的【数值】之和:

fitness = 0.17 + 0.26 + 0.0.7 +0.13 + 0.26 + .... +0.11

2.Ga类

              源码如下:

                类中包含了实现的算法具体实现，将在后文中详解，可先了解其

  1. class Ga:
  2.     def __init__(self, input_):
  3.         global city_dist_mat
  4.         city_dist_mat = input_
  5.         self.best = None  # 每一代的最佳个体
  6.         self.individual_list = []  # 每一代的个体列表
  7.         self.result_list = []  # 每一代对应的解
  8.         self.fitness_list = []  # 每一代对应的适应度
  9.  
  10.     # 进行每代个体之间的交叉  返回生成的新基因list
  11.     def cross(self):
  12.         # 具体实现省略，后文给出
  13.         return new_gen
  14.  
  15.     # 变异 用reverse来模拟变异
  16.     def mutate(self, new_gen):
  17.         # 具体实现省略， 后文给出
  18.         self.individual_list += new_gen
  19.  
  20.     def select(self):
  21.           # 具体实现省略， 后文给出
  22.         self.individual_list = winners
  23.  
  24.     @staticmethod
  25.     def rank(group):
  26.         # 冒泡排序  以fitness为依据
  27.         for i in range(1, len(group)):
  28.             for j in range(0, len(group) - i):
  29.                 if group[j].fitness > group[j + 1].fitness:
  30.                     group[j], group[j + 1] = group[j + 1], group[j]
  31.         return group
  32.  
  33.     def next_gen(self):
  34.         # 交叉
  35.         new_gen = self.cross()
  36.         # 变异
  37.         self.mutate(new_gen)
  38.         # 选择
  39.         # 选择
  40.         self.select()   # 有多种算法 轮盘赌 / 锦标赛
  41.         # 获得这一代留下的individual_list
  42.         for individual in self.individual_list:
  43.             # 遍历比较得到该代最好的individual
  44.             if individual.fitness < self.best.fitness:
  45.                 self.best = individual
  46.  
  47.     def train(self):
  48.         # 初代种群
  49.         self.individual_list = [Individual() for _ in range(individual_num)]
  50.         self.best = self.individual_list[0]
  51.         for i in range(gen_num):
  52.             self.next_gen()
  53.             result = copy_list(self.best.genes)
  54.             result.append(result[0])
  55.             self.result_list.append(result)
  56.             self.fitness_list.append(self.best.fitness)
  57.         return self.result_list, self.fitness_list, self.individual_list

        导读解析:

Ga类

代表了每一次的种群迭代

每个迭代拥有如下【属性/特征】

  • 【best】 每一代筛选出来的最优个体【best】        
    • 最优的判断标准为: 其fitness在该代中最小，即路径之和最短
  • 【individual_list】 个体表 其中存放每次迭代过程中存货的个体[individual]
  • 【result_list】 每一代筛选出来的最优个体【best】的genes序列将保存在该list中
  • 【fitness_list】 每一代筛选出的最优个体【best】的fitness适应度将保存到该list中

每个迭代拥有如下【方法/能力】：

  • 【cross】交叉遗传
  • 【mutate】随机变异
  • 【select】竞争存活
    • 【rank】具体模拟”竞争“的算法
  • 【next_gen】生成下一个迭代
    • 即按一定顺序进行【cross】/【mutate】/【select】
  • 【train】模拟整个遗传算法并生成最后结果
    • 获取最终结果【result_list】+【fitness_list】

二.主要算法实现

        1.cross 交叉遗传

                先放图文解析，便于理解。

                以某一次的交叉遗传为例

               A.打乱individual_List，随机选择两个individual的随机长度的基因序列

                假设此次选取了13号和20号个体【长度为3】，【起始位置为:1】的基因序列进行cross

                 B.错误的Cross

注意:

两个片段直接cross不是简单的交换序列，这样会导致一个individual中存在相同“城市DNA”的问题，如下图所示:

                 C.正确的Cross

正确的Cross:

        两个待交换片段互相提供想要交换的城市DNA编码，然后在各自的DNA序列中进行交换。将原有的individual间的片段交换，转换为individual内片段的交换.

下面以一次实际交换为例进行分析：

        D.算法实现

算法的核心是需要记录序列中每个DNA的位置，可采用字典进行记录，每次swap后动态更新字典，即可实现简单的Cross。

  1.     # 进行每代个体之间的交叉  返回生成的新基因list
  2.     def cross(self):
  3.         new_gen = []
  4.         # 打乱该代的个体列表
  5.         random.shuffle(self.individual_list)
  6.         # 选取相邻的两个个体进行交叉
  7.         for i in range(0, individual_num - 1, 2):
  8.             # 父代基因
  9.             genes1 = copy_list(self.individual_list[i].genes)
  10.             genes2 = copy_list(self.individual_list[i + 1].genes)
  11.             # 随机选择两个父代基因的截断位置进行交叉
  12.             # 交换的长度由index2-index1的长度决定
  13.             # index1需至少留下一个位置给index2 所以其random的取值为 len - 2
  14.             index1 = random.randint(0, gene_len - 2)
  15.             index2 = random.randint(index1, gene_len - 1)
  16.             # 得到parent基因的原序列字典
  17.             pos1_recorder = {value: idx for idx, value in enumerate(genes1)}
  18.             pos2_recorder = {value: idx for idx, value in enumerate(genes2)}
  19.             # (index1, index2 即为选出的待交换的片段)
  20.             for j in range(index1, index2):
  21.                 # 取出parent基因j位置的值
  22.                 value1, value2 = genes1[j], genes2[j]
  23.                 # pos1查找母序列j位置的值在父序列的原位置
  24.                 # pos2查找父序列j位置的值在母序列的原位置
  25.                 pos1, pos2 = pos1_recorder[value2], pos2_recorder[value1]
  26.                 # 根据pos和j交换单个序列模拟cross
  27.                 genes1[j], genes1[pos1] = genes1[pos1], genes1[j]
  28.                 genes2[j], genes2[pos2] = genes2[pos2], genes2[j]
  29.                 # 更新插入数据字典
  30.                 pos1_recorder[value1], pos1_recorder[value2] = pos1, j
  31.                 pos2_recorder[value1], pos2_recorder[value2] = j, pos2
  32.             # 将生成的新基因append到list中
  33.             new_gen.append(Individual(genes1))
  34.             new_gen.append(Individual(genes2))
  35.         return new_gen

        2.mutate 随机变异

变异的方法有很多种，源程序中选取的是【反转reverse基因片段】

即随机选取一定长度的基因片段，将该片段反转后替换原片段。

用下图举一个简单的例子:

源代码:

  1.     # 变异 用reverse来模拟变异
  2.     def mutate(self, new_gen):
  3.         # 从cross得到的新基因序列中遍历个体
  4.         for individual in new_gen:
  5.             # 根据生成的随机数与【变异概率相比较】
  6.             if random.random() < mutate_prob:
  7.                 # 翻转切片
  8.                 old_genes = copy_list(individual.genes)
  9.                 # 随机选取进行mutate的基因片段
  10.                 index1 = random.randint(0, gene_len - 2)
  11.                 index2 = random.randint(index1, gene_len - 1)
  12.                 # 截取基因片段
  13.                 genes_mutate = old_genes[index1:index2]
  14.                 # reverse基因片段
  15.                 genes_mutate.reverse()
  16.                 # 更新mutate后的individual的genes
  17.                 individual.genes = old_genes[:index1] + genes_mutate + old_genes[index2:]
  18.         # 两代合并
  19.         self.individual_list += new_gen

        3.select 竞争

竞争的目的是筛选出每代保留下的个体，即生成新的individual_list。筛选的方法依据遗传算法的知识可知，有多种可以选择，例如：轮盘赌算法，锦标赛算法。

本次采用锦标赛算法，具体逻辑在这里就不多赘述了。直接贴上源码

  1.     def select(self):
  2.         # 锦标赛算法筛选此次迭代最终留下的individual
  3.         group_num = 10  # 小组数
  4.         group_size = 10  # 每小组人数
  5.         group_winner = individual_num // group_num  # 每小组筛选出的individual【获胜者】
  6.         winners = []  # 锦标赛结果
  7.         for i in range(group_num):
  8.             group = []
  9.             for j in range(group_size):
  10.                 # 随机组成小组
  11.                 player = random.choice(self.individual_list)    # 随机选择参赛者
  12.                 player = Individual(player.genes)   # 抽取参赛者的基因序列
  13.                 group.append(player)
  14.             group = Ga.rank(group)  # 对本次锦标赛获胜者按适应度排序
  15.             # 取出获胜者
  16.             winners += group[:group_winner]
  17.         self.individual_list = winners
  18.  
  19.     @staticmethod
  20.     def rank(group):
  21.         # 冒泡排序  以fitness为依据
  22.         for i in range(1, len(group)):
  23.             for j in range(0, len(group) - i):
  24.                 if group[j].fitness > group[j + 1].fitness:
  25.                     group[j], group[j + 1] = group[j + 1], group[j]
  26.         return group

        4.next_gen 迭代

迭代的函数的作用: 将前面介绍的【cross】+【mutate】+【select】按一定的顺序执行，达到模拟一次遗传算法的过程，以一个流程图该函数的执行顺序.

        A.流程图

        B.源代码

  1.     def next_gen(self):
  2.         # 交叉
  3.         new_gen = self.cross()
  4.         # 变异
  5.         self.mutate(new_gen)
  6.         # 选择
  7.         # 选择
  8.         self.select()   # 有多种算法 轮盘赌 / 锦标赛
  9.         # 获得这一代留下的individual_list
  10.         for individual in self.individual_list:
  11.             # 遍历比较得到该代最好的individual
  12.             if individual.fitness < self.best.fitness:
  13.                 self.best = individual

三.数据可视化

遗传算法执行完后，将得到【result_list】和【fitness_list】两个list，其内容分别为:

·【result_list】:每次迭代过程中保存的最优秀个体【best_genes】的集合，共40个

·【fitness_list】：【result_list】中每个【best_genes】对应的fitness集合，共40个

因此，现在要做的是将【result_list】中的最后一个元素取出作为【result】,因为该list中的最后一元素即最后一次迭代过程中【best_genes】，将其基因序列按坐标形式绘制并依次连接相邻两点，最终将得到路线图，我在up主源代码的基础上稍做了一些变动，既有Python原生实现的方法，也有Vue + Echarts实现的方案。

1.Python实现可视化

基于Python的matplotlib.pyplot库实现，使用前请先自行安装。

每次运行后，生成的图片将自动保存到【项目文件夹下】

只给出绘图部分的代码，替换github代码仓库中main.py中相对应的部分即可

  1. # 绘图
  2. # 解决中文显示问题
  3. plt.rcParams['font.sans-serif'] = ['KaiTi']  # 指定默认字体
  4. plt.rcParams['axes.unicode_minus'] = False  # 解决保存图像是负号'-'显示为方块的问题
  5.  
  6. # 根据结果绘图
  7. fig = plt.figure()
  8. x = result_pos_list[:, 0].copy().tolist()
  9. y = result_pos_list[:, 1].copy().tolist()
  10. np.savetxt("data.txt",result_pos_list)
  11. # print("x轴", x)
  12. # print("y轴", y)
  13. # [:, 0]表示将二维数组的第一个下标全部取出并保存为一维数组 这里对应每个初始X轴的坐标
  14. plt.plot(x, y, 'o-r',label="路线")
  15. for a, b in zip(x, y):  # 添加这个循环显示坐标
  16.     a = round(a, 3)
  17.     b = round(b, 3)
  18.     plt.text(a, b, (a, b), ha='center', va='bottom', fontsize=10)
  19. plt.title(u"路线")
  20. plt.legend()
  21. fig.show()
  22. plt.savefig("./route.png")
  23. plt.clf()
  24. fig = plt.figure()
  25. plt.plot(fitness_list,  label="适应度")
  26. plt.title(u"适应度曲线")
  27. plt.legend()
  28. plt.savefig("./fitness.png")

实现效果:

观察绘制结果可发现：根据图片不能确定哪一个是起点，也不知道两城市之间的路径长度，若你认为这个图片已经能满足你的需求，则不需要再阅读接下来的部分。 

2.Vue2 + Echarts实现可视化

Echarts是一个不错的可视化工具，若有Vue基础的同学可自行尝试以下代码。

实现思路:

        【前提】本次实验数据已被保存到了项目文件夹下的data.txt中

         使用input框读取data.txt文件

        对读取的数据内容进行处理，使其满足绘制Echarts图的要求

        导入Echarts包，调用API完成绘图。

        A.tempalte部分

  1. <div class="container">
  2.     <input type="file" @change="getFile">
  3.     <button @click="handleData">切片</button>
  4.     <button @click="renderChart">绘图</button>
  5.     <div class="echarts" ref="myChart" id="myChart"></div>
  6. </div>

        B.script部分

  1. <script>
  2. export default {
  3.   data() {
  4.     return {
  5.       readData: '',
  6.       routeX: [],
  7.       routeY: [],
  8.       routeData: [],
  9.       routeLineData: [],
  10.     },
  11.      methods: {
  12.     getFile(e) {
  13.       const that = this
  14.       console.log("选择的文件", e.target.files[0])
  15.       const fs = new FileReader()
  16.       fs.readAsText(e.target.files[0])
  17.       fs.onload = function (e) {
  18.         that.readData = this.result
  19.       }
  20.     },
  21.     handleData() {
  22.       const rawRes = this.readData.split('\r')
  23.       rawRes.forEach((item, index) => {
  24.         // console.log("x轴", item.split(' ')[0])
  25.         // console.log("y轴",item.split(' ')[1])
  26.         this.routeX.push(Number(item.split(' ')[0]) )
  27.         this.routeY.push(Number(item.split(' ')[1]) )
  28.         var nodeName = ''
  29.         if (index === 15) {
  30.           nodeName = "起点"
  31.         }
  32.         else {
  33.           if(index !==0)
  34.             nodeName = "城市" + (index + 1).toString()
  35.         }
  36.         var newArr = [Number(item.split(' ')[0] ) , Number(item.split(' ')[1] ), nodeName]
  37.         this.routeData.push(newArr)
  38.       })
  39.       this.routeData.forEach((item, index) => {
  40.         var newLineArr = []
  41.         if (index != this.routeData.length - 1) {
  42.           const distance = Math.sqrt(Math.pow(this.routeX[index]- this.routeX[index+1],2) + Math.pow(this.routeY[index] - this.routeY[index+1],2)).toFixed(2) 
  43.           newLineArr = [
  44.             {
  45.               coord: [this.routeX[index], this.routeY[index]],
  46.               
  47.               label: {
  48.                 show: true,
  49.                 distance:0,
  50.                 formatter: function (params) {
  51.                   return `${distance}`
  52.                 },
  53.                 position: "insideMiddleBottom",
  54.                 fontSize:8
  55.               },
  56.               lineStyle: {
  57.                 width: 1,
  58.                 type: 'solid',
  59.                 color: '#3E3E3E',
  60.               },
  61.             },
  62.             {
  63.               coord: [this.routeX[index + 1], this.routeY[index + 1]],
  64.               lineStyle: {
  65.                 width: 1,
  66.                 type: 'solid',
  67.                 color: '#3E3E3E',
  68.               },
  69.             }
  70.           ]
  71.         }
  72.         else {
  73.           newLineArr = [
  74.             {
  75.  
  76.               coord: [this.routeX[0], this.routeY[0],0],
  77.               lineStyle: {
  78.                 width: 1,
  79.                 type: 'solid',
  80.                 color: '#3E3E3E',
  81.               },
  82.             },
  83.             {
  84.               coord: [this.routeX[index], this.routeY[index],1],
  85.               lineStyle: {
  86.                 width: 1,
  87.                 type: 'solid',
  88.                 color: '#3E3E3E',
  89.               },
  90.             }
  91.           ]
  92.         }
  93.         this.routeLineData.push(newLineArr)
  94.       })
  95.       // console.log("连线数据", this.routeLineData)
  96.       // console.log("坐标数据", this.routeData)
  97.     },
  98.     renderChart() {
  99.       // console.log("传入的数据", this.inputValue)
  100.       this.setMyEchart()
  101.     },
  102.     setMyEchart() {
  103.       const myChart = this.$refs.myChart;  //通过ref获取到DOM节点
  104.       if (myChart) {
  105.         const thisChart = this.$echarts.init(myChart);  //利用原型调取Echarts的初始化方法
  106.         //{}内写需要图表的各种配置，可以在官方案例中修改完毕后复制过来
  107.         // console.log("绘图数据", this.routeData)
  108.         const option = {
  109.           title: {
  110.             text: "路线图"
  111.           },
  112.           tooltip: {
  113.             trigger: "axis",
  114.             formatter: function (params) {
  115.               let x = params[0].value[0].toFixed(2)
  116.               let y = params[0].value[1].toFixed(2)
  117.               let city = params[0].value[2]
  118.               return `<div style="color:blue">坐标:</div>
  119.                       <div>x:${x}</div>
  120.                       <div>y:${y}</div>
  121.                       <div>${city}</div>`
  122.             }
  123.           },
  124.           xAxis: {
  125.           },
  126.           yAxis: {
  127.           },
  128.           series: [
  129.             {
  130.               data: this.routeData,
  131.               type: 'scatter',
  132.               // label: {
  133.               //   distance:5,
  134.               //   show: true,
  135.               //   position: "left",
  136.               //   formatter: '{@[2]}',
  137.               //   fontSize:9
  138.               // },
  139.               itemStyle: {
  140.                 color: function (node) {
  141.                   if (node.dataIndex === 0 || node.dataIndex === 15) {
  142.                     return 'red'
  143.                   }
  144.                   else {
  145.                     return 'blue'
  146.                   }
  147.                 }
  148.               },
  149.               markLine: {
  150.                 silent: false,
  151.                 symbol: 'none',
  152.                 data: this.routeLineData,
  153.               }
  154.             }
  155.           ]
  156.         };
  157.         thisChart.setOption(option);  //将编写好的配置项挂载到Echarts上
  158.         window.addEventListener("resize", function () {
  159.           thisChart.resize();  //页面大小变化后Echarts也更改大小
  160.         });
  161.       }
  162.     },
  163. } 
  164. </script>

 C.css部分

  1. <style>
  2.     
  3. .container {
  4.   width: 100%;
  5.   height: 100%;
  6.   display: flex;
  7.   justify-content: center;
  8.   align-items: center;
  9. }
  10. .echarts {
  11.   width: 500px;
  12.   height: 500px;
  13.   background-color: whitesmoke;
  14.  
  15. }
  16. </style>

D.实现效果:

 

 

 

 

网站建设定制开发 软件系统开发定制 定制软件开发 软件开发定制 定制app开发 app开发定制 app开发定制公司 电商商城定制开发 定制小程序开发 定制开发小程序 客户管理系统开发定制 定制网站 定制开发 crm开发定制 开发公司 小程序开发定制 定制软件 收款定制开发 企业网站定制开发 定制化开发 android系统定制开发 定制小程序开发费用 定制设计 专注app软件定制开发 软件开发定制定制 知名网站建设定制 软件定制开发供应商 应用系统定制开发 软件系统定制开发 企业管理系统定制开发 系统定制开发