[科普中国]-启发式程序

概述

启发式搜索法是一种有效的重要方法，它不是依靠数学上的理论推导，而主要是靠一些总结出来的解决问题的有效经验，如策略、法制、简化步骤等来解决问题，把这些经验性的东西写成规则形式就是启发式规则。

所谓搜索过程是指一种利用局部性知识(如何从任一状态向目标状态靠近的知识)构造出全局性答案(问题的一个解或最佳解)的过程，系统内部事先没有构造这种答案的全局性知识。反之，如果系统内部已经具有直接构造全局性答案的完整知识，则构造这个答案的过程不是搜索过程。2

1987年，比利时学者H.穆勒利用启发式知识发展支持决策系统，开发了复杂柔性生产系统的生产计划专家系统H11。

1995年，何栋中研究了启发式搜索法在确定坯一材关系中的应用，制订了优化的剪切方案。

启发式程序是实现启发式搜索算法的计算机程序。著名的启发式搜索程序有20世纪70年代初N．J．尼尔松给出的A算法、A‘算法，以及后来的与或图启发式AO‘搜索算法等。1

启发式程序的应用包括两个主要环节：一是知识表示；二是搜索求解。

布鲁纳还提出了启发式程序的某种特性：“启发式程序实质上是达到解决难题的一种不严密的方法：启发式程序常常使难题解决，但它提不出解决难题的保证。此外，算法也是解答问题的一种程序，如果进行得准确，它保证会经由一定的步骤发现问题的解答办法——只要这个问题有解答之道。当算法的程序不明了的时候，往往可用启发式程序，这是启发式程序的优点之一。而且，即使有合用的算法时，启发式程序也往往进度更快得多。另一方面，经常应用一般的启发式规则——利用类比：3

性质启发式程序具有3个性质：

（1）局部性：启发式程序在求解某类问题的结果时．不一定保证是准确解或最佳解；

（2）试探性：启发式程序求解问题时允许失误而改用其他的方法；

（3）针对性：启发式程序可以利用某些被解问题的特殊规律，大大简化该问题的求解过程，具有较强的针对性。

依靠启发，只须事先掌握把前提和结论联系起来的部分先验信息，一般求解问题比较简捷，在求解复杂问题时，可以更好地表现出人类智慧的特征。在处理实际问题时．并不是单纯地使用上述两种方法中的某一种，而是交替地使用算法和启发。一般是在战略决策上较多地使用启发，在战术推进上较多地使用算法。4

启发式程序的应用环节知识表示解决一个问题的前提是对此问题进行准确的描述，也就是对此问题中涉及的知识进行适当的表示。因此，运用知识表示方法对问题的概念、特点做出准确描述，为所求解问题建立准确的模型具有重要的意义。

知识表示方法是关于如何描述事物的一组约定。问题求解过程主要是一个获得并应用知识的过程，而知识必须有适当的表示才能在计算机中储存、检索、使用和修改。所谓知识的机器表示技术就是研究在计算机中如何用最适合的形式对问题求解过程中所需的各种知识进行组织，它与问题的性质和求解的方法有密切的关系。

状态空间表示法是最基本的知识表示方法，是讨论其他形式化方法和问题求解技术的出发点。下面对状态、操作和状态空间做一简单介绍。

所谓状态(state)，就是为描述某一类事物中各个不同事物之间的差异而引入的一组变量q(0)，q(1)，q(2)，…的有序组合。它常表示成矢量形式：Q=[q(0)，q(1)，q(2)，…]

式中，每个元素q(i)称为分量，其相应的变域为[q(i)，b(i)]。状态的维数可以是有限的，也可以是无限的。给定每个分量的值g(i，k)，就得到一个具体的状态：Q(k)=[q(0，k)，q(1，k)，q(2，k)，…]

状态还可以表示成多元数组[q(0)，q(1)，q(2)，…]或其他方便的形式。

引起状态中的某些分量发生改变，从而使问题由一个具体状态变化到另一个具体状态的作用，称为算子(operator)，它可以是一个机械性的步骤、过程、操作或规则。算子描述了状态之间的关系。

问题的状态空间(state space)是一个表示该问题的全部可能状态及其相互关系的图，一般是一个赋值有向图，其中包括以下三方面的详细说明：

S：问题可能有的初始状态的集合；

F：操作的集合；

G：目标状态的集合。

