[智能计算]蚁群算法针对TSP问题的简明实现(Python)

文章结构概述

• 思维框架
  • Python3 程序代码
  • • 信息组织方式
    • 样本集合
    • 蚁群优化算法

思路大纲

1. 建立一个完整的图结构tsp_map，该结构包含TSP问题中涉及的所有城市及其相互连接的道路。
2. 设定超参数ant_count和iter_num，分别表示参与计算的蚂蚁数量以及整个算法的迭代次数。
3. 在每次迭代过程中，对每只模拟蚂蚁进行路径选择操作，其可能的行为方式有两种：

• 为了避免陷入局部最优解，按照随机概率random_choose选择一个未访问的城市作为下一步的目的地；
• 或者依据信息素浓度与启发式信息共同作用的结果来确定下一个访问的城市；其中d_{ij}表示城市之间的距离、\tau_{ij}代表城市i与城市j之间的信息素浓度、p_{ij}^{k}为蚂蚁k从城市i转移到城市j的概率：
  p_{ij}^{k}=\frac{\tau_{ij}\times d_{ij}^{-1}}{\sum_k{\Delta\tau_{ij}^{k}\times d_{ij}^{-1}}}

\tau_{ij}\times d_{ij}^{-1}还可以通过引入超参数\alpha和$\beta