蚁群算法求解城市路线 - Python 代码实现

以下是使用蚁群算法求解城市1到城市8的最优路线的 Python 代码：

import numpy as np

# 设置参数
num_cities = 8  # 城市数量
num_ants = 10  # 蚂蚁数量
alpha = 1.0  # 信息素重要程度
beta = 5.0  # 启发式因子重要程度
rho = 0.5  # 信息素蒸发因子
Q = 100  # 信息素增加强度
num_iterations = 100  # 迭代次数

# 城市距离矩阵
distance_matrix = np.array([[0, 3, 4, 5, 6, 7, 8, 9],
                            [3, 0, 2, 3, 4, 5, 6, 7],
                            [4, 2, 0, 1, 2, 3, 4, 5],
                            [5, 3, 1, 0, 1, 2, 3, 4],
                            [6, 4, 2, 1, 0, 1, 2, 3],
                            [7, 5, 3, 2, 1, 0, 1, 2],
                            [8, 6, 4, 3, 2, 1, 0, 1],
                            [9, 7, 5, 4, 3, 2, 1, 0]])

# 初始化信息素矩阵
pheromone_matrix = np.ones((num_cities, num_cities))

# 迭代寻找最优路线
best_path = None
best_distance = float('inf')

for iteration in range(num_iterations):
    # 初始化蚂蚁路线
ant_paths = np.zeros((num_ants, num_cities), dtype=int)

    # 每只蚂蚁按概率选择下一个城市
    for ant in range(num_ants):
        visited_cities = set()  # 已访问城市的集合
        current_city = np.random.randint(0, num_cities)  # 随机选择起始城市
        visited_cities.add(current_city)
        ant_paths[ant, 0] = current_city

        for step in range(1, num_cities):
            unvisited_cities = np.array(list(set(range(num_cities)) - visited_cities))
            next_city = -1

            if np.random.rand() < 0.9:
                # 按信息素和启发式因子选择下一个城市
                probabilities = np.zeros(len(unvisited_cities))

                for i, city in enumerate(unvisited_cities):
                    probabilities[i] = (pheromone_matrix[current_city, city] ** alpha) * \
                                       ((1.0 / distance_matrix[current_city, city]) ** beta)

                probabilities /= np.sum(probabilities)
                next_city = np.random.choice(unvisited_cities, p=probabilities)
            else:
                # 随机选择下一个城市
                next_city = np.random.choice(unvisited_cities)

            ant_paths[ant, step] = next_city
            visited_cities.add(next_city)
            current_city = next_city

    # 计算蚂蚁路径的总距离
    path_distances = np.zeros(num_ants)

    for ant in range(num_ants):
        path = ant_paths[ant]
        path_distances[ant] = np.sum(distance_matrix[path[:-1], path[1:]])

    # 更新最优路径
    if np.min(path_distances) < best_distance:
        best_distance = np.min(path_distances)
        best_path = ant_paths[np.argmin(path_distances)]

    # 更新信息素矩阵
    pheromone_matrix *= (1 - rho)

    for ant in range(num_ants):
        path = ant_paths[ant]
        for i in range(num_cities - 1):
            pheromone_matrix[path[i], path[i+1]] += (Q / path_distances[ant])

# 输出最终路线和距离
print('最终路线：', best_path + 1)  # 加1是因为城市编号从1开始
print('最短距离：', best_distance)

注意，以上代码中，城市编号从0开始，最终输出的最优路线需要将每个城市的编号加1才能得到1到8的城市顺序。