基于遗传算法求解TSP问题-python完整代码

@[toc] ### TSP问题 ‌TSP问题，即旅行商问题（Traveling Salesman Problem），是一个经典的组合优化问题。它描述了一个旅行商需要访问一系列城市，**每个城市仅访问一次，并最后返回起点，目标是找到访问这些城市的最短路线**。TSP问题是一个NP难问题，随着城市数量的增加，解决方案的空间迅速增长，导致精确算法在处理大规模问题时变得不切实际。因此，研究者们开发了各种启发式和近似算法来寻找可行解，尽管这些解可能不是最优的，但在实际应用中通常是可接受的。‌ ### GA算法 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。 染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码（ 1 代表接下来位置的基因存在，0 意味着丢失）。 初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合**交叉（crossover）和变异（mutation）**，产生出代表新的解集的种群。 这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。  ### GA-TSP 使用遗传算法解决旅行商问题（TSP）通常包括以下几个步骤： - 初始化种群： 生成一个初始种群，其中每个个体代表一个可能的解决方案，即城市访问顺序的一种排列。 种群大小需要预先设定。 - 适应度评估： 计算每个个体的适应度值，对于TSP问题，通常是计算路径的总长度（以最短路径为目标）或其倒数（以转化为最大值优化为目标）。 适应度函数可以帮助选择哪些个体更有可能被选中进行下一步的遗传操作。 - 选择操作： 根据适应度值从当前种群中选择个体进行繁殖，常用的选择方法有**轮盘赌选择**、锦标赛选择等。 目的是让适应度高的个体有更大的机会被选中，从而保留优秀的特征到下一代。 - 交叉操作： 对选出的个体进行配对，并通过交叉操作产生新的后代。 交叉方法需要保证后代仍然是一条有效的路径，常见的交叉算子如顺序交叉、部分匹配交叉等。 交叉概率需要提前设定。 - 变异操作： 对新产生的后代进行变异操作，以增加种群多样性。 常见的变异操作包括交换两个城市的顺序、逆序一段路径等。 变异概率通常较小，以避免破坏优秀的解决方案。 - 替换操作： 使用新产生的后代替换旧种群中的个体，可以采用精英策略保留最好的个体。 替换操作确保每一代种群大小保持不变。 - 终止条件判断： 判断是否达到预设的终止条件，例如迭代次数、适应度阈值等。 如果未达到，则返回步骤3继续迭代；否则，输出最优解。 - 结果输出： 输出最优路径及其对应的总距离和路线。 #### 数据集 数据来源于华为杯研赛2015F题，通过经纬度查询提取好了31个省市共201个景区的经纬度数据，并用地图汇绘制：    以江苏省为例： jiansu.tsp 格式 ```c NAME: st19 TYPE: TSP COMMENT: 70-city problem (Smith/Thompson) DIMENSION: 19 EDGE_WEIGHT_TYPE : EUC_2D NODE_COORD_SECTION 1 120.636 31.3303 0.5 苏州园林 2 120.856 31.1208 0.5 苏州昆山 3 118.836 32.0709 0.5 南京钟山 4 120.24 31.4819 0.5 无锡影视 5 120.112 31.4444 0.5 无锡灵山 6 120.725 31.1641 0.5 苏州吴江 7 118.899 31.8231 0.5 南京夫子庙 8 120.015 31.824 0.5 常州恐龙 9 119.425 32.4148 0.5 扬州瘦西湖 10 120.878 32.0217 0.5 南通濠河 11 120.097 32.6301 0.5 泰州姜堰 12 120.705 31.3176 0.5 苏州金鸡湖 13 119.49 32.2453 1 镇江三山 14 120.226 31.5336 0.5 无锡鼋头渚 15 120.581 31.1743 1 苏州吴中太湖 16 120.708 31.6758 1 苏州常熟 17 119.447 31.3215 1 常州溧阳 18 119.314 31.7877 1 镇江句容 19 119.149 33.5131 0.5 淮安故里 EOF ``` jiangsu.txt 格式 ```c 1 120.636 31.3303 0.5 苏州园林 2 120.856 31.1208 0.5 苏州昆山 3 118.836 32.0709 0.5 南京钟山 4 120.24 31.4819 0.5 无锡影视 5 120.112 31.4444 0.5 无锡灵山 6 120.725 31.1641 0.5 苏州吴江 7 118.899 31.8231 0.5 南京夫子庙 8 120.015 31.824 0.5 常州恐龙 9 119.425 32.4148 0.5 扬州瘦西湖 10 120.878 32.0217 0.5 南通濠河 11 120.097 32.6301 0.5 泰州姜堰 12 120.705 31.3176 0.5 苏州金鸡湖 13 119.49 32.2453 1 镇江三山 14 120.226 31.5336 0.5 无锡鼋头渚 15 120.581 31.1743 1 苏州吴中太湖 16 120.708 31.6758 1 苏州常熟 17 119.447 31.3215 1 常州溧阳 18 119.314 31.7877 1 镇江句容 19 119.149 33.5131 0.5 淮安故里 ``` #### python完整代码 ```python import random import math import numpy as np import matplotlib.pyplot as plt from matplotlib import rcParams # 设置字体为 SimHei 显示中文 rcParams['font.sans-serif'] = ['SimHei'] rcParams['axes.unicode_minus'] = False # 正常显示负号 class GA(object): def __init__(self, num_city, num_total, iteration, data): self.num_city = num_city self.num_total = num_total self.scores = [] self.iteration = iteration self.location = data self.ga_choose_ratio = 0.2 self.mutate_ratio = 0.05 # fruits中存每一个个体是下标的list self.dis_mat = self.compute_dis_mat(num_city, data) self.fruits = self.greedy_init(self.dis_mat,num_total,num_city) # 显示初始化后的最佳路径 scores = self.compute_adp(self.fruits) sort_index = np.argsort(-scores) init_best = self.fruits[sort_index[0]] init_best = self.location[init_best] # 存储每个iteration的结果，画出收敛图 self.iter_x = [0] self.iter_y = [1. / scores[sort_index[0]]] def random_init(self, num_total, num_city): tmp = [x for x in range(num_city)] result = [] for i in range(num_total): random.shuffle(tmp) result.append(tmp.copy()) return result def greedy_init(self, dis_mat, num_total, num_city): start_index = 0 result = [] for i in range(num_total): rest = [x for x in range(0, num_city)] # 所有起始点都已经生成了 if start_index >= num_city: start_index = np.random.randint(0, num_city) result.append(result[start_index].copy()) continue current = start_index rest.remove(current) # 找到一条最近