Python: 多优化算法TSP求解方案，物流路径规划代码实践 - 附详尽注释及标准数据集

Python模拟退火算法、蚁群算法、遗传算法、粒子群算法求解旅行商问题(TSP)的Python代码程序。 物流路径规划问题。 -- 数据集采用的tsplib标准数据集可以根据自己需求修改城市坐标。 代码完整注释详细打印每次迭代结果对新手非常友好点击即可运行。今天我们来聊聊如何使用Python实现几种经典的优化算法来解决旅行商问题TSP。TSP问题简单来说就是给定一组城市和它们之间的距离找出一条最短的路径使得旅行商能够访问每个城市一次并最终回到起点。这个问题在物流路径规划中非常常见。Python模拟退火算法、蚁群算法、遗传算法、粒子群算法求解旅行商问题(TSP)的Python代码程序。 物流路径规划问题。 -- 数据集采用的tsplib标准数据集可以根据自己需求修改城市坐标。 代码完整注释详细打印每次迭代结果对新手非常友好点击即可运行。首先我们需要一个数据集。这里我们采用tsplib标准数据集你可以根据需要修改城市坐标。我们来看一下如何用Python实现模拟退火算法、蚁群算法、遗传算法和粒子群算法。模拟退火算法模拟退火算法是一种基于概率的全局优化算法灵感来自金属退火过程。它通过接受比当前解更差的解来避免陷入局部最优。import random import math def simulated_annealing(cities, initial_temp, cooling_rate): current_solution random.sample(cities, len(cities)) current_distance calculate_distance(current_solution) best_solution current_solution best_distance current_distance temp initial_temp while temp 1: new_solution generate_neighbor(current_solution) new_distance calculate_distance(new_solution) if acceptance_probability(current_distance, new_distance, temp) random.random(): current_solution new_solution current_distance new_distance if current_distance best_distance: best_solution current_solution best_distance current_distance temp * cooling_rate print(fTemp: {temp}, Best Distance: {best_distance}) return best_solution, best_distance def calculate_distance(solution): distance 0 for i in range(len(solution)): distance math.sqrt((solution[i][0] - solution[(i1)%len(solution)][0])**2 (solution[i][1] - solution[(i1)%len(solution)][1])**2) return distance def generate_neighbor(solution): a, b random.sample(range(len(solution)), 2) solution[a], solution[b] solution[b], solution[a] return solution def acceptance_probability(current_distance, new_distance, temp): if new_distance current_distance: return 1.0 return math.exp((current_distance - new_distance) / temp) cities [(0, 0), (1, 5), (2, 3), (5, 2)] initial_temp 1000 cooling_rate 0.995 best_solution, best_distance simulated_annealing(cities, initial_temp, cooling_rate) print(fBest Solution: {best_solution}, Best Distance: {best_distance})蚁群算法蚁群算法模拟蚂蚁寻找食物的过程通过信息素的积累和挥发来寻找最优路径。import random def ant_colony_optimization(cities, num_ants, num_iterations, alpha, beta, evaporation_rate): pheromone [[1.0 for _ in range(len(cities))] for _ in range(len(cities))] best_solution None best_distance float(inf) for iteration in range(num_iterations): solutions [] for ant in range(num_ants): solution construct_solution(cities, pheromone, alpha, beta) distance calculate_distance(solution) solutions.append((solution, distance)) if distance best_distance: best_solution solution best_distance distance update_pheromone(pheromone, solutions, evaporation_rate) print(fIteration: {iteration}, Best Distance: {best_distance}) return best_solution, best_distance def construct_solution(cities, pheromone, alpha, beta): solution [random.choice(cities)] remaining_cities set(cities) remaining_cities.remove(solution[0]) while remaining_cities: last_city solution[-1] next_city select_next_city(last_city, remaining_cities, pheromone, alpha, beta) solution.append(next_city) remaining_cities.remove(next_city) return solution def select_next_city(last_city, remaining_cities, pheromone, alpha, beta): probabilities [] total 0.0 for city in remaining_cities: pheromone_level pheromone[last_city][city] distance math.sqrt((last_city[0] - city[0])**2 (last_city[1] - city[1])**2) probabilities.append((city, (pheromone_level ** alpha) * ((1.0 / distance) ** beta))) total probabilities[-1][1] probabilities [(city, prob / total) for city, prob in probabilities] probabilities.sort(keylambda x: x[1], reverseTrue) r random.random() cumulative_probability 0.0 for city, prob in probabilities: cumulative_probability prob if r cumulative_probability: return city return probabilities[0][0] def update_pheromone(pheromone, solutions, evaporation_rate): for i in range(len(pheromone)): for j in range(len(pheromone[i])): pheromone[i][j] * (1.0 - evaporation_rate) for solution, distance in solutions: for i in range(len(solution)): pheromone[solution[i]][solution[(i1)%len(solution)]] 1.0 / distance # 示例调用 cities [(0, 0), (1, 5), (2, 3), (5, 2)] num_ants 10 num_iterations 100 alpha 1.0 beta 2.0 evaporation_rate 0.5 best_solution, best_distance ant_colony_optimization(cities, num_ants, num_iterations, alpha, beta, evaporation_rate) print(fBest Solution: {best_solution}, Best Distance: {best_distance})遗传算法遗传算法模拟生物进化过程通过选择、交叉和变异来寻找最优解。import random def genetic_algorithm(cities, population_size, num_generations, mutation_rate): population [random.sample(cities, len(cities)) for _ in range(population_size)] best_solution None best_distance float(inf) for generation in range(num_generations): population evolve_population(population, mutation_rate) current_best_solution min(population, keycalculate_distance) current_best_distance calculate_distance(current_best_solution) if current_best_distance best_distance: best_solution current_best_solution best_distance current_best_distance print(fGeneration: {generation}, Best Distance: {best_distance}) return best_solution, best_distance def evolve_population(population, mutation_rate): new_population [] for _ in range(len(population)): parent1 select_parent(population) parent2 select_parent(population) child crossover(parent1, parent2) mutate(child, mutation_rate) new_population.append(child) return new_population def select_parent(population): tournament_size 5 tournament random.sample(population, tournament_size) return min(tournament, keycalculate_distance) def crossover(parent1, parent2): child parent1[:] start, end sorted(random.sample(range(len(parent1)), 2)) for i in range(start, end): if parent2[i] not in child: child[i] parent2[i] return child def mutate(child, mutation_rate): if random.random() mutation_rate: a, b random.sample(range(len(child)), 2) child[a], child[b] child[b], child[a] # 示例调用 cities [(0, 0), (1, 5), (2, 3), (5, 2)] population_size 20 num_generations 100 mutation_rate 0.01 best_solution, best_distance genetic_algorithm(cities, population_size, num_generations, mutation_rate) print(fBest Solution: {best_solution}, Best Distance: {best_distance})粒子群算法粒子群算法模拟鸟群觅食的过程通过个体和群体的历史最优来更新粒子的位置。import random def particle_swarm_optimization(cities, num_particles, num_iterations, w, c1, c2): particles [random.sample(cities, len(cities)) for _ in range(num_particles)] velocities [[random.uniform(-1, 1) for _ in range(len(cities))] for _ in range(num_particles)] personal_best_solutions particles[:] personal_best_distances [calculate_distance(p) for p in particles] global_best_solution min(personal_best_solutions, keycalculate_distance) global_best_distance calculate_distance(global_best_solution) for iteration in range(num_iterations): for i in range(num_particles): for j in range(len(cities)): r1, r2 random.random(), random.random() velocities[i][j] w * velocities[i][j] c1 * r1 * (personal_best_solutions[i][j] - particles[i][j]) c2 * r2 * (global_best_solution[j] - particles[i][j]) particles[i][j] velocities[i][j] distance calculate_distance(particles[i]) if distance personal_best_distances[i]: personal_best_solutions[i] particles[i] personal_best_distances[i] distance if distance global_best_distance: global_best_solution particles[i] global_best_distance distance print(fIteration: {iteration}, Best Distance: {global_best_distance}) return global_best_solution, global_best_distance # 示例调用 cities [(0, 0), (1, 5), (2, 3), (5, 2)] num_particles 10 num_iterations 100 w 0.5 c1 1.5 c2 1.5 best_solution, best_distance particle_swarm_optimization(cities, num_particles, num_iterations, w, c1, c2) print(fBest Solution: {best_solution}, Best Distance: {best_distance})总结通过以上四种算法的实现我们可以看到不同的优化方法在解决TSP问题时的表现。每种算法都有其独特的优势和适用场景你可以根据具体需求选择合适的算法。希望这些代码对你有所帮助也欢迎你进一步探索和优化这些算法