計算機科學之論述智能算法 推薦本站高人氣期刊：《計算機科學》由國家科技部主管，西南信息中心主辦，系“中文科技核心期刊”、“中國科技論文統計與分析用期刊”、“中國科學引文數據庫來源期刊”、“中國期刊方陣雙效期刊”。主要報導國內外計算機科學與技術的發展動態，涉及面廣的方法論與技術，和反映新苗頭、能起承先啟后作用的研究成果。內容涉及程序理論、計算機軟件、計算機網絡與信息、數據庫、人工智能、人機界面、國際會議、應用等。

　　摘要：隨著計算機技術的飛速發展，智能計算方法的應用領域也越來越廣泛，本文介紹了當前存在的一些智能計算方法，闡述了其工作原理和特點，同時對智能計算方法的發展進行了展望。

　　關鍵詞：計算機科學,人工神經網絡,遺傳算法,模擬退火算法,群集智能,蟻群算法,粒子群算

　　1 什么是智能算法

　　智能計算也有人稱之為“軟計算”，是們受自然(生物界)規律的啟迪，根據其原理，模仿求解問題的算法。從自然界得到啟迪，模仿其結構進行發明創造，這就是仿生學。這是我們向自然界學習的一個方面。另一方面，我們還可以利用仿生原理進行設計(包括設計算法)，這就是智能計算的思想。這方面的內容很多，如人工神經網絡技術、遺傳算法、模擬退火算法、模擬退火技術和群集智能技術等。

　　2 人工神經網絡算法

　　“人工神經網絡”(ARTIFICIAL NEURAL NETWORK，簡稱ANN)是在對人腦組織結構和運行機制的認識理解基礎之上模擬其結構和智能行為的一種工程系統。早在本世紀40年代初期，心理學家McCulloch、數學家Pitts就提出了人工神經網絡的第一個數學模型，從此開創了神經科學理論的研究時代。其后，F Rosenblatt、Widrow和J. J .Hopfield等學者又先后提出了感知模型，使得人工神經網絡技術得以蓬勃發展。

　　神經系統的基本構造是神經元(神經細胞)，它是處理人體內各部分之間相互信息傳遞的基本單元。據神經生物學家研究的結果表明，人的一個大腦一般有1010～1011個神經元。每個神經元都由一個細胞體，一個連接其他神經元的軸突和一些向外伸出的其它較短分支——樹突組成。軸突的功能是將本神經元的輸出信號(興奮)傳遞給別的神經元。其末端的許多神經末梢使得興奮可以同時傳送給多個神經元。樹突的功能是接受來自其它神經元的興奮。神經元細胞體將接受到的所有信號進行簡單處理(如：加權求和，即對所有的輸入信號都加以考慮且對每個信號的重視程度——體現在權值上——有所不同)后由軸突輸出。神經元的樹突與另外的神經元的神經末梢相連的部分稱為突觸。

　　2.1 人工神經網絡的特點

　　人工神經網絡是由大量的神經元廣泛互連而成的系統，它的這一結構特點決定著人工神經網絡具有高速信息處理的能力。人腦的每個神經元大約有103～104個樹突及相應的突觸，一個人的大腦總計約形成1014～1015個突觸。用神經網絡的術語來說，即是人腦具有1014～1015個互相連接的存儲潛力。雖然每個神經元的運算功能十分簡單，且信號傳輸速率也較低(大約100次/秒)，但由于各神經元之間的極度并行互連功能，最終使得一個普通人的大腦在約1秒內就能完成現行計算機至少需要數10億次處理步驟才能完成的任務。

　　人工神經網絡的知識存儲容量很大。在神經網絡中，知識與信息的存儲表現為神經元之間分布式的物理聯系。它分散地表示和存儲于整個網絡內的各神經元及其連線上。每個神經元及其連線只表示一部分信息，而不是一個完整具體概念。只有通過各神經元的分布式綜合效果才能表達出特定的概念和知識。

