蚁群算法简述及实现VIP专享

蚁群算法简述及实现1 蚁群算法的原理分析蚁群算法是受自然界中真实蚁群算法的集体觅食行为的启发而进展起来的一种基于群体的模拟进化算法,属于随机搜索算法,所以它更恰当的名字应该叫“人工蚁群算法”,我们一般简称为蚁群算法。M.Dorigo 等人充分的利用了蚁群搜索食物的过程与著名的 TSP 问题的相似性,通过人工模拟蚁群搜索食物的行为来求解 TSP 问题。蚂蚁这种社会性动物,虽然个体行为及其简单,但是由这些简单个体所组成的群体却表现出及其复杂的行为特征。这是因为蚂蚁在寻找食物时,能在其经过的路径上释放一种叫做信息素的物质,使得一定范围内的其他蚂蚁能够感觉到这种物质,且倾向于朝着该物质强度高的方向移动。蚁群的集体行为表现为一种正反馈现象,蚁群这种选择路径的行为过程称之为自催化行为。由于其原理是一种正反馈机制,因此也可以把蚁群的行为理解成所谓的增强型学习系统(Reinforcement Learning System)。引用 M.Dorigo 所举的例子来说明蚁群发现最短路径的原理和机制,见图 1 所示。假设 D和 H 之间、B 和 H 之间以及 B 和 D 之间(通过 C)的距离为 1,C 位于 D 和 B 的中央(见图 1 (a))。现在我们考虑在等间隔等离散世界时间点(t=0,1,2……)的蚁群系统情况。假设每单位时间有 30 只蚂蚁从 A 到 B,另三十只蚂蚁从 E 到 D,其行走速度都为 1(一个单位时间所走距离为 1),在行走时,一只蚂蚁可在时刻 t 留下浓度为 1 的信息素。为简单起见,设信息素在时间区间(t+1，t+2)的中点(t+1.5)时刻瞬时完全挥发。在 t=0 时刻无任何信息素,但分别有 30 只蚂蚁在 B、30 只蚂蚁在 D 等待出发。它们选择走哪一条路径是完全随机的,因此在两个节点上蚁群可各自一分为二,走两个方向。但在 t=1 时刻,从 A 到 B 的 30 只蚂蚁在通向 H 的路径上(见图 1 (b))发现一条浓度为 15 的信息素,这是由 15 只从 B 走向 H 的先行蚂蚁留下来的;而在通向 C 的路径上它们可以发现一条浓度为 30 的信息素路径,这是由 15 只走向 BC 的路径的蚂蚁所留下的气息与 15 只从 D 经 C 到达 B 留下的气息之和(图 1 (c))。这时,选择路径的概率就有了偏差,向 C 走的蚂蚁数将是向 H 走的蚂蚁数的 2 倍。对于从 E 到 D 来的蚂蚁也是如此。（a） （b） （c）图 1 蚁群路径搜索实例这个过程一直会持续到所有的蚂蚁最终都选择了最短的路径为止。这样,我们就可以理解蚁群算法的基本思...