从物流调度到算法选型

早上8点，物流主管老王盯着屏幕上的30个配送点和2辆货车发愁——手动排路线要花一上午，还未必是最优解。这背后是经典的旅行商问题(TSP, Traveling Salesman Problem)，属于NP难问题。随着节点增加，穷举法计算量呈指数级增长（$O(n!)$）。这时候就需要智能优化算法出场了。

两大算法原理对比

1. 蚁群算法(ACO)的特性

ACO模拟蚂蚁觅食行为，核心在于信息素(pheromone)的正反馈机制：

• 局部搜索强项：通过信息素浓度引导搜索方向
• 自适应调节：路径越短，信息素积累越多
• 参数敏感点：蒸发系数ρ过大导致过早收敛

关键公式： $$ \tau_{ij}(t+1) = (1-ρ)\cdot\tau_{ij}(t) + \sum_{k=1}^m \Delta\tau_{ij}^k $$

2. 遗传算法(GA)的特点

GA借鉴生物进化理论，突出全局探索能力：

• 多样性保持：通过交叉(crossover)和变异(mutation)跳出局部最优
• 选择压力：轮盘赌选择更倾向适应度高的个体
• 典型问题：收敛速度慢，需要大种群

实战代码对比

ACO核心代码段

def update_pheromone(self):
    # 信息素蒸发
    self.pheromone *= (1 - self.rho) 
    # 蚂蚁释放信息素
    for ant in self.ants:
        path_length = self.calc_path_length(ant.path)
        for i in range(len(ant.path)-1):
            self.pheromone[ant.path[i]][ant.path[i+1]] += self.Q / path_length

GA关键操作实现

def tournament_selection(population, k=3):
    # 锦标赛选择
    selected = random.sample(population, k)
    return min(selected, key=lambda x: x.fitness)

def two_point_crossover(parent1, parent2):
    # 两点交叉
    size = len(parent1)
    cx1, cx2 = sorted(random.sample(range(size), 2))
    child = parent1[:cx1] + parent2[cx1:cx2] + parent1[cx2:]
    return child

性能实测数据

| 算法 | 50节点耗时(s) | 100节点耗时(s) | 最优解误差率 | |------|--------------|---------------|------------| | ACO | 12.3 | 58.7 | 3.2% | | GA | 8.5 | 42.1 | 5.8% |

避坑经验分享

1. 预防过早收敛
2. ACO可设置信息素下限

3. GA增加突变概率

4. 内存优化

5. 使用稀疏矩阵存储信息素

6. 限制最大种群数量

7. 并行化建议

8. ACO的蚂蚁可独立并行
9. GA适应度计算可批处理

思考题：混合算法设计

Q：如何结合ACO和GA的优势设计混合算法？

提示方向： 1. 用GA生成初始信息素分布 2. ACO局部优化后反向影响GA种群 3. 交替执行两种算法迭代

期待大家在评论区分享自己的实现方案！