　　由于人工神經網絡中神經元個數眾多以及整個網絡存儲信息容量的巨大，使得它具有很強的不確定性信息處理能力。即使輸入信息不完全、不準確或模糊不清，神經網絡仍然能夠聯想思維存在于記憶中的事物的完整圖象。只要輸入的模式接近于訓練樣本，系統就能給出正確的推理結論。

　　正是因為人工神經網絡的結構特點和其信息存儲的分布式特點，使得它相對于其它的判斷識別系統，如：專家系統等，具有另一個顯著的優點：健壯性。生物神經網絡不會因為個別神經元的損失而失去對原有模式的記憶。最有力的證明是，當一個人的大腦因意外事故受輕微損傷之后，并不會失去原有事物的全部記憶。人工神經網絡也有類似的情況。因某些原因，無論是網絡的硬件實現還是軟件實現中的某個或某些神經元失效，整個網絡仍然能繼續工作。

　　人工神經網絡是一種非線性的處理單元。只有當神經元對所有的輸入信號的綜合處理結果超過某一門限值后才輸出一個信號。因此神經網絡是一種具有高度非線性的超大規模連續時間動力學系統。它突破了傳統的以線性處理為基礎的數字電子計算機的局限，標志著人們智能信息處理能力和模擬人腦智能行為能力的一大飛躍。

　　2.2 幾種典型神經網絡簡介

　　2.2.1 多層感知網絡(誤差逆傳播神經網絡)

　　在1986年以Rumelhart和McCelland為首的科學家出版的《Parallel Distributed Processing》一書中，完整地提出了誤差逆傳播學習算法，并被廣泛接受。多層感知網絡是一種具有三層或三層以上的階層型神經網絡。典型的多層感知網絡是三層、前饋的階層網絡，即：輸入層I、隱含層(也稱中間層)J和輸出層K。相鄰層之間的各神經元實現全連接，即下一層的每一個神經元與上一層的每個神經元都實現全連接，而且每層各神經元之間無連接。

　　但BP網并不是十分的完善，它存在以下一些主要缺陷：學習收斂速度太慢、網絡的學習記憶具有不穩定性，即：當給一個訓練好的網提供新的學習記憶模式時，將使已有的連接權值被打亂，導致已記憶的學習模式的信息的消失。?

　　2.2.2 競爭型(KOHONEN)神經網絡

　　它是基于人的視網膜及大腦皮層對剌激的反應而引出的。神經生物學的研究結果表明：生物視網膜中，有許多特定的細胞，對特定的圖形(輸入模式)比較敏感，并使得大腦皮層中的特定細胞產生大的興奮，而其相鄰的神經細胞的興奮程度被抑制。對于某一個輸入模式，通過競爭在輸出層中只激活一個相應的輸出神經元。許多輸入模式，在輸出層中將激活許多個神經元，從而形成一個反映輸入數據的“特征圖形”。競爭型神經網絡是一種以無教師方式進行網絡訓練的網絡。它通過自身訓練，自動對輸入模式進行分類。競爭型神經網絡及其學習規則與其它類型的神經網絡和學習規則相比，有其自己的鮮明特點。在網絡結構上，它既不象階層型神經網絡那樣各層神經元之間只有單向連接，也不象全連接型網絡那樣在網絡結構上沒有明顯的層次界限。它一般是由輸入層(模擬視網膜神經元)和競爭層(模擬大腦皮層神經元，也叫輸出層)構成的兩層網絡。兩層之間的各神經元實現雙向全連接，而且網絡中沒有隱含層。有時競爭層各神經元之間還存在橫向連接。競爭型神經網絡的基本思想是網絡競爭層各神經元競爭對輸入模式的響應機會，最后僅有一個神經元成為競爭的勝者，并且只將與獲勝神經元有關的各連接權值進行修正，使之朝著更有利于它競爭的方向調整。神經網絡工作時，對于某一輸入模式，網絡中與該模式最相近的學習輸入模式相對應的競爭層神經元將有最大的輸出值，即以競爭層獲勝神經元來表示分類結果。這是通過競爭得以實現的，實際上也就是網絡回憶聯想的過程。