所以状态空间常记为三重序元(S，F，G)。在状态空间表示法中，问题求解过程转化为在图中寻找从初始状态出发到达目标状态的路径问题，也就是寻找操作序列口的问题。所以状态空间中的解也常记为三重序元(，a，)，它包含了以下三方面的详细说明：

：某个初始状态；

：某个目标状态；

a：把变换成的有限操作序列。2

搜索求解所谓搜索过程是指一种利用局部性知识(如何从任一状态向目标状态靠近的知识)构造出全局性答案(问题的一个解或最佳解)的过程，系统内部事先没有构造这种答案的全局性知识。反之，如果系统内部已经具有直接构造全局性答案的完整知识，则构造这个答案的过程不是搜索过程。例如盲人爬山时，他不知山在何方，向何处走(全局性答案)，只知道每步都选最陡的方向前进(局部性知识)，这个过程是搜索；而利用解一元一次方程的算法，可以直接求出结果，这个过程不是我们所讨论的搜索问题，或称为零步搜索问题。

搜索技术是应用十分广泛的机械化推理技术之一，特别是其中的启发式搜索原理(heuristic search theory)，它可以帮助我们利用部分状态空间来求解问题，这样就大大提高了解题效率。

传统的基本搜索策略都是非启发式的搜索，其控制性知识仅仅是基本搜索策略，没有包含辅助性策略，例如被解问题的解的任何特性。基本搜索策略的优点是控制性知识比较简单，但它原则上都要求知道问题的全部状态空间图，其搜索效率不高，不便于许多复杂问题的求解。为了提高搜索效率，人们研究了许多有较强启发能力的搜索策略。

启发式搜索的基本思想是在控制性知识中增加关于被解问题的解的某些特性，以便指导搜索朝最有希望的方向前进。所以启发式搜索与基本搜索不同，从原则上讲只需要知道问题的部分状态空间就可以求解该问题，搜索效率较高。通过后面的讨论可以看出，正是控制性知识中的启发信息，弥补了由于略去部分状态空间带来的信息损失。2

启发式搜索策略一般而言，问题的求解过程表现为从初始状态（初始可行解）开始，不断搜索寻找目标状态（最终优化解）的过程。由于求解问题的过程中求解条件的不确定性和不完备性，造成可能的分支有很多，从而使得众多求解路径构成了一个图，即问题解的状态空间。问题的求解实际上就是状态空间搜索过程。

常用的状态空间搜索策略有深度优先搜索策略和广度优先搜索策略。广度优先搜索策略是从初始状态一层一层向下找，直到找到目标解为止。深度优先搜索策略是按照一定的顺序先查找完一个分支，再查找另一个分支，以至找到目标解为止。然而广度优先搜索和深度优先搜索都是在一个给定的状态空间中进行穷举搜索，如果问题状态空间非常大，且不可预测时，则深度优先搜索和广度优先搜索效率太低，甚至不可完成。

启发式搜索策略是在问题状态空间的搜索中首先对每一个可能的搜索位置进行评估，得到一个最好的位置，再从这个位置出发进行下一步搜索，直到找到目标解，从而省略大量的搜索路径，提高了搜索效率。

在启发式搜索中，对某个位置的评估是十分重要的。采用不同的评估函数可以有不同的效果，其一般形式如下：

其中是节点的估价函数，是在状态空间中从初始节点到节点n的实际代价，代表了搜索广度的优先趋势。 是从节点n到目标节点最佳路径的估计代价，它体现了搜索的启发信息。

设为解的可行域，启发式搜索算法的基本思想是从一个初始解开始，然后运用局部搜索策略，持续地在当前解的邻域中搜索比 更优的解。若找到比更优的解，就用这个解取代，成为当前解，再对当前解继续重复上述过程，直到当前解优于其邻域中的所有解为止。

从PSO算法的仿生优化原理上看，PSO算法是一种启发式算法。因为PSO算法是通过对某种社会性群体搜索现象的简化模拟而设计的。PSO算法搜索的每一步都是在粒子自身历史经验和群体中最优粒子的指导（或启发）下进行搜索的。PSO算法并没有从原理上说明这种算法为什么有效，以及它的适用范围，因此PSO算法特点也符合启发式算法的定义：启发式算法是一种技术，这种技术使得在可接受的计算费用内去寻找最好的解，但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法阐述所得解与最优解的近似程度。5