### Python 实现 TSP 旅行商问题 对于TSP旅行商问题，遗传算法是一种有效的启发式方法来找到近似最优解[^1]。下面展示了一个简单的Python实现，该程序利用遗传算法求解给定城市的最短路径。 #### 遗传算法的关键组件 - **种群初始化**：创建初始种群，即一系列可能的解决方案。 - **适应度函数**：评估每个个体的好坏程度，通常是最小化总行程距离。 - **选择操作**：依据适应度挑选出更优的个体作为父母代。 - **交叉操作**：通过交换两个父本的部分基因形成新的子代。 - **变异操作**：随机改变某些后代的一部分以增加多样性。 ```python import random from operator import attrgetter, itemgetter import numpy as np class City: 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 f"({self.x}, {self.y})" def create_route(city_list): route = random.sample(city_list, len(city_list)) return route def initial_population(pop_size, city_list): population = [] for _ in range(0, pop_size): population.append(create_route(city_list)) return population def rank_routes(population): fitness_results = {} for i in range(len(population)): fitness_results[i] = Fitness(population[i]).route_fitness() sorted_results = dict(sorted(fitness_results.items(), key=itemgetter(1), reverse=True)) return sorted_results def selection(pop_ranked, elite_size): selection_results = [] df = pd.DataFrame(np.array(list(pop_ranked.items())), columns=["Index", "Fitness"]) df['cum_sum'] = df.Fitness.cumsum() df['cum_perc'] = 100 * df.cum_sum / df.Fitness.sum() for i in range(elite_size): selection_results.append(pop_ranked.keys()[i]) for _ in range(len(pop_ranked) - elite_size): pick = 100 * random.random() for index in range(len(pop_ranked)): if pick <= df.iat[index, 3]: selection_results.append(pop_ranked.keys()[index]) break return selection_results def mating_pool(population, selection_results): matingpool = [] for result in selection_results: index = result matingpool.append(population[index]) return matingpool def breed(parent1, parent2): child = [] child_p1 = [] child_p2 = [] 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) for i in range(start_gene, end_gene): child_p1.append(parent1[i]) child_p2 = [item for item in parent2 if item not in child_p1] child = child_p1 + child_p2 return child def breed_population(matingpool, elite_size): children = [] length = len(matingpool) - elite_size pool = random.sample(matingpool, len(matingpool)) for i in range(elite_size): children.append(matingpool[i]) for i in range(length): child = breed(pool[i], pool[len(matingpool)-i-1]) children.append(child) return children def mutate(individual, mutation_rate): for swapped in range(len(individual)): if random.random() < mutation_rate: swap_with = int(random.random() * len(individual)) city1 = individual[swapped] city2 = individual[swap_with] individual[swapped] = city2 individual[swap_with] = city1 return individual def mutate_population(population, mutation_rate): mutated_pop = [] for ind in range(0, len(population)): mutated_ind = mutate(population[ind], mutation_rate) mutated_pop.append(mutated_ind) return mutated_pop def next_generation(current_gen, elite_size, mutation_rate): pop_ranked = rank_routes(current_gen) selection_results = selection(pop_ranked, elite_size) matingpool = mating_pool(current_gen, selection_results) children = breed_population(matingpool, elite_size) next_gen = mutate_population(children, mutation_rate) return next_gen def genetic_algorithm(population, pop_size, elite_size, mutation_rate, generations): pop = initial_population(pop_size, population) print("Initial distance: " + str(1 / rank_routes(pop)[list(rank_routes(pop).keys())[0]])) for i in range(0, generations): pop = next_generation(pop, elite_size, mutation_rate) print("Final distance: " + str(1 / rank_routes(pop)[list(rank_routes(pop).keys())[0]])) best_route_index = list(rank_routes(pop).keys())[0] best_route = pop[best_route_index] return best_route class Fitness: def __init__(self, route): self.route = route self.distance = 0 self.fitness= 0.0 def route_distance(self): if self.distance == 0: path_distance = 0 for i in range(0, len(self.route)): from_city = self.route[i] to_city = None if i + 1 < len(self.route): to_city = self.route[i + 1] else: to_city = self.route[0] path_distance += from_city.distance(to_city) self.distance = path_distance return self.distance def route_fitness(self): if self.fitness == 0: self.fitness = 1 / float(self.route_distance()) return self.fitness cityList = [] for i in range(0,25): cityList.append(City(x=int(random.random() * 200), y=int(random.random() * 200))) geneticAlgorithmResult = genetic_algorithm(population=cityList, pop_size=100, elite_size=20, mutation_rate=0.01, generations=500) print(geneticAlgorithmResult) ``` 上述代码展示了如何构建一个基本框架用于解决TSP问题，并采用遗传算法逐步优化路线直到达到满意的解为止。注意，在实际应用中还需要考虑更多细节调整参数设置以及改进策略提高效率和效果。