　　除了競爭的方法外，還有通過抑制手段獲取勝利的方法，即網絡競爭層各神經元抑制所有其它神經元對輸入模式的響應機會，從而使自己“脫穎而出”，成為獲勝神經元。除此之外還有一種稱為側抑制的方法，即每個神經元只抑制與自己鄰近的神經元，而對遠離自己的神經元不抑制。這種方法常常用于圖象邊緣處理，解決圖象邊緣的缺陷問題。

　　競爭型神經網絡的缺點和不足：因為它僅以輸出層中的單個神經元代表某一類模式。所以一旦輸出層中的某個輸出神經元損壞，則導致該神經元所代表的該模式信息全部丟失。

　　2.2.3 Hopfield神經網絡

　　1986年美國物理學家J.J.Hopfield陸續發表幾篇論文，提出了Hopfield神經網絡。他利用非線性動力學系統理論中的能量函數方法研究反饋人工神經網絡的穩定性，并利用此方法建立求解優化計算問題的系統方程式。基本的Hopfield神經網絡是一個由非線性元件構成的全連接型單層反饋系統。

　　網絡中的每一個神經元都將自己的輸出通過連接權傳送給所有其它神經元，同時又都接收所有其它神經元傳遞過來的信息。即：網絡中的神經元t時刻的輸出狀態實際上間接地與自己的t-1時刻的輸出狀態有關。所以Hopfield神經網絡是一個反饋型的網絡。其狀態變化可以用差分方程來表征。反饋型網絡的一個重要特點就是它具有穩定狀態。當網絡達到穩定狀態的時候，也就是它的能量函數達到最小的時候。這里的能量函數不是物理意義上的能量函數，而是在表達形式上與物理意義上的能量概念一致，表征網絡狀態的變化趨勢，并可以依據Hopfield工作運行規則不斷進行狀態變化，最終能夠達到的某個極小值的目標函數。網絡收斂就是指能量函數達到極小值。如果把一個最優化問題的目標函數轉換成網絡的能量函數，把問題的變量對應于網絡的狀態，那么Hopfield神經網絡就能夠用于解決優化組合問題。

　　對于同樣結構的網絡，當網絡參數(指連接權值和閥值)有所變化時，網絡能量函數的極小點(稱為網絡的穩定平衡點)的個數和極小值的大小也將變化。因此，可以把所需記憶的模式設計成某個確定網絡狀態的一個穩定平衡點。若網絡有M個平衡點，則可以記憶M個記憶模式。

　　當網絡從與記憶模式較靠近的某個初始狀態(相當于發生了某些變形或含有某些噪聲的記憶模式，也即：只提供了某個模式的部分信息)出發后，網絡按Hopfield工作運行規則進行狀態更新，最后網絡的狀態將穩定在能量函數的極小點。這樣就完成了由部分信息的聯想過程。

　　Hopfield神經網絡的能量函數是朝著梯度減小的方向變化，但它仍然存在一個問題，那就是一旦能量函數陷入到局部極小值，它將不能自動跳出局部極小點，到達全局最小點，因而無法求得網絡最優解。

　　3 遺傳算法

　　遺傳算法(Genetic Algorithms)是基于生物進化理論的原理發展起來的一種廣為應用的、高效的隨機搜索與優化的方法。其主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不依賴于梯度信息。它是在70年代初期由美國密執根(Michigan)大學的霍蘭(Holland)教授發展起來的。1975年霍蘭教授發表了第一本比較系統論述遺傳算法的專著《自然系統與人工系統中的適應性》(《Adaptation in Natural and Artificial Systems》)。遺傳算法最初被研究的出發點不是為專門解決最優化問題而設計的，它與進化策略、進化規劃共同構成了進化算法的主要框架，都是為當時人工智能的發展服務的。迄今為止，遺傳算法是進化算法中最廣為人知的算法。

