ACS蚁群算法最佳路径收敛不理想，达不到预期

Question

算法来源

算法来自论文 AntColonySystem:ACooperativeLearning ApproachtotheTravelingSalesmanProblem
测试集来自于【路径规划】全局路径规划算法——蚁群算法（含python实现），最优解里面的算法可以求得到

主要问题

参数我改了很多次，但是达不到最优解解，每次只差一点，而且运行效率也很慢，需要大量的迭代次数，有没有同行帮忙看看是不是算法设计出差错了。

下面是我的源代码

import numpy as np
import matplotlib.pyplot as plt


# 城市坐标(52个城市)
coordinates = np.array([[565.0,575.0],[25.0,185.0],[345.0,750.0],[945.0,685.0],[845.0,655.0],
            [880.0,660.0],[25.0,230.0],[525.0,1000.0],[580.0,1175.0],[650.0,1130.0],
            [1605.0,620.0],[1220.0,580.0],[1465.0,200.0],[1530.0,  5.0],[845.0,680.0],
            [725.0,370.0],[145.0,665.0],[415.0,635.0],[510.0,875.0],[560.0,365.0],
            [300.0,465.0],[520.0,585.0],[480.0,415.0],[835.0,625.0],[975.0,580.0],
            [1215.0,245.0],[1320.0,315.0],[1250.0,400.0],[660.0,180.0],[410.0,250.0],
            [420.0,555.0],[575.0,665.0],[1150.0,1160.0],[700.0,580.0],[685.0,595.0],
            [685.0,610.0],[770.0,610.0],[795.0,645.0],[720.0,635.0],[760.0,650.0],
            [475.0,960.0],[95.0,260.0],[875.0,920.0],[700.0,500.0],[555.0,815.0],
            [830.0,485.0],[1170.0, 65.0],[830.0,610.0],[605.0,625.0],[595.0,360.0],
            [1340.0,725.0],[1740.0,245.0]])

def getdistmat(coordinates):
    num = coordinates.shape[0]
    distmat = np.zeros((52, 52))
    for i in range(num):
        for j in range(i, num):
            distmat[i][j] = distmat[j][i] = np.linalg.norm(
                coordinates[i] - coordinates[j])
    return distmat


# #//初始化
distmat = getdistmat(coordinates)
numant = 45 ##// 蚂蚁个数
numcity = coordinates.shape[0] ##// 城市个数
alpha = 1 ##// 信息素重要程度因子
beta = 5 ##// 启发函数重要程度因子
rho = 0.1 ##// 信息素的挥发速度
Q = 1 ##//信息素释放总量
iter = 0##//循环次数
itermax = 200#//循环最大值
etatable = 1.0 / (distmat + np.diag([1e10] * numcity)) #// 启发函数矩阵，表示蚂蚁从城市i转移到矩阵j的期望程度
pheromonetable = np.ones((numcity, numcity)) #// 信息素矩阵
pathtable = np.zeros((numant, numcity)).astype(int) #// 路径记录表
distmat = getdistmat(coordinates) #// 城市的距离矩阵
lengthaver = np.zeros(itermax) #// 各代路径的平均长度
lengthbest = np.zeros(itermax) #// 各代及其之前遇到的最佳路径长度
pathbest = np.zeros((itermax, numcity)) #// 各代及其之前遇到的最佳路径长度
#//核心点-循环迭代
while iter < itermax:
    #// 随机产生各个蚂蚁的起点城市
    if numant <= numcity:
        #// 城市数比蚂蚁数多
        pathtable[:, 0] = np.random.permutation(range(0, numcity))[:numant]
    else:
        #// 蚂蚁数比城市数多，需要补足
        pathtable[:numcity, 0] = np.random.permutation(range(0, numcity))[:]
        pathtable[numcity:, 0] = np.random.permutation(range(0, numcity))[
            :numant - numcity]
    length = np.zeros(numant)  # 计算各个蚂蚁的路径距离
    for i in range(numant):
        visiting = pathtable[i, 0]  # 当前所在的城市
        unvisited = set(range(numcity))  # 未访问的城市,以集合的形式存储{}
        unvisited.remove(visiting)  # 删除元素；利用集合的remove方法删除存储的数据内容
        for j in range(1, numcity):  # 循环numcity-1次，访问剩余的numcity-1个城市
            # 每次用轮盘法选择下一个要访问的城市
            listunvisited = list(unvisited)
            probtrans = np.zeros(len(listunvisited))
            for k in range(len(listunvisited)):
                probtrans[k] = np.power(pheromonetable[visiting][listunvisited[k]], alpha) \
                    * np.power(etatable[visiting][listunvisited[k]], beta)
            cumsumprobtrans = (probtrans / sum(probtrans)).cumsum()
            cumsumprobtrans -= np.random.rand()
            k = listunvisited[(np.where(cumsumprobtrans > 0)[0])[0]]
            # 元素的提取（也就是下一轮选的城市）
            pathtable[i, j] = k  # 添加到路径表中（也就是蚂蚁走过的路径)
            unvisited.remove(k)  # 然后在为访问城市set中remove（）删除掉该城市
            length[i] += distmat[visiting][k]
            visiting = k
        # 蚂蚁的路径距离包括最后一个城市和第一个城市的距离
        length[i] += distmat[visiting][pathtable[i, 0]]
        # 包含所有蚂蚁的一个迭代结束后，统计本次迭代的若干统计参数
    lengthaver[iter] = length.mean()
    if iter == 0:
        lengthbest[iter] = length.min()
        pathbest[iter] = pathtable[length.argmin()].copy()
    else:
        if length.min() > lengthbest[iter - 1]:
            lengthbest[iter] = lengthbest[iter - 1]
            pathbest[iter] = pathbest[iter - 1].copy()
        else:
            lengthbest[iter] = length.min()
            pathbest[iter] = pathtable[length.argmin()].copy()
    # 更新信息素
    changepheromonetable = np.zeros((numcity, numcity))
    for i in range(numant):
        for j in range(numcity - 1):
            changepheromonetable[pathtable[i, j]][pathtable[i, j + 1]] += Q / distmat[pathtable[i, j]][
                pathtable[i, j + 1]]  # 计算信息素增量
        changepheromonetable[pathtable[i, j + 1]][pathtable[i, 0]] += Q / distmat[pathtable[i, j + 1]][pathtable[i, 0]]
    pheromonetable = (1 - rho) * pheromonetable + \
        changepheromonetable  # 计算信息素公式
    if iter%30==0:
        print("iter(迭代次数):", iter)
    iter += 1  # 迭代次数指示器+1

