算法整理：2-opt求解旅行商（Python代码）

算法思想

通过交换边进行寻优。

算法步骤

1. 把初始解作为当前解

2. 通过交换边生成新解
   

3. 如果新解优于历史最优解，则更新当前解为新解

4. 重复2，3，直到当前解交换了所有的边均不能改善。

代码1·纯函数

def two_opt(I, c):
    """Two-opt 旅行商路径优化算法
    I: 城市编号的list
    c: 距离矩阵c[i,j]
    """
    best_distance = sum(c[I[i], I[i + 1]] for i in range(len(I) - 1))
    best_solution = I[:]
    improve = True
    s = 0
    while improve:
        improve = False
        for i in range(len(I) - 1):
            for j in range(i + 1, len(I) - 1):
                if j - i >= 1:  # 确保至少有两个城市在i和j之间
                    delta = (
                        c[best_solution[i - 1], best_solution[j]] +
                        c[best_solution[i], best_solution[j + 1]] -
                        c[best_solution[i - 1], best_solution[i]] -
                        c[best_solution[j], best_solution[j + 1]]
                    )
                    if delta < -0.0001:
                        # 进行反转操作
                        best_solution[i:j + 1] = reversed(best_solution[i:j + 1])
                        plot_route(cities, best_solution)
                        best_distance += delta
                        improve = True
    return best_solution, best_distance

• 注意代码中当i == 0时，best_solution[i - 1] =best_solution[- 1]，指向了最后一个城市，由于是TSP问题，并不违反逻辑。

代码2·纯函数+数据+可视化

import time
import numpy as np
import matplotlib.pyplot as plt

def generate_random_cities(num_cities):
    """生成随机的城市坐标及距离矩阵"""

    np.random.seed(3)   # 锁定随机种子
    cities = np.random.rand(num_cities, 2)  # 生成随机坐标
    distance_matrix = np.zeros((num_cities, num_cities))
    for i in range(num_cities):
        for j in range(num_cities):
            distance_matrix[i, j] = np.linalg.norm(cities[i] - cities[j])  # 计算欧几里得距离
    return cities, distance_matrix

def two_opt(I, c):
    """Two-opt 旅行商路径优化算法
    I: 城市编号的list
    c: 距离矩阵c[i,j]
    """
    best_distance = sum(c[I[i], I[i + 1]] for i in range(len(I) - 1))
    best_solution = I[:]
    improve = True
    s = 0
    while improve:
        improve = False
        for i in range(len(I) - 1):
            for j in range(i + 2, len(I) - 1):
                delta = (
                    c[best_solution[i - 1], best_solution[j]] +
                    c[best_solution[i], best_solution[j + 1]] -
                    c[best_solution[i - 1], best_solution[i]] -
                    c[best_solution[j], best_solution[j + 1]]
                )
                if delta < -1e-6:
                    # 进行反转操作
                    best_solution[i:j + 1] = reversed(best_solution[i:j + 1])
                    plot_route(cities, best_solution)
                    best_distance += delta
                    improve = True
    return best_solution, best_distance

def plot_route(cities, solution):
    """可视化城市和路径"""

    # 画出路径
    plt.plot(cities[solution][:, 0], cities[solution][:, 1], color='black', marker='o')
    plt.plot([cities[solution[0], 0], cities[solution[-1], 0]],
             [cities[solution[0], 1], cities[solution[-1], 1]], color='black', marker='o')  # 回到起点
    
    # 去掉坐标轴黑框
    ax = plt.gca()
    ax.spines['top'].set_color('none')
    ax.spines['right'].set_color('none')
    ax.spines['left'].set_color('none')
    ax.spines['bottom'].set_color('none')

    # 隐藏坐标轴刻度
    ax.xaxis.set_ticks_position('none')
    ax.yaxis.set_ticks_position('none')

    # 隐藏坐标轴刻度标签
    ax.set_xticks([]) 
    ax.set_yticks([])

    # 每帧显示时间
    plt.pause(1)

    # 清空内容
    plt.cla()

# 主程序
num_cities = 10  # 城市数量
cities, distance_matrix = generate_random_cities(num_cities)
I = list(range(num_cities))  # 编号的集合

# 运行 two_opt 算法
optimized_solution, optimized_distance = two_opt(I, distance_matrix)

# 打印结果
print("优化后的路径:", optimized_solution)
print("优化后的距离:", optimized_distance)

# 可视化优化后的路径
plot_route(cities, optimized_solution)