什么是人工智能算法.ppt

什么是人工智能算法
*
第1页，本讲稿共65页
蚁群算法
起源
应用领域
研究背景
基本原理
*
第2页，本讲稿共65页
蚁群优化算法起源
蚁群算法最开始的提出是在90年代有人受了蚂蚁觅食时的通讯机制的启发用来解的蚂蚁寻食过程 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图中的每一条弧 赋信息素初值