参考链接

https://www.bilibili.com/video/BV13R4y157as?vd_source=7beaef42746f5650c5e06c4c41030865

一、旅行商（TSP）问题

1.例题：

现需要遍历全国共34个城市，请设计遍历方案，访问每一座城市一次，并最终回到起始城市，且总路径最短。

2.问题分析：

  • 模型假设：遍历过程中，两两城市之间的直线距离视为遍历时的最短路径
  • 将每个目的地看作节点，每条路径看作边，整个问题就是图论问题。

    二、蚁群算法介绍

    蚂蚁觅食的过程中，发现蚁群整体会体现一些智能的行为，例如蚁群可以在不同的环境下，寻找最短到达食物源的路径。 后经进一步研究发现，这是因为蚂蚁会在其经过的路径上释放一种可以称之为信息素的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会沿着“信息素”浓度较高路径行走，而每只路过的蚂蚁都会在路上留下“信息素”，这就形成一种类似正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。
    由上述蚂蚁找食物模式演变来的算法，即是蚁群算法。这种算法具有分布计算、信息正反馈和启发式搜索的特征，本质上是进化算法中的一种启发式全局优化算法。 最近几年，该算法在网络路由中的应用受到越来越多学者的关注，并提出了一些新的基于蚂蚁算法的路由算法。同传统的路由算法相比较，该算法在网络路由中具有信息分布式性、动态性、随机性和异步性等特点，而这些特点正好能满足网络路由的需要。
    image.png

    算法步骤

    image.png
    image.png
    image.png
    image.png
    image.png
    image.png

    三、论文应用

    最佳旅游路线的选择模型.pdf
    image.png
    image.png
    image.png

    算法步骤：（论文中要画算法流程图）

    image.png
    image.png