計算智能算法的研究

摘 要：智能計算方法的發展對智能計算的應用有深廣的意義。本文對計算智能的主要算法進行了介紹，并對計算智能所取得的成就和存在的問題進行了剖析，對當前廣泛關注的熱點問題提出了一些新的思路和解決方法，最后對該領域的發展趨勢進行了預測。

關鍵詞：計算智能 神經網絡 模擬退火 模糊邏輯

1 概述

什么是計算智能，并沒有確切的定義。如同人工智能一樣，不同的人對計算智能有不同的理解。我們不必急于為計算智能下定義，更不必像爭論“智能計算機”一樣在名詞上浪費時間，重要的是弄明白“計算智能”究竟包含哪些新思想。廣義地講，人工智能也是試圖用計算機來實現人的智能，所以人工智能也可以看作計算智能。當加拿大的學者創辦“計算智能”學術刊物時，人們只覺得增添了一種人工智能學報，并未仔細考慮這兩者的區別。隨著人工神經網絡、遺傳算法、進化程序、混沌計算等研究逐漸興旺，而每年召開的人工智能學術會議，如AAAI(美國人工智能協會)等，又不太樂意接受這方面的論文與產品演示，從事上述研究的學者逐步組織自己的有相當規模的國際學術會議，取名為計算智能，似乎造成一種與人工智能分庭抗禮的局面。但從學術上講，把計算智能看成人工智能研究的新方向也許更恰當［１］。

計算智能是在1994年IEEE舉辦的首屆計算智能世界大會上提出的，它以連接主義和進化主義思想為基礎，計算智能中的主要算法自適應的結構、隨機產生的或指定的初始狀態、適應度的評測函數、修改結構的操作、系統狀態存儲器、終止計算的條件、指示結果的方法、控制過程參數等共同要素，具有自學習、自組織、自適應的特征和簡單、通用、魯棒性強、易并行處理等特點，這些特征已被用于信息安全、模式識別、數據分類與挖掘、優化設計、故障診斷、機器學習、聯想記憶和控制等領域［２］。本文從計算智能主要算法的角度來對計算智能的研究現狀作分析。［２］

2 計算智能的主要算法

計算智能的主要算法有神經網絡、模擬退火、模糊邏輯、遺傳與演化算法、禁忌搜索算法、DNA軟計算、人工免疫系統、蟻群算法、粒子群算法、多代理（Agent）系統等。

計算智能的算法雖然有很多種，但它們多是受自然或生物界規律的啟迪，根據其原理、思想來模仿求解問題的算法。這樣它們也就具有自然界或生物界的一些特性，同時它們通過長時間的發展變化，逐漸成熟，形成了自己獨有的特點。下面對它們的共同特點作一個介紹：（1）它們大都引入了隨機因素，具有不確定性。很多計算過程實際上是在計算機上作隨機過程的模擬。比如著名的蒙特卡羅模擬。（2）它們大多具有自適應機制的動力體系或隨機動力體系，并且在計算過程中體系結構還在不斷作自我調整。（3）它們都是針對通用的一般目標而設計的，它們不同于針對特殊問題而設計的算法。（4）一些算法在低維或簡單的情況下顯得很笨，但是到了高維復雜的情形下具有很強的競爭力。［３］

3 主要的計算智能算法

3.1 人工神經網絡

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

“人工神經網絡”（artificial neural network：簡稱ANN）是在對人腦組織結構和運行機制的認識理解基礎之上模擬其結構和智能行為的一種工程系統，是對人大腦神經細胞的簡單近似的模擬。大量的神經元廣泛互連而成的系統，它的這一結構特點決定著人工神經網絡具有高速信息處理的能力。人腦的每個神經元大約有10³—10⁴個樹突及相應的突觸，一個人的大腦總計約形成10¹⁴—10¹⁵個突觸。用神經網絡的術語來說，即是人腦具有10¹⁴—10¹⁵個互相連接的存儲潛力。雖然每個神經元的運算功能十分簡單，且信號傳輸速率也較低(大約100次/秒)，但由于各神經元之間的極度并行互連功能，最終使得一個普通人的大腦在約1秒內就能完成現行計算機至少需要數10億次處理步驟才能完成的任務。

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

因此ANN具有快速、并行處理、容錯性強和自學習能力強等特點。幾種典型的ANN為：多層感知網絡、競爭型神經網絡、Hopfield神經網絡。