# 做出平均路径长度和最优路径长度
fig, axes = plt.subplots(nrows=2, ncols=1, figsize=(12, 10))
axes[0].plot(lengthaver, 'k', marker=u'')
axes[0].set_title('Average Length')
axes[0].set_xlabel(u'iteration')

axes[1].plot(lengthbest, 'k', marker=u'')
axes[1].set_title('Best Length')
axes[1].set_xlabel(u'iteration')
fig.savefig('average_best.png', dpi=500, bbox_inches='tight')
plt.show()

# 作出找到的最优路径图
bestpath = pathbest[-1]
plt.plot(coordinates[:, 0], coordinates[:, 1], 'r.', marker=u'$\cdot$')
plt.xlim([-100, 2000])
plt.ylim([-100, 1500])

for i in range(numcity - 1):
    m = int(bestpath[i])
    n = int(bestpath[i + 1])
    plt.plot([coordinates[m][0], coordinates[n][0]], [
             coordinates[m][1], coordinates[n][1]], 'k')
plt.plot([coordinates[int(bestpath[0])][0], coordinates[int(n)][0]],
         [coordinates[int(bestpath[0])][1], coordinates[int(n)][1]], 'b')
ax = plt.gca()
ax.set_title("Best Path")
ax.set_xlabel('X axis')
ax.set_ylabel('Y_axis')

plt.savefig('best path.png', dpi=500, bbox_inches='tight')
plt.show()

直接运行就行了，可能有点慢，参数区的参数都是可以调节的

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

针对您所描述的问题，可以从以下几个方面进行分析和优化：

1. 参数调整：不同的参数设置会影响到算法的效果。对于蚁群算法来说，参数的选择十分重要，您可以针对以下几个参数进行调整：信息素挥发速度（rho）、信息素释放总量（Q）、信息素重要程度因子（alpha）和启发函数重要程度因子（beta）。每个参数的具体调整方式和范围需要根据实际问题来确定，可以通过试验不同的参数组合来找到最优的参数设置。
2. 算法实现细节：检查算法的实现细节是否正确。例如，路径选择过程中是否正确地使用了信息素和启发函数，信息素的更新是否正确等。有时候算法实现中的小错误可能会导致算法效果不佳。
3. 算法收敛性：蚁群算法是一种启发式算法，其求解过程不一定能够收敛到全局最优解。您可以考虑增加迭代次数来观察算法的收敛情况。此外，还可以使用其他的优化技巧来提高算法的求解效率，例如使用启发式函数来引导蚂蚁选择更优的路径。
4. 测试集选择：确保您使用的测试集能够反映问题的真实情况，并且具有足够的多样性。有时候测试集过于简单或者过于复杂都会导致算法效果不佳。
5. 分析和可视化：您可以对算法的运行过程进行可视化分析，例如绘制出每次迭代的平均路径长度和最优路径长度，以及找到的最优路径等。这有助于您更好地理解算法的运行过程和发现潜在的问题。同时，您也可以通过分析算法的中间结果来发现可能的改进方向。

最后，针对您的代码实现，我注意到以下几点可能存在的问题和改进建议：

• 在初始化蚂蚁的路径时，对于蚂蚁数多于城市数的情况，您使用随机选择城市作为起点，但没有处理可能存在的重复起点的情况。这可能导致一些蚂蚁在路径规划中从一开始就存在错误。建议您在处理重复起点时使用合适的策略来保证每个蚂蚁的起点都是唯一的。
• 在更新信息素时，您的代码似乎只考虑了蚂蚁走过的路径，而没有考虑未访问的城市或路径上的其他城市之间的信息素传递。您可以考虑在更新信息素时加入这些因素来增强算法的搜索能力。

希望以上建议能够帮助您优化蚁群算法的效果。如果您还有其他问题或需要进一步的帮助，请随时提问。