(启发式搜索).docx

人工智能技术报告启发式搜索产生背景: 何谓启发式搜索算法在说它之前先提提状态空间搜索。状态空间搜索,如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说,两点之间求一线路,这两点是求解的开始和问题的结果, 而这一线路不一定是直线,可以是曲折的。由于求解问题的过程中分枝有很多, 主要是求解过程中求解条件的不确定性,不完备性造成的,使得求解的路径很多这就构成了一个图,我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找,直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支, 再查找另一个分支,以至找到目标为止。这两种算法在数据结构书中都有描述, 可以参看这些书得到更详细的解释。前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法,可是当状态空间十分大,且不预测的情况下就不可取了。他的效率实在太低,甚至不可完成。在这里就要用到启发式搜索了。定义: 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径, 提到了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。启发中的估价是用估价函数表示的,如: f(n) = g(n) + h(n) 其中 f(n) 是节点 n的估价函数, g(n) 是在状态空间中从初始节点到 n节点的实际代价, h(n) 是从 n到目标节点最佳路径的估计代价。在这里主要是 h(n) 体现了搜索的启发信息,因为 g(n) 是已知的。如果说详细点, g(n) 代表了搜索的广度的优先趋势。但是当 h(n) >> g(n) 时,可以省略 g(n) ,而提高效率。这些就深了。算法举例启发算法有:蚁群算法,遗传算法、模拟退火算法等蚁群算法是一种来自大自然的随机搜索寻优方法,是生物界的群体启发式行为,现己陆续应用到组合优化、人工智能、通讯等多个领域。蚁群算法的正反馈性和协同性使其可用于分布式系统,隐含的并行性更使之具有极强的发展潜力。从数值仿真结果来看,它比目前风行一时的遗传算法、模拟退火算法等有更好的适应性。分析: 蚁群算法蚁群算法(ant colony optimization , ACO) ,又称蚂蚁算法,指的是一种源于自然现象的算法,也是一种 meta heuristic ,即与具体问题关系不大的优化算法,也就是它是一种用来在图中寻找优化路径的机率型技术。蚂蚁觅食原理: 自然界中,蚂蚁这种视盲生物,在没有任何先知经验的情况下总能找到从其巢穴到食物源的最佳路径,甚至在该路径上放置障碍物之后, 它们仍然能很快重新找到新的最佳路线。这是因为在蚂蚁个体之间是通过一种称为信息素的物质进行信息传递的。蚂蚁在运动过程中,不但能够在它所经过的路径上留下该物质,而且能够感知这种物质的存在及其强度,并朝着该物质强度高的方向移动,为此指导自己的运动方向。因此,由大量蚂蚁组成的蚁群集体行为表现出一种信息正反馈现象。在一定时间内较短路径通过的蚂蚁要多于较长路径,而某一路径上走过的蚂蚁