算法介绍
历史
蚁群优化算法是一种用来在图中寻找优化路径的几率型算法。它由MarcoDorigo于年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。
背景
现实世界中，（初始状态）每个蚂蚁将在一定范围内随机游走，并通过在所经过路径上选留信息素的方式，不断把相关的食物信息反馈给蚁群。如果其他蚂蚁发现了那条路径，那么这些蚂蚁很可能不再保持原来的随机游走，而跟随这条路径**（一条路径上的信息素越多，其他蚂蚁选择这条路径的可能性越大）**。如果由该路径他们最终发现了食物，那么他们将在这条路径上继续增加信息素。由于这条路径上信息素的不断增加，最终所有蚂蚁将找到食物。
算法原理
蚁群算法试验中，在各个蚂蚁在没有事先告诉它们食物在什么地方的前提下开始寻找；
其次，要让蚂蚁找到食物，就需要让它们遍历空间上的所有点；
再次，如果要让蚂蚁找到最短的路找食物。当一只找到食物以后，它会向环境释放一种信息素，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物。
但有些蚂蚁并没有像其它蚂蚁一样总重复同样的路，它们会另辟蹊径，**如果令开辟的道路比原来的其他道路更短，那么更多的蚂蚁被吸引到这条较短的路上来。**最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。
假设，dij为节点i到节点j距离，节点i、j上的信息素含量用τij(t)表示。先选定一个起始节点，将所有u个蚂蚁放在起点处，所有路径上信息素含量相同，蚂蚁k根据各条路径上信息素分布的大小选择下一个移动节点，加入禁忌表List来记录每一只蚂蚁经过节点的顺序，防止蚂蚁再次经过该节点，蚂蚁经过所有指定的节点即完成了一次算法的迭代。在蚂蚁搜索路径节点的过程中，t时刻下，蚂蚁k从节点i移动至节点j的移动概率p为：
其中，allowedk表示蚂蚁k从当前节点移动到下一个所有可能经过节点的集合。
依据上述内容α为信息素启发式因子，代表路径上信息素存在的多少，信息素多表示该路径通过的蚂蚁多，反之少量蚂蚁通过。β为期望启发因子，表示蚂蚁在选择该路径节点重要性的考虑，其值越大，说明移动到此点的几率越大，启发式函数ηij(t)计算方法为：
由上可以看出启发函数ηij(t)和dij对于每一只蚂蚁成反比关系，节点之间的距离越长，启发函数的值越小。当所有的蚂蚁完成一次循环后，各个城市间链接路径上的信息素浓度需进行更新。首先是信息素挥发，其次是蚂蚁在它们所经过的边上释放信息素，其中ρ为信息素挥发系数，且0ρ≤1，计算公式为：
当（i，j）在Lk上
=dij，当蚂蚁构建的路径长度dij越小，则路径上各条边就会获得更多的信息素，则在以后的迭代中就更有可能被其他的蚂蚁选择。每当蚂蚁完成一次循环后，便清空禁忌表，重新回到初始城市，准备下一次周游。
除此之外还可以通过更新改进信息素规则和启发函数可以缩小全局路径和理论最优路径差值。
算步骤
1.对相关参数进行初始化，如蚁群规模（蚂蚁数量）u、信息素重要程度因子α、启发函数重要程度因子β、信息素挥发因子ρ、信息素释放总量Q、最大迭代次数itermax。
2.构建解空间，将各个蚂蚁随机地置于不同的出发点，计算每个蚂蚁k（k=1,2,3…m）下一个待访问城市，直到所有蚂蚁访问完所有城市。
3.更新信息苏计算每个蚂蚁经过路径长度Lk(k=1,2,…，m），记录当前迭代次数中的最优解（最短路径）。同时，对各个城市连接路径上信息素浓度进行更新。
4.判断是否终止若iteritermax，则令iter=iter+1,清空蚂蚁经过路径的记录表，并返回步骤2；否则，终止计算，输出最优解。
