第2课：蚁群算法

1. 蚁群算法的生物学背景

蚁群算法（Ant Colony Optimization, ACO）由 Marco Dorigo 于 1992 年提出，灵感来源于自然界蚂蚁的觅食行为。蚂蚁在觅食过程中会释放信息素，形成一条"气味走廊"。较短路径上的蚂蚁往返更快，信息素积累更多，从而吸引更多蚂蚁——这是一个典型的正反馈过程。

2. ACO 数学模型

蚂蚁 k 从城市 i 选择下一城市 j 的概率为：

其中：

• τ_ij：边(i,j)上的信息素浓度
• η_ij = 1/d_ij：启发式信息（距离的倒数）
• α：信息素重要程度（通常1-2）
• β：启发式信息重要程度（通常2-5）

信息素更新规则：

• ρ ∈ (0,1)：信息素挥发系数
• Q：信息素强度常数
• L_k：蚂蚁 k 的路径总长度

3. 算法流程

1. 初始化信息素矩阵 τ_ij = τ_0
2. 对每只蚂蚁：根据概率规则构造完整路径
3. 计算所有蚂蚁的路径长度
4. 信息素挥发：τ_ij ← (1-ρ)·τ_ij
5. 信息素更新：τ_ij += Σ Δτ_ij^k
6. 记录最优解，返回步骤2

4. 参数选择指南

5. Python实现：ACO求解TSP

import random, math
random.seed(42)

# 蚁群优化(ACO)求解TSP
cities = [(random.uniform(0,100), random.uniform(0,100)) for _ in range(15)]
n = len(cities)

def dist(i, j):
    return math.hypot(cities[i][0]-cities[j][0], cities[i][1]-cities[j][1])

# 距离矩阵
D = [[dist(i,j) for j in range(n)] for i in range(n)]

# 信息素矩阵
tau = [[1.0]*n for _ in range(n)]
rho = 0.1  # 挥发率
Q = 100
alpha, beta = 1, 2

best_path = None
best_len = float('inf')

for iteration in range(50):
    paths = []
    for ant in range(20):
        visited = [random.randint(0, n-1)]
        while len(visited) < n:
            cur = visited[-1]
            probs = []
            for j in range(n):
                if j in visited: probs.append(0)
                else: probs.append((tau[cur][j]**alpha) * ((1/D[cur][j])**beta))
            s = sum(probs)
            if s == 0: break
            probs = [p/s for p in probs]
            r = random.random()
            cum = 0
            nxt = 0
            for j, p in enumerate(probs):
                cum += p
                if cum >= r: nxt = j; break
            visited.append(nxt)
        length = sum(D[visited[i]][visited[i+1]] for i in range(n-1)) + D[visited[-1]][visited[0]]
        paths.append((visited, length))
        if length < best_len:
            best_len = length
            best_path = visited[:]
    # 挥发
    for i in range(n):
        for j in range(n):
            tau[i][j] *= (1-rho)
    # 更新信息素
    for path, length in paths:
        for i in range(n-1):
            tau[path[i]][path[i+1]] += Q/length
            tau[path[i+1]][path[i]] += Q/length
        tau[path[-1]][path[0]] += Q/length
        tau[path[0]][path[-1]] += Q/length
    if iteration % 10 == 0:
        print(f"迭代 {iteration:3d}: 最优路径长度 = {best_len:.2f}")

print(f"\\n最终最优路径长度: {best_len:.2f}")
print(f"最优路径: {' → '.join(str(c) for c in best_path)} → {best_path[0]}")
print("✅ 验证通过：蚁群算法成功收敛到较短路径")

迭代   0: 最优路径长度 = 407.71
迭代  10: 最优路径长度 = 284.91
迭代  20: 最优路径长度 = 284.91
迭代  30: 最优路径长度 = 284.91
迭代  40: 最优路径长度 = 284.91

最终最优路径长度: 284.91
最优路径: 4 → 11 → 1 → 13 → 6 → 5 → 8 → 7 → 2 → 10 → 14 → 12 → 3 → 9 → 0 → 4
✅ 验证通过：蚁群算法成功收敛到较短路径

6. ACO变体

7. 练习

9. ACO的收敛性分析

ACO的收敛性已被严格证明。在信息素挥发率 ρ > 0 的条件下：

收敛速度与以下因素相关：

• 蚂蚁数量m：越多收敛概率越高，但计算开销越大
• 挥发率ρ：越大收敛越快但可能早熟，越小越慢但更可靠
• 问题规模n：城市数增加时收敛所需迭代次数超线性增长

10. ACO在实际问题中的应用案例