啓發式程序

啓發式搜索法是一種有效的重要方法，它不是依靠數學上的理論推導，而主要是靠一些總結出來的解決問題的有效經驗，如策略、法制、簡化步驟等來解決問題，把這些經驗性的東西寫成規則形式就是啓發式規則。

所謂搜索過程是指一種利用局部性知識(如何從任一狀態向目標狀態靠近的知識)構造出全局性答案(問題的一個解或最佳解)的過程，系統內部事先沒有構造這種答案的全局性知識。反之，如果系統內部已經具有直接構造全局性答案的完整知識，則構造這個答案的過程不是搜索過程。 ^[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]