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(f"Temp: {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[(i+1)%len(solution)][0])**2 + (solution[i][1] - solution[(i+1)%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(f"Best 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(f"Iteration: {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(key=lambda x: x[1], reverse=True)
    
    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[(i+1)%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(f"Best 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, key=calculate_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(f"Generation: {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, key=calculate_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(f"Best 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, key=calculate_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(f"Iteration: {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(f"Best Solution: {best_solution}, Best Distance: {best_distance}")

总结

通过以上四种算法的实现，我们可以看到不同的优化方法在解决TSP问题时的表现。每种算法都有其独特的优势和适用场景，你可以根据具体需求选择合适的算法。希望这些代码对你有所帮助，也欢迎你进一步探索和优化这些算法！

# 分布式账本
Logo
快递鸟一站式物流API解决方案

电商企业物流数字化转型必备！快递鸟 API 接口，72 小时快速完成物流系统集成。全流程实战1V1指导，营造开放的API技术生态圈。

更多推荐

苹方字体跨平台解决方案：告别Windows与Mac的字体显示鸿沟

在Web开发中，我们经常面临一个令人头疼的问题：精心设计的页面在Mac上优雅精致，到了Windows设备上却因字体差异而显得平庸。今天，我们为您介绍一个专业的解决方案——PingFangSC字体包，它让苹方字体的优雅设计能够在所有平台上完美呈现。这个开源项目提供了完整的6种字重，支持ttf和woff2双格式，真正实现了跨平台字体统一。## 为什么跨平台字体一致性如此重要？🔍现代Web应用

avatar 快递鸟社区

Ascend-SACT/Mineru-Optimization后端引擎对比：Pipeline、Hybrid与VLM模式如何选择？

Ascend-SACT/Mineru-Optimization提供三种强大的后端引擎模式——Pipeline、Hybrid和VLM，帮助用户高效处理各类文档。本文将深入对比这三种模式的核心特性、性能表现和适用场景，助你快速找到最适合的解决方案。## 三大引擎模式核心特性解析 🚀### Pipeline模式：传统OCR流程的极致优化**核心架构**：采用模块化设计，包含版面分析、OCR、

avatar 快递鸟社区

如何永久保存微信聊天记录？WeChatMsg免费开源工具终极指南

你是否曾担心更换手机后，那些珍贵的微信对话会永远消失？与家人的温馨聊天、重要的工作沟通、朋友间的难忘回忆，这些数字记忆都值得被永久珍藏。**WeChatMsg**是一款完全免费的开源工具，专门用于**微信聊天记录永久保存和深度分析**，让你的每一段对话都能成为永恒的数字资产。## 🔍 你的聊天记录正在面临什么风险？微信已经成为我们日常生活中不可或缺的沟通工具，但官方并未提供完整的聊天记录

avatar 快递鸟社区