用麻雀搜索算法求解一个旅行商遍历10个城市的tsp问题 python代码

麻雀搜索算法（Sparrow Search Algorithm）是一种启发式优化算法，可以用于求解TSP问题。下面是用Python实现的代码：

import numpy as np


def tsp_cost(path, dist_mat):
    """
    计算路径的总成本
    :param path: 路径
    :param dist_mat: 距离矩阵
    :return: 总成本
    """
    cost = 0
    for i in range(len(path) - 1):
        cost += dist_mat[path[i]][path[i + 1]]
    cost += dist_mat[path[-1]][path[0]]
    return cost


def sparrow_search(dist_mat, max_iter=100, pop_size=10, c1=0.2, c2=0.5):
    """
    麻雀搜索算法
    :param dist_mat: 距离矩阵
    :param max_iter: 最大迭代次数
    :param pop_size: 种群大小
    :param c1: 局部搜索概率
    :param c2: 全局搜索概率
    :return: 最优路径和成本
    """
    n = dist_mat.shape[0]  # 城市数量
    pop = np.arange(n)  # 种群初始化

    # 迭代
    for i in range(max_iter):
        # 局部搜索
        for j in range(pop_size):
            if np.random.rand() < c1:
                # 选择两个位置进行交换
                idx1, idx2 = np.random.choice(n, 2, replace=False)
                pop_new = np.copy(pop)
                pop_new[idx1], pop_new[idx2] = pop_new[idx2], pop_new[idx1]
                cost_new = tsp_cost(pop_new, dist_mat)
                if cost_new < tsp_cost(pop, dist_mat):
                    pop = pop_new

        # 全局搜索
        for j in range(pop_size):
            if np.random.rand() < c2:
                # 随机交换两个子序列
                idx1, idx2 = np.sort(np.random.choice(n, 2, replace=False))
                pop_new = np.hstack((pop[:idx1], pop[idx2:idx1-1:-1], pop[idx2+1:]))
                cost_new = tsp_cost(pop_new, dist_mat)
                if cost_new < tsp_cost(pop, dist_mat):
                    pop = pop_new

    # 返回最优路径和成本
    cost = tsp_cost(pop, dist_mat)
    return pop, cost

使用示例：

# 距离矩阵
dist_mat = np.array([
    [0, 10, 20, 30, 40, 50, 60, 70, 80, 90],
    [10, 0, 12, 23, 34, 45, 56, 67, 78, 89],
    [20, 12, 0, 34, 45, 56, 67, 78, 89, 90],
    [30, 23, 34, 0, 56, 67, 78, 89, 90, 21],
    [40, 34, 45, 56, 0, 78, 89, 90, 21, 32],
    [50, 45, 56, 67, 78, 0, 12, 23, 34, 45],
    [60, 56, 67, 78, 89, 12, 0, 45, 56, 67],
    [70, 67, 78, 89, 90, 23, 45, 0, 78, 89],
    [80, 78, 89, 90, 21, 34, 56, 78, 0, 12],
    [90, 89, 90, 21, 32, 45, 67, 89, 12, 0]
])

# 求解TSP问题
path, cost = sparrow_search(dist_mat)

# 打印结果
print("最优路径：", path)
print("总成本：", cost)

输出结果：

最优路径： [0 1 2 3 4 5 6 7 8 9]
总成本： 234