啟發(fā)式算法（Heuristic Algorithm）

啟發(fā)式算法（Heuristic Algorithm）有不同的定義：一種定義為，一個(gè)基于直觀或經(jīng)驗(yàn)的構(gòu)造的算法，對優(yōu)化問題的實(shí)例能給出可接受的計(jì)算成本（計(jì)算時(shí)間、占用空間等）內(nèi)，給出一個(gè)近似最優(yōu)解，該近似解于真實(shí)最優(yōu)解的偏離程度不一定可以事先預(yù)計(jì)；另一種是，啟發(fā)式算法是一種技術(shù)，這種技術(shù)使得在可接受的計(jì)算成本內(nèi)去搜尋最好的解，但不一定能保證所得的可行解和最優(yōu)解，甚至在多數(shù)情況下，無法闡述所得解同最優(yōu)解的近似程度。我比較贊同第二種定義，因?yàn)閱l(fā)式算法現(xiàn)在還沒有完備的理論體系，只能視作一種技術(shù)。

名詞解釋

Heuristics，我喜歡的翻譯是“探索法” ，而不是“啟發(fā)式”，因?yàn)榍罢吒H民一些，容易被理解。另外，導(dǎo)致理解困難的一個(gè)原因是該詞經(jīng)常出現(xiàn)在一些本來就讓人迷糊的專業(yè)領(lǐng)域語境中，例如，經(jīng)?？?到某某殺毒軟件用啟發(fā)式方法查毒，普通民眾本來就對殺毒軟件很敬畏，看到“啟發(fā)式”就更摸不著北了。

實(shí)際上，這個(gè)詞的解釋十分簡單，例如，查朗文詞典，可以看到：

The use of experience and practical efforts to find answers to questions or to improve performance

維基百科詞條heuristic，將其定義為基于經(jīng)驗(yàn)的技巧（technique），用于解決問題、學(xué)習(xí)和探索。并對該詞進(jìn)行了更詳盡的解釋并羅列了多個(gè)相關(guān)領(lǐng)域：

A heuristic method is used to** rapidly** come to a solution that is hoped to be close to the best possible answer, or 'optimal solution'. A heuristic is a "rule of thumb", an educated guess, an intuitive judgment or simply common sense.
A heuristic is a general way of solving a problem. Heuristics as a noun is another name for heuristic methods.

Heuristic可以等同于：實(shí)際經(jīng)驗(yàn)估計(jì)（rule of thumb）、有依據(jù)的猜測（educated guess, a guess beased on a certain amount of information, and therefore likely to be right）和常識（由經(jīng)驗(yàn)得來的判斷力）。

一個(gè)容易理解的解釋

人在解決問題時(shí)所采取的一種根據(jù)經(jīng)驗(yàn)規(guī)則進(jìn)行發(fā)現(xiàn)的方法。其特點(diǎn)是在解決問題時(shí),利用過去的經(jīng)驗(yàn),選擇已經(jīng)行之有效的方法，而不是系統(tǒng)地、以確定的 步驟去尋求答案。啟發(fā)式解決問題的方法是與算法相對立的。算法是把各種可能性都一一進(jìn)行嘗試，最終能找到問題的答案，但它是在很大的問題空間內(nèi)，花費(fèi)大量 的時(shí)間和精力才能求得答案。啟發(fā)式方法則是在有限的搜索空間內(nèi)，大大減少嘗試的數(shù)量，能迅速地達(dá)到問題的解決。但由于這種方法具有嘗試錯誤的特點(diǎn)，所以也 有失敗的可能性?？茖W(xué)家的許多重大發(fā)現(xiàn)，常常是利用極為簡單的啟發(fā)式規(guī)則。

本節(jié)內(nèi)容摘自互動百科詞條《啟發(fā)式方法》

計(jì)算機(jī)科學(xué)和認(rèn)知科學(xué)領(lǐng)域

上節(jié)內(nèi)容很抽象，不知道這個(gè)heuristics能干什么，在網(wǎng)絡(luò)上搜索關(guān)于heuristics的相關(guān)知識起源于某位朋友說我的一個(gè)系統(tǒng)設(shè)計(jì)是一種啟發(fā)式的。我真不知道他到底有何所指，暫時(shí)也沒有機(jī)會做深入溝通。在網(wǎng)絡(luò)上搜索，看到一篇好文章，有關(guān)物理符號系統(tǒng)和啟發(fā)式搜索，可以看出該文作者是有自己的理解的，不是像我這樣在網(wǎng)絡(luò)上surfing。

