人工智能算法综述

1 目 录 摘要

2 人工智能算法综述 通信工程专业

 摘要：随着人工智能再当今科学技术中的飞速发展和应用，人工智能算法的开发学习及应用 也随之越来越广泛，它介绍了当前存在的一些人工智能算法，阐述了其工作原理和特点并对 其加以比较、评价，还对产生背景、应用领域加以说明，同时又对人工智能算法的发展应用 进行了展望。人工智能算法要解决的一般是最优化问题。搜索技术和神经网络渗透在各种人 工智能系统中，在专家系统、自然语言理解、自动程序设计、模式识别、机器人学、信息检 索和博弈等领域都广泛使用。 关键词：盲目式搜索 启发式搜索 局部搜索等高级搜索 人工神经网络算法 Algorithms summary of Artificial Intelligence Student majoring in Communication Engineering Luopu Tutor ZhangJinghu Abstract: With today's science and technology of artificial intelligence and then the rapid development and application of artificial intelligence algorithms and application development also will learn more and more widely, it introduces some existing artificial intelligence algorithm, described its working principle and characteristics and comparison of their evaluation, also gave instructions on the applications, while the development and application of artificial intelligence algorithms were reviewed. Artificial intelligence algorithms to solve the optimization problem in general is. Search technology and neural network penetration in various artificial intelligence system, the expert systems, natural language understanding, automatic programming, pattern recognition, robotics, information retrieval and game fields are widely used. Key words: blind-type local search and other heuristic search Advanced Search artificial neural network.。 引言 自从人工智能学科体系诞生以来，通过对自然界奥秘的研究，涌现出 了很多人工智能算法，人工智能算法又称“软计算”，根据其原理，从自然界得 到启迪，模仿其结构进行发明创造，这就是仿生学。这是我们向自然界学习的一 个方面。另一方面，我们还可以利用仿生原理进行设计(包括设计算法)，这就是 智能计算的思想。这方面的内容很多，如盲目式搜索算法、启发式搜索算法、模 拟退火算法、遗传算法、和群集智能算法、人工神经网络算法等。本文通过对若 干智能算法的综述，在一定程度上集合总结了大部分算法的基本原理、功能特点、 应用领域，并对其加以比较，使人们能够对人工智能算法有更清晰明了的认识， 减少对算法应用方面上的失误让使用者能够方便快速的了解到各算法的相关资 料从而提高运算效率。 人工智能算法要解决的一般是最优化问题，智能算法最优化问题是一种以数 学为基础，用于求解各种工程问题中最优解或者满意解的应用技术。实际问题求 解中，绝大多数问题通过变化都可以转化为求解最优化问题的研究：另外，在数 学领域以及工程领域中存在较多的 NP 问题，很难找到精确的数学公式比如：背 包问题，组合优化问题，任务指派等，或许有些问题根本不需要精确解，而只要 寻找到近似最优解即可，所以智能算法寻优问题目前已成为当前的热点研究方 向。下面就盲目式和启发式搜索、高级搜索、神经网络等算法分别作出详细综述。 3 1.无信息的搜索策略——盲目式搜索算法 即除了问题定义之外没有任何关于状态的附加信息，可做的事情只是生成后继， 并测试是否目标状态。盲目式搜索算法不考虑给定问题所具有的特定知识, 系统 根据事先确定好的某种固定排序, 依次调用规则或随机调用规则,一般统称为无 信息引导的搜索策略。典型的盲目搜索方法是深度优先搜索和广度优先搜索。一 般只适用于求解比较简单的问题。 1.1 广度优先搜索算法 又称宽度优先搜索算法，是最简便的图的搜索算法之一，首先是扩展根结点， 接着扩展根结点的所有后继，然后再扩展他们的后继，以此类推，一般在下一层 的任何结点扩展之前搜索树上本层深度的所有结点都已经扩展过。之所以称为广 度优先算法，是因为算法自始至终一直通过已找到和末找到顶点之间的边界 向外扩展。 如果最浅的目标结点处于一个有限的深度，广度优先搜索在扩展完比 他浅的所有结点之后最终能找到这个目标结点，所以说他是完备的。最浅 目标结点不一定是最优目标结点；技术上讲如果路径耗散是结点深度的非 递减函数，广度优先搜索才是最优的。另外到目前为止，关于广度优先搜 索的消息都是好的。 广度优先搜索算法时间和空间复杂度都比较高，当目标结点距离初始 结点较远时会产生许多无用的结点，搜索效率低，时间需求是一个很大的 问题，特别是当搜索深度较大时，尤为严重，但空间需求是比执行时间更 严重的问题。其优点是目标结点如果存在，用宽度优先搜索可以找到该目 标结点。 1.2 代价一致搜索算法 代价一致搜索算法对一条路径的步数并不关心，而只关心所经步骤的 总耗散，因此在扩展到一个具有能返回同一状态的零耗散行动的结点时就 会陷入无限循环。代价一致搜索由路径的耗散引导而不是深度，代价一致 搜索在搜索包括耗散大但可能是有用的步骤的路径之前，可能而且经常会 先探索耗散小的步骤所在的很大的树。 当所有单步耗散相等的时候广度优先搜索时最优的，因为他总是先扩 展深度最浅的为扩展结点。取代扩展深度最浅结点，代价一致搜索扩展的 是路径消耗最低的结点。如果当所有单步耗散都相等的话，这种算法集合 广度优先搜索算法相同。 1.3 深度优先搜索算法（又名回溯) 深度优先搜索算法总是扩展搜索树的当前边缘中最深的结点，搜索直 接推进到搜索树的最深层，那里的结点没有后继结点，当那些结点扩展完 之后，他们被从边缘中去掉，然后搜索算法“向上回到”下一个还有未扩 展后继结点的稍浅结点。 优点：比宽度优先搜索算法需要较少的时间，该算法只需要保存搜索 树的一部分，它由当前正在搜索的路径和该路径上还没有完全展开的结点 标志组成。因此，深度优先搜索的存储器要求是深度约束的线性函数。 缺点：可能搜索到了错误的路径上（很多问题可能具有很深甚至无限 搜索树，如不幸选择了一个错误的路径，则会一直搜索下去）要么陷入无 4 限循环而不能给出答案，要么最后找到一个答案，但路径很长且不是最优 答案（既不是完备的，也不是最优的）对于深度较大的情况下，深度优先 搜索需要很长的运行时间而且不能解答 [1] 。 有界深度优先搜索方法，总体上按深度优先算法进行，但对深度给出 一个限制达到限制时没有找到解答就停止对该分支的搜索，换到另一分支 上。他是一种回避选择最优深度限制问题的策略。宽度优先搜索算法需要 指数数量的空间；深度的空间复杂度和最大搜索深度呈线性关系，迭代加 深对一棵受控树深度优先搜索，结合宽度和深度优点，即最优的和完备的。 1.4 深度有限搜索算法 无边界的搜索树问题可以通过对深度优先搜索提供一个预先设定的深度限 制来解决，即深度为l 的结点被当做没有后继的结点对待。这种方法就是深度有 限搜索算法。他解决了无穷路径的问题，但当选择ld 时深度有限搜索同样也不是最优的深度优先搜索可以看做 是深度有限搜索的一种特殊情况（其深度限制 l=∞）然而对于大多数问题，不 到问题已经解决我们是无法知道一个好的深度限制的。深度有限搜索也可以通过 对一般的树搜索算法或者递归深度优先搜索算法进行简单的修改来实现 1.5 迭代深入深度优先搜索算法 它是一个用来寻找最合适的深度限制的通用策略，它经常和深度优先搜索结 合使用（不断地增大深度限制直到找到目标结点）当深度限制达到最浅目标结点 深度时，就能找到目标结点。迭代深入搜索算法结合了深度优先搜索算法和广度 优先搜索算法的优点。他的空间需求和深度优先搜索一样小，他和广度优先搜索 一样当分支因子有限时是完备的，当路径耗散是结点深度的非递增函数时则是最 优的。迭代深入搜索因为在一棵每层的分支因子都有相同（或近似相同）的搜索 树中绝大多数都在底而上层结点生成多次影响不大并不像看起来那么浪费。 迭代深入搜索和广度优先搜索是类似的，在每次迭代进行到下一层之前要把 整个当前层的新结点全部探索过。发展类似于代价一致搜索的迭代搜索看起来是 值得的，在继承代价一致搜索的最优化保证的同时避免了大量的内存需求。主要 思想是用不断增加的路径耗散限制代替不断增加的深度限制，按照这种思想产生 的算法被称作“迭代延长搜索”。不过不幸的是，与代价一致搜索相比，事实上 迭代延长将导致实在的额外开销。 1.6 双向搜索算法 双向搜索算法的思想是运行两个同时的搜索——其中一个从初始状态向前 搜索而另一个从目标状态向后搜索，当他们相遇时搜索终止。 双向搜索时通过这样一种方式实现的：让他的一个或者全部搜索在扩展结点 之前先检查该结点是否在另一棵搜索树的边缘结点集里；如果在，那么就找到了 一个解。空间需求是双向搜索最显著的弱点，当所用的两个搜索都是广度优先搜 索时，这个算法是完备的和最优的（在相同单步耗散的情况下），其他搜索组合 可能会牺牲完备性或最优性，或者两者都牺牲。双向搜索中最困难的情况就是目 标测试只给出对可能很大的目标状态集合的一个隐性描述。 2.有信息的搜索——启发式搜索算法 是一种在问题本身的定义之外的还利用问题的特定知识策略——如何能够比无 信息的策略更有效的找到解。考虑问题领域可应用的知识, 动态地确定规则的排 序, 优先调用较合适的规则使用。启发式搜索弥补盲目搜索的不足，提高搜索效 5 率。 2.1 最佳优先搜索算法 在最好优先搜索算法中，搜索是从最有希望的结点开始，并且生成其所有的 子结点，然后计算每个结点的性能，基于该性能选择最有希望的结点扩展（对所 有结点进行选择优点：如果早期选择了一个错误的结点，最好优先搜索就提供了 一个修改的机会），但是，该算法并没有显示地给出如何定义启发式函数并且不 能保证当从起始节点到目的结点的最短路径存在时，一定能够找到他。（为此， 需要对启发式函数等进行限制，A*算法就是对启发式函数限制后得到的一种启发 式搜索算法） 2.2 贪婪最佳优先搜索算法 试图扩展离目标结点最近的结点建立在这样可能很快找到解的基础上，他的 搜索代价最小而不是最优，之所以称之为“贪婪”，是因为在每一步他都要试图 找到离目标尽可能最近的结点。 贪婪最佳优先搜索算法再某些方面与深度搜索类似，它和深度优先搜索算法 一样更倾向于沿着一条路径搜索下去直到目标，但在遇到死路的时候会退回，所 以他和深度有同样缺陷——他不是最优的也不是最完备的（有可能沿着一条无限 的路径走下去而不回来尝试其他的选择）。 2.3 一般图启发式搜索A 算法 启发式搜索算法A，简称为A 算法，是一种典型的启发式搜索算法。其基本 思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望 的节点来扩展。利用评价函数f(n)=g(n)+h(n)来排列OPEN 表节点顺序的图搜索。 图搜索算法只记录状态空间中那些被搜索过的状态，他们组成一个搜索图称为 G。 2.4 启发式搜索算法A*，最小化总的估计解耗散 它把到达结点的耗散量和从该结点到目标结点的消耗结合起来对结点进行 评价：f(n)=g(n)+h(n),g(n)给出了从起始结点到结点n 的路径耗散，而h(n)是 从结点n 到目标结点的最低耗散路径的估计耗散值。f(n)=经过结点n 的最低耗 散解估计耗散。 A*算法是完备的最优的并且是有效地，但并不是说 A*算法对所有搜索问题 的需求，对大多数搜索问题搜索目标时的搜索空间的结点数仍然是目标结点深度 指数，从这个结果可以看到搜索过程中的复杂性仍然会以指数增长，除非启发式 函数中差值的增长没有比实际路径费用的岁数来的大，对于大多数在实际中使用 启发式函数来说，差值至少和路径的费用成正比，并且指数增长最终会使任何一 台计算机无法承受巨大的计算量。在 A*算法中计算时间不是主要问题，由于 A* 算法把所有生成的结点保存，所以 A*算法在耗尽计算时间之前一般早已经把空 间耗尽了。 2.5 存储限制的启发式搜索算法 2.5.1 迭代加深A*算法IDA* 以深度优先的方式在有限制的深度内搜索目标结 点，该算法在每一个深度上检查目标结点是否出现，如果出现则停止，否则，加 深加,继续搜索，而A*算法是选择具有最小估价函数值的结点扩展，IDA*是上述 两种算法的结合。 IDA*与A*相比主要优点是对于内存的需求。A*算法需要指数级数量的存储空间， 因为没有深度方面限制，而 IDA*算法只有当结点的所有子结点的 f(n)′小于限 制值时才扩展他，这样就可以节省大量内存。当启发式函数是最优的时候，IDA* 6 算法和A*算法扩展相同的结点。 2.5.2 递归最佳优先搜索算法 RBFS 是一个模仿标准的最佳优先搜索的递归算 法，但是他只使用线性的存储空间。他的结构和递归深度优先搜索类似，但是它 不沿着当前的不确定路径继续下去，而是记录从当前结点的祖先可得到的最佳可 替换路径的f 值。如果当前结点超过了这个限制，递归将转回到替换的路径上， 当递归回溯时，对回溯前的路径上的每一个结点，RBFS 用其子结点的最佳 f 值 替换其 f 值。这样，RBFS 能记住被他遗忘的子树中的最佳叶节点 f 值，并因此 能够在以后某个时刻决定是否值得重新扩展该子树。 RBFS 算法比IDA*算法效率更高，但是他还是需要重复生成大量结点。像A* 算法一样，如果启发函数h(n)是可采纳的，那么RBFS 算法是最优的，他的空间 复杂度是 O（bd）,时间复杂度难以刻画，既取决于他的启发函数的准确性，又 取决于当扩展结点时改变最佳路径的频度，IDA*和 RBFS 都服从和图搜索联系在 一起的潜在指数增长复杂度，因为他们都无法检测除了当前路径上的状态之外的 重复状态，因此，他们可能反复对一个状态探索多次。IDA*和 RBFS 的问题在于 利用的内存过于小了。在两次迭代之间，IDA*只保留一个数字：当前的f 耗散值 限制。RBFS 在内存中保留的信息多一些，但他只能利用复杂度为O（bd）的内存， 即便有了更多可用的内存，RBFS 也没有办法利用。 2.5.3 MA*和SMA*算法（储限制Ａ*和简化MA*） SMA*算法和A*算法一样，扩 展最佳叶结点直到内存放满为止。不丢弃一个旧结点他就无法在搜索树上加入一 个新结点，SMA*总是丢弃最差的一个叶结点——即f 值最高的。然后像RBFS 一 样把被遗忘结点的值备份到父结点。这样被遗忘子树的祖先结点可以了解那棵子 树中最佳路径的质量。只有当所有其他路径看来比被遗忘路径要差的时候 SMA* 才会利用这个信息重新生成该子树。 从实用角度来讲，SMA*算法是最好的寻找最优解的通用算法，尤其当状态空 间是一个图，单步耗散不一致，并且与维护open 表和close 表的附加系统开销 相比生成结点更大的时候。然而，一些非常困难的问题中通常 SMA*算法将会在 候选解路径集里的路径之间换来换去，只有一个很小的子集可以放到内存中。那 么重复生成相同的结点需要额外的时间意味着一个在有无限内存的条件下能被 Ａ*算法实际解决的问题，对于SMA*算法会成为不可操作的 [2] 。 2.6 与或图的启发式搜索算法AO* 对于与或图来说，由于局部图中有多个叶节点，不能像普通图搜索那样，通 过对某一个节点的评价来实现对整个局部图的评价。在普通图搜索中， f(n)=g(n)+h(n)，表面上是对n 的评价，实际上是对通过n 的这条路径的评价。 因此对于与或图搜索来说，就是通过对局部图的评价来选择待扩展的节点。为了 在AND-OR 图中找到解需要一个类似于A*的算法，Nilsson 把它称之为AO*算法。 AO*算法可以划分为两个阶段，即图生成过程和耗散值计算过程。 AO*算法类似于普通图搜索中的 A*算法。在 A*算法中，对当前搜索图的"前 沿"（即在OPEN 表中的节点）节点进行评价，选取f 值最小的节点进行扩展。 他和A*算法的主要区别在于：1.AO*算法能够处理AND 图，他应该找出一条路径， 即从该图的开始结点出发到达代表解状态的遗嘱结点。2.如果有些路径通往的结 点是其他路径上的结点扩展出来的结点，那么不能独立于这些路径去考虑某些从 结点到结点的个别路径。A*算法中，从一结点到另一结点的预期路径总是带最低 耗费的路径，但在 AO*算法中却并非如此。3.AO*算法仅对保证不含有任何回路 的图进行操作。这种保证是因为储存一条回路路径没有必要。这样的路径代表了 7 一条循环推理链。此外，AO*算法没有考虑子目标间的任一交互。 3.局部搜索算法等高级算法 3.1 爬山搜索算法 爬山法 （hill-climbing）：登高将会在达到一个巅峰时终止，相邻状态没 有比他更高的值。他是一个向值增加的方向移动的简单循环过程（最基本的局部 搜索算法，在每一步中当前的结点都会被最佳邻结点所替代） 缺点:该算法又称作贪婪局部搜索算法，因为它只是选择邻居状态中最好的 一个而事先不考虑之后下一步往哪个方向走。爬山算法从来不“下山”，即不会 向值比当前结点低的（或耗散高的）方向搜索，他肯定是不完备的因为它可能停 留在局部极大值上。 优点：尽管这样贪婪算法却往往有很好的效果，爬山法能很快的朝着解得方 向进展，因为他通常很容易一个块的状态。 爬山状态的成功与否在很大程度上取决于状态空间地形图的形状，如果在图 中几乎没有局部极大值和高原，随机重新开始的爬山法将会很快的找到好解。 3.2 局部剪枝搜索算法 只在内存中保存一个结点看来是对内存限制问题的一个极端反应。局部剪枝 搜索（local beam search）算法记录k 个状态而不是一个。它是由k 个随机生 成的状态开始。每一步生成全部k 个状态的所有后继状态，如果其中有一个是目 标状态，算法就停止。否则，它从整个后继列表中选择k 个最佳的后继，然后重 复这个过程。 在其简单的形式中，局部剪枝搜索会受到这k 个状态缺乏多样性的影响—— 他们将很快聚集到状态空间中的一小块区域内，使得搜索比一个代价高昂的爬山 法版本略多一些。这个算法的变化称为随机剪枝搜索，以随机爬山法类似，帮助 缓解这个问题。随机剪枝搜索不是从候选后继集合中选择最好的k 个后继状态， 而是按一定概率随机的选择k 个后继状态，其中选择给定后继状态的概率是状态 值的递增函数。随机剪枝选择和自然选择的过程有些相似性 [3] 。 3.3 模拟退火搜索算法 （simulated annealing,SA）的思想最早是由Metropolis 等于1953 年提出 的，SA 算法是基于 Mente Carlo 迭代求解策略的一种随机寻优算法，其出发点 是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火 算法在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随 机寻找目标函数的全局最优解，即局部最优解能概率性地跳出并最终趋于全局最 优。模拟退火算法是一种通用的搜索，优化算法，目前已在工程中得到广泛应用， 诸如VLSI，生产调度，控制工程，机器学习，神经网络，图像处理等领域。 模拟退火算法将爬山法和随机行走以某种方式结合起来，同时得到效率和完 备性；在（冶金中，退火是增强金属和玻璃的韧性和硬度，而先把它们加热到高 温再让它们逐渐冷却过程，能使材料结合成一个低能量的结晶态）。模拟退火搜 索算法和爬山搜索算法类似，不过它没有选择最佳的移动而选择随机的移动（一 个允许下山的随机爬山算法），在退火初期下山移动容易被接受，而随着时间的 推移下山的次数越来越少。 模拟退火算法的实验性能具有质量高，初值鲁棒性强，通用易于实现的优点。 但是为了寻到最优解的算法通常要求较高的初温，较慢的降温速率，较低的终止 温度以及各温度下足够多次的抽样，因而模拟退火算法往往优化过程过长，这也 8 是SA 算法的缺点。 3.4 遗传算法 （Genetic Algorithms 简称GA）由美国michigan 大学John holland 教授创 建的基于达尔文的进化论和孟德尔的自然遗传学说，是模拟遗传选择和自然淘汰 的生物进化过程的一种随机搜索与全局优化算法。 遗传算法首先采用某种编码方式将解空间映射到编码空间，每个编码对应 问题的一个解，称为个体或染色体，再随机确定起始的一群个体，称为种群。在 后续迭代中，按照适者生存原理，根据适应度大小挑选个体，并借助各种遗传算 子对个体进行交叉和变异，生成代表新的解集的种群，该种群比前代更适应环境， 如此进化下去直到满足优化准则。此时末代个体，经过解码，可作为问题近似最 优解。 遗传算法以有限的代价解决搜索和优化，其与传统搜索方法的区别主要在 于：①遗传算法直接处理问题参数的适当编码而不是参数集本身。②遗传算法按 并行方式搜索一个种群数目的点，而不是单点。 ③ 遗传算法不需要求导或其他 辅助知识，只需要适应度函数值。④ 遗传算法使用概率转换规则，而非确定的 转换规则指导搜索。⑤ 遗传算法在搜索过程中不易陷入局部最优，有较好的全 局优化能力。 遗传算法提供了一种求解复杂系统优化问题的通用模型，不依赖于问题的 具体领域和种类，故它广泛应用于许多领域：函数优化方面；组合优化方面有背 包问题，图划分问题等；生产调度问题方面有流水生产车间调度等；机器人学方 面有路径规划等；图象处理方面有模式识别，特征抽取等；机器学习方面有学习 模糊控制规则等；数据挖掘方面有规则开采等 [4] 。 3.5 群集智能算法 受社会性昆虫行为的启发，计算机工作者通过对社会性昆虫的模拟产生了一 系列对于传统问题的新的解决方法，这些研究就是群集智能的研究。群集智能中 的群体指的是“一组相互之间可以进行直接通信或者间接通信(通过改变局部环 境)的主体，这组主体能够合作进行分布问题求解”。而所谓群集智能指的是“无 智能的主体通过合作表现出智能行为的特性”。群集智能在没有集中控制并且不 提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了基础。 群集智能的特点和优点：群体中相互合作的个体是分布式的，这样更能够适 应当前网络环境下的工作状态; 没有中心的控制与数据，这样的系统更具有鲁棒 性，不会由于某一个或者某几个个体的故障而影响整个问题的求解。可以不通过 个体之间直接通信而是通过非直接通信进行合作，这样的系统具有更好的可扩充 性。由于系统中个体的增加而增加的系统的通信开销在这里十分小。系统中每个 个体的能力十分简单，这样每个个体的执行时间比较短，并且实现也比较简单， 具有简单性。因为具有这些优点，虽说群集智能的研究还处于初级阶段，并且存 在许多困难，但是可以预言群集智能的研究代表了以后计算机研究发展的一个重 要方向。 在计算智能领域有两种基于群智能的算法，蚂群算法和粒子群算法前者是对 蚂蚁群落食物采集过程的模拟，已经成功运用在很多离散优化问题上。 3.5.1 蚁群算法 (ant colony optimization, ACO)又叫蚂蚁算法，是一种用来 在图中寻找优化路径的机率型技术。20 世纪90 年代初意大利学者M.Dorigo 等通过模拟蚂蚁搜索路径的行为，提出了一种新型的仿生优化算法——蚁群算 法，并将其应用于经典的旅行商问题( TSP) ,取得了较好的实验效果, 在二次分 9 配问题(QAP) ,车间任务调度问题(JSP) 等问题中也得到了成功的应用。 蚂蚁在运动过程中，在它所经过的路程上留下信息素并感知信息素的存在及 其强度朝着强度高的方向移动，因此，由大量蚂蚁组成的蚁群集体行为表现出一 种信息正反馈现象。某一路径上走过的蚂蚁越多，后来的蚂蚁选择该路径概率就 越大，蚂蚁个体之间就是通过这种信息的交流进行路径的最优选择，从而达到搜 索食物的目的。 蚁群算法采用了正反馈并行自催化机制，具有较强的鲁棒性、优良的分布式 计算机制、易于与其他方法结合的优点，在短期内得到了很大发展，其应用领域 也不断得到扩展，显示了其在求解复杂的组合优化问题方面已展现出其优异的性 能和巨大的发展潜力。同时由于蚁群算法收敛速度慢，容易发生停滞，易于陷入 局部最优解等不足，国内外专家学者对其进行了不断的改进，提高了算法的性能。 蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质. 针对 PID 控制器参数优化设计问题,将蚁群算法与遗传算法的设计结果进行了比 较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应 用价值。蚁群算法是一种求解组合最优化问题的新型通用启发式方法，该方法具 有正反馈、分布式计算和富于建设性的贪婪的特点。 3.5.2 粒子群优化算法(Particle Swarm optimization，PSO)是一种进化计算技术，有 Eberhart 博士和Kennedy 博士发明。源于对鸟群捕食的行为研究。 PSO 模拟鸟群的捕食行为。一群鸟在随机搜索食物，在这个区域里只有一块 食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。 那么找到食物的最优策略就是搜寻目前离食物最近的鸟的周围区域。PSO 从这种 模型中得到启示并用于解决优化问题。PSO 中，每个优化问题的解都是搜索空间 中的一只鸟。称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应 值，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前 的最优粒子在解空间中搜索。 PSO 同遗传算法类似，是一种基于叠代的优化工具。系统初始化为一组随机 解，通过叠代搜寻最优值。与遗传算法比较，PSO 的信息共享机制是很不同的。 在遗传算法中，染色体 互相共享信息，所以整个种群的移动是比较均匀的向最 优区域移动。在 PSO 中, 只有 gBest (or lBest) 给出信息给其他的粒子， 这 是单向的信息流动。整个搜索更新过程是跟随当前最优解的过程。与遗传算法比 较, 在大多数的情况下，所有的粒子可能更快的收敛于最优解。研究表明PSO 是 一种很有潜力的神经网络算法，同时 PSO 速度比较快而且可以得到比较好的结 果。 同遗传算法比较，PSO 的优势在于简单容易实现并且没有许多参数需要调整。 目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的 应用领域。两者都随机初始化种群，而且都使用适应值来评价系统，而且都根据 适应值来进行一定的随机搜索。两个系统都不是保证一定找到最优解。但是，PSO 没有遗传操作如交叉和变异，而是根据自己的速度来决定搜索。粒子还有一个重 要的特点，就是有记忆 [5] 。 4.人工神经网络算法 “人工神经网络”(Artificial Neural Network 简称 ANN)是在对人脑组织 结构和运行机制的认识理解基础之上模拟其结构和智能行为的一种工程系统。早 在本世纪 40 年代初期，心理学家 McCulloch、数学家 Pitts 就提出了人工神经 10 网络的第一个数学模型，从此开创了神经科学理论的研究时代。其后，F Rosenblatt、Widrow 和J. J .Hopfield 等学者又先后提出了感知模型，使得人 工神经网络技术得以蓬勃发展。 人工神经网络是由大量的神经元广泛互连而成的系统，它的这一结构特点决 定着人工神经网络具有高速信息处理的能力。人脑的每个神经元大约有 103～ 104 个树突及相应的突触，一个人的大脑总计约形成 1014～1015 个突触。用神 经网络的术语来说，即是人脑具有 1014～1015 个互相连接的存储潜力。虽然每 个神经元的运算功能十分简单，且信号传输速率也较低(大约 100 次/秒)，但由 于各神经元之间的极度并行互连功能，最终使得一个普通人的大脑在约1 秒内就 能完成现行计算机至少需要数 10 亿次处理步骤才能完成的任务。人工神经网络 是一种非线性的处理单元。只有当神经元对所有的输入信号的综合处理结果超过 某一门限值后才输出一个信号。因此神经网络是一种具有高度非线性的超大规模 连续时间动力学系统。它突破了传统的以线性处理为基础的数字电子计算机的局 限，标志着人们智能信息处理能力和模拟人脑智能行为能力的一大飞跃 [6] 。 4.1 多层感知网络(误差逆传播神经网络) （Back Propagation，BP）网络是 1986 年由 Rumelhart 和 McCelland 为首的科学家小组提出，是一种按误差逆传播算法训练的多层前馈网络， 是目前应用最广泛的神经网络模型之一。BP 网络能学习和存贮大量的输入- 输出模式映射关系，而无需事前揭示描述这种映射关系的数学方程。它的 学习规则是使用最速下降法，通过反向传播来不断调整网络的权值和阈值， 使网络的误差平方和最小。BP 神经网络模型拓扑结构包括输入层、隐层和 输出层，相邻层之间的各神经元实现全连接且每层各神经元之间无连接。 BP 算法是一种有监督式的学习算法，其主要思想是：输入学习样本， 使用反向传播算法对网络的权值和偏差进行反复的调整训练，使输出的向 量与期望向量尽可能地接近，当网络输出层的误差平方和小于指定的误差 时训练完成，保存网络的权值和偏差。 但BP 网并不是十分的完善，它存在以下一些主要缺陷：学习收敛速度太慢、 网络的学习记忆具有不稳定性，即：当给一个训练好的网提供新的学习记忆模式 时，将使已有的连接权值被打乱，导致已记忆的学习模式的信息的消失。 4.2 竞争型(KOHONEN)神经网络 竞争型神经网络的基本思想是网络竞争层各神经元竞争对输入模式的响应 机会，最后仅有一个神经元成为竞争的胜者，并且只将与获胜神经元有关的各连 接权值进行修正，使之朝着更有利于它竞争的方向调整。神经网络工作时，对于 某一输入模式，网络中与该模式最相近的学习输入模式相对应的竞争层神经元将 有最大的输出值，即以竞争层获胜神经元来表示分类结果。这是通过竞争得以实 现的，实际上也就是网络回忆联想的过程。 竞争型神经网络的缺点和不足：因为它仅以输出层中的单个神经元代表某 一类模式。所以一旦输出层中的某个输出神经元损坏，则导致该神经元所代表的 该模式信息全部丢失。 4.3 Hopfield 神经网络 1986 年美国物理学家 J.J.Hopfield 提出的 Hopfield 神经网络是一层单层 反馈非线性神经网络，是神经网络发展史上的一个重要里程碑。他利用非线性动 力学系统理论中的能量函数方法研究反馈人工神经网络的稳定性，并利用此方法 建立求解优化计算问题的系统方程式。 11 网络中的每一个神经元都将自己的输出通过连接权传送给所有其它神经元， 同时又都接收所有其它神经元传递过来的信息，所以 Hopfield 神经网络是一个 反馈型的网络。其状态变化可以用差分方程来表征。反馈型网络的一个重要特点 就是它具有稳定状态。当网络达到稳定状态的时候，也就是它的能量函数达到最 小的时候。这里的能量函数是在表达形式上与物理意义上的能量概念一致，来表 征网络状态的变化的趋势，并可以依据 Hopfield 工作运行规则不断进行状态变 化，最终能够达到的某个极小值的目标函数。网络收敛就是指能量函数达到极小 值。如果把一个最优化问题的目标函数转换成网络的能量函数，把问题的变量对 应于网络的状态，那么Hopfield 神经网络就能够用于解决优化组合问题。 Hopfield 神经网络的能量函数是朝着梯度减小的方向变化，但它仍然存在 一个问题，那就是一旦能量函数陷入到局部极小值，它将不能自动跳出局部极小 点，到达全局最小点，因而无法求得网络最优解 [7] 。 5.展望： 虽然目前的人工智能算法研究水平暂时还很难使“人工智能机器”真正具备 人类的常识和思维，但人工智能算法将会在今后的各个领域得到蓬勃发展。不仅 仅只是功能模仿要持有信息机理一致的观点。即人工脑与生物脑将不只是功能模 仿，而是具有相同的特性。这两者的结合将开辟一个全新的领域，开辟很多新的 研究方向。人工智算法将探索智能的新概念，新理论，新方法和新技术来引导人 工智能在我们社会生活和科学技术的跨跃，而这一切将在以后的发展中取得重大 成就 [8] 。 致谢： 在本论文的写作过程中，我的导师倾注了大量的心血，从选题到开题报告， 从写作提纲，到一遍又一遍地指出每稿中的具体问题，严格把关，循循善诱，在 此我表示衷心感谢。同时我还要感谢在我学习期间给我极大关心和支持的各位老 师以及关心我的同学和朋友。 参考文献： [1]贲可荣，张彦铎.人工智能[M]：清华大学出版社，2006.3 [2]Stuart Russell，Peter Norvig . Artificial Intelligence A Modern Approach[M].2 版.姜哲等译.人民邮电出版社，2004.6 [3]邵军力，张景，魏长华.人工智能基础[M]：电子工业出版社，2000.3 [4]Thomas Dean，James Allen，Yiannis Aloimonos, 人工智能——理论与实践[M].刘海波， 宇等译.电子工业出版社，2004.6 [5]朱福喜，汤怡群，傅建明.人工智能原理[M]：武汉大学出版社，2002.2 [6]Fredric M.Ham Ivica Kostanic.神经计算原理[M]. 叶世伟，王海娟译.机械工业出版社， 2007.5 [7]丁永生.计算智能——理论、技术与应用[M]：科学出版社，2004.8 [8]黄席樾，向长城，殷礼胜.现代智能算法理论及应用[M].2 版：科学出版社，2005.4