1 / 65
文档名称:

什么是人工智能算法.ppt

格式:ppt   大小:3,281KB   页数:65页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

什么是人工智能算法.ppt

上传人:文库新人 2022/2/21 文件大小:3.20 MB

下载得到文件列表

什么是人工智能算法.ppt

文档介绍

文档介绍:什么是人工智能算法
*
第1页,此课件共65页哦
蚁群算法
起源
应用领域
研究背景
基本原理
*
第2页,此课件共65页哦
蚁群优化算法起源
蚁群算法最开始的提出是在90年代有人受了蚂蚁觅食时的通讯机制的启发用共65页哦
简化的蚂蚁寻食过程 1/3
蚂蚁从A点出发,速度相同,食物在D点,可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁,每个时间单位行走一步,本图为经过9个时间单位时的情形:走ABD的蚂蚁到达终点,而走ACD的蚂蚁刚好走到C点,为一半路程。
*
第10页,此课件共65页哦
简化的蚂蚁寻食过程 2/3
本图为从开始算起,经过18个时间单位时的情形:走ABD的蚂蚁到达终点后得到食物又返回了起点A,而走ACD的蚂蚁刚好走到D点。
*
第11页,此课件共65页哦
简化的蚂蚁寻食过程 3/3
假设蚂蚁每经过一处所留下的信息素为一个单位,则经过36个时间单位后,所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物,此时ABD的路线往返了2趟,每一处的信息素为4个单位,而 ACD的路线往返了一趟,每一处的信息素为2个单位,其比值为2:1。
寻找食物的过程继续进行,则按信息素的指导,蚁群在ABD路线上增派一只蚂蚁(共2只),而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后,两条线路上的信息素单位积累为12和4,比值为3:1。
若按以上规则继续,蚁群在ABD路线上再增派一只蚂蚁(共3只),而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后,两条线路上的信息素单位积累为24和6,比值为4:1。
若继续进行,则按信息素的指导,最终所有的蚂蚁会放弃ACD路线,而都选择ABD路线。这也就是前面所提到的正反馈效应。
*
第12页,此课件共65页哦
自然蚁群与人工蚁群算法
基于以上蚁群寻找食物时的最优路径选择问题,可以构造
人工蚁群,来解决最优化问题,如TSP问题。
人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的
相似之处在于都是优先选择信息素浓度大的路径。较短路径的
信息素浓度高,所以能够最终被所有蚂蚁选择,也就是最终的
优化结果。
两者的区别在于人工蚁群有一定的记忆能力,能够记忆已
经访问过的节点。同时,人工蚁群再选择下一条路径的时候是
按一定算法规律有意识地寻找最短路径,而不是盲目的。例如
在TSP问题中,可以预先知道当前城市到下一个目的地的距离。
*
第13页,此课件共65页哦
蚁群算法与TSP问题 1/3
TSP问题表示为一个N个城市的有向图G=(N,A),
其中
城市之间距离
目标函数为 ,
其中 为城市1,2,…n的
一个排列, 。
*
第14页,此课件共65页哦
蚁群算法与TSP问题 2/3
TSP问题的人工蚁群算法中,假设m只蚂蚁在图的相邻节点间移动,从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定:1 信息素值 也称信息素痕迹。2 可见度,即先验值。
信息素的更新方式有2种,一是挥发,也就是所有路径上的信息素以一定的比率进行减少,模拟自然蚁群的信息素随时间挥发的过程;二是增强,给评价值“好”(有蚂蚁走过)的边增加信息素。
*
第15页,此课件共65页哦
蚁群算法与TSP问题 3/3
蚂蚁向下一个目标的运动是通过一个随机原则来实现的,也就是运用当前所在节点存储的信息,计算出下一步可达节点的概率,并按此概率实现一步移动,逐此往复,越来越接近最优解。
蚂蚁在寻找过程中,或者找到一个解后,会评估该解或解的一部分的优化程度,并把评价信息保存在相关连接的信息素中。
*
第16页,此课件共65页哦
初始的蚁群优化算法—基于图的蚁群系统(GBAS) 1/12
初始的蚁群算法是基于图的蚁群算法,graph-based ant system,简称为GBAS,是由Gutjahr W J在2000年的Future Generation Computing Systems提出的,算法步骤如下:
STEP 0 对n个城市的TSP问题,
城市间的距离矩阵为 ,给TSP图中的每一条弧 赋信息素初值