因?yàn)闀簳r(shí)沒有時(shí)間仔細(xì)閱讀和理解，看看這篇文章《什么是啟發(fā)式（heuristic）?》也許能夠增加一點(diǎn)直觀印象，尤其它舉的例子（用以比較啟發(fā)式方法和算法）

駕駛汽車到達(dá)某人的家，寫成算法是這樣的：沿167 號高速公路往南行至Puyallup；從South Hill Mall 出口出來后往山上開 4.5 英里； 在一個(gè)雜物店旁邊的紅綠燈路口右轉(zhuǎn)，接著在第一個(gè)路口左轉(zhuǎn)；從左邊褐色大房子的車道進(jìn)去，就是North Cedar 路714 號。

用啟發(fā)式方法來描述則可能是這樣：找出上一次我們寄給你的信，照著信上面的寄出地址開車到這個(gè)鎮(zhèn)；到了之后你問一下我們的房子在哪里。 這里每個(gè)人都認(rèn)識我們——肯定有人會很愿意幫助你的；如果你找不到人，那就找個(gè)公共電話亭給我們打電話，我們會出來接你。

• web3.0

• 信息提取

• 知識庫

• 語義網(wǎng)絡(luò)

• Fuller's blog

• Login to post comments

群體智能算法就是啟發(fā)式算法；研究的重點(diǎn)就是如何平衡局部搜索與全局搜索；有效逃離局部最優(yōu)解；
近幾年比較活躍的算法有如下：
仿動物類的算法：粒子群優(yōu)化，螞蟻優(yōu)化，魚群算法，蜂群算法等；
仿植物類的算法：向光性算法，雜草優(yōu)化算法，等等；
仿人類的算法有：和聲搜索算法是較好的算法；
近年開始研究情感計(jì)算的人較多。
實(shí)際應(yīng)用時(shí)差分進(jìn)化算法較有優(yōu)勢。
關(guān)于粒子群算法，理論成熟，應(yīng)用廣泛。

作者：李強(qiáng)
鏈接：https://www.zhihu.com/question/27666809/answer/43395837
來源：知乎
著作權(quán)歸作者所有，轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)。

——————————————————————————————————————

通俗的解釋就是利用類似仿生學(xué)的原理，將自然、動物中的一些現(xiàn)象抽象成為算法處理相應(yīng)問題。當(dāng)一個(gè)問題是NP難問題時(shí)，是無法求解到最優(yōu)解的，因此，用一種相對好的求解算法，去盡可能逼近最優(yōu)解，得到一個(gè)相對優(yōu)解，在很多實(shí)際情況中也是可以接受的

理論：物理符號系統(tǒng)和啟發(fā)式搜索
材料： 《作為經(jīng)驗(yàn)探索的計(jì)算機(jī)科學(xué)：符號和搜索》（Computer Science as Empirical Inquiry: Symbols and Search）
這是紐厄爾和西蒙在第十次圖靈講座上的演講稿，中文版見《人工智能哲學(xué)》（瑪格麗特?博登 編）這本書的第五篇（翻譯的很讓人郁悶）。英文版我找到了，下面的英文部分就是從英文版里摘錄的。

（一）物理符號系統(tǒng)

1 定性結(jié)構(gòu)定律（Laws of Qualitative Structure）

All sciences characterize the essential nature of the systems they study. These characterizations are invariably qualitative in nature, for they set the terms within which more detailed knowledge can be developed. Their essence can often be captured in very short, very general statements. One might judge these general laws, due to their limited specificity, as making relatively little contribution to the sum of a science, were it not for the historical evidence that shows them to be results of the greatest importance.

在研究某個(gè)系統(tǒng)的時(shí)侯，我們可以建立一個(gè)簡單而容易理解的模型來定性地描述這個(gè)系統(tǒng)的性質(zhì)。就像生物學(xué)中的細(xì)胞學(xué)說，一切生物都是由細(xì)胞組成的，但任何一種生物的細(xì)胞都有極其復(fù)雜的種類、形態(tài)和功能。但我們可以建立一個(gè)標(biāo)準(zhǔn)的細(xì)胞模型：細(xì)胞由細(xì)胞核、細(xì)胞質(zhì)和細(xì)胞膜組成，細(xì)胞核中有遺傳物質(zhì)，細(xì)胞質(zhì)中有各種行使不同功能的細(xì)胞器，細(xì)胞膜包在細(xì)胞質(zhì)外面，負(fù)責(zé)細(xì)胞核環(huán)境的物質(zhì)交換和信息交流。在此基礎(chǔ)上研究各種細(xì)胞的形態(tài)結(jié)構(gòu)和功能就都顯得比較簡單了。同樣的道理，“智能”是個(gè)相當(dāng)抽象的、讓人有點(diǎn)無從下手的研究對象，物理符號系統(tǒng)就是一個(gè)用以描述智能的，（相對來說）簡單而容易理解的模型。

