蚁群算法求解旅行商问题（TSP）实现异常求助

问题背景 #

我尝试用蚁群优化算法（Ant Colony Optimisation, ACO）求解旅行商问题（Travelling Salesman Problem, TSP），目前已基于现有认知用Python完成初步实现，但求解结果总距离在76-78之间，远高于已知最优解39，希望帮忙排查代码问题并提供优化建议。

实现思路 #

初始化信息素水平，通过多只“蚂蚁”遍历路径积累信息素，迭代过程中对信息素进行挥发，最终期望得到概率最高的最短路径。

代码实现 #

初始化参数 #

import numpy as np

num_cities = len(distance_matrix)
num_ants = 20
num_iterations = 100
decay = 0.5
alpha = 1  
beta = 2  

pheromone_levels = np.ones((num_cities, num_cities)) * 1e-6

辅助函数 #

def select_next_city(pheromone_levels, distance_matrix, current_city, visited):
    pheromones = pheromone_levels[current_city] ** alpha
    visibility = np.zeros_like(pheromones) 
    for city in range(num_cities):
        if city not in visited and distance_matrix[current_city][city] != 0:
            visibility[city] = (1.0 / distance_matrix[current_city][city]) ** beta
    probabilities = pheromones * visibility
    probabilities_sum = probabilities.sum()
    if probabilities_sum == 0:
        return np.random.choice([city for city in range(num_cities) if city not in visited])
    probabilities /= probabilities_sum
    return np.random.choice(num_cities, p=probabilities)

def update_pheromones(pheromone_levels, routes, scores):
    for i, route in enumerate(routes):
        for j in range(num_cities - 1):
            pheromone_levels[route[j], route[j+1]] += 1 / scores[i]
        pheromone_levels[route[-1], route[0]] += 1 / scores[i]
    pheromone_levels *= (1 - decay) 

核心循环 #

best_route = None
best_distance = float('inf')

for iteration in range(num_iterations):
    routes = []
    distances = []

    for ant in range(num_ants):
        route = [np.random.randint(num_cities)]
        while len(route) < num_cities:
            current_city = route[-1]
            next_city = select_next_city(pheromone_levels, distance_matrix, current_city, route)
            route.append(next_city)
        routes.append(route)
        route_distance = sum(distance_matrix[route[i]][route[i+1]] for i in range(-1, len(route)-1))
        distances.append(route_distance)

        if route_distance < best_distance:
            best_distance = route_distance
            best_route = route

    update_pheromones(pheromone_levels, routes, distances)

print("Best route:", best_route)
print("Best route distance:", best_distance)

问题排查请求 #

当前求解结果远高于已知最优解，恳请帮忙排查代码中可能存在的问题，提供优化方向。

内容的提问来源于stack exchange，提问作者a9302c