当前位置：首页 > article >正文

蚁群算法（ACO算法）求解实例---旅行商问题 (TSP)

article 2024/11/15 11:10:37

一、采用ACO求解 TSP
二、旅行商问题
- 2.1 实际例子：求解 6 个城市的 TSP
- 2.2 ==**求解该问题的代码**==
- 2.3 代码运行过程截屏
- 2.4 代码运行结果截屏（后续和其他算法进行对比）
三、 ==如何修改代码？==
- 3.1 减少城市坐标，如下：
- 3.2 增加城市坐标，如下：
四、蚁群算法 (Ant Colony Optimization, ACO) 原理
- 4.1 ACO算法定义
- 4.2 ACO算法的基本思想
- 4.3 ACO算法的工作原理
- 4.4 ACO算法的参数
- 4.5 ACO算法的优缺点
- - 4.5.1 优点
  - 4.5.2 缺点
- 4.6 ACO算法的应用场景

一、采用ACO求解 TSP

求解代码在文中，后续会出其他算法求解TSP问题，你们参加数学建模竞赛只需要会改代码即可。

用来对比此专栏的
遗传算法（GA算法）求解实例—旅行商问题 (TSP)
粒子群算法（PSO算法）求解实例—旅行商问题 (TSP)
模拟退火算法（SA算法）求解实例—旅行商问题 (TSP)
注意每次运行SA算法得到的结果可能不太一样。

我知道大家对原理性的东西不感兴趣，我把原理性的东西放在后面，大家如果需要写数模论文可以拿去，但是记得需要改一改，要不然查重过不去。

二、旅行商问题

2.1 实际例子：求解 6 个城市的 TSP

假设有 6 个城市，其坐标如下：

城市	X 坐标	Y 坐标
0	10	20
1	30	40
2	20	10
3	40	30
4	10	10
5	50	20

目标是找到一个经过所有城市且总距离最短的路径。

2.2 求解该问题的代码

import numpy as np
import random

# 定义城市坐标
cities = np.array([
    [10, 20],
    [30, 40],
    [20, 10],
    [40, 30],
    [10, 10],
    [50, 20]
])


# 计算两城市之间的欧几里得距离
def calculate_distance(city1, city2):
    return np.sqrt(np.sum((city1 - city2) ** 2))


# 计算所有城市之间的距离矩阵
def calculate_distance_matrix(cities):
    num_cities = len(cities)
    distance_matrix = np.zeros((num_cities, num_cities))
    for i in range(num_cities):
        for j in range(num_cities):
            if i != j:
                distance_matrix[i][j] = calculate_distance(cities[i], cities[j])
    return distance_matrix


# 蚁群算法主函数
def ant_colony_optimization(cities, num_ants=10, num_iterations=100, alpha=1.0, beta=2.0, evaporation_rate=0.5, Q=100):
    num_cities = len(cities)
    distance_matrix = calculate_distance_matrix(cities)

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

    # 存储最佳路径和最短距离
    best_path = None
    best_distance = float('inf')

    for iteration in range(num_iterations):
        all_paths = []
        all_distances = []

        # 每只蚂蚁构建一条路径
        for ant in range(num_ants):
            # 随机选择起始城市
            current_city = random.randint(0, num_cities - 1)
            path = [current_city]
            visited = set(path)

            # 构建路径
            for _ in range(num_cities - 1):
                probabilities = []
                for next_city in range(num_cities):
                    if next_city not in visited:
                        pheromone = pheromone_matrix[current_city][next_city] ** alpha
                        visibility = (1.0 / distance_matrix[current_city][next_city]) ** beta
                        probabilities.append((next_city, pheromone * visibility))

                # 选择下一个城市
                next_city = random.choices(
                    [city for city, _ in probabilities],
                    [prob for _, prob in probabilities]
                )[0]

                path.append(next_city)
                visited.add(next_city)
                current_city = next_city

            # 计算路径距离并存储
            path_distance = sum(distance_matrix[path[i], path[i + 1]] for i in range(num_cities - 1))
            path_distance += distance_matrix[path[-1], path[0]]  # 回到起点
            all_paths.append(path)
            all_distances.append(path_distance)

            # 更新全局最优路径
            if path_distance < best_distance:
                best_distance = path_distance
                best_path = path

        # 更新信息素矩阵
        pheromone_matrix *= (1 - evaporation_rate)
        for path, distance in zip(all_paths, all_distances):
            for i in range(num_cities - 1):
                pheromone_matrix[path[i]][path[i + 1]] += Q / distance
            pheromone_matrix[path[-1]][path[0]] += Q / distance

        print(f"Iteration {iteration + 1}: Best distance = {best_distance:.2f}")

    return best_path, best_distance