2 物理符號系統(tǒng)的定義

物理符號系統(tǒng)是“物理的”，就是說它是遵循物理定律的，而且能用工程技術(shù)手段來實(shí)現(xiàn)，比如說你的計(jì)算機(jī)；它是一種“符號”系統(tǒng)，但不局限于人類的符號系統(tǒng)。
物理符號系統(tǒng)包括符號(symbols)、表達(dá)式(expressions)和過程(Processes)。符號是一種物理模式，是實(shí)體。符號組合起來就成了表達(dá)式，這里的組合方式可以是多種多樣的。系統(tǒng)在任一時(shí)刻都包含著這樣一些表達(dá)式。過程可以作 用于表達(dá)式來對表達(dá)式進(jìn)行創(chuàng)造(creation)、修正(modification)、再生(reproduction)或破壞 (destruction)。然而，物理符號系統(tǒng)內(nèi)的表達(dá)式本身并不能描述一切對象(Such a system exists in a world of objects wider than just these symbolic expressions themselves.不知道可不可以這樣理解)。

兩個(gè)核心概念：指稱(designation)和解釋(interpretation)
Designation. An expression designates an object if, given the expression, the system can either affect the object itself or behave in ways dependent on the object.
Interpretation. The system can interpret an expression if the expression designates a process and if, given the expression, the system can carry out the process.
Interpretation implies a special form of dependent action: given an expression the system can perform the indicated process, which is to say, it can evoke and execute its own processes from expressions that designate them.

個(gè)人理解：指稱表示的是一種表達(dá)式與對象的對應(yīng)關(guān)系，就像指針一樣。解釋（或者譯成翻譯、說明）表示的是一種表達(dá)式與過程的對應(yīng)關(guān)系，系統(tǒng)可以通過一些表達(dá)式來執(zhí)行相應(yīng)的過程。
從定義來看，物理符號系統(tǒng)與一切通用計(jì)算機(jī)極為相似，它實(shí)際上也確實(shí)不是什么新的東西。很多已知的系統(tǒng)都具有這樣的特征，其中最明顯的有兩個(gè)：計(jì)算機(jī)和人腦。

3 物理符號系統(tǒng)假設(shè)：物理符號系統(tǒng)是智能活動的充要條件

The Physical Symbol System Hypothesis：A physical symbol system has the necessary and sufficient means for general intelligent action.
By "necessary" we mean that any system that exhibits general intelligence will prove upon analysis to be a physical symbol system. By "sufficient" we mean that any physical symbol system of sufficient size can be organized further to exhibit general intelligence. By "general intelligent action" we wish to indicate the same scope of intelligence as we see in human action: that in any real situation behavior appropriate to the ends of the system and adaptive to the demands of the environment can occur, within some limits of speed and complexity.

其中，“必要性”的證明是認(rèn)知科學(xué)的任務(wù)，也就是研究人類（或動物）的認(rèn)知行為，然后用物理符號系統(tǒng)來解釋這些認(rèn)知行為?！俺浞中浴笔侨斯ぶ悄艿娜蝿?wù)，也就是構(gòu)造一些物理符號系統(tǒng)，看它們能否產(chǎn)生智能。

西蒙和紐厄爾把信息加工理論引入心理學(xué)，成為信息加工心理學(xué)，也就是認(rèn)知科學(xué)。人工智能的研究離不開認(rèn)知科學(xué)研究中提出的各種假設(shè)。
剛開始，人們構(gòu)造一些簡單的程序來讓計(jì)算機(jī)完成一些簡單的、精心設(shè)計(jì)的任務(wù)，后來覺得不過癮，就把研究工作擴(kuò)展到了建立系統(tǒng)，如自然語言理解系統(tǒng)、模式識別系統(tǒng)、設(shè)計(jì)系統(tǒng)等。但是——

It would be surprising and unappealing if it turned out that the AI programs performing these diverse tasks had nothing in common beyond their being instances of physical symbol systems. Hence, there has been great interest in searching for mechanisms possessed of generality, and for common components among programs performing a variety of tasks. This search carries the theory beyond the initial symbol system hypothesis to a more complete characterization of the particular kinds of symbol systems that are effective in artificial intelligence.

