下载此文档

智能控制理论和方法(第二版)第7章蚁群算法及其在智能控制中的应用.ppt


文档分类:高等教育 | 页数:约78页 举报非法文档有奖
1/78
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/78 下载此文档
文档列表 文档介绍
第7章蚁群算法及其在智能控制中的应用
引言
蚁群觅食奥秘
基本人工蚁群算法
改进的蚁群优化算法
用蚁群算法求解Job Shop问题
引言 20世纪90年代意大利学者Marco Dorigo等人通过观察蚁群觅食的过程,发现众多蚂蚁在寻找食物的过程中,总能够找到一条从蚂蚁巢穴到食物源之间的最短路径。。于是,重新在实验室中对蚁群觅食行为进行了实验,即当蚁群在蚂蚁巢穴和食物之间建立取食路径后,人为地在蚂蚁巢穴和食物之间设置一定的障碍物。研究发现,在人为设置障碍物之后,蚁群经过一段时间的探索,又重新走出一条蚂蚁巢穴到食物之间的最短路径。通过对蚁群觅食机制的深入研究,M. Dorigo等人提出了蚁群算法[1]。进一步的实验表明,蚁群算法具有正反馈、分布式计算以及贪婪的启发式搜索等特点。这些特点为更好地解决复杂的组合优化问题提供了可能。用这种算法来求解旅行商问题[2],即TSP(Traveling Salesman Problem)问题时,结果比较理想。
蚁群觅食奥秘 蚁群觅食 蚂蚁属节肢动物门,昆虫纲、膜翅目、蚁科,有成千上万种。任何一种都是群体生活,建有独特的蚂蚁社会,具有合作、品级分化和个体利他等特点。 觅食是蚁群最重要且有趣的社会活动之一[3]。据昆虫学家的观察和研究,发现蚂蚁食性甚杂,各种蚂蚁喜欢不同的食物和取食方式。比如,当弓背蚁属(学名: Camponotus,又名巨山蚁属、木匠蚁属,俗称木匠蚁、木蚁)的一只工蚁发现食物时,它在食物的周围释放一种分泌物作标记,然后回巢,并一路释放分泌物作为示踪标记。
在巢内,它以“摇摆表演”的方式告知同伴它发现了食物。随即,巢穴内的工蚁跟随它或沿着分泌物的气味来到食物源。如果食物源有足够多的食物,就会吸引大批的工蚁一起涌向食物源,于是成百上千的工蚁在蚂蚁巢穴和食物源之间来回忙碌,将食物搬运回蚂蚁巢穴。在蚁群取食一段时间后,人们发现,蚂蚁竟然找到一条从蚂蚁巢穴到食物源之间最短的路径,并沿着这条路径搬运食物。当人为地在上述路径上设置一障碍物时,经一段时间后,蚁群又能找到一条从蚂蚁巢穴到食物源之间最短的搬运食物路径。。
(a)为蚂蚁已经在蚂蚁巢穴与食物之间建立了最短的取食路径AE(或EA)。(b)(a)所示的蚂蚁取食路径上设置一障碍物HC,从而使蚂蚁的可取食路径为AHE(或EHA)或ACE(或ECA),蚂蚁只能选其一。显然,AHE路径较ACE路径长。(c)为蚂蚁经过一段时间的探索、寻找,找到了食物源到蚂蚁巢穴之间最短的取食路径ACE(或ECA)。 小小的爬行蚂蚁靠什么总能够准确寻找到最短的取食路径?
在蚂蚁取食路径设置障碍的实验
蚁群的信息系统及使用机制 蚁群有着令人称奇的信息系统,其中包括视觉、声音、无声语言及其有效的信息机制,特别是蚂蚁独门绝技的无声语言及相应的使用机制。研究发现,当蚂蚁外出觅食或在回巢穴的途中,它们都会释放一种特殊的信息素(pheromone)气味(通常称信息素)来标示行进的轨迹,蚂蚁用这种独有的无声语言来设置类似人类路标的蚁踪。有了示踪的信息素,蚂蚁就能顺利回“家”。进一步的研究发现,蚂蚁在寻找食物过程中,在它们经过的地方所留下的信息素,不仅能被同一蚁群中的其他蚂蚁感知到,而且其强度也能被感知,蚂蚁会倾向于沿信息素浓度较高的方向移动,而移动过程又会留下新的信息素,对原有的信息素进行加强。如此,越多蚂蚁经过的路径,信息素会越强,而后续的蚂蚁选择走该路径的可能性也越大。最后,几乎所有的蚂蚁都走信息素最强的路径。基于信息素及信息素的使用机制,蚂蚁就能在食物源和蚂蚁巢穴之间建立一条最短的取食路径。
,结合具体示例数据来说明蚁群在食物源和蚂蚁巢穴之间建立一条最短的取食路径的原理。
蚁群取食最短路径产生示意图
(b)中,A是蚂蚁巢穴,E是食物源,HC是障碍物。图中有两条路径从蚂蚁巢穴通向食物源,(a)所示,称图中的A-C-E(或E-C-A)为路径Ⅰ;称A-H-E(或E-H-A)为路径Ⅱ。为方便说明,我们假定路径Ⅱ的长度是路径Ⅰ长度的两倍,分别为2和1个单位长度。现假设所有蚂蚁在一个单位时间可移动的距离为1单位长度。任何蚂蚁在行走时,都会在1个单位长度上均匀留下浓度为1个单位的信息素。在t=0时刻前,上述两条路径上均无信息素,信息素量为0(也可以设为不为0的初始值)。 设t=0时刻,有20只蚂蚁从A点出发,由于此时两条路径上的信息素相同均为0,所以20只蚂蚁选择两条路径的概率相等。不妨假设

智能控制理论和方法(第二版)第7章蚁群算法及其在智能控制中的应用 来自淘豆网www.taodocs.com转载请标明出处.

非法内容举报中心
文档信息
  • 页数78
  • 收藏数0 收藏
  • 顶次数0
  • 上传人autohww
  • 文件大小1.83 MB
  • 时间2018-04-23