　　近幾年來，遺傳算法主要在復雜優化問題求解和工業工程領域應用方面，取得了一些令人信服的結果，所以引起了很多人的關注。在發展過程中，進化策略、進化規劃和遺傳算法之間差異越來越小。遺傳算法成功的應用包括：作業調度與排序、可靠性設計、車輛路徑選擇與調度、成組技術、設備布置與分配、交通問題等等。

　　3.1 特點

　　遺傳算法是解決搜索問題的一種通用算法，對于各種通用問題都可以使用。搜索算法的共同特征為： ① 首先組成一組候選解; ② 依據某些適應性條件測算這些候選解的適應度; ③ 根據適應度保留某些候選解，放棄其他候選解; ④ 對保留的候選解進行某些操作，生成新的候選解。在遺傳算法中，上述幾個特征以一種特殊的方式組合在一起：基于染色體群的并行搜索，帶有猜測性質的選擇操作、交換操作和突變操作。這種特殊的組合方式將遺傳算法與其它搜索算法區別開來。

　　遺傳算法還具有以下幾方面的特點：

　　(1)遺傳算法從問題解的串集開始嫂索，而不是從單個解開始。這是遺傳算法與傳統優化算法的極大區別。傳統優化算法是從單個初始值迭代求最優解的;容易誤入局部最優解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優。(2)許多傳統搜索算法都是單點搜索算法，容易陷入局部的最優解。遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進行評估，減少了陷入局部最優解的風險，同時算法本身易于實現并行化。

　　(3)遺傳算法基本上不用搜索空間的知識或其它輔助信息，而僅用適應度函數值來評估個體，在此基礎上進行遺傳操作。適應度函數不僅不受連續可微的約束，而且其定義域可以任意設定。這一特點使得遺傳算法的應用范圍大大擴展。

　　(4)遺傳算法不是采用確定性規則，而是采用概率的變遷規則來指導他的搜索方向。

　　(5)具有自組織、自適應和自學習性。遺傳算法利用進化過程獲得的信息自行組織搜索時，硬度大的個體具有較高的生存概率，并獲得更適應環境的基因結構。

　　3.2 運用領域

　　前面描述是簡單的遺傳算法模型，可以在這一基本型上加以改進，使其在科學和工程領域得到廣泛應用。下面列舉了一些遺傳算法的應用領域： ① 優化：遺傳算法可用于各種優化問題。既包括數量優化問題，也包括組合優化問題。 ② 程序設計：遺傳算法可以用于某些特殊任務的計算機程序設計。 ③ 機器學習：遺傳算法可用于許多機器學習的應用，包括分類問題和預測問題等。 ④ 經濟學：應用遺傳算法對經濟創新的過程建立模型，可以研究投標的策略，還可以建立市場競爭的模型。 ⑤ 免疫系統：應用遺傳算法可以對自然界中免疫系統的多個方面建立模型，研究個體的生命過程中的突變現象以及發掘進化過程中的基因資源。 ⑥ 進化現象和學習現象：遺傳算法可以用來研究個體是如何學習生存技巧的，一個物種的進化對其他物種會產生何種影響等等。 ⑦ 社會經濟問題：遺傳算法可以用來研究社會系統中的各種演化現象，例如在一個多主體系統中，協作與交流是如何演化出來的。

　　4 模擬退火算法

　　模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最后在常溫時達到基態，內能減為最小。根據Metropolis準則，粒子在溫度T時趨于平衡的概率為e-ΔE/(kT)，其中E為溫度T時的內能，ΔE為其改變量，k為Boltzmann常數。用固體退火模擬組合優化問題，將內能E模擬為目標函數值f ，溫度T演化成控制參數t，即得到解組合優化問題的模擬退火算法：由初始解i和控制參數初值t開始，對當前解重復“產生新解→計算目標函數差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當前解即為所得近似最優解，這是基于蒙特卡羅迭代求解法的一種啟發式隨機搜索過程。退火過程由冷卻進度表(Cooling Schedule)控制，包括控制參數的初值t及其衰減因子Δt、每個t值時的迭代次數L和停止條件S。

