蚁群算法解决旅行商问题 (TSP) - 详细代码实现与可视化分析

蚁群算法解决旅行商问题 (TSP) - 详细代码实现与可视化分析

本文将详细介绍使用蚁群算法解决旅行商问题 (TSP) 的步骤和代码实现，并通过可视化展示了最优路径和距离迭代过程，方便理解算法原理和应用。

1. 问题描述

旅行商问题 (Traveling Salesperson Problem, TSP) 是一个经典的组合优化问题。问题描述如下：给定一组城市和城市之间的距离，求解一条最短的路线，使得旅行商能够访问每个城市一次且仅一次，最终返回起点城市。

2. 蚁群算法

蚁群算法 (Ant Colony Optimization, ACO) 是一种模拟蚂蚁觅食行为的启发式算法。蚂蚁在寻找食物的过程中会释放信息素，信息素浓度越高表明路径越优。其他蚂蚁会根据信息素浓度选择路径，并不断更新信息素浓度，最终找到最佳路径。

3. 代码实现

以下代码使用 Python 实现蚁群算法解决 TSP 问题，并通过 matplotlib 库进行可视化展示。

import numpy as np  # 导入函数库, 数学基础库, 存储和处理大型多维矩阵
import matplotlib.pyplot as plt  # 提供一个绘图框架
import matplotlib  # matplotlib 是 python 上的一个 2D 绘图库
import math
import random
matplotlib.rcParams['font.family'] = 'STSong'  
# 设定绘制区域的全部字体变成华文仿宋；便于中文输出，否则中文出现 []

city_name = []  # 创建空数组，用于存放 30 城市名称
city_condition = []  # 创建空数组，用于存放 30 城市坐标
with open('30城市的坐标.txt', 'r', encoding='UTF-8') as f:  # 打开文件并用 f 表示
    lines = f.readlines()
# 调用 readlines() 一次读取所有内容并按行返回 list 给 lines

