蚁群算法

来自计算思维百科
跳转至: 导航搜索
蚁群算法.png

蚂蚁是自然界中常见的一种生物,人们对蚂蚁的关注都只限于“蚂蚁搬家,天要下雨”的民谚上。蚁群算法是一种由于受自然界生物的行为启发而产生的“自然”算法。

基本概念

蚂蚁在寻找食物或回巢的路途中,会在他们经过的地方留下一些化学物质(我们称之为“外激素”)。这些物质可以被同一蚁群中的后来的蚂蚁感受到,并作为一种信号继续影响后到者的行动(具体表现在后来的蚂蚁选择有激素的路径的可能性比选择没有激素的路径的可能性大得多),后到的蚂蚁留下的外激素对原有的外激素进行加强,如此循环。这样,经过蚂蚁越多的路径,在被后到的蚂蚁选中的可能性就越大。在一定时间内,越短的路径会被越多的蚂蚁访问,因此积累下的外激素也就越多,在之后被选中的可能性就越大。这个过程会一直持续到所有蚂蚁都走最短的那一条路径为止。而蚁群算法正是受蚂蚁行动的启发,模仿蚂蚁寻找最佳路径的模式,可以解决各种图问题如旅行商问题,分配问题及许多组合优化问题。

应用范围

蚁群优化算法被广泛用于解决组合优化问题,调度问题、分配问题、车辆路径问题以及在网络路由上的应用等。

应用案例

应用—“蚂蚁系统”解决旅行商问题

旅行商要找到一系列城市的最短遍历路线。利用“蚂蚁系统”,基于一组蚂蚁,每只完成一次城市间的遍历。在每个阶段,蚂蚁根据一些规则选择从一个城市移动到另一个:

(1)它必须访问每个城市一次;

(2)一个越远的城市被选中的机会越少(能见度更低);

(3)在两个城市边际的一边形成的信息素越浓烈,这边被选择的概率越大;

(4)如果路程短的话,已经完成旅程的蚂蚁会在所有走过的路径上沉积更多信息素,每次迭代后,信息素轨迹挥发。

可以体现的计算思维

蚁群算法是从蚂蚁寻觅食物的行动中获得启发而发展出的一种算法,其本质上是并行的算法。每只蚂蚁搜索的过程彼此独立,仅通过信息激素进行通信,它在问题空间的多点同时开始进行独立的解搜索,不仅增加了算法的可靠性,也使得算法具有较强的全局搜索能力,但是也正是由于其并行性的本质,蚁群算法的搜索时间较长。在计算科学领域中,有很多这种在解决问题时,利用过去的经验,选择已经行之有效的方法,而不是系统地、以确定的步骤去寻求答案的算法,正是计算思维中启发式思维的具体表现。