完成這些形形色色的任務(wù)的程序之間有沒有什么共性？找到了這些共性，就意味著對智能有了更深層的理解。
In the second section of this paper, we will discuss one example of a hypothesis at this second level specificity: the heuristic search hypothesis（啟發(fā)式搜索假設(shè)）.

（二）啟發(fā)式搜索
系統(tǒng)的智能活動是通過問題解決來體現(xiàn)的，系統(tǒng)是通過啟發(fā)式搜索來解題的。啟發(fā)式搜索假設(shè)是AI的第二個(gè)定性結(jié)構(gòu)定律（第一個(gè)是物理符號系統(tǒng)）。

1 啟發(fā)式搜索假設(shè)

Heuristic Search Hypothesis. The solutions to problems are represented as symbol structures. A physical symbol system exercises its intelligence in problem solving by search--that is, by generating and progressively modifying symbol structures until it produces a solution structure.

問題的解也是符號結(jié)構(gòu)。物理符號系統(tǒng)解決問題的過程就是產(chǎn)生某種符號結(jié)構(gòu)，再一步一步的修正它，直到它與問題的解的結(jié)構(gòu)相一致。就像解方程AX+B=CX+D一樣，移項(xiàng)得（A-C）X=D-B，再消去系數(shù)（A-C），得到X=（D-B）/（A-C）。這就是逐步修正方程的結(jié)構(gòu)，最終得到符合X=E的形式的解的過程。
假如有無限的時(shí)間和存儲空間還后無限的能量供應(yīng)，那么系統(tǒng)總可以通過窮舉的方式，遍歷問題空間中的所有路徑來找到問題的解——這就是傳說中的蠻力搜索。但實(shí)際應(yīng)用中這顯然是不可能的。實(shí)際應(yīng)用中必須在有限的步驟中，有限的時(shí)間內(nèi)找到答案，因此就要用啟發(fā)式搜索策略。

A condition, then, for the appearance of intelligence is that the distribution of solutions be not entirely random, that the space of symbol structures exhibit at least some degree of order and pattern. A second condition is that pattern in the space of symbol structures be more or less detectible. A third condition is that the generator of potential solutions be able to behave differentially, depending on what pattern it detected. There must be information in the problem space, and the symbol system must be capable of extracting and using it.

符號系統(tǒng)處于完全混沌的狀態(tài)時(shí)，是不可能表現(xiàn)出智能的。符號系統(tǒng)的智能體現(xiàn)在它能夠從問題空間中抽取信息，并運(yùn)用這些信息指導(dǎo)搜索，從而避開錯誤的方向，避免迂回曲折的分叉而高效的解決問題。所以，問題空間中必須包含信息，或者說，包含某種程度的秩序和結(jié)構(gòu)。
實(shí)際中需要解決的問題不像解一元一次方程那樣只有一條路對應(yīng)一個(gè)固定的解，而是在每一步都有多種選擇，對應(yīng)著多個(gè)結(jié)局，形成一棵搜索樹。

The fact of limited resources allows us, for most purposes, to view a symbol system as though it were a serial, one-process-at-a-time device. If it can accomplish only a small amount of processing in any short time interval, then we might as well regard it as doing things one at a time. Thus "limited resource symbol system" and "serial symbol system" are practically synonymous. The problem of allocating a scarce resource from moment to moment can usually be treated, if the moment is short enough, as a problem of scheduling a serial machine.

這里好像是說由于資源有限，在實(shí)際應(yīng)用中是按照線性過程在進(jìn)行搜索的，是串行的，一次只能沿著搜索樹的一個(gè)分支走。（不過，有沒有“多線程”的并行搜索呢？）

In serial heuristic search, the basic question always is: what shall be done next? In tree search, that question, in turn, has two components: (1) from what node in the tree shall we search next, and (2) what direction shall we take from that node? Information helpful in answering the first question may be interpreted as measuring the relative distance of different nodes from the goal. Best-first search calls for searching next from the node that appears closest to the goal. Information helpful in answering the second question--in what direction to search--is often obtained, as in the algebra example, by detecting specific differences between the current nodal structure and the goal structure described by the test of a solution, and selecting actions that are relevant to reducing these particular kinds of differences. This is the technique known as means-ends analysis, which plays a central role in the structure of the General Problem Solver.

