用遗传算法和动态规划来求解经典算法问题-TSP商旅问题_Pytho源代码

import pandas as pd import numpy as np import random, operator import matplotlib.pyplot as plt class City(object): """城市""" def __init__(self, x, y): self.x = x self.y = y def distance(self, city): # 计算两个城市的距离,使用欧拉距离，也就是两个坐标的直线距离 dx = abs(self.x - city.x) dy = abs(self.y - city.y) return np.sqrt((dx ** 2) + (dy ** 2)) def __repr__(self): return "({},{})".format(self.x, self.y) def generate_city(n): # 用于生成随机城市，返回两种形式的表达 city_list = [] # 一种是城市坐标列表 distances_array = [] # 一种是城市与城市间的距离矩阵 for i in range(n): city_list.append(City( x=int(random.random() * 200), y=int(random.random() * 200))) for i in range(n): row = list() for j in range(n): row.append(np.linalg.norm( city_list[i].distance(city_list[j]))) distances_array.append(row) distances_array = np.array(distances_array) return city_list, distances_array class GeneticAlgorithm(object): """遗传算法解决旅行者问题""" def __init__(self, city_list, population_size, elite_size, mutation_rate, generations): self.city_list = city_list # 城市列表 self.population_size = population_size # 种群大小 self.elite_size = elite_size # 精英模式数量 self.mutation_rate = mutation_rate # 变异的概率 self.generations = generations # 进化的总代数 self.progress = [] # 记录每一代的最优结果 def init_population(self): # 创建一个种群 population = [] for i in range(self.population_size): route = random.sample(self.city_list, len(self.city_list)) population.append(route) return population def fitness(self, route): # 计算个体的适应能力值 path_distance = 0 # 路径的总距离 for i in range(0, len(route)): from_city = route[i] if i + 1 < len(route): to_city = route[i + 1] else: to_city = route[0] path_distance += from_city.distance(to_city) distance = path_distance # 距离越长，适应能力值越小，因此用路径长度的倒数作为适应能力值 return 1 / float(distance) def rank_routes(self, population): # 适应能力值排名 fitness_results = {} for i in range(0, len(population)): fitness_results[i] = self.fitness(population[i]) return sorted(fitness_results.items(), key=operator.itemgetter(1), reverse=True) def selection(self, population, population_ranked): # 根据适应能力值挑选个体进入杂交处理 mating_pool = [] # 记录被挑选的个体 df = pd.DataFrame(np.array(population_ranked), columns=["Index", "Fitness"]) # 通过这个方法，把适应能力值归一化后，变成一个按排名的分数 df['cum_sum'] = df.Fitness.cumsum() df['cum_perc'] = 100 * df.cum_sum / df.Fitness.sum() for i in range(0, self.elite_size): # 精英模式 mating_pool.append(population[population_ranked[i][0]]) for i in range(0, len(population_ranked) - self.elite_size): # 剩下的按轮盘赌选择 pick = 100 * random.random() # 每次生成一个（0到1）随机数 for i in range(0, len(population_ranked)): if pick <= df.iat[i, 3]: # 看落在那个区间，选择该个体 mating_pool.append(population[population_ranked[i][0]]) break return mating_pool def breed_population(self, mating_pool): # 杂交处理 def breed(parent1, parent2): # 父母杂交，创建新的一代 child_p1 = [] # 来自parent1的基因 child_p2 = [] # 来自parent2的基因 gene_A = int(random.random() * len(parent1)) gene_B = int(random.random() * len(parent1)) start_gene = min(gene_A, gene_B) end_gene = max(gene_A, gene_B) # 随机抽取parent1一段基因 for i in range(start_gene, end_gene): child_p1.append(parent1[i]) for item in parent2: # 剩下的都来自parent2 if item not in child_p1: child_p2.append(item) child = child_p1 + child_p2 return child children = [] # 记录下一代个体 length = len(mating_pool) - self.elite_size pool = random.sample(mating_pool, len(mating_pool)) # 打乱顺序 for i in range(0, self.elite_size): # 精英模式，直接进入下一代 children.append(mating_pool[i]) for i in range(0, length): child = breed(pool[i], pool[len(mating_pool) - i - 1]) children.append(child) return children def mutate_population(self, population): # 基因突变处理 def mutate(individual): for index_city1 in range(len(individual)): if (random.random() < self.mutation_rate): # 若个体（路径）发生变异，随机挑选两个城市交换位置 index_city2 = int(random.random() * len(individual)) city1 = individual[index_city1] city2 = individual[index_city2] individual[index_city1] = city2 individual[index_city2] = city1 return individual mutated_population = [] for index_population in range(0, len(population)): mutated_population.append(mutate(population[index_population])) return mutated_population def next_generation(self, current_generation): # 生成下一代 population_ranked = self.rank_routes(current_generation) # 计算排名 mating_pool = self.selection(current_generation, population_ranked) # 挑选个体繁衍 children = self.breed_population(mating_pool) # 杂交处理 new_generation = self.mutate_population(children) # 基因突变处理 return new_generation # 最后返回新的一代种群 def run(self): # 算法调用的入口 population = self.init_population() self.progress.append(1 / self.rank_routes(population)[0][1]) print("第一代最短路径: " + str(self.progress[0])) for i in range(0, self.generations): population = self.next_generation(population) self.progress.append(1 / self.rank_routes(population)[0][1]) print("最后一代最短路径: " + str(1 / self.rank_routes(population)[0][1])) index_best_route = self.rank_routes(population)[0][0] return population[index_best_route] def draw_progress(self): plt.plot(self.progress) plt.ylabel('Distance') plt.xlabel('Generation') plt.show() if __name__ == '__main__': citys, arr = generate_city(3) print(citys) print(arr) ga = GeneticAlgorithm(city_list=citys, population_size=50, elite_size=5, mutation_rate=0.01, generations=30) result = ga.run() ga.draw_progress()