遗传算法求解TSP问题的详细完整代码兼案例数据

#!/usr/bin/env python # coding: utf-8 # In[18]: import random import math import numpy as np import matplotlib.pyplot as plt plt.rcParams["font.sans-serif"] = ["SimHei"] # In[2]: # 读取数据 def read_tsp(path): lines = open(path, 'r').readlines() assert 'NODE_COORD_SECTION\n' in lines index = lines.index('NODE_COORD_SECTION\n') data = lines[index + 1:-1] tmp = [] for line in data: line = line.strip().split(' ') if line[0] == 'EOF': continue tmpline = [] for x in line: if x == '': continue else: tmpline.append(float(x)) if tmpline == []: continue tmp.append(tmpline) data = tmp return data # In[19]: 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) # 找到一条最近邻路径 result_one = [current] while len(rest) != 0: tmp_min = math.inf tmp_choose = -1 for x in rest: if dis_mat[current][x] < tmp_min: tmp_min = dis_mat[current][x] tmp_choose = x current = tmp_choose result_one.append(tmp_choose) rest.remove(tmp_choose) result.append(result_one) start_index += 1 return result # 计算不同城市之间的距离 def compute_dis_mat(self, num_city, location): dis_mat = np.zeros((num_city, num_city)) for i in range(num_city): for j in range(num_city): if i == j: dis_mat[i][j] = np.inf continue a = location[i] b = location[j] tmp = np.sqrt(sum([(x[0] - x[1]) ** 2 for x in zip(a, b)])) dis_mat[i][j] = tmp return dis_mat # 计算路径长度 def compute_pathlen(self, path, dis_mat): try: a = path[0] b = path[-1] except: import pdb pdb.set_trace() result = dis_mat[a][b] for i in range(len(path) - 1): a = path[i] b = path[i + 1] result += dis_mat[a][b] return result # 计算种群适应度 def compute_adp(self, fruits): adp = [] for fruit in fruits: if isinstance(fruit, int): import pdb pdb.set_trace() length = self.compute_pathlen(fruit, self.dis_mat) adp.append(1.0 / length) return np.array(adp) def swap_part(self, list1, list2): index = len(list1) list = list1 + list2 list = list[::-1] return list[:index], list[index:] def ga_cross(self, x, y): len_ = len(x) assert len(x) == len(y) path_list = [t for t in range(len_)] order = list(random.sample(path_list, 2)) order.sort() start, end = order # 找到冲突点并存下他们的下标,x中存储的是y中的下标,y中存储x与它冲突的下标 tmp = x[start:end] x_conflict_index = [] for sub in tmp: index = y.index(sub) if not (index >= start and index < end): x_conflict_index.append(index) y_confict_index = [] tmp = y[start:end] for sub in tmp: index = x.index(sub) if not (index >= start and index < end): y_confict_index.append(index) assert len(x_conflict_index) == len(y_confict_index) # 交叉 tmp = x[start:end].copy() x[start:end] = y[start:end] y[start:end] = tmp # 解决冲突 for index in range(len(x_conflict_index)): i = x_conflict_index[index] j = y_confict_index[index] y[i], x[j] = x[j], y[i] assert len(set(x)) == len_ and len(set(y)) == len_ return list(x), list(y) def ga_parent(self, scores, ga_choose_ratio): sort_index = np.argsort(-scores).copy() sort_index = sort_index[0:int(ga_choose_ratio * len(sort_index))] parents = [] parents_score = [] for index in sort_index: parents.append(self.fruits[index]) parents_score.append(scores[index]) return parents, parents_score def ga_choose(self, genes_score, genes_choose): sum_score = sum(genes_score) score_ratio = [sub * 1.0 / sum_score for sub in genes_score] rand1 = np.random.rand() rand2 = np.random.rand() for i, sub in enumerate(score_ratio): if rand1 >= 0: rand1 -= sub if rand1 < 0: index1 = i if rand2 >= 0: rand2 -= sub if rand2 < 0: index2 = i if rand1 < 0 and rand2 < 0: break return list(genes_choose[index1]), list(genes_choose[index2]) def ga_mutate(self, gene): path_list = [t for t in range(len(gene))] order = list(random.sample(path_list, 2)) start, end = min(order), max(order) tmp = gene[start:end] # np.random.shuffle(tmp) tmp = tmp[::-1] gene[start:end] = tmp return list(gene) def ga(self): # 获得优质父代 scores = self.compute_adp(self.fruits) # 选择部分优秀个体作为父代候选集合 parents, parents_score = self.ga_parent(scores, self.ga_choose_ratio) tmp_best_one = parents[0] tmp_best_score = parents_score[0] # 新的种群fruits fruits = parents.copy() # 生成新的种群 while len(fruits) < self.num_total: # 轮盘赌方式对父代进行选择 gene_x, gene_y = self.ga_choose(parents_score, parents) # 交叉 gene_x_new, gene_y_new = self.ga_cross(gene_x, gene_y) # 变异 if np.random.rand() < self.mutate_ratio: gene_x_new = self.ga_mutate(gene_x_new) if np.random.rand() < self.mutate_ratio: gene_y_new = self.ga_mutate(gene_y_new) x_adp = 1. / self.compute_pathlen(gene_x_new, self.dis_mat) y_adp = 1. / self.compute_pathlen(gene_y_new, self.dis_mat) # 将适应度高的放入种群中 if x_adp > y_adp and