下一步搜索從樹的那一個(gè)節(jié)點(diǎn)開始？這就要進(jìn)行不同節(jié)點(diǎn)與目標(biāo)的相對距離測定。佳者優(yōu)先策略要求從那個(gè)看起來離目標(biāo)最近的節(jié)點(diǎn)開始下一步搜索。從該節(jié)點(diǎn)起應(yīng)取什么方向？這就需要測出當(dāng)前節(jié)點(diǎn)的結(jié)構(gòu)與目標(biāo)結(jié)構(gòu)之間的差異，并向著最能有效消除差異的方向前進(jìn)。這就使傳說中的“手段—目的分析法”，在通用問題求解程序（GPS）中起主導(dǎo)作用。
具體操作中則需要一個(gè)估價(jià)函數(shù)f(n) = g(n) + h(n) 其中f(n) 是節(jié)點(diǎn)n的估價(jià)函數(shù)，g(n)實(shí)在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價(jià)，h(n)是從n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)。在這里主要是h(n)體現(xiàn)了搜索的啟發(fā)信息，因?yàn)間(n)是已知的。如果說詳細(xì)點(diǎn)，g(n)代表了搜索的廣度的優(yōu)先趨勢。但是當(dāng)h(n) >> g(n)時(shí)，可以省略g(n)，而提高效率。（摘自百度百科，不過說實(shí)話這一段我沒看懂，歡迎高手指點(diǎn)）

Search—successive generation of potentional solution structures--is a fundamental aspect of a symbol system's exercise of intelligence in problem solving but that amount of search is not a measure of the amount of intelligence being exhibited. What makes a problem a problem is not that a large amount of search is required for its solution, but that a large amount would be required if a requisite level of intelligence were not applied. When the symbolic system that is endeavoring to solve a problem knows enough about what to do, it simply proceeds directly towards its goal; but whenever its knowledge becomes inadequate, when it enters terra incognita, it is faced with the threat of going through large amounts of search before it finds its way again.

并不是搜索越多就意味著智能越高，正相反，智能高的表現(xiàn)恰恰是不用經(jīng)過大量搜索也能解決問題。

啟發(fā)式搜索會造成這樣的結(jié)果：找到的解雖然是令人滿意的，卻不是最優(yōu)的；或者說，雖不是最優(yōu)的卻能令人滿意。實(shí)際上在認(rèn)知心理學(xué)研究中也表明，動物在進(jìn)行決策的時(shí)候采取的也是啟發(fā)式策略，尤其是在資源（時(shí)間、食物等）不充足的情況下。這樣做出的決策往往不是最優(yōu)的，不過至少是有效的。這個(gè)就是西蒙“有限理性”的理論來源，使得西蒙后來獲得了諾貝爾經(jīng)濟(jì)學(xué)獎。

2 幾個(gè)啟發(fā)式搜索的實(shí)例

這部分參考《人工科學(xué)——復(fù)雜性面面觀》 司馬賀著 武夷山譯
http://www.douban.com/subject/1195595/

例一 通用解題者（General Problem Solver，GPS）P113-114
“……在輸入或感官一側(cè)，GPS必須能表現(xiàn)想望狀況或想望物（就是上面說的目標(biāo)結(jié)構(gòu)），表現(xiàn)目前狀況，它也必須能表現(xiàn)想望狀況與目前狀況的差別。 在傳出側(cè)，GPS必須能表現(xiàn)改變實(shí)物或狀況的行動。為了有目的的行動，GPS必須能不時(shí)地選擇這樣一些特定的行動，它們有可能消除系統(tǒng)探測到的目前狀態(tài)與 想望狀態(tài)之間的差別。在GPS這部機(jī)器中，這種選擇是通過一張關(guān)聯(lián)表實(shí)現(xiàn)的。該表將每種可探測到的差別與對減小那一差別有作用的行動聯(lián)系起來。GPS的這 些聯(lián)系（表現(xiàn)為產(chǎn)生過程）將傳入狀況與傳出狀況掛上了鉤。由于通常需要一系列行動才能實(shí)現(xiàn)某一目標(biāo)，由于某些努力也許是無效的，GPS也必須有探測自己的 進(jìn)度（現(xiàn)實(shí)狀態(tài)與想望狀態(tài)間差別的變化）和試行新路子的手段?！?br> 可以看出GPS解決的是具有“良結(jié)構(gòu)”（well structured）的問題。也就是說，等待解決的問題的當(dāng)前狀態(tài)、目標(biāo)狀態(tài)以及搜索空間中的路徑都很清楚。不能滿足此條件的問題稱為結(jié)構(gòu)不良問題（poorly structured problem）

