什么是人工智能算法

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

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

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

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

4、电信QoS管理、生物系统建模、流 程规划、信号处理、机器人控制、决策支持以 及仿真和系统辩识等方面，群智能理论和方法 为解决这类应用问题提供了新的途径。5蚁群优化算法研究背景 1/3蚁群算法属于群智理论。群智能理论研究 领域有两种主要的算法：蚁群算法(Ant Colony Optimization, ACO)和微粒群算法（ Particle Swarm Optimization, PSO）。前者 是对蚂蚁群落食物采集过程的模拟，已成功 应用于许多离散优化问题。微粒群算法也是 起源于对简单社会系统的模拟，最初是模拟 鸟群觅食的过程，但后来发现它是一种很好 的优化工具。6蚁群优化算法研究背景 2/

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

6、其 梯度信息。已完成的群智能理论和应用方法研究证 明群智能方法是一种能够有效解决大多数全局优化 问题的新方法。更为重要是，群智能潜在的并行性 和分布式特点为处理大量的以数据库形式存在的数 据提供了技术保证。无论是从理论研究还是应用研 究的角度分析，群智能理论及其应用研究都是具有 重要学术意义和现实价值的。 8蚁群算法原理蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种 仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一 种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在 运动过程中能够感知这种物质，并以此指导自己的运动方向，因 此由大量蚂蚁组成的蚁群集体行为便表现出一

7、种信息正反馈现象 ：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越 大。为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的 具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴 之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出 一种特殊的信息素。当它们碰到一个还没有走过的路口时就随 机地挑选一条路径前行。与此同时释放出与路径长度有关的信息 素。路径越长，释放的激素浓度会越低.当后来的蚂蚁再次碰到这 个路口的时候选择激素浓度较高路径概率就会相对较大。这样 形成一个正反馈。最优路径上的激索浓度越来越大而其它的路 径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出 最优路

8、径。9简化的蚂蚁寻食过程 1/3蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD 或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走 一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点 ，而走ACD的蚂蚁刚好走到C点，为一半路程。10简化的蚂蚁寻食过程 2/3本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁 到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D 点。11简化的蚂蚁寻食过程 3/3假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单 位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时 ABD的路线往返了2趟

9、，每一处的信息素为4个单位，而 ACD的路线往返了 一趟，每一处的信息素为2个单位，其比值为2：1。寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派 一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位 后，两条线路上的信息素单位积累为12和4，比值为3：1。若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而 ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息 素单位积累为24和6，比值为4：1。若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而 都选择ABD路线。这也就是前面所提到的正反馈效应。12自然蚁群与人工

10、蚁群算法基于以上蚁群寻找食物时的最优路径选择问题，可以构造 人工蚁群，来解决最优化问题，如TSP问题。人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的 相似之处在于都是优先选择信息素浓度大的路径。较短路径的 信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的 优化结果。两者的区别在于人工蚁群有一定的记忆能力，能够记忆已 经访问过的节点。同时，人工蚁群再选择下一条路径的时候是 按一定算法规律有意识地寻找最短路径，而不是盲目的。例如 在TSP问题中，可以预先知道当前城市到下一个目的地的距离 。13蚁群算法与TSP问题 1/3TSP问题表示为一个N个城市的有向图G=（N，A），其中城市之间距离

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

12、可达节点的概率，并按此概率实现一步 移动，逐此往复，越来越接近最优解。蚂蚁在寻找过程中，或者找到一个 解后，会评估该解或解的一部分的优化 程度，并把评价信息保存在相关连接的 信息素中。16初始的蚁群优化算法基于图的蚁群系 统（GBAS） 1/12初始的蚁群算法是基于图的蚁群算法，graph-based ant system,简称为GBAS，是由Gutjahr W J在2000年的 Future Generation Computing Systems提出的，算法步 骤如下：STEP 0 对n个城市的TSP问题，城市间的距离矩阵为 ，给TSP图中的每 一条弧 赋信息素初值 ，假设m 只蚂蚁在工作

13、，所有蚂蚁都从同一城市 出发。当前最 好解是。17初始的蚁群优化算法基于图的蚁群系 统（GBAS） 2/12STEP 1 （外循环）如果满足算法的停止规则，则停止计算并输 出计算得到的最好解。否则使蚂蚁s从起点 出发，用 表示 蚂蚁s行走的城市集合，初始 为空集， 。STEP 2 (内循环) 按蚂蚁 的顺序分别计算。当蚂 蚁在城市i，若 完成第s只蚂蚁的计算。否则，若，则以概率，到达j， ；若则到达重复STEP 2。 18初始的蚁群优化算法基于图的蚁群系 统（GBAS） 3/12STRP 3 对 ，若 ，按 中城市的顺序计算 路径程度；若 ，路径长度置为一个无穷大值（即不可 达）。比较m只蚂蚁

14、中的路径长度，记走最短路径的蚂蚁为t。 若 ，则 。用如下公式对W路径 上的信息素痕迹加强，对其他路径上的信息素进行挥发。 得到新的 ，重复步骤STEP 1。19初始的蚁群优化算法基于图的蚁群系 统（GBAS） 4/12在STEP 3 中，挥发因子 对于一个固定的 ，满足并且经过k次挥发，非最优路径的信息素逐渐减少至消失。20初始的蚁群优化算法基于图的蚁群系 统（GBAS） 5/12以上算法中，在蚂蚁的搜寻过程中，以信息素的概率分布来决定从城市 i到城市j的转移。算法中包括信息素更新的过程1 信息素挥发（evaporation） 信息素痕迹的挥发过程是每个连接上的信 息素痕迹的浓度自动逐渐减弱

15、的过程，由 表示，这个 挥发过程主要用于避免算法过快地向局部最优区域集中，有助于搜索区 域的扩展。2 信息素增强（reinforcement）增强过程是蚁群优化算法中可选的部分， 称为离线更新方式（还有在线更新方式）。这种方式可以实现由单个蚂 蚁无法实现的集中行动。也就是说，增强过程体现在观察蚁群（m只蚂蚁） 中每只蚂蚁所找到的路径，并选择其中最优路径上的弧进行信息素的增强， 挥发过程是所有弧都进行的，不于蚂蚁数量相关。这种增强过程中进行的 信息素更新称为离线的信息素更新。在STEP 3中，蚁群永远记忆到目前为止的最优解。21图的蚁群系统（GBAS） 6/12可以验证，下式满足：即 是一个随机矩阵。 四个城市的非对称TSP问题，距离矩阵和城市图示如下：22初始的蚁