展会信息港展会大全

什么是“蚁群算法”以及其特点?
来源:互联网   发布日期:2011-08-28 21:34:55   浏览:15939次  

导读: 想了解 蚁群算法 与SEO的关系,我们还是先来看看“蚁群算法”的由来: 蚂蚁是地球上最常见、数量最多的昆虫种类之一,常常成群结队地出现在人类的日常生活环境中。这些昆虫的群体生物智能特征,引起了一些学者的注意。意大利学者M.Dorigo,V.Maniezzo等人在...

想了解蚁群算法与SEO的关系,我们还是先来看看“蚁群算法”的由来:

蚂蚁是地球上最常见、数量最多的昆虫种类之一,常常成群结队地出现在人类的日常生活环境中。这些昆虫的群体生物智能特征,引起了一些学者的注意。意大利学者M.Dorigo,V.Maniezzo等人在观察蚂蚁的觅食习性时发现,蚂蚁总能找到巢穴与食物源之间的最短路径。

经研究发现,蚂蚁的这种群体协作功能是通过一种遗留在其来往路径上的叫做信息素(Pheromone)的挥发性化学物质来进行通信和协调的。化学通信是蚂蚁采取的基本信息交流方式之一,在蚂蚁的生活习性中起着重要的作用。通过对蚂蚁觅食行为的研究,他们发现,整个蚁群就是通过这种信息素进行相互协作,形成正反馈,从而使多个路径上的蚂蚁都逐渐聚集到最短的那条路径上。

这样,M.Dorigo等人于1991年首先提出了蚁群算法。其主要特点就是:通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法。它充分利用了生物蚁群能通过个体间简单的信息传递,搜索从蚁巢至食物间最短路径的集体寻优特征,以及该过程与旅行商问题求解之间的相似性。得到了具有NP难度的旅行商问题的最优解答。同时,该算法还被用于求解Job-Shop调度问题、二次指派问题以及多维背包问题等,显示了其适用于组合优化类问题求解的优越特征。

多年来世界各地研究工作者对蚁群算法进行了精心研究和应用开发,该算法现己被大量应用于数据分析、机器人协作问题求解、电力、通信、水利、采矿、化工、建筑、交通等领域。

蚁群算法之所以能引起相关领域研究者的注意,是因为这种求解模式能将问题求解的快速性、全局优化特征以及有限时间内答案的合理性结合起来。其中,寻优的快速性是通过正反馈式的信息传递和积累来保证的。而算法的早熟性收敛又可以通过其分布式计算特征加以避免,同时,具有贪婪启发式搜索特征的蚁群系统又能在搜索过程的早期找到可以接受的问题解答。

这种优越的问题分布式求解模式经过相关领域研究者的关注和努力,已经在最初的算法模型基础上得到了很大的改进和拓展。经过一定时间,从食物源返回的蚂蚁到达D点同样也碰到障碍物,也需要进行选择。此时A, B两侧的信息素浓度相同,它们仍然一半向左,一半向右。但是当A侧的蚂蚁已经完全绕过障碍物到达C点时,B侧的蚂蚁由于需走的路径更长,还不能到达C点。如图1所示。

蚁群算法

图 1 :蚁群在障碍物前经过一段时间后的情形

此时对于从蚁巢出发来到C点的蚂蚁来说,由于A侧的信息素浓度高,B侧的信息素较低,就倾向于选择A侧的路径。这样的结果是A侧的蚂蚁越来越多,最终所有蚂蚁都选择这条较短的路径。如图2所示。

蚁群算法

图 2 蚁群最终选择的路径

上述过程,很显然是由蚂蚁所留下的信息素的“正反馈”过程而导致的。蚂蚁个体就是通过这种信息的交流来达到搜索食物的目的。蚁群算法的基本思想也是从这个过程转化而来的。

蚁群算法的特点

赞助本站

人工智能实验室

相关热词: 什么 蚁群算法 其特点

AiLab云推荐
展开

热门栏目HotCates

Copyright © 2010-2024 AiLab Team. 人工智能实验室 版权所有    关于我们 | 联系我们 | 广告服务 | 公司动态 | 免责声明 | 隐私条款 | 工作机会 | 展会港