3.2 模擬退火

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

模擬退火是一種全局優化方法，就是人為地引入噪聲，使得當某算法陷入局部最優的陷阱時，而造成從該陷阱中逃脫的條件，進而再逐步減小噪聲，以使得算法能停留在全局最優點。其實早在1965年，Khas就提出了這一想法，不過并未受到計算機科學與優化應用領域的足夠重視。直到1983年，Kirkpatrick提出模擬退火算法，才引起了優化應用領域的重視，成為熱點流行起來。它的特點主要有以下幾個方面：（1）以一定的概率接受惡化解，在迭代過程中不僅接受使目標函數變“好”的試探點，而且還能以一定的概率接受目標函數值變“差”的試探點，迭代中出現的狀態是隨機產生的，并且不強求后一個狀態一定優于前一個狀態，即以一定的可能容忍的退化狀態的出現；（2）引進算法控制參數T，它將優化過程分為各個階段，并決定各個階段下隨機狀態的取舍標準，接受函數由Metropolis算法給出一個簡單的數學模型，接受概率隨著溫度的下降而逐漸減小；（3）使用對象函數值（即適應值）進行搜索，它僅使用由目標函數變換來的適應度函數值，就可確定進一步的搜索方向和搜索范圍，無需其它一些輔助信息［４］。

3.3 模糊邏輯

模糊邏輯（FUZZY，fuzzy logic system）自提出以后，特別是在人工智能和控制等領域得到較好的應用之后，已經引起研究人員的濃厚興趣。進入20世紀90年代，模糊邏輯無論在理論上還是在應用方面都得到了較快地發展。

模糊邏輯本身并不模糊，而是用來對“模糊”進行處理以達到消除模糊的邏輯。其最大特點是用它可以自然地處理人類的概念。由于輸入、輸出均為實型變量，所以特別適用于工程應用系統，FUZZY提供了一種描述專家組織的模糊“If-then”規則的一般化模式，模糊產生器、模糊推理機和反模糊化的選擇也有很大的自由度。FUZZY的知識表達易于理解，但難于利用數值信息，自學習能力較差。

3.4 遺傳算法

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

遺傳算法是解決搜索問題的一種通用算法，對于各種通用問題都可以使用。在遺傳算法中，基于染色體群的并行搜索，帶有猜測性質的選擇操作、交換操作和突變操作。這種特殊的組合方式將遺傳算法與其它搜索算法區別開來。

遺傳算法具有以下幾方面的特點：（1）遺傳算法從問題解的串集開始嫂索，而不是從單個解開始。這是遺傳算法與傳統優化算法的極大區別。傳統優化算法是從單個初始值迭代求最優解的；容易誤入局部最優解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優。

(2)許多傳統搜索算法都是單點搜索算法，容易陷入局部的最優解。遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進行評估，減少了陷入局部最優解的風險，同時算法本身易于實現并行化。

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

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

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

3.5 禁忌搜索算法

Tabu Search是由美國科羅拉多州大學的Fred Glover教授在1977年左右提出來的，是一個用來跳出局部最優的搜尋方法。

禁忌搜索是對局部鄰域搜索的一種擴展，是一種全局逐步尋求最優算法。禁忌搜索算法中充分體現了集中和擴散兩個策略，它的集中策略體現在局部搜索，即從一點出發，在這點的鄰域內尋求更好的解，以達到局部最優解而結束，為了跳出局部最優解，擴散策略通過禁忌表的功能來實現。禁忌表中記下已經到達的某些信息，算法通過對禁忌表中點的禁忌，而達到一些沒有搜索的點，從而實現更大區域的搜索。

禁忌搜索算法算法具有以下幾方面的特點：（1）從移動規則看，每次只與最優點比較，而不與經過點比較，故可以爬出局部最優。

（2）選優規則始終保持曾經達到的最優點，所以即使離開了全局最優點也不會失去全局最優性。

（3）終止規則不以達到局部最優為終止規則，而以最大迭代次數、出現頻率限制或者目標值偏離成都為終止規則。

所以禁忌搜索算法是一種局部搜索能力很強的全局迭代尋優算法。

3.6 DNA軟計算

