什么是人工智能算法.ppt

《什么是人工智能算法.ppt》由会员分享，可在线阅读，更多相关《什么是人工智能算法.ppt（65页珍藏版）》请在优知文库上搜索。

1、1什么是人工智能算法 n随着计算机技术的飞速发展，智能计算方法的应用领域也越来越广泛，当前存在的一些智能算法有人工神经网络 遗传算法 模拟退火算法 群集智能 蚁群算法 粒子群算 等等。 蚁群算法只是其中的一种。人工智能计算也有人称之为“软计算”，是们受自然（生物界）规律的启迪，根据其原理，模仿求解问题的算法。从自然界得到启迪，模仿其结构进行发明创造，这就是仿生学。这是我们向自然界学习的一个方面。另一方面，我们还可以利用仿生原理进行设计(包括设计算法)，这就是智能计算的思想。2蚁群算法n起源n应用领域n研究背景n基本原理3蚁群优化算法起源蚁群算法最开始的提出是在90年代有人受了蚂蚁觅食时的通讯机

2、制的启发用来解决计算机算法学中经典的“旅行商问题（Traveling Salesman Problem, TSP）”。TSP问题属于易于描述但难于解决的著名难题之一，至今世界上还有不少人在研究它。该问题的基本描述是：某售货员要到若干个村庄售货，各村庄之间的路程是已知的，为了提高效率，售货员决定从所在商店出发，到每个村庄都售货一次后再返回商店，问他应选择一条什么路线才能使所走的总路程最短? 其实有很多实际问题可归结为TSP问题。4蚁群优化算法起源 例如邮路问题就是一个TSP问题。假定有一辆邮车要到n个不同的地点收集邮件，这种情况可以用n十1个结点的图来表示。一个结点表示此邮车出发并要返回的那个邮

3、局，其余的n个结点表示要收集邮件的n个地点。邮车所行经的路线是一条周游路线，希望求出具有最小长度的周游路线。再举一个例子在一条装配线上用一个机械手去紧固待装配部件上的螺帽问题。机械手由其初始位置(该位置在第一个要紧固的螺帽的上方)开始，依次移动到其余的每一个螺帽，最后返回到初始位置。一条最小成本周游路线将使这机械手完成其工作所用的时间取最小值。所以TSP问题的研究也是具有很多实际价值。5蚁群算法应用领域 这种方法能够被用于解决大多数优化问题或者能够转化为优化求解的问题。现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信QoS管理、生物系统建模、流程规划、信号处理、机器人控制、

4、决策支持以及仿真和系统辩识等方面，群智能理论和方法为解决这类应用问题提供了新的途径。6蚁群优化算法研究背景 1/3 蚁群算法属于群智理论。群智能理论研究领域有两种主要的算法：蚁群算法(Ant Colony Optimization, ACO)和微粒群算法（Particle Swarm Optimization, PSO）。前者是对蚂蚁群落食物采集过程的模拟，已成功应用于许多离散优化问题。微粒群算法也是起源于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化工具。 7蚁群优化算法研究背景 2/3与大多数基于梯度的应用优化算法不同，群智能依靠的是概率搜索算法。虽然概率搜索

5、算法通常要采用较多的评价函数，但是与梯度方法及传统的演化算法相比，其优点还是显著的 ，主要表现在以下几个方面：1 无集中控制约束，不会因个别个体的故障影响整个问题 的求解，确保了系统具备更强的可靠性 2 以非直接的信息交流方式确保了系统的扩展性 3 并行分布式算法模型，可充分利用多处理器 4 对问题定义的连续性无特殊要求 5 算法实现简单 8蚁群优化算法研究背景 3/3 群智能方法易于实现，算法中仅涉及各种基本的数学操作，其数据处理过程对CPU和内存的要求也不高。而且，这种方法只需目标函数的输出值，而无需其梯度信息。已完成的群智能理论和应用方法研究证明群智能方法是一种能够有效解决大多数全局优化

6、问题的新方法。更为重要是，群智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还是应用研究的角度分析，群智能理论及其应用研究都是具有重要学术意义和现实价值的。 9蚁群算法原理 蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。 为了说明蚁群算法的原理，先简要介

7、绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激素浓度会越低.当后来的蚂蚁再次碰到这个路口的时候选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。10简化的蚂蚁寻食过程 1/3蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只

8、蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。11简化的蚂蚁寻食过程 2/3本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。12简化的蚂蚁寻食过程 3/3 假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而 ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。 寻找食物的过程继续进行，则按信息素的指导

9、，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。 若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。 若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。13自然蚁群与人工蚁群算法 基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如TSP问题。 人工蚁群中把具有简单功能的工作单元看作蚂蚁