　　5 群體(群集)智能(Swarm Intelligence)

　　受社會性昆蟲行為的啟發，計算機工作者通過對社會性昆蟲的模擬產生了一系列對于傳統問題的新的解決方法，這些研究就是群集智能的研究。群集智能(Swarm Intelligence)中的群體(Swarm)指的是“一組相互之間可以進行直接通信或者間接通信(通過改變局部環境)的主體，這組主體能夠合作進行分布問題求解”。而所謂群集智能指的是“無智能的主體通過合作表現出智能行為的特性”。群集智能在沒有集中控制并且不提供全局模型的前提下，為尋找復雜的分布式問題的解決方案提供了基礎。

　　群集智能的特點和優點：群體中相互合作的個體是分布式的(Distributed)，這樣更能夠適應當前網絡環境下的工作狀態; 沒有中心的控制與數據，這樣的系統更具有魯棒性(Robust)，不會由于某一個或者某幾個個體的故障而影響整個問題的求解。可以不通過個體之間直接通信而是通過非直接通信(Stimergy)進行合作，這樣的系統具有更好的可擴充性(Scalability)。由于系統中個體的增加而增加的系統的通信開銷在這里十分小。系統中每個個體的能力十分簡單，這樣每個個體的執行時間比較短，并且實現也比較簡單，具有簡單性(Simplicity)。因為具有這些優點，雖說群集智能的研究還處于初級階段，并且存在許多困難，但是可以預言群集智能的研究代表了以后計算機研究發展的一個重要方向。

　　在計算智能(Computational Intelligence)領域有兩種基于群智能的算法，蟻群算法(Ant Colony Optimization)和粒子群算法(Particle Swarm Optimization)，前者是對螞蟻群落食物采集過程的模擬，已經成功運用在很多離散優化問題上。

　　5.1 蟻群優化算法

　　受螞蟻覓食時的通信機制的啟發，90年代Dorigo提出了蟻群優化算法(Ant Colony Optimization，ACO)來解決計算機算法學中經典的“貨郎擔問題”。如果有n個城市，需要對所有n個城市進行訪問且只訪問一次的最短距離。

　　在解決貨郎擔問題時，蟻群優化算法設計虛擬的“螞蟻”將摸索不同路線，并留下會隨時間逐漸消失的虛擬“信息素”。虛擬的“信息素”也會揮發，每只螞蟻每次隨機選擇要走的路徑，它們傾向于選擇路徑比較短的、信息素比較濃的路徑。根據“信息素較濃的路線更近"的原則，即可選擇出最佳路線。由于這個算法利用了正反饋機制，使得較短的路徑能夠有較大的機會得到選擇，并且由于采用了概率算法，所以它能夠不局限于局部最優解。

　　蟻群優化算法對于解決貨郎擔問題并不是目前最好的方法，但首先，它提出了一種解決貨郎擔問題的新思路;其次由于這種算法特有的解決方法，它已經被成功用于解決其他組合優化問題，例如圖的著色(Graph Coloring)以及最短超串(Shortest Common Supersequence)等問題。

　　5.2 粒子群優化算法

　　粒子群優化算法(PSO)是一種進化計算技術(Evolutionary Computation)，有Eberhart博士和Kennedy博士發明。源于對鳥群捕食的行為研究。

　　PSO同遺傳算法類似，是一種基于疊代的優化工具。系統初始化為一組隨機解，通過疊代搜尋最優值。但是并沒有遺傳算法用的交叉(crossover)以及變異(mutation)。而是粒子在解空間追隨最優的粒子進行搜索。

　　同遺傳算法比較，PSO的優勢在于簡單容易實現并且沒有許多參數需要調整。目前已廣泛應用于函數優化，神經網絡訓練，模糊系統控制以及其他遺傳算法的應用領域。

　　粒子群優化算法(PSO) 也是起源對簡單社會系統的模擬，最初設想是模擬鳥群覓食的過程，但后來發現PSO是一種很好的優化工具。

