请对该代码缩进:import sys sys.setrecursionlimit(10000) import math import random import…
- User
请对该代码缩进:import sys sys.setrecursionlimit(10000) import math import random import matplotlib.pyplot as plt
生成特殊城市图
city_map = {} for i in range(1, 2024): for j in range(i + 1, 2024): if abs(j - i) > 23: continue lcm = abs(i * j) // math.gcd(i, j) city_map[(i, j)] = lcm city_map[(j, i)] = lcm # 添加与 (i, j) 相反的一条路径
city_map[(2024, 1)] = city_map[(1, 2024)] = abs(1 * 2024) // math.gcd(1, 2024) # 添加虚拟城市
class GA: def init(self, pop_size=50, elite_size=10, mutation_rate=0.01, generations=1000): self.pop_size = pop_size self.elite_size = elite_size self.mutation_rate = mutation_rate self.generations = generations self.population = None
def create_route(self): route = list(range(1, 2024)) random.shuffle(route) return route
def initial_population(self): self.population = [self.create_route() for _ in range(self.pop_size)]
def rank_routes(self): distances = [] for route in self.population: distance = 0 for i in range(len(route) - 1): distance += city_map[(route[i], route[i+1])] distances.append((route, distance + city_map[(route[-1], 1)])) distances.sort(key=lambda x: x[1]) self.population = [x[0] for x in distances]
def selection(self): return self.population[:self.elite_size]
def crossover(self, parent1, parent2): child = [None] * len(parent1) start = random.randint(0, len(parent1) - 1) end = random.randint(start + 1, len(parent1)) child[start:end] = parent1[start:end] for i in range(len(parent2)): if parent2[i] not in child: for j in range(len(child)): if child[j] is None: child[j] = parent2[i] break return child
def breed_population(self, elites): children = [] while len(children) < self.pop_size - self.elite_size: parent1, parent2 = random.sample(elites, 2) child = self.crossover(parent1, parent2) children.append(child) return elites + children
def mutate(self, individual): i1 = random.randint(0, len(individual) - 1) i2 = random.randint(0, len(individual) - 1) individual[i1], individual[i2] = individual[i2], individual[i1]
def mutate_population(self, population): for i in range(self.elite_size, len(population)): if random.random() < self.mutation_rate: self.mutate(population[i])
def optimize(self): self.initial_population() progress = [] for i in range(self.generations): self.rank_routes() elites = self.selection() children = self.breed_population(elites) self.mutate_population(children) self.population = elites + children progress.append(self.population[0][1]) return self.population[0][0], progress
def run_ga(): ga = GA(pop_size=50, elite_size=10, mutation_rate=0.01, generations=1000) path, progress = ga.optimize() cost = sum([city_map[(path[i], path[i+1])] for i in range(len(path) - 1)]) + city_map[(path[-1], 1)] print('GA: 最短路径长度', cost) plot_progress(progress) plot_path(path) if name == 'main': run_ga()
- Assistant
import sys sys.setrecursionlimit(10000) import math import random import matplotlib.pyplot as plt
生成特殊城市图
city_map = {} for i in range(1, 2024): for j in range(i + 1, 2024): if abs(j - i) > 23: continue lcm = abs(i * j) // math.gcd(i, j) city_map[(i, j)] = lcm city_map[(j, i)] = lcm # 添加与 (i, j) 相反的一条路径
city_map[(2024, 1)] = city_map[(1, 2024)] = abs(1 * 2024) // math.gcd(1, 2024) # 添加虚拟城市
class GA: def init(self, pop_size=50, elite_size=10, mutation_rate=0.01, generations=1000): self.pop_size = pop_size self.elite_size = elite_size self.mutation_rate = mutation_rate self.generations = generations self.population = None
def create_route(self): route = list(range(1, 2024)) random.shuffle(route) return route def initial_population(self): self.population = [self.create_route() for _ in range(self.pop_size)] def rank_routes(self): distances = [] for route in self.population: distance = 0 for i in range(len(route) - 1): distance += city_map[(route[i], route[i+1])] distances.append((route, distance + city_map[(route[-1], 1)])) distances.sort(key=lambda x: x[1]) self.population = [x[0] for x in distances] def selection(self): return self.population[:self.elite_size] def crossover(self, parent1, parent2): child = [None] * len(parent1) start = random.randint(0, len(parent1) - 1) end = random.randint(start + 1, len(parent1)) child[start:end] = parent1[start:end] for i in range(len(parent2)): if parent2[i] not in child: for j in range(len(child)): if child[j] is None: child[j] = parent2[i] break return child def breed_population(self, elites): children = [] while len(children) < self.pop_size - self.elite_size: parent1, parent2 = random.sample(elites, 2) child = self.crossover(parent1, parent2) children.append(child) return elites + children def mutate(self, individual): i1 = random.randint(0, len(individual) - 1) i2 = random.randint(0, len(individual) - 1) individual[i1], individual[i2] = individual[i2], individual[i1] def mutate_population(self, population): for i in range(self.elite_size, len(population)): if random.random() < self.mutation_rate: self.mutate(population[i]) def optimize(self): self.initial_population() progress = [] for i in range(self.generations): self.rank_routes() elites = self.selection() children = self.breed_population(elites) self.mutate_population(children) self.population = elites + children progress.append(self.population[0][1]) return self.population[0][0], progressdef run_ga(): ga = GA(pop_size=50, elite_size=10, mutation_rate=0.01, generations=1000) path, progress = ga.optimize() cost = sum([city_map[(path[i], path[i+1])] for i in range(len(path) - 1)]) + city_map[(path[-1], 1)] print('GA: 最短路径长度', cost) plot_progress(progress) plot_path(path)
if name == 'main': run_ga()
- User
代码报错,请完成合适的缩进
- Assistant
import sys sys.setrecursionlimit(10000) import math import random import matplotlib.pyplot as plt
生成特殊城市图
city_map = {} for i in range(1, 2024): for j in range(i + 1, 2024): if abs(j - i) > 23: continue lcm = abs(i * j) // math.gcd(i, j) city_map[(i, j)] = lcm city_map[(j, i)] = lcm # 添加与 (i, j) 相反的一条路径
city_map[(2024, 1)] = city_map[(1, 2024)] = abs(1 * 2024) // math.gcd(1, 2024) # 添加虚拟城市
class GA: def init(self, pop_size=50, elite_size=10, mutation_rate=0.01, generations=1000): self.pop_size = pop_size self.elite_size = elite_size self.mutation_rate = mutation_rate self.generations = generations self.population = None
def create_route(self): route = list(range(1, 2024)) random.shuffle(route) return route def initial_population(self): self.population = [self.create_route() for _ in range(self.pop_size)] def rank_routes(self): distances = [] for route in self.population: distance = 0 for i in range(len(route) - 1): distance += city_map[(route[i], route[i+1])] distances.append((route, distance + city_map[(route[-1], 1)])) distances.sort(key=lambda x: x[1]) self.population = [x[0] for x in distances] def selection(self): return self.population[:self.elite_size] def crossover(self, parent1, parent2): child = [None] * len(parent1) start = random.randint(0, len(parent1) - 1) end = random.randint(start + 1, len(parent1)) child[start:end] = parent1[start:end] for i in range(len(parent2)): if parent2[i] not in child: for j in range(len(child)): if child[j] is None: child[j] = parent2[i] break return child def breed_population(self, elites): children = [] while len(children) < self.pop_size - self.elite_size: parent1, parent2 = random.sample(elites, 2) child = self.crossover(parent1, parent2) children.append(child) return elites + children def mutate(self, individual): i1 = random.randint(0, len(individual) - 1) i2 = random.randint(0, len(individual) - 1) individual[i1], individual[i2] = individual[i2], individual[i1] def mutate_population(self, population): for i in range(self.elite_size, len(population)): if random.random() < self.mutation_rate: self.mutate(population[i]) def optimize(self): self.initial_population() progress = [] for i in range(self.generations): self.rank_routes() elites = self.selection() children = self.breed_population(elites) self.mutate_population(children) self.population = elites + children progress.append(self.population[0][1]) return self.population[0][0], progressdef run_ga(): ga = GA(pop_size=50, elite_size=10, mutation_rate=0.01, generations=1000) path, progress = ga.optimize() cost = sum([city_map[(path[i], path[i+1])] for i in range(len(path) - 1)]) + city_map[(path[-1], 1)] print('GA: 最短路径长度', cost) plot_progress(progress) plot_path(path)
if name == 'main': run_ga()