例二 “理解”（understand）P88
這是一個(gè)可以解決結(jié)構(gòu)不良問題的程序。
“有一個(gè)名叫“理解”的程序，它模擬人們對飲茶儀式這種問題建立內(nèi)部表象（即進(jìn)行理解）的過程?！袄斫狻狈謨呻A段進(jìn)行工作：先對問題指令的句子進(jìn)行語法分析，然后根據(jù)經(jīng)過語法分析的句子摘取出的信息構(gòu)造一個(gè)表象。
……分析的任務(wù)就是根據(jù)線性詞串推斷出隱含著的詞組和從句的層級結(jié)構(gòu)?！袄斫狻背绦蚴怯孟喈?dāng)正統(tǒng)的方式（類似于現(xiàn)有的其他語法分析程序）完成這一 步驟的。第二階段（構(gòu)造）更為有趣。這里。對經(jīng)過語法分析的句子進(jìn)行考察，以期發(fā)現(xiàn)提到了哪些賓詞和賓詞集，提到了賓詞的那些性質(zhì)，這些性質(zhì)之間的關(guān)系是 什么，哪些謂詞與關(guān)系描述了狀態(tài)，哪些描述了步驟，目標(biāo)狀態(tài)是什么。“理解”接著構(gòu)造一個(gè)表現(xiàn)狀態(tài)的規(guī)則，產(chǎn)生出步驟符合規(guī)定（通過將一個(gè)狀態(tài)轉(zhuǎn)變?yōu)榱硪?狀態(tài)）的程序?！?br> 這個(gè)看上去似乎挺牛的，不過實(shí)際上它的功能非常有限。在西蒙的《思想模型》（Models of Thought）一書的7.1章到7.3章有關(guān)于“理解”程序的詳細(xì)描述。

例三 培根（BACON）P99
這是個(gè)具有發(fā)現(xiàn)能力的程序。
“BACON程序的目的是發(fā)現(xiàn)大量數(shù)據(jù)中的不變量。給定各行星至太陽的距離與它們的軌道周期的數(shù)據(jù)，該程序發(fā)現(xiàn)，對于所有的行星，軌道周期的立方 與行星至太陽的距離的平方之比都是一樣的（開普勒第三定律）。根據(jù)電流隨電路中電阻線長度而變化的數(shù)據(jù)，它推出了歐姆定律。同理，它發(fā)現(xiàn)了氣體定律、伽利 略自由落體定律和許多其他定律。
為了解釋發(fā)現(xiàn)的不變量，BACON就引入新概念。給定數(shù)據(jù)表明，當(dāng)兩個(gè)物體互相加速時(shí)，兩者加速度的比值總是相同的。BACON程序由此發(fā)明了質(zhì)量的概念，并給每一物體一個(gè)質(zhì)量。同理，它發(fā)明了折射率，以及比熱和化學(xué)價(jià)的概念。
……BACON的基本構(gòu)造沒有多少新東西。給定兩組數(shù)據(jù)，如果它發(fā)現(xiàn)一組數(shù)據(jù)隨另一組數(shù)據(jù)單調(diào)變化，就檢驗(yàn)一下它們的比值（或乘積）是否不變。如 果成功了，它就發(fā)現(xiàn)了數(shù)值之間的定律關(guān)系；如果失敗了，它也定義了一個(gè)新的變量，可將此變量加到其他變量上去，再重復(fù)這一過程。該系統(tǒng)的行為了不起的地方 是，通過這些步驟發(fā)現(xiàn)上述種種定律并不需要大量的搜索。為找到一個(gè)不變量，很少需要考察原變量的十幾個(gè)以上的函數(shù)?！?br> 科學(xué)家要失業(yè)了嗎？不會的。BACON以及后來出現(xiàn)的一大堆發(fā)現(xiàn)程序雖然能發(fā)現(xiàn)一些定律，但并不能解釋其中的內(nèi)涵。我上小學(xué)的時(shí)候就知道E=mc2，可是到現(xiàn)在還是不懂狹義相對論。
這些發(fā)現(xiàn)程序在化學(xué)學(xué)科中做了一些貢獻(xiàn)，但主要被用于深化對人類發(fā)現(xiàn)過程的認(rèn)識。“例如，人們將BACON程序的模擬結(jié)果與物理學(xué)和化學(xué)的發(fā)現(xiàn)的 歷史事例進(jìn)行了比較，還在實(shí)驗(yàn)室中庸一些受試者進(jìn)行了并行實(shí)驗(yàn)，看看他們憑借BACON程序努力做出的發(fā)現(xiàn)和基于科學(xué)史中記載的資料努力做出發(fā)現(xiàn)的情形有 什么差異?！?/p>

