20220120-蚁群算法

发表于 阅读次数： 本文字数： 987 阅读时长 ≈ 1 分钟

蚁群算法

蚁群算法具有分布计算、信息正反馈、启发式搜索特征，本质是进化算法中的一种启发式全局优化算法。蚁群算法应用广泛，如旅行商问题、指派问题、job-shop调度问题、车辆路径问题、图着色问题、网络路由问题等。和传统的路由算法相较，该算法在网络路由中具有信息分布式性、动态性、随机性和异步性等特点，而这些特点正好能满足网络路由的需要。

1. 蚁群算法的特点

  • 高度结构化的组织：虽然蚂蚁的个体行为极其简单，但由个体组成的蚁群却构成高度结构化的社会组织，蚂蚁社会的成员有分工，有相互的通信和信息传递；
  • 自然优化：蚁群在觅食过程中，在没有任何提示下总能找到从蚁巢到事物源之间的最短路径。当经过的路线上出现障碍物时，还能迅速找到新的最优路径；
  • 信息正反馈：蚂蚁在寻找食物时，在其经过的路径上释放信息素（外激素）。蚂蚁基本没有视觉，但能在小范围内察觉同类散发的信息素的轨迹，由此来决定何去何从，并倾向于朝向信息素强度高的方向移动。由于采用正反馈机制，使得搜索过程不断收敛，最终逼近最优解；
  • 自催化行为：某条路径上走过的蚂蚁越多，留下的信息素也越多（随时间蒸发一部分），后来蚂蚁选择该路径的概率也越高。
  • 搜索过程采用分布式计算方式，多个个体同时进行并行计算，大大提高了算法的计算能力和运行效率；
  • 启发式的概率搜索方式不容易陷入局部最优，易于找到全局最优解；

2. 蚁群算法的基本思想

  • 首先根据具体问题设置多只蚂蚁，分头并行搜索；
  • 每只蚂蚁完成一次周游后，在行进的路上释放信息素，信息素量与解的质量成正比；
  • 蚂蚁路径的选择根据信息素强度大小（初始信息素设为相等），同时考虑两点之间的距离，采用随机的局部搜索策略。这使得距离较短的边上的信息素量较大，后来的蚂蚁选择该边的概率也较大；
  • 每只蚂蚁只能走合法线路（经过城市1次且仅1次），为此设置禁忌表来控制；
  • 所有蚂蚁都搜索完一次就是迭代一次，每迭代一次就对所有的边做一次信息素更新，原来的蚂蚁死掉，新的蚂蚁进行新一轮搜索；
  • 更新信息素包括原有信息素的蒸发和经过路径上信息素的增加；
  • 达到预定的迭代步数，或出现停滞现象（所有蚂蚁都选择同样的路径，解不再变化），则算法结束，以当前最优解作为问题的最优解；

3. 需要关注的计算公式