数学建模中用到的启发式算法

启发式搜索启发(heuristic)是关于发现和发明规则及方法的研究。在状态空间搜索中,启发式被定义成一系列规则,它从状态空间中选择最有希望到达问题解的路径。人工智能问题求解者在两种基本情况下运用启发式策略:1.一个问题由于在问题陈述和数据获取方面固有的模糊性可能使它没有一个确定的解。医疗诊断即是一例。所给出的一系列症状可能有多个原因;医生运用启发搜索来选择最有可能的论断并依此产生治疗的计划。视觉问题又是一例。看到的景物经常是模糊的,各个物体在其连接、范围和方向上可以有多个解释。光所造成的幻觉加大了这些模糊性,视觉系统可运用启发式策略选择一给定景象的最有可能解释。2.一个问题可能有确定解,但是求解过程中的计算机代价令人难以接受。在很多问题(如国际象棋)中,状态空间的增长特别快,可能的状态数随着搜索的深度呈指数级增长、分解。在这种情况下,穷尽式搜索策略,诸如深度优先或广度优先搜索,在一个给定的较实际的时空内很可能得不到最终的解。启发式策略通过指导搜索向最有希望的方向前进降低了复杂性。通过仔细考虑,删除某些状态及其延伸,启发式算法可以消除组合爆炸,并得到令人能接受的解。然而,和发明创造的所有规则一样,启发式策略也是极易出错的。在解决问题过程中启发仅仅是下一步将要采取措施的一个猜想。它常常根据经验和直觉来判断。由于启发式搜索只有有限的信息,诸如当前Open表中状态的描述,要想预测进一步搜索过程中状态空间的具体的行为很难办到。一个启发式搜索可能得到一个次最佳解,也可能一无所获。这是启发式搜索固有的局限性。这种局限性不可能由所谓更好的启发式策略或更有效的搜索算法来消除。启发式策略及算法设计一直是人工智能的核心问题。博奕和定理证明是两个最古老的应用:二者都需要启发式知识来剪枝以减少状态空间。显然,检查数学领域中每一步推理或棋盘上每一步可能的移动是不可行的。启发式搜索常常仅是实践中的解答。近来,专家系统的研究把启发式策略作为问题求解的一个重要部分。当一个专家解决问题时,他检查所获取的信息并作出决定。实际上,专家用来解决问题的拇指法则很大程度上是启发式的。这些启发性知识被专家系统的设计者提取出来并形成规则。通常启发式算法由两部分组成:启发方法和使用该方法搜索状态空间的算法。本章先介绍最好优先搜索的算法,再讨论启发式算法的设计和评估。在一字棋游戏中(图4.5),穷尽搜索的组合数很大。第一步移动共有九种移法,每一种又有八种对应走法……依次类推,这个问题在穷尽搜索策略下需考虑9!个状态。根据对称性可以减少搜索空间的数目。棋盘上很多构造是等价的。譬如,第一步实际上只有三种移法,角、边的中央以及网络正中。在状态空间的第二层上,由对称性可进一步减少到12×7!种。在图5.1中可见到该状态空间比最初的状态空间要小,但它在扩展过程中还要继续分解。然而,一个简单的启发式策略几乎可以整个地消除复杂的搜索过程。首先,将棋子移到棋盘上×有最多的赢线的点。最初的三种状态显示在图5.2中。若两种状态有相等的赢的机率,取其中的第一个。这样的话,可设计一种算法(完全实现启发式搜索),它选择并移到具有最高启发值的状态。在这种情况下,×占椐网络的中间点,其它的各种状态都不再考虑,它们的延伸状态同时也给消除了。如图5.3所示三分之二的状态空间就这样给剪枝了。第一步走完后,对方只能有两种走法(见图5.3)。无论选择哪种走法,我方均可以通过启发式搜索选择下一步可能的走法。在搜索过程中,每一步只需估价一下单个节点的子结点;不需要强力搜索。图5.3显示了游戏前三步简化了的搜索过程。每种状态都标记了它的启发值。要精确地计算待检查的状态的数目比较难,但可以大致计算它的上限。一盘棋最多走九步,每步的下一步平均有四、五种走法。这样大约就是4.5×9,近40种状态,比9!改善了很多。5.1启发信息和估计函数人工智能的核心课题是问题求解。所谓问题求解就是在广义图中寻找一条从初始状态出发,到达目标状态的解树。例如旅行问题是解决从出发点到达目的地的路线和工具问题;机器人装配机器,就是给出把一堆零件变成一台机器的一系列操作;定理证明就是寻找一条从前提条件到达结论的通路等等。在实际解决一个具体问题时,人们常常把一个具有复杂联系的实际问题抽象化,保留某些主要因素,忽略掉大量次要因素,从而将这个实际问题转化成具有明确结构的有限状态空间问题,这个空间中的状态和变化规律都是已知的有限集合,因此可以找到一个求解该问题的算法。然而,在智能活动中使用最多的不是具有完备性的算法,而是不一定完备的启发式方法。其原因有二:首先,大多数情况下,智能系统不知道与实际问题有关的全部信息,因而无法知道该问题的全部状态空间,不可能用一套算法来求解其中的所有问题,这样就只能依靠部分状态空间和一些特殊的经验性规则来求解其中的部分问题。其次,有些问题在理论上存在求解算法,但是在工程实践中,这些算法不是效率太低,就是根本无法实现,为了提高解题的效率,不得不放弃使用这些算法,而求助于一些经验性的启发式规则。例如在博弈问题中,计算机为了保证最后胜利,可以将所有可能的走法都试一遍,然后选择最佳走步。这样的算法是可以找到的,但计算所需的时空代价十分惊人。就可能有的棋局数讲,一字棋是9!=3.6×105,西洋跳棋是1078,国际象棋是10120,围棋是10761。假设每步可能选择一种棋局,用极限并行速度(10-104年/步)计算,国际象棋的算法也得1016年即1亿亿年才可以算完,而我们已知的宇宙史才100亿年!由此看来,启发式的问题求解,不仅在实践上是需要的,而且在理论上也是必不可少的。对问题空间进行搜索时,提高搜索效率需要有和被解问题的解有关的大量控制性知识作为搜索的辅助性策略。有两种极端的情况:一种是没有任何这种控制性知识作为搜索的依据,因而搜索的每一步完全是随意的,如随机搜索;另一种是有充分控制性知识作为依据,因而搜索的每步选择都是正确的,这种搜索叫最佳搜索。一般情况是介于二者之间,这些控制性信息反映在估价函数之中。估价函数的任务就是估计待搜索结点的重要程度,给它们排定次序。估价函数f(x)可以是任意一种函数,如有的定义它是结点x处于最佳路径上的概率,或是x结点和目标结点之间的距离,或是x格局的得分等等。一般来说,估价一个结点的价值,必须综合考虑两方面的因素:已经付出的代价和将要付出的代价。在此,我们把估价函数f(n)定义为从初始结点经过n结点到达目标结点的最小代价路径的代价估计值,它的一般形式是:f(n)=g(n)+h(n)其中g(n)是从初始结点到n的实际代价,h(n)是从n到目标结点的最佳路径的估计代价,主要是h(n)体现了搜索的启发信息。因为实际代价g(n)可以根据生成的搜索树实际计算出来,而估计代价h(n)却依赖于某种经验估计,它来源于我们对问题的解的某些特性的认识,这些特性可以帮助我们更快地找到问题的解。一般地,在f(n)中,g(n)的比重越大,越倾向于广度优先搜索方式;h(n)的比重越大,越倾向于深度优先搜索方式。g(n)的作用一般是不可忽略的,因为它代表了从初始结点经过n到达目标结点的总代价估值中实际已付出的那一部分。保持g(n)项就保持了搜索的广度优先趋势,这有利于搜索的完备性,但影响搜索的效率。在特殊情况下,如果只希望找到达到目标结点的路径而不关心已付出的代价,则g(n)的作用可以忽略。另外,h(n)g(n)时,也可以忽略g(n),这时有f(n)=h(n),这有利于搜索的效率,但影响搜索的完备性。给定一个问题后,根据问题的特性和解的特性,可以有多种方法定义估价函数,用不同的估价函数指导搜索,其效果可以相差很远。因此,必须尽可能选择最能体现问题特性的,最佳的估价函数。5.2启发式搜索算法5.2.1局部择优搜索法(瞎子爬山法)实现启发式搜索最简单的方法是瞎子爬山法(hillclimbing)。瞎子爬山法在搜索过程中扩展当前结点并估价它的子结点。最优的子结点被选择并进一步扩展;该子结点的兄弟结点和父结点都不再保留。当搜索达到一种状态,该状态比它的所有子结点都要好,则搜索停止。瞎子爬山法可以这样理解──一个盲人急切地想登上山顶,他总是沿着最陡的山路向上爬,直到再不能找到新的路径。瞎子爬山法有这样一个缺陷:一个错误的启发知识可能导致搜索无法沿着正确的路径前进,从而增加了搜索的深度,甚至是无穷尽地搜索。由于瞎子爬山法不保存所走过的结点信息,故瞎子爬山算法无法修正错误的路径。瞎子爬山法还可能在一个局部的最佳点上停止。当搜索到一个结点,它的估计代价比任一个子结点都要小,则算法结束。如果此时并不是目标状态,而只是一个局部最优结点,则该算法就不能得到目标解。因此,在一个限定的环境下,瞎子爬山法可能会极大地提高搜索效率,但是对于整个搜索空间,就有可能无法得到最佳解。重排九宫游戏就是一个突出的例子。为了将一个特定的格局移到它的目标位置上,常常需要移动已经在其目标位置上的将牌。这对于完成拼图是必要的,但它显然暂时恶化了拼板上的状态。由于更好并不是最好,瞎子爬山法无法区别局部和全局最优解。处理这个问题时有许多种方法,譬如随时地修正估价函数来突破局部最优的限制。但是总的来说,没有一种方法能保证瞎子爬山法的最佳效率。下面介绍一个瞎子爬山法的例子──跳棋程序。在人工智能中,Samuel的跳棋程序最早应用该方法。在跳棋程序中,不仅运用了启发式搜索,还实现了简单的学习功能。跳棋程序中根据几个不同启发值的总和来估算棋局的状态:∑aixii其中xi是棋局的一系列特征,如残局优势、残局棋子力量分布,中心点位置的控制等。这些xi的系数由它在整个估值中所处的重要性来确定。也就是说,如果残局优势比控制中心点重要,则残局优势的系数要大。该程序将搜索空间扩展到一定局数并根据多项式估值函数估算该局中所有状态值。根据5.4.2节介绍的极大极小法,程序可倒推出图中所有状态的估值。游戏者根据结点的最佳状态走棋;对手走棋后,根据新的棋局状态,整个过程将再来一遍。若多项式估值函数导向一系列不能取胜的移动,程序将调整其系数以提高能力。具有较大系数的因素由于在输棋原因中占很大比重,它的系数将减小,而较小的系数将增大以提高相关因素的影响力。如果取胜则情况相反。通过与人或其自身的不同版本对抗,程序不断训练学习。可以看出,跳棋游戏在学习过程中采用的是瞎子爬山法,通过对多项式估值函数的局部的改进来提高自身的性能。该程序能不断改进到水平很高为止。然而,由于算法依靠瞎子爬山法,它不可避免地具有某些限制。例如,由于采用的不是全局的策略,程序容易被对手利用某种启发策略导向陷阱。同样,程序的自学习功能容易被对手的随手棋所迷惑;例如,老对手灵活地采用多种策略,或故意乱下棋,这就会使多项式估值函数的系数随意性很大,从而全面降低了程序的能力。上例表明,尽管瞎子爬山法有其局限性,但是若估价函数选取得当并能够避免局部最优解和无穷搜索时,它就会充分发挥搜索的高效率。总之,启发式搜索需要一个具有很多启发信息的算法,而最好优先搜索就提供了这一算法。5.2.2最好优先搜索法(有序搜索法)和第四章中所提到的深度优先及广度优先搜索算法一样,最好优先搜索算法也使用了两张表来记录结点信息:在Open表中保留所有已生成而未考察的结点;在Closed表中记录已访问过的结点。算法中有一步是根据某些启发信息,按结点距离目标状态的长度大小重排Open表中的结点这样。循环中的每一步只考虑Open表中状态最好的结点,这就是最好优先搜索算法,又称为有序搜索法。其数据结构(Open表)既不同于广度优先使用的队(先进先出),也不同于深度优先使用的栈(后进先出),而是一个按结点的启发估计函数值的大小为序排列的一个表,有时也称为优先队。进入优先队的结点不是简单地排在队尾(或队首),而是根据其估值的大小插入队中合适的位置,每次从队中优先取出估值最小的结点加以扩展。最好优先搜索的算法描述如下:PROCEDUREBEST-FIRST-SEARCHINITIALIZE:OPEN=[START];CLOSED=[];WHILEOPEN≠[]DOBEGI