/code-ant

蚁群算法

Primary LanguageHTMLMIT LicenseMIT

蚁群算法

蚂蚁几乎没有视力,但他们却能够在黑暗的世界中找到食物,而且能够找到一条从洞穴到食物的最短路径。它们是如何做到的呢?

蚂蚁寻找食物的过程

单只蚂蚁的行为及其简单,行为数量在10种以内,但成千上万只蚂蚁组成的蚁群却能拥有巨大的智慧,这离不开它们信息传递的方式——信息素。

蚂蚁在行走过程中会释放一种称为“信息素”的物质,用来标识自己的行走路径。在寻找食物的过程中,根据信息素的浓度选择行走的方向,并最终到达食物所在的地方。

信息素会随着时间的推移而逐渐挥发。

在一开始的时候,由于地面上没有信息素,因此蚂蚁们的行走路径是随机的。蚂蚁们在行走的过程中会不断释放信息素,标识自己的行走路径。随着时间的推移,有若干只蚂蚁找到了食物,此时便存在若干条从洞穴到食物的路径。由于蚂蚁的行为轨迹是随机分布的,因此在单位时间内,短路径上的蚂蚁数量比长路径上的蚂蚁数量要多,从而蚂蚁留下的信息素浓度也就越高。这为后面的蚂蚁们提供了强有力的方向指引,越来越多的蚂蚁聚集到最短的路径上去。

什么是蚁群算法?

蚁群算法就是模拟蚂蚁寻找食物的过程,它能够求出从原点出发,经过若干个给定的需求点,最终返回原点(去到目标)的最短路径。这也就是著名的旅行商问题(Traveling Saleman Problem,TSP)。

本文采用可视的方式模拟蚂蚁寻路过程,旨在理解蚂蚁算法的解题过程。

参考bz51/AntColonyAlgorithm

实例

计算随机人际关系链中,随机两个人的最短关系链。

通过蚁群算法,我们可以轻松找到给定人际关系链中任意两人最短关系链。

people-relationship.html