蚁群算法及Matlab实现——TSP问题

2744557306

下面是对于代码主要流程的介绍，代码在附件中

• 初始化蚂蚁的起点城市，使用randi函数随机生成m个起点城市，并将其作为路径的第一个城市。
• 构建解空间，即所有城市的索引。
• 对每个蚂蚁进行路径选择，通过禁忌表tabu记录已访问的城市，通过待访问的城市集合allow_index确定可以访问的城市。然后根据信息素Tao和启发式因子Heu_F计算城市间的转移概率P，利用轮盘赌法选择下一个要访问的城市，将该城市加入路径中。逐步完成蚂蚁的路径选择。
• 计算每个蚂蚁的路径距离Length，包括经过的所有城市的距离。
• 计算当前迭代次数下的最短路径距离min_Length和平均距离Length_ave。如果是第一次迭代，则直接将最优路径和距离赋值为当前的蚂蚁最优解。否则，根据动态规划思想，更新最优路径和距离。
• 更新信息素，根据蚂蚁的路径计算信息素增量Delta_Tau。逐个蚂蚁计算每个城市之间的信息素增量，其中Q为常数。
• 更新全局信息素矩阵Tao，将上一次迭代的信息素乘以(1-p)衰减系数，再加上本次迭代计算得到的Delta_Tau。
• 更新迭代次数iter和路径记录表Paths，继续下一次迭代。
  
  % |% m/ _, O. I1 A& U/ m: d

在代码中通过不断更新信息素矩阵和路径选择，尝试找到具有较短路径距离的最优解。

, P$ _+ p! q0 C0 A
# z3 _2 w  G$ y5 r5 o以下是实验结果



0 Y) a. s+ s+ y  i1 p! k
7 Z" T( M3 I" R! M" `