【建模算法】Python调用scikit-opt工具箱中的蚁群算法求解TSP问题

TSP (traveling salesman problem，旅行商问题)是典型的NP完全问题，即其最坏情况下的时间复杂度随着问题规模的增大按指数方式增长，到目前为止还未找到一个多项式时间的有效算法。本文探讨了Python调用scikit-opt工具箱中的蚁群算法求解TSP问题。

一、问题描述

​ 本案例以31个城市为例，假定31个城市的位置坐标如表1所列。寻找出一条最短的遍历31个城市的路径。

二、scikit-opt工具箱简介

scikit-opt工具箱是一个封装了7种启发式算法的 Python 代码库，包含差分进化算法、遗传算法、粒子群算法、模拟退火算法、蚁群算法、鱼群算法、免疫优化算法。官网链接：https://scikit-opt.github.io/scikit-opt/#/zh/

三、调用scikit-opt工具箱中蚁群算法求解TSP问题的步骤

1.安装工具箱

pip install scikit-opt

2.编写自定义问题

主要是将自己问题的数据输入到封装的代码中，操作简单，修改码量很少
其中只有两行代码需要修改

num_points = 31                #num_points指需要遍历的节点个数
points_coordinate = np.random.rand(num_points, 2)    #points_coordinate是自定义问题中的节点坐标信息

3.调用蚁群算法进行求解

from sko.ACA import ACA_TSP

aca = ACA_TSP(func=cal_total_distance, n_dim=num_points,
              size_pop=50, max_iter=200,
              distance_matrix=distance_matrix)

best_x, best_y = aca.run()

4.绘制近似最优路径图像

其中的best_points_ 表示从起点出发并回到起点的路径。
（其实与best_points差别就是在best_points后加入起点（best_points的第一个点））

fig, ax = plt.subplots(1, 2)
best_points_ = np.concatenate([best_x, [best_x[0]]])
best_points_coordinate = points_coordinate[best_points_, :]
ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')
pd.DataFrame(aca.y_best_history).cummin().plot(ax=ax[1])
plt.show()

四、求解结果

城市序列与距离：

TSP图和Loss图：

五、完整源代码

python源码：

#蚁群(ACA)算法求解31城市TSP问题完整代码：
import pandas as pd
import matplotlib.pyplot as plt
import numpy as np
from scipy import spatial
from sko.ACA import ACA_TSP
from matplotlib.ticker import FormatStrFormatter
from time import perf_counter


def cal_total_distance(routine):
    num_points, = routine.shape
    return sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)])

def print_route(best_points):
    result_cur_best=[]
    for i in best_points:
        result_cur_best+=[i]
    for i in range(len(result_cur_best)):
        result_cur_best[i] += 1
    result_path = result_cur_best
    result_path.append(result_path[0])
    return result_path

if __name__=="__main__":
    file_name = 'data.csv'        #城市坐标数据
    points_coordinate = np.loadtxt(file_name, delimiter=',')
    num_points = points_coordinate.shape[0]
    distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean')
    
    start=perf_counter()       #计时开始
    # 执行蚁群(ACA)算法
    aca = ACA_TSP(func=cal_total_distance, n_dim=num_points,size_pop=50, max_iter=200,distance_matrix=distance_matrix)

    # 结果输出
    best_x, best_y = aca.run()    
    print("运行时间是: {:.5f}s".format(perf_counter()-start))   #计时结束
    print("最优路线：", print_route(best_x))
    print("最优值：", best_y)

    # 绘图
    best_points_ = np.concatenate([best_x, [best_x[0]]])
    best_points_coordinate = points_coordinate[best_points_, :]

    plt.rcParams['font.sans-serif'] = 'SimHei'  # 设置中文显示
    plt.rcParams['axes.unicode_minus'] = False
    fig1, ax1 = plt.subplots(1, 1)
    ax1.set_title('优化过程', loc='center')
    ax1.plot(pd.DataFrame(aca.y_best_history).cummin())
    ax1.set_xlabel("迭代次数")
    ax1.set_ylabel("最优值")

    fig2, ax2 = plt.subplots(1, 1)
    ax2.set_title('轨迹图', loc='center')
    line=ax2.plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], marker='>', mec='r', mfc='w',label=u'路线')
    ax2.legend()  # 让图例生效
    for i in range(num_points):
        plt.text(best_points_coordinate[:, 0][i] + 0.05, best_points_coordinate[:, 1][i] + 0.05, str(best_x[i]+1), color='red')
    ax2.xaxis.set_major_formatter(FormatStrFormatter('%.3f'))
    ax2.yaxis.set_major_formatter(FormatStrFormatter('%.3f'))
    ax2.set_xlabel("横坐标")
    ax2.set_ylabel("纵坐标")
    plt.show()