浅谈人工智能中的启发式搜索策略

摘要:人工智能所要解决的问题大部分是非结构化或结构不良的问题,启发式搜索可以极大提高效率。讲述了搜索策略中的启发式搜索,对它的原理进行讲解,前景进行了展望。

关键词:人工智能;启发式搜索;估价函数

中图分类号:TP391 文献标识码:A文章编号:1007-9599 (2010) 06-0000-01

Discussion on Heuristic Search Strategy in Artificial Intelligence

Hu Lidan,Yuan Yun,Yin Wen

(School of Information and Electrical Engineering,CUMT,Xuzhou221008,China)

Abstract:The problems to be solved by artificial intelligence(AI)are mostly unstructured or poorly structured.And the heuristic search is more efficient.The principle of the heuristic search is demonstrated and its processing is summarized.

Keywords:Artificial intelligence;Heuristic search;Valuation function

盲目搜索即是按预定的控制策略进行搜索[1],这种搜索具有盲目性,效率不高,不便于复杂问题的求解。为解决此类问题,人们提出启发式搜索策略,即在搜索中加入与问题有关的启发式信息,用以指导搜索朝着最有希望的方向前进,加速问题求解的效率并找到最优解。

一、启发式搜索策略的发展历史

40年代:由于实际需要,提出了启发式算法,具有快速有效的特点。50年代:启发式搜索逐步繁荣,其中贪婪算法和局部搜索得到人们的关注。

60年代:反思阶段,人们发现以前提出的启发式算法速度很快,但是解的质量不稳定,而且对大规模的问题仍然无能为力。

70年代:计算复杂性理论的提出。人们发现贪婪算法和局部搜索算法速度快,但解不好的原因是得到的解没有全局最优性。Holland的遗传算法的出现再次引发了人们研究启发式算法的兴趣。

80年代以后,模拟退火算法,人工神经网络,禁忌搜索等新式算法相继出现。

二、启发式搜索策略的工作原理

盲目式搜索求解的过程中,节点的扩展次序是随意的,且没有利用已解决问题的特性,为此需要扩展的节点数会非常大。启发式搜索则克服了上述缺点,它利用搜索过程中的有用信息优化搜索。

(一)一般搜索过程

基本思想[2]:把初始结点作为当前状态,选择适用的算符对其进行操作,生成一组子状态,然后检查目标状态是否在其中出现。若出现,则搜索成功,否则从已生成的状态中再选一个状态作为当前状态。重复上述过程,直到目标状态出现或者不再有可供操作的状态和算符时为止。

在给出具体过程之前,首先介绍两个数据结构――OPEN表和CLOSED表。OPEN表用于存放刚生成的节点。CLOSED表用于存放将要扩展或者已经扩展的节点。

搜索的一般过程如下:

1.把初始节点S0放入OPEN表,并建立目前只包含S0的图,记为G。

2.检查OPEN表是否为空,若为空则问题无解,退出。

3.把OPEN表的第一个节点取出放入到CLOSED表,并记该节点为节点n。

4.考察节点n是否为目标节点。若是,则求得了问题的解,退出。

5.扩展节点n,生成一组子节点。把其中不是节点n先辈的那些子节点记作集合M,并把这些子节点作为节点n的子节点加入到G中。

6.针对M中子节点的不同情况,分别进行如下处理:①对于那些未曾在G中出现过的M成员设置一个指向父节点(即节点n)的指针,并把他们放入OPEN表中;②对于那些先前已在G中出现过的M成员,确定是否需要修改指向父节点的指针;③对于那些先前已在G中出现并且已经扩展了M的成员,确定是否需要修改其后继节点指向父节点的指针。

7.按某种搜索策略对OPEN表中的节点进行排序。

8.转向2步。

由以上介绍可知,问题的求解过程实际上就是搜索过程,问题的求解的状态空间图是通过搜索逐步形成的,边搜索边形成,而且搜索每前进一步,就要检查一下是否到达了目标状态,这样就可尽量少生成与问题无关的状态,即节省了存储空间,又提高了求解效率。

(二)估价函数

用于估价节点重要性的函数称为估价函数[3],其一般形式为:f(x)=g(x)+h(x),g(x)为从初始节点S0到节点x已经实际付出的代价;h(x)是从节点x到目标节点Sg的最优路径的估计代价,它体现了问题的启发性信息,其形式要根据问题的特性确定。例如,它可以是节点x到节点的距离,也可以是处于最优路经上的概率等;h(x)称为启发函数。

估价函数f(x)表示从初始节点经过节点x到目标节点的最优路径的代价估价值,它的作用是估价OPEN表中各节点的重要程度,决定它们在OPEN表中的次序。其中g(x)指出了搜索的横向趋势,它有利于搜索的完备性,但影响搜索的效率。如果我们只关心到达目标节点的路径,并且希望有较高的搜索效率,则g(x)可以忽略,但此时会影响搜索的完备性,因此,在确定f(x)时,要权衡各种利弊得失,使g(x)与h(x)各占适当的比重。

三、小结

启发式搜索算法是一种很实用、很有效的算法,比如SA算法具有对初始点的不依赖性,可以任意选取初始解和随机序列,应用广泛。SA普及的最重要的原因是能在复杂的情况下产生更高质量的解,因此,它特别适用于非线性和复杂的系统。在多目标优化领域,SA还处于起步阶段,在种群选择以及如何与Pareto前沿结合等方面,还需要进一步地研究,SA具有广阔的发展前景。

参考文献:

[1]George F.Luger著,史忠植,张银奎译.人工智能[M].北京:机械工业出版社,2004

[2]田中.人工智能中搜索策略的探讨[J].福建电脑,2004,(08):30-31

[3]王万森.智能原理及其应用(第2版)[M].北京:电子工业出版社,2007