　　5.2.1 算法介紹

　　PSO模擬鳥群的捕食行為。一群鳥在隨機搜索食物，在這個區域里只有一塊食物。所有的鳥都不知道食物在那里。但是他們知道當前的位置離食物還有多遠。那么找到食物的最優策略是什么呢。最簡單有效的就是搜尋目前離食物最近的鳥的周圍區域。

　　PSO從這種模型中得到啟示并用于解決優化問題。PSO中，每個優化問題的解都是搜索空間中的一只鳥。我們稱之為“粒子”。所有的粒子都有一個由被優化的函數決定的適應值(fitness value)，每個粒子還有一個速度決定他們飛翔的方向和距離。然后粒子們就追隨當前的最優粒子在解空間中搜索。

　　PSO初始化為一群隨機粒子(隨機解)，然后通過疊代找到最優解，在每一次疊代中，粒子通過跟蹤兩個“極值”來更新自己。第一個就是粒子本身所找到的最優解，這個解叫做個體極值pBest，另一個極值是整個種群目前找到的最優解，這個極值是全局極值gBest。另外也可以不用整個種群而只是用其中一部分最優粒子的鄰居，那么在所有鄰居中的極值就是局部極值。

　　5.2.2 PSO算法過程

　　① 種群隨機初始化。

　　② 對種群內的每一個個體計算適應值(fitness value)。適應值與最優解的距離直接有關。

　　③ 種群根據適應值進行復制 。

　　④ 如果終止條件滿足的話，就停止，否則轉步驟 ② 。

　　從以上步驟，我們可以看到PSO和遺傳算法有很多共同之處。兩者都隨機初始化種群，而且都使用適應值來評價系統，而且都根據適應值來進行一定的隨機搜索。兩個系統都不是保證一定找到最優解。但是，PSO沒有遺傳操作如交叉(crossover)和變異(mutation)，而是根據自己的速度來決定搜索。粒子還有一個重要的特點，就是有記憶。

　　與遺傳算法比較，PSO的信息共享機制是很不同的。在遺傳算法中，染色體(chromosomes) 互相共享信息，所以整個種群的移動是比較均勻的向最優區域移動。在PSO中, 只有gBest (or lBest) 給出信息給其他的粒子， 這是單向的信息流動。整個搜索更新過程是跟隨當前最優解的過程。與遺傳算法比較, 在大多數的情況下，所有的粒子可能更快的收斂于最優解。

　　現在已經有一些利用PSO代替反向傳播算法來訓練神經網絡的論文。研究表明PSO 是一種很有潛力的神經網絡算法，同時PSO速度比較快而且可以得到比較好的結果。

　　6 展望

　　目前的智能計算研究水平暫時還很難使“智能機器”真正具備人類的常識，但智能計算將在21世紀蓬勃發展。不僅僅只是功能模仿要持有信息機理一致的觀點。即人工腦與生物腦將不只是功能模仿，而是具有相同的特性。這兩者的結合將開辟一個全新的領域，開辟很多新的研究方向。智能計算將探索智能的新概念，新理論，新方法和新技術，而這一切將在以后的發展中取得重大成就。

　　參考文獻

　　[1] “Ant-Colony Optimization Algorithms(ACO)”

　　[2 ] “Swarm intelligence-what is it and why is it interesting”

　　[3] Tony White,“Swarm Intelligence: A Gentle Introduction With Application”,

　　[4] 胡守仁等.神經網絡導論[M].長沙:國防科技大學出版社,1993.113～117.

　　[5] 姚新,陳國良,徐惠敏等.進化算法研究進展[J].計算機學報,1995,18(9):694-706.

　　[6] 張曉,戴冠中,徐乃平.一種新的優化搜索算法—遺傳算法.控制理論與應用[J].1995, 12(3):265-273.

　　[7] 楊志英.BP神經網絡在水質評價中的應用[J].中國農村水利水電,2001,9:27-29.