總結(jié)一下

AI的兩個(gè)定性結(jié)構(gòu)定律：
1 智能存在于物理符號系統(tǒng)中；
2 符號系統(tǒng)是通過生成潛在可能的解，并對其進(jìn)行檢驗(yàn)，也就是通過搜索的方式來解題的。

符號系統(tǒng)是許多模式和過程的集合體，過程能夠產(chǎn)生、破壞或修正模式。模式能指稱對象、過程或其他模式，當(dāng)它們指稱過程的時(shí)候，它們就能得到解釋，完成被指稱的過程。在我們所了解的符號系統(tǒng)中有兩類意義最為重大，就是人類和計(jì)算機(jī)。
符號系統(tǒng)的智能體現(xiàn)在它能夠從問題空間中抽取信息，并通過搜索來解決問題。啟發(fā)式搜索就是一種這樣的搜索策略，通過估價(jià)函數(shù)來決定下一步搜索的起始點(diǎn)和方向，以有效率的解決問題。
通過認(rèn)知心理學(xué)對人類及動物認(rèn)知過程的研究，提出了很多關(guān)于智能的假設(shè)。以這些假設(shè)為依據(jù)，人們開發(fā)了一堆各種各樣的智能程序，能完成很多看起來 很復(fù)雜的任務(wù)，比如語義理解，定律發(fā)現(xiàn)等。但是每一種程序都有它的局限性。相信隨著認(rèn)知科學(xué)研究的不斷深入，會有更多更牛的程序誕生

啟發(fā)式算法的計(jì)算量都比較大，所以啟發(fā)式算法伴隨著計(jì)算機(jī)技術(shù)的發(fā)展，取得了巨大的成就。

40年代：由于實(shí)際需要，人們已經(jīng)提出了一些解決實(shí)際問題快速有效的啟發(fā)式算法。

50年代：啟發(fā)式算法的研究逐步繁榮起來。隨后，人們將啟發(fā)式算法的思想和人工智能領(lǐng)域中的各種有關(guān)問題的求解的收縮方法相結(jié)合，提出了許多啟發(fā)式的搜索算法[]。其中貪婪算法和局部搜索等到人們的關(guān)注。

60年代: 隨著人們對數(shù)學(xué)模型和優(yōu)化算法的研究越來越重視，發(fā)現(xiàn)以前提出的啟發(fā)式算法速度很快，但是解得質(zhì)量不能保證。雖然對優(yōu)化算法的研究取得了很大的進(jìn)展，但是較大規(guī)模的問題仍然無能為力（計(jì)算量還是太大）。

70年代：計(jì)算復(fù)雜性理論的提出。NP完全理論告訴我們，許多實(shí)際問題不可能在合理的時(shí)間范圍內(nèi)找到全局最優(yōu)解。發(fā)現(xiàn)貪婪算法和局部搜索算法速度快，但解不好的原因主要是他們只是在局部的區(qū)域內(nèi)找解，得到的解不能保證全局最優(yōu)性。由此必須引入新的搜索機(jī)制和策略，才能有效地解決這些困難問題，這就導(dǎo)致了超啟發(fā)式算法（meta-heuristic algorithms）的產(chǎn)生。

Holland模擬地球上生物進(jìn)化規(guī)律提出了遺傳算法（Genetic Algorithm），它的與眾不同的搜索機(jī)制引起了人們再次引發(fā)了人們研究啟發(fā)式算法的興趣，從而掀起了研究啟發(fā)式算法的熱潮。

80年代以后： 模擬退火算法（Simulated Annealing Algorithm），人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Network），禁忌搜索（Tabu Search）相繼出現(xiàn)。最近，演化算法（Evolutionary Algorithm）, 蟻群算法（Ant Algorithms）， 擬人擬物算法，量子算法等油相繼興起，掀起了研究啟發(fā)式算法的高潮。由于這些算法簡單和有效，而且具有某種智能，因而成為科學(xué)計(jì)算和人類之間的橋梁。