# 运行蚁群算法
best_path, best_distance = ant_colony_optimization(cities)
print("Best path:", best_path)
print("Best distance:", best_distance)

2.3 代码运行过程截屏

在这里插入图片描述

2.4 代码运行结果截屏（后续和其他算法进行对比）

在这里插入图片描述

三、如何修改代码？

这一部分是重中之重，大家参加数学建模肯定是想跑出自己的结果，所以大家只需要把自己遇到的数学问题，抽象成TSP问题，然后修改代码的城市坐标，然后运行即可。

# 定义城市坐标
cities = np.array([
    [10, 20],
    [30, 40],
    [20, 10],
    [40, 30],
    [10, 10],
    [50, 20]
])

3.1 减少城市坐标，如下：

# 定义城市坐标
cities = np.array([
    [10, 20],
    [30, 40],
    [20, 10],
    [40, 30]
])

3.2 增加城市坐标，如下：

# 定义城市坐标
cities = np.array([
    [10, 20],
    [30, 40],
    [20, 10],
    [40, 30],
    [30, 40],
    [20, 10],
    [10, 10],
    [50, 20]
])

四、蚁群算法 (Ant Colony Optimization, ACO) 原理

4.1 ACO算法定义

蚁群算法 (Ant Colony Optimization, ACO) 是一种基于群体智能的优化算法，由 Marco Dorigo 于 1992 年提出。蚁群算法模拟了自然界中蚂蚁群体寻找最短路径的行为，利用蚂蚁在行走过程中留下的信息素来引导后续蚂蚁选择路径。通过不断迭代和信息素更新，算法逐渐找到问题的最优解或近似最优解。ACO 主要用于求解组合优化问题，如旅行商问题 (TSP)、背包问题、车辆路径问题等。

4.2 ACO算法的基本思想

蚁群算法的核心思想是利用信息素 (Pheromone) 的正反馈机制来逐步优化解。蚂蚁在行走过程中会释放信息素，信息素的浓度与路径的质量（通常是路径的长度或花费的时间）有关。路径越短，信息素越浓，后续蚂蚁选择该路径的概率就越高。这种机制可以通过多次迭代不断强化优质路径，逐渐逼近最优解。

4.3 ACO算法的工作原理

初始化：
- 在图的每条边上初始化一个较小的信息素值，表示蚂蚁可以选择的路径。
- 设置蚂蚁数量、最大迭代次数、信息素挥发系数、信息素重要性因子 α 和启发信息重要性因子 β 等参数。
蚂蚁构建解：
- 每只蚂蚁从随机选择的起始节点出发，按照一定的概率规则选择下一个节点（城市）。
- 选择下一个节点的概率 P_{ij} 由信息素浓度和启发信息共同决定：
  $P_{ij} = \frac{(\tau_{ij})^\alpha \cdot (\eta_{ij})^\beta}{\sum_{k \in \text{allowed}} (\tau_{ik})^\alpha \cdot (\eta_{ik})^\beta}$
  其中：
  - $\tau_{ij}$ 是节点 $i$ 和 $j$ 之间的信息素浓度。
  - $\eta_{ij} = \frac{1}{d_{ij}}$ 是节点 $i$ 和 $j$ 之间距离的倒数，表示启发信息（距离越短，选择的概率越大）。
  - $\alpha$ 和 $\beta$ 分别是信息素和启发信息的重要性因子。
路径评估：
- 每只蚂蚁在构建完一条完整路径后，计算路径的总距离（或其他目标函数值）。
信息素更新：
- 信息素挥发：为了避免信息素无限积累，所有路径上的信息素会以一定比例挥发：
  $\tau_{ij} \leftarrow (1 - \rho) \cdot \tau_{ij}$
  其中，(\rho) 是信息素挥发系数，取值在 (0, 1) 之间。
- 信息素增量：每只蚂蚁根据其找到的路径长度在路径上留下信息素：
  $\tau_{ij} \leftarrow \tau_{ij} + \sum_{\text{所有蚂蚁}} \Delta \tau_{ij}^{k}$
  其中， $\Delta \tau_{ij}^{k} = \frac{Q}{L^{k}}$ ， $L^{k}$ 是蚂蚁 $k$ 找到的路径长度， $Q$ 是常数。
迭代和终止：
- 重复步骤 2-4，直到达到最大迭代次数或找到满意解。