計算智能算法的研究

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

關(guān)鍵詞：計算智能 神經(jīng)網(wǎng)絡(luò) 模擬退火 模糊邏輯

1 概述

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

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

2 計算智能的主要算法

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

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

3 主要的計算智能算法

3.1 人工神經(jīng)網(wǎng)絡(luò)

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

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

因?yàn)槿斯ど窠?jīng)網(wǎng)絡(luò)的結(jié)構(gòu)特點(diǎn)和其信息存儲的分布式特點(diǎn)，使得它相對于其它的判斷識別系統(tǒng)，如專家系統(tǒng)等，具有另一個顯著的優(yōu)點(diǎn)：健壯性。生物神經(jīng)網(wǎng)絡(luò)不會因?yàn)閭€別神經(jīng)元的損失而失去對原有模式的記憶。最有力的證明是，當(dāng)一個人的大腦因意外事故受輕微損傷之后，并不會失去原有事物的全部記憶。人工神經(jīng)網(wǎng)絡(luò)也有類似的情況。因某些原因，無論是網(wǎng)絡(luò)的硬件實(shí)現(xiàn)還是軟件實(shí)現(xiàn)中的某個或某些神經(jīng)元失效，整個網(wǎng)絡(luò)仍然能繼續(xù)工作。

因此ANN具有快速、并行處理、容錯性強(qiáng)和自學(xué)習(xí)能力強(qiáng)等特點(diǎn)。幾種典型的ANN為：多層感知網(wǎng)絡(luò)、競爭型神經(jīng)網(wǎng)絡(luò)、Hopfield神經(jīng)網(wǎng)絡(luò)。

3.2 模擬退火

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

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

3.3 模糊邏輯

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

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

3.4 遺傳算法

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

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

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

(2)許多傳統(tǒng)搜索算法都是單點(diǎn)搜索算法，容易陷入局部的最優(yōu)解。遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進(jìn)行評估，減少了陷入局部最優(yōu)解的風(fēng)險，同時算法本身易于實(shí)現(xiàn)并行化。

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

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

(5)具有自組織、自適應(yīng)和自學(xué)習(xí)性。遺傳算法利用進(jìn)化過程獲得的信息自行組織搜索時，硬度大的個體具有較高的生存概率，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。

3.5 禁忌搜索算法

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

禁忌搜索是對局部鄰域搜索的一種擴(kuò)展，是一種全局逐步尋求最優(yōu)算法。禁忌搜索算法中充分體現(xiàn)了集中和擴(kuò)散兩個策略，它的集中策略體現(xiàn)在局部搜索，即從一點(diǎn)出發(fā)，在這點(diǎn)的鄰域內(nèi)尋求更好的解，以達(dá)到局部最優(yōu)解而結(jié)束，為了跳出局部最優(yōu)解，擴(kuò)散策略通過禁忌表的功能來實(shí)現(xiàn)。禁忌表中記下已經(jīng)到達(dá)的某些信息，算法通過對禁忌表中點(diǎn)的禁忌，而達(dá)到一些沒有搜索的點(diǎn)，從而實(shí)現(xiàn)更大區(qū)域的搜索。

禁忌搜索算法算法具有以下幾方面的特點(diǎn)：（1）從移動規(guī)則看，每次只與最優(yōu)點(diǎn)比較，而不與經(jīng)過點(diǎn)比較，故可以爬出局部最優(yōu)。

（2）選優(yōu)規(guī)則始終保持曾經(jīng)達(dá)到的最優(yōu)點(diǎn)，所以即使離開了全局最優(yōu)點(diǎn)也不會失去全局最優(yōu)性。

（3）終止規(guī)則不以達(dá)到局部最優(yōu)為終止規(guī)則，而以最大迭代次數(shù)、出現(xiàn)頻率限制或者目標(biāo)值偏離成都為終止規(guī)則。

所以禁忌搜索算法是一種局部搜索能力很強(qiáng)的全局迭代尋優(yōu)算法。

3.6 DNA軟計算

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

3.7 人工免疫系統(tǒng)

人工免疫系統(tǒng)（AIS，artificial immune system）是研究借鑒和利用生物免疫系統(tǒng)的信息處理機(jī)制而發(fā)展的各類信息處理技術(shù)、計算技術(shù)及應(yīng)用的總稱，用于復(fù)雜問題的解決。AIS結(jié)合了分類器、神經(jīng)網(wǎng)絡(luò)和機(jī)器推理學(xué)習(xí)系統(tǒng)的優(yōu)點(diǎn)，是一種突現(xiàn)計算，但也存在收斂速度慢等缺點(diǎn)。1994年以來，AIS成為國際上新的研究熱點(diǎn)。目前這一領(lǐng)域還處于起步階段［２］。

3.8 蟻群算法

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

3.9 粒子群算法

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

3.10 多代理（Agent）系統(tǒng)

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

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

結(jié)束語

本文對主要的計算智能算法及各自的特點(diǎn)作了一個介紹，這些算法在解決實(shí)際問題中都發(fā)揮了相當(dāng)?shù)淖饔茫?dāng)然也有待我們進(jìn)一步研究、改進(jìn)和提高。計算智能是一個發(fā)展?jié)摿薮蟮姆较颍磥淼陌l(fā)展一定會越來越智能化，個性化的傾向越來越濃，目的性變得日益明確，應(yīng)用的領(lǐng)域也會越來越廣。

參考文獻(xiàn)：

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

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

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

［4］項(xiàng)寶衛(wèi)，凌塑勇.計算智能算法的研究現(xiàn)狀［J］.臺州學(xué)院學(xué)報，2006.6，(3)：22-25.

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

［6］任立紅，丁永生，邵世煌.DNA計算研究的現(xiàn)狀與展望.信息與控制，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.