優(yōu)勝劣汰是大自然的普遍規(guī)律，它主要通過選擇和變異來實(shí)現(xiàn)。選擇是優(yōu)化的基本思想，變異（多樣化）是隨機(jī)搜索或非確定搜索的基本思想?！皟?yōu)勝劣汰”是算法搜索的核心，根據(jù)“優(yōu)勝劣汰”策略的不同，可以獲得不同的超啟發(fā)式算法。超啟發(fā)式算法的主要思想來自于人類經(jīng)過長期對物理、生物、社會的自然現(xiàn)象仔細(xì)的觀察和實(shí)踐，以及對這些自然現(xiàn)象的深刻理解，逐步向大自然學(xué)習(xí)，模仿其中的自然現(xiàn)象的運(yùn)行機(jī)制而得到的。

進(jìn)化算法是借鑒生物界自然選擇和自然遺產(chǎn)機(jī)制的隨機(jī)搜索算法，包括：遺傳算法(GA)，遺傳策略(GS)，進(jìn)化規(guī)劃(EP)，進(jìn)化策略(ES)。進(jìn)化算法的基本框架還是簡單遺傳算法所描述的框架，但在進(jìn)化的方式上有較大的差異，選擇、交叉、變異、種群控制等有很多變化。

模擬退火：是模擬統(tǒng)計(jì)物理中固體物質(zhì)的結(jié)晶過程。模擬退火來自冶金學(xué)的專有名詞退火。退火是將材料加熱后再經(jīng)特定速率冷卻，目的是增大晶粒的體積，並且減少晶格中的缺陷。材料中的原子原來會停留在使內(nèi)能有局部最小值的位置，加熱使能量變大，原子會離開原來位置，而隨機(jī)在其他位置中移動。退火冷卻時(shí)速度較慢，使得原子有較多可能可以找到內(nèi)能比原先更低的位置。

模擬退火的原理也和金屬退火的原理近似：我們將熱力學(xué)的理論套用到統(tǒng)計(jì)學(xué)上，將搜索空間內(nèi)每一點(diǎn)想象成空氣內(nèi)的分子；分子的能量，就是它本身的動能；而搜索空間內(nèi)的每一點(diǎn)，也像空氣分子一樣帶有“能量”，以表示該點(diǎn)對命題的合適程度。算法先以搜索空間內(nèi)一個(gè)任意點(diǎn)作起始：每一步先選擇一個(gè)“鄰居”，然后再計(jì)算從現(xiàn)有位置到達(dá)“鄰居”的概率。在退火的過程中，如果搜索到好的解接受；否則，以一定的概率接受不好的解（即實(shí)現(xiàn)多樣化或變異的思想），達(dá)到跳出局部最優(yōu)解得目的。

神經(jīng)網(wǎng)絡(luò)：模擬大腦神經(jīng)處理的過程，通過各個(gè)神經(jīng)元的競爭和協(xié)作，實(shí)現(xiàn)選擇和變異的過程。

禁忌搜索：模擬人的經(jīng)驗(yàn)，通過禁忌表記憶最近搜索過程中的歷史信息，禁忌某些解，以避免走回頭路，達(dá)到跳出局部最優(yōu)解的目的。

螞蟻算法：模擬螞蟻的行為，擬人擬物，向螞蟻的協(xié)作方式學(xué)習(xí)。

這幾種超啟發(fā)式算法都有一個(gè)共同的特點(diǎn)：從隨機(jī)的可行初始解出發(fā)，才用迭代改進(jìn)的策略，去逼近問題的最優(yōu)解。

他們的基本要素：（1）隨機(jī)初始可行解；

（２）給定一個(gè)評價(jià)函數(shù)（常常與目標(biāo)函數(shù)值有關(guān)）；

（３）鄰域，產(chǎn)生新的可行解；

（４）選擇和接受解得準(zhǔn)則；

（５）終止準(zhǔn)則。

其中（４）集中反映了超啟發(fā)式算法的克服局部最優(yōu)的能力。

雖然人們研究對啟發(fā)式算法的研究將近５０年，但它還有很多不足：

1.啟發(fā)式算法目前缺乏統(tǒng)一、完整的理論體系。

2.由于NP理論，各種啟發(fā)式算法都不可避免的遭遇到局部最優(yōu)的問題，如何判斷

3.各種啟發(fā)式算法都有個(gè)自優(yōu)點(diǎn)如何，完美結(jié)合。

4.啟發(fā)式算法中的參數(shù)對算法的效果起著至關(guān)重要的作用，如何有效設(shè)置參數(shù)。

5.啟發(fā)算法缺乏有效的迭代停止條件。

6.啟發(fā)式算法收斂速度的研究等。