DNA軟計算是一種基于DNA湯（種群）和生物進貨機制的隨機搜索算法，其設計變量服從均值和方差進化過程變化的正態分布，不必預先設定其取值范圍，且算法引導種群逐步向優化區域搜索，確保其全局收斂能力［５］，它的特點主要有以下幾個方面：首先，DNA具有不可估量水平的并行性。其次，DNA軟計算有很高的能量效率和存貯容量。此外，嘗試開發實際的DNA軟計算能促進生物學和生物化學獲得更靈活的操作和更可靠的技術［６］。

3.7 人工免疫系統

人工免疫系統（AIS，artificial immune system）是研究借鑒和利用生物免疫系統的信息處理機制而發展的各類信息處理技術、計算技術及應用的總稱，用于復雜問題的解決。AIS結合了分類器、神經網絡和機器推理學習系統的優點，是一種突現計算，但也存在收斂速度慢等缺點。1994年以來，AIS成為國際上新的研究熱點。目前這一領域還處于起步階段［２］。

3.8 蟻群算法

蟻群算法是人們通過對自然界中蟻群群體行為的研究而提出的一種基于種群的模擬進化算法［７］。該算法通過模擬螞蟻搜索食物的過程來求解一些實際問題。螞蟻能夠在沒有任何可見提示下找出蟻穴到食物源的最短路徑，并且能隨著環境的變化而變化，然后搜索新的路徑，產生新的選擇。受螞蟻覓食時的通信機制的啟發，90年代Dorigo提出了蟻群優化算法。由于這個算法利用了正反饋機制，使得較短的路徑能夠有較大的機會得到選擇，并且由于采用了概率算法，所以它能夠不局限于局部最優解。

3.9 粒子群算法

粒子群算法(PSO，particle swarm optimization)是一種進化計算技術(Evolutionary Computation)，有Eberhart博士和Kennedy博士發明。源于對鳥群捕食的行為研究。PSO同遺傳算法類似，是一種基于疊代的優化工具。系統初始化為一組隨機解，通過疊代搜尋最優值。但是并沒有遺傳算法用的交叉(crossover)以及變異(mutation)。而是粒子在解空間追隨最優的粒子進行搜索。同遺傳算法比較，PSO的優勢在于簡單，容易實現并且沒有許多參數需要調整。目前已廣泛應用于函數優化、神經網絡訓練、模糊系統控制以及其他遺傳算法的應用領域。粒子群優化算法(PSO)也是起源對簡單社會系統的模擬，最初設想是模擬鳥群覓食的過程，但后來發現PSO是一種很好的優化工具。

3.10 多代理（Agent）系統

多Agent系統（Multi-Agent System，MAS）是指由多個自主構件組成的所有類型的系統，它是一個松散耦合的問題求解器網絡，其目標是為了解決那些超出每個問題求解器的單獨能力或知識的問題。這些問題的求解器就是Agent，它們是自主的，并可能是異構的。

多Agent系統的表現通過Agent的交互來實現，主要研究多個Agent，為了聯合采取行動實際系統時，多Agent系統通過各Agent間的通信、合作、協調、管理及控制來表達系統的結構、功能及行為特性。多代理體系中，知識具有局部性，而問題具有全局性，在大多數情況下，需要同其他的代理聯合解決一個問題，這樣代理間的信息傳遞不可避免，因此需要有代理通訊語言（ACL）。

結束語

本文對主要的計算智能算法及各自的特點作了一個介紹，這些算法在解決實際問題中都發揮了相當的作用，當然也有待我們進一步研究、改進和提高。計算智能是一個發展潛力巨大的方向，未來的發展一定會越來越智能化，個性化的傾向越來越濃，目的性變得日益明確，應用的領域也會越來越廣。

參考文獻：

［1］李國杰.計算智能：一個重要的研究方向［A］.

［2］蘇建元.計算智能主要算法的比較與融合［J］.中國電子科學研究院學報，2007.2，(1)：52-56.

［3］錢敏平，龔光魯.從數學角度看計算智能［J］.科學通報，1998，（16）：1681-1695.

［4］項寶衛，凌塑勇.計算智能算法的研究現狀［J］.臺州學院學報，2006.6，(3)：22-25.

［5］黃自元，師黎等.一類自適應范圍DNA軟計算模型.控制理論與應用，2004.12，（6）：889-992.

［6］任立紅，丁永生，邵世煌.DNA計算研究的現狀與展望.信息與控制，1999，（4）.

［7］Marco Dorigo，Vittorio Maniezzo，Alberto Colorni。The ant system：Optimization by a colony of co-operation agents［J］.IEEE Transaction on Systems，1996.26，(1)：1-2.