# for 循环每次读取一行，即一个城市的坐标数据
    for line in lines:  # 从 lines 列表中逐个读取元素，赋给 line 变量
        line = line.split('
')[0]  # 用 split（）将该行的单词分割成列表，每个单词就时一个列表项目
        line = line.split(',')
        city_name.append(line[0])  # 用于在列表末尾添加新的对象，列表只占一个索引位，在原有列表上增加
        city_condition.append([float(line[1]), float(line[2])])
        # print('城市名称+坐标信息：', line)
city_condition = np.array(city_condition)  # 获取 30 城市坐标
# print(city_condition)

# Distance 距离矩阵
city_count = len(city_name)  # 取数组长度
Distance = np.zeros((city_count, city_count))  # 30*30 的零矩阵
for i in range(city_count):
    for j in range(city_count):
        if i != j:
            Distance[i][j] = math.sqrt((city_condition[i][0] - city_condition[j][0]) ** 2 + (city_condition[i][1] - city_condition[j][1]) ** 2)
        else:
            Distance[i][j] = 100000  # 不为 0 即可

# 蚂蚁数量
AntCount = 200
# 城市数量
city_count = len(city_name)
# 信息素
alpha = 1  # 信息素重要程度因子
beta = 2  # 启发函数重要程度因子
rho = 0.1  # 挥发速度
iter = 0  # 迭代初始值
MAX_iter = 200  # 最大迭代值
Q = 1
# 初始信息素矩阵，全是为 1 组成的矩阵
pheromonetable = np.ones((city_count, city_count))

# 候选集列表, 存放 100 只蚂蚁的路径(一只蚂蚁一个路径), 一共就 Antcount 个路径，一共是蚂蚁数量*31 个城市数量
candidate = np.zeros((AntCount, city_count)).astype(int)

# path_best 存放的是相应的，每次迭代后的最优路径，每次迭代只有一个值
path_best = np.zeros((MAX_iter, city_count))

# 存放每次迭代的最优距离
distance_best = np.zeros(MAX_iter)
# 倒数矩阵
etable = 1.0 / Distance

while iter < MAX_iter:
    # first：蚂蚁初始点选择
    if AntCount <= city_count:
    # np.random.permutation 随机排列一个数组的
    # x[:,n] 表示在全部数组（维）中取第 n 个数据，直观来说，x[:,n] 就是取所有集合的第 n 个数据,
        candidate[:, 0] = np.random.permutation(range(city_count))[:AntCount]

    else:
        m = AntCount - city_count
        n = 2
        candidate[:city_count, 0] = np.random.permutation(range(city_count))[:]
        while m > city_count:
            candidate[city_count * (n - 1):city_count * n, 0] = np.random.permutation(range(city_count))[:]
            m = m - city_count
            n = n + 1
        candidate[city_count * (n - 1):AntCount, 0] = np.random.permutation(range(city_count))[:m]
    length = np.zeros(AntCount)  # 每次迭代的 N 个蚂蚁的距离值
    # print(candidate)

    # second：选择下一个城市选择
    for i in range(AntCount):
        # 移除已经访问的第一个元素
        unvisit = list(range(city_count))  # 列表形式存储没有访问的城市编号
        visit = candidate[i, 0]  # 当前所在点, 第 i 个蚂蚁在第一个城市
        unvisit.remove(visit)  # 在未访问的城市中移除当前开始的点
        for j in range(1, city_count):  # 访问剩下的 city_count 个城市，city_count 次访问
            protrans = np.zeros(len(unvisit))  # 每次循环都更改当前没有访问的城市的转移概率矩阵 1*30,1*29,1*28...
            # 下一城市的概率函数
            for k in range(len(unvisit)):
                # 计算当前城市到剩余城市的（信息素浓度^alpha）*（城市适应度的倒数）^beta
                # etable[visit][unvisit[k]],(alpha+1) 是倒数分之一，pheromonetable[visit][unvisit[k]] 是从本城市到 k 城市的信息素
                protrans[k] = np.power(pheromonetable[visit][unvisit[k]], alpha) * np.power(
                    etable[visit][unvisit[k]], (alpha + 1))

            # 累计概率，轮盘赌选择
            cumsumprobtrans = (protrans / sum(protrans)).cumsum()
            cumsumprobtrans -= np.random.rand()  # 在 [0,1] 区间内产生一个均匀分布的伪随机r；
            # 求出离随机数产生最近的索引值
            k = unvisit[list(cumsumprobtrans > 0).index(True)]  # 若 q[1]-r>0，则选择个体 1;index() 返回查找对象的索引位置,此处返回 q[1]-r>0 为真的位置
            # 下一个访问城市的索引值
            candidate[i, j] = k
            unvisit.remove(k)
            length[i] += Distance[visit][k]
            visit = k  # 更改出发点，继续选择下一个到达点
        length[i] += Distance[visit][candidate[i, 0]]  # 最后一个城市和第一个城市的距离值也要加进去


    '''
    更新路径等参数
    '''
    # 如果迭代次数为一次，那么无条件让初始值代替 path_best,distance_best.
    if iter == 0:
        distance_best[iter] = length.min()
        path_best[iter] = candidate[length.argmin()].copy()  # argmin() 给出水平方向最小值的下标
    else:
        # 如果当前的解没有之前的解好，那么当前最优还是为之前的那个值；并且用前一个路径替换为当前的最优路径
        if length.min() > distance_best[iter - 1]:
            distance_best[iter] = distance_best[iter - 1]
            path_best[iter] = path_best[iter - 1].copy()  # 拷贝父对象（一级目录），子对象（二级目录）不拷贝，还是引用
        else:  # 当前解比之前的要好，替换当前解和路径
            distance_best[iter] = length.min()
            path_best[iter] = candidate[length.argmin()].copy()

    '''
        信息素的更新
    '''
    # 信息素的增加量矩阵
    changepheromonetable = np.zeros((city_count, city_count))
    for i in range(AntCount):
        for j in range(city_count - 1):
            # 当前路径比如城市 23 之间的信',