• 日期: 2026-09-03 18:27:00
  • 标签: 常规

本实验主要目的是使用蚁群算法解决旅行商问题（TSP），即给定若干城市之间的距离，如何求出经过每个城市且距离最短的路径。通过本实验可以学习到蚁群算法的基本原理和实现方法，以及如何使用Python实现该算法。同时，还可以了解到TSP问题的应用背景和解决方法。

具体实现步骤如下：

  1. 读入城市的坐标信息，并计算出城市之间的距离矩阵。

  2. 设定蚂蚁数量、信息素重要程度因子、启发函数重要程度因子、挥发速度等参数，并初始化信息素矩阵。

  3. 迭代过程中，首先随机选择起始点，并依次选择下一个访问的城市。每个城市的选择是根据信息素和启发函数计算出的概率进行轮盘赌选择的。

  4. 每个蚂蚁走完所有城市后，更新路径等参数，包括记录最优路径和距离值，并根据蚂蚁的路径更新信息素矩阵。

  5. 迭代完成后，输出最优路径和距离值，并绘制路线图和距离迭代图。

通过本实验可以加深对蚁群算法的理解，同时也可以了解到如何使用Python实现该算法，并将其应用于解决实际问题。

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之间的信息素的增量：1/当前蚂蚁行走的总距离的信息素
            changepheromonetable[candidate[i, j]][candidate[i][j + 1]] += Q / length[i]
            #Distance[candidate[i, j]][candidate[i, j + 1]]
        #最后一个城市和第一个城市的信息素增加量
        changepheromonetable[candidate[i, j + 1]][candidate[i, 0]] += Q / length[i]
    #信息素更新的公式：
    pheromonetable = (1 - rho) * pheromonetable + changepheromonetable
    iter += 1

print("蚁群算法的最优路径",path_best[-1]+1)
print("迭代", MAX_iter,"次后","蚁群算法求得最优解",distance_best[-1])

# 路线图绘制
fig = plt.figure()
plt.title("Best roadmap")
x = []
y = []
path = []
for i in range(len(path_best[-1])):
    x.append(city_condition[int(path_best[-1][i])][0])
    y.append(city_condition[int(path_best[-1][i])][1])
    path.append(int(path_best[-1][i])+1)
x.append(x[0])
y.append(y[0])
path.append(path[0])
for i in range(len(x)):
    plt.annotate(path[i], xy=(x[i], y[i]), xytext=(x[i] + 0.3, y[i] + 0.3)) #注释，xy：被注释的坐标点，二维元组形如(x,y)；xytext：注释文本的坐标点，也是二维元组，默认与xy相同
plt.plot(x, y,'-o')

# 距离迭代图
fig = plt.figure()
#plt.figure语()---在plt中绘制一张图片
plt.title("Distance iteration graph")#距离迭代图
plt.plot(range(1, len(distance_best) + 1), distance_best)
plt.xlabel("Number of iterations")#迭代次数
plt.ylabel("Distance value")#距离值
plt.show()  写书该实验的实验目的
蚁群算法解决旅行商问题(TSP) - Python 实现与应用

原文地址: https://www.cveoy.top/t/topic/nxT4 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录