蚁群算法

  蚁群算法是上世纪90年代初由M. Dorigo等学者提出的一种利用蚂蚁觅食行为的内在机制来求解复杂问题的方法。在研究蚂蚁觅食行为的过程中,人们发现,尽管单只蚂蚁的能力十分有限,而整个蚁群却能在觅食过程中发现从蚁巢到食物源的最短路径。蚂蚁能够通过一种称为“媒介质”(stigmergy)的机制来解决复杂问题:每当蚂蚁发现了一条通往食物源的路径,它就会向该路径上释放一定量的化学物质——信息素。同时,随后的蚂蚁具有感知信息素浓度的能力,并根据信息素的浓度的大小来选择它将要移动的方向。假设有两条路从窝通向食物,开始的时候,走这两条路的蚂蚁数量同样多(或者较长的路上蚂蚁多,这也无关紧要)。当蚂蚁沿着一条路到达终点以后会马上返回来,这样,短的路蚂蚁来回一次的时间就短,这也意味着重复的频率就快,因而在单位时间里走过的蚂蚁数目就多,洒下的信息素自然也会多,自然会有更多的蚂蚁被吸引过来,从而洒下更多的信息素……;而长的路正相反,因此,越来越多地蚂蚁聚集到较短的路径上来,最短的路径就近似找到了。可以说,蚂蚁以信息素作为媒介实现了群体内部的间接通信,依赖自身催化与正向反馈的机制最终发现觅食的最短路径。

  在蚂蚁觅食行为的启发下,学者们在计算机上模拟真实蚂蚁的群体行为,并把该思想用于解决众多复杂的实际应用问题,这就产生了蚁群算法。蚁群算法是人们受到真实世界中蚂蚁群体行为的启示而提出的一种优化算法,通过个体之间的信息交流与相互协作,最终得到待求问题的解。计算机学者首先把待解问题转换成相应的构建图,然后让人工蚁群在构建图中仿照真实蚂蚁的行为:人工蚂蚁在构建图中游走,并根据某些规则释放一定量的人工信息素,随着信息素在构建图中某些成分上的不断积累,人工蚂蚁可以探测人工信息素的浓度并以此为依据构造出问题的解。这种方法具有分布性、并行性、全局寻优、无须依赖具体问题的数学特性等特点,能够在较短的时间内发现问题的近似最优解,并迅速成为最成功的启发式算法之一。

  在网络路由处理中,网络的流量分布不断变化,网络链路或结点也会随机地失效或重新加入。蚁群的自身催化与正向反馈机制正好符合了这类问题的求解特点,因而,蚁群算法在网络领域得到一定应用。

  蚁群觅食行为所呈现出的并行与分布特性使得算法特别适合于并行化处理。因而,实现算法的并行化执行对于大量复杂的实际应用问题的求解来说是极具潜力的。

  蚂蚁算法还在聚类、网页文档分类及主题图显示、智能机器人控制等领域得到成功的应用。

  在某群体中若存在众多无智能的个体,它们通过相互之间的简单合作所表现出来的智能行为即称为集群智能(Swarm Intelligence)。互联网上的交流,不过是更多的神经元连接(人脑)通过互联网相互作用的结果,光缆和路由器不过是轴突和突触的延伸。

  从自组织现象的角度上看,人脑的智能和蚁群也没有本质上的区别,单个神经元没有智能可言,单个蚂蚁也没有,但是通过连接形成的体系,是一个智能体。

  代码见该Github地址:https://github.com/ChenDa1994/ant-colony-system-demo

  这个代码可以自己选择要走蚁群算法的点,还有GUI已经做好了,可以自动设置迭代次数生成最优路线。

发表评论