10、。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。 两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。14蚁群算法与TSP问题 1/3TSP问题表示为一个N个城市的有向图G=（N，A），其中城市之间距离目标函数为 ，其中 为城市1,2，n的一个排列， 。, |j), (iA n1,2,.,NNjinnijd)(nliilldwf11)(),(21niiiw

11、11iin15蚁群算法与TSP问题 2/3 TSP问题的人工蚁群算法中，假设m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：1 信息素值 也称信息素痕迹。2 可见度，即先验值。 信息素的更新方式有2种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”(有蚂蚁走过)的边增加信息素。16蚁群算法与TSP问题 3/3 蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越

12、接近最优解。 蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。17初始的蚁群优化算法基于图的蚁群系统（GBAS） 1/12初始的蚁群算法是基于图的蚁群算法，graph-based ant system,简称为GBAS，是由Gutjahr W J在2000年的Future Generation Computing Systems提出的，算法步骤如下：STEP 0 对n个城市的TSP问题，城市间的距离矩阵为 ，给TSP图中的每一条弧 赋信息素初值 ，假设m只蚂蚁在工作，所有蚂蚁都从同一城市 出发。当前最好解是。, |j), (iA n1,

13、2,.,NNjinnijd)(),(ji|1)0(Aij0i),2,1(nw18初始的蚁群优化算法基于图的蚁群系统（GBAS） 2/12STEP 1 （外循环）如果满足算法的停止规则，则停止计算并输出计算得到的最好解。否则使蚂蚁s从起点 出发，用 表示蚂蚁s行走的城市集合，初始 为空集， 。STEP 2 (内循环) 按蚂蚁 的顺序分别计算。当蚂蚁在城市i，若 完成第s只蚂蚁的计算。否则，若，则以概率，到达j， ；若则到达重复STEP 2。0i)(sL)(sLms 11sm( ) |( , ),( )L sNli lA lL s 或0( ) |( , ),( ) L sNTli lA lL si

14、 且(1),(1)ijijijl TkpjTk0,ijpjT( )( ) , :L sL sjij0( ) |( , ),( ) L sNTli lA lL si 且000, ( )( ) , :;i L sL siii19初始的蚁群优化算法基于图的蚁群系统（GBAS） 3/12STRP 3 对 ，若 ，按 中城市的顺序计算路径程度；若 ，路径长度置为一个无穷大值（即不可达）。比较m只蚂蚁中的路径长度，记走最短路径的蚂蚁为t。若 ，则 。用如下公式对W路径上的信息素痕迹加强，对其他路径上的信息素进行挥发。 得到新的 ，重复步骤STEP 1。1sm( )L sN( )L s( )L sN( (

15、)( ()f L tf L W( )WL t( ), :1ijk kk111( )(1)(1)( , )( )(1)(1)( , )kijkijijkijkki jWWkki jW为上的一条弧不是上的一条弧20初始的蚁群优化算法基于图的蚁群系统（GBAS） 4/12在STEP 3 中，挥发因子 对于一个固定的 ，满足并且 经过k次挥发，非最优路径的信息素逐渐减少至消失。kln1,ln(1)kkkKk 1K 1kk 21初始的蚁群优化算法基于图的蚁群系统（GBAS） 5/12 以上算法中，在蚂蚁的搜寻过程中，以信息素的概率分布来决定从城市i到城市j的转移。 算法中包括信息素更新的过程 1 信息素

16、挥发（evaporation） 信息素痕迹的挥发过程是每个连接上的信息素痕迹的浓度自动逐渐减弱的过程，由 表示，这个挥发过程主要用于避免算法过快地向局部最优区域集中，有助于搜索区域的扩展。 2 信息素增强（reinforcement）增强过程是蚁群优化算法中可选的部分，称为离线更新方式（还有在线更新方式）。这种方式可以实现由单个蚂蚁无法实现的集中行动。也就是说，增强过程体现在观察蚁群（m只蚂蚁）中每只蚂蚁所找到的路径，并选择其中最优路径上的弧进行信息素的增强，挥发过程是所有弧都进行的，不于蚂蚁数量相关。这种增强过程中进行的信息素更新称为离线的信息素更新。 在STEP 3中，蚁群永远记忆到目前为止的最优解。(1)( )kijk 22图的蚁群系统（GBAS） 6/12可以验证，下式满足：即 是一个随机矩阵。( )k( , )( )1,0iji jAkk 四个城市的非对称TSP问题，距离矩阵和城市图示如下：010.511011()1.55011110ijDd23初始的蚁群优化算法基于图的蚁群系统（GBAS） 7/12假设共4只蚂蚁，所有蚂蚁都从城市A出发，挥发因子 。此时，观察GBAS的计算