自然計算研究進(jìn)展

莫宏偉

(哈爾濱工程大學(xué)自動化學(xué)院，黑龍江哈爾濱 150001)

自然計算研究進(jìn)展

莫宏偉

(哈爾濱工程大學(xué)自動化學(xué)院，黑龍江哈爾濱 150001)

自然計算是計算機(jī)科學(xué)與人工智能領(lǐng)域中重要的研究內(nèi)容之一.經(jīng)過幾十年的發(fā)展，已經(jīng)逐漸發(fā)展成為涉及多個學(xué)科的新興交叉研究領(lǐng)域，其研究目的在于從自然界中尋求解決人類所面臨的復(fù)雜問題的方法.早期自然計算主要集中在進(jìn)化計算、人工神經(jīng)網(wǎng)絡(luò)、模糊系統(tǒng)3個主要方面，近20年研究人員提出群體智能、人工免疫系統(tǒng)、DNA計算等新方法.對群體智能等新方法的研究現(xiàn)狀、發(fā)展趨勢、存在的問題進(jìn)行分析，指出未來發(fā)展重點(diǎn)和方向.

自然計算;生物啟發(fā)的計算;群智能;分子計算

自然計算是自然解決各種問題的理論.遺傳算法、人工神經(jīng)網(wǎng)絡(luò)、模糊系統(tǒng)等經(jīng)典方法從誕生至今已經(jīng)各自演變成相對獨(dú)立的人工智能研究領(lǐng)域，保持著長久不衰的生命力，半個多世紀(jì)以來不斷得到改進(jìn)，衍生出眾多新方法.特別是最近20余年，有關(guān)進(jìn)化計算的學(xué)術(shù)論文逐年增加，主要發(fā)表在《IEEE Transactions on Evolutionary Computation》和《Evolutionary Computation》等雜志以及在 CEC、GECCO、PPSN、FOGA和EuroGP等國際學(xué)術(shù)會議上.焦李成等人2008年在《Evolutionary Computation》上提出了一種求解多目標(biāo)優(yōu)化的免疫算法——非支配鄰域免疫算法［1］，是該期刊創(chuàng)刊以來國內(nèi)學(xué)者在該刊物發(fā)表的第2篇論文.唐珂、王勇等一批國內(nèi)青年學(xué)者在進(jìn)化計算研究領(lǐng)域發(fā)表了一批高水平論文［2－4］，取得國際矚目的成果.有關(guān)多目標(biāo)進(jìn)化算法的研究也漸成體系［5－6］.近年來，進(jìn)化計算的研究已相對成熟，基本算法設(shè)計、基本理論研究方面趨于完善，一些基于演化原理的、為更好解決實際問題的算法，如多目標(biāo)演化算法、協(xié)同演化算法、約束優(yōu)化演化算法以及將演化計算與神經(jīng)網(wǎng)絡(luò)等方法、技術(shù)相結(jié)合引起了研究者們廣泛的興趣［7］.

人工神經(jīng)網(wǎng)絡(luò)近些年在理論和應(yīng)用2個方面都取得了豐碩成果.例如在神經(jīng)網(wǎng)絡(luò)與認(rèn)知科學(xué)的結(jié)合、神經(jīng)網(wǎng)絡(luò)與量子理論的結(jié)合、神經(jīng)網(wǎng)絡(luò)與進(jìn)化算法的結(jié)合、神經(jīng)網(wǎng)絡(luò)與生物醫(yī)學(xué)的結(jié)合、神經(jīng)網(wǎng)絡(luò)與灰色系統(tǒng)的結(jié)合以及與其他多種智能技術(shù)結(jié)合的各種混合神經(jīng)網(wǎng)絡(luò).代表性研究成果有:脈沖耦合神經(jīng)網(wǎng)絡(luò)［8］、神經(jīng)網(wǎng)絡(luò)集成［9］等.應(yīng)用技術(shù)研究不斷深入，涉及民用和軍用領(lǐng)域［10］.

經(jīng)過40多年的發(fā)展，模糊集已經(jīng)成為一個理論基礎(chǔ)雄厚、學(xué)術(shù)影響深遠(yuǎn)的交叉學(xué)科.理論研究方面，模糊分析學(xué)、模糊代數(shù)學(xué)和模糊拓?fù)鋵W(xué)等分支成果豐碩.應(yīng)用研究方面，模糊控制、模糊聚類分析、模糊模式識別、模糊神經(jīng)網(wǎng)絡(luò)和模糊專家系統(tǒng)等發(fā)展迅速.國際模糊集理論研究，主要集中在模糊集理論、模糊集以及與其他理論的交叉融合技術(shù)等方面［7，11］.

在上述3種經(jīng)典自然啟發(fā)的計算算法基礎(chǔ)上，從20世紀(jì)90年代起，基本每10年左右就會涌現(xiàn)一批新的自然計算方法，20世紀(jì)90年代初代表性的有蟻群算法(ant colony optimization，ACO)［12］、粒子群算法(particle swarm optimization，PSO)［13］、免疫算法［14－15］、文化算法［16］、DNA 計算［17］、細(xì)胞膜計算［18－19］、Memetic 算法［20］，前 2 種算法又形成一個新的自然計算分支——群體智能，其中粒子群算法影響最大［21］.2000年以后的10年，人工免疫系統(tǒng)發(fā)展迅速［22］，這一時期，人工魚群算法(artificial fish swarm optimization，AFSO)［23－24］、細(xì) 菌 覓 食 算 法(bacteria algorithm，BA)［25］、蜂群算法［26］、生物地理優(yōu)化算法(biogeography－based optimization algorithm，BBO)［27］、人群搜索算法［28］、螢火蟲算法［29］、野草入侵優(yōu)化算法［30］、量子群智能算法［31］、生態(tài)系統(tǒng)算法［32］、化學(xué)計算［33］等新方法不斷涌現(xiàn)，使自然計算家族不斷壯大.

上述所有自然啟發(fā)的計算可以分成:生物啟發(fā)的計算［34］，包括受各種生物系統(tǒng)啟發(fā)而設(shè)計的多種算法;受物理現(xiàn)象或規(guī)律啟發(fā)的計算，包括模擬退火算法［35］、量子計算［36］、磁場優(yōu)化算法［37］等;化學(xué)啟發(fā)的計算是利用化學(xué)反應(yīng)過程實現(xiàn)問題求解.如果從廣義的角度把人類社會及思維看作是自然界生物的一部分，則受人類社會啟發(fā)的計算也應(yīng)該看作是自然計算的一部分，比如智能主體、形式語言等.這3種類型的計算的共同特征具有較高的智能性.

自然啟發(fā)的計算實際上是自然計算的一部分.根據(jù)文獻(xiàn)［38］的觀點(diǎn)，自然計算內(nèi)容擴(kuò)展如圖1所示.主要包括3方面:1)受自然啟發(fā)，用現(xiàn)代計算機(jī)高級編程語言來實現(xiàn)，應(yīng)用范圍廣泛;2)利用現(xiàn)代計算機(jī)建立自然系統(tǒng)的模型和仿真系統(tǒng)，研究自然界及生物本身，如人工生命、人工植物;3)利用生物或物理、化學(xué)性能或機(jī)制設(shè)計能夠突破馮氏計算機(jī)結(jié)構(gòu)限制的裝置、設(shè)備，如分子計算機(jī)、生物計算機(jī)、量子計算機(jī)、光子計算機(jī)等.本文限于篇幅，不能一一闡述所有自然計算內(nèi)容，只以生物啟發(fā)的計算中相對更為活躍的群體智能以及效率更高的分子計算為重點(diǎn)，闡述自然計算發(fā)展的趨勢、特點(diǎn)以及存在的問題，并對未來的發(fā)展方向進(jìn)行探討.

圖1 自然計算的內(nèi)容Fig.1 Content of natural computing

1 生物啟發(fā)的計算

生物啟發(fā)的計算的研究有雙重目的:可以解決生物學(xué)以外的工程和科學(xué)問題;反過來，這些方法又能提供新的工具和技術(shù)用于研究解決生物學(xué)本身的問題.

1.1 群體智能

群體智能(swarm intelligence，SI)是一種模仿自然界動物昆蟲覓食筑巢行為的計算技術(shù)，研究由若干簡單個體組成的分散系統(tǒng)的集體行為，其中每個個體與其他個體以及環(huán)境都有相互作用.Bonabeau定義群智能為:任何受到社會昆蟲群體和其他動物社會集體行為啟發(fā)所設(shè)計的算法或者分布式問題求解設(shè)備［39］.群智能算法著眼于自然界中的生物社會群落，比如蟻群、鳥群、乃至人群等社會群體行為.目前SI包括粒子群優(yōu)化算法、蟻群算法、人工魚群算法、蜂群算法、細(xì)菌算法以及生物地理優(yōu)化算法等.

1.1.1 細(xì)菌優(yōu)化算法

細(xì)菌為了覓食采取必要的行動使每單位時間攝取的能量最大化，自然界中的細(xì)菌覓食策略行為實際上可看作是一種優(yōu)化策略，隱含的思想可以用于解決實際優(yōu)化問題.在細(xì)菌群體覓食行為中，具有一種趨藥性，這種性質(zhì)促使細(xì)菌試圖運(yùn)動到營養(yǎng)濃度高的地方以避免有害物質(zhì)并從經(jīng)過的物質(zhì)中搜索路徑.基于細(xì)菌覓食和趨藥性概念，Muller和Passino分別提出細(xì)菌覓食優(yōu)化算法(bacteria foraging optimization algorithm，BFOA)［40］和細(xì)菌趨藥性算法(bacterial chemotaxis algorithm，BCA)［41］.這 2 個算法雖然在實現(xiàn)步驟上有很大不同，但在模擬生物機(jī)制上存在交叉.文獻(xiàn)［42］提出變化環(huán)境細(xì)菌覓食方法，利用基于個體的模型方法模擬細(xì)菌活動和細(xì)菌群體的進(jìn)化;文獻(xiàn)［43］提出基于BFOA獨(dú)立主元素分析，該算法產(chǎn)生的均方差性能比約束遺傳算法的ICA更好;文獻(xiàn)［44］提出經(jīng)典梯度下降搜索模式下模擬趨藥性的數(shù)學(xué)分析;文獻(xiàn)［45］提出 GA和BFOA混合，提出的算法在幾個數(shù)值測試上和PID控制器設(shè)計上超過GA和BFOA;文獻(xiàn)［46］提出一個模糊參考模式，選擇最優(yōu)趨藥步驟，得到模糊細(xì)菌聚集FBF，該方法不適合優(yōu)化測試函數(shù);文獻(xiàn)［47］將BFOA與PSO混合的細(xì)菌群體優(yōu)化，統(tǒng)計意義上比經(jīng)典方法好.BFOA已經(jīng)成功用于控制器設(shè)計［48］、股票預(yù)測［49］、電力系統(tǒng)問題［50］，本文作者將BFOA優(yōu)化K－means聚類中心，得到細(xì)菌覓食聚類算法并用于圖像分割，取得較好效果［51］.

研究趨藥性算法的先驅(qū)是Brenermann及其同事［13］.基本BCA依賴于單個細(xì)菌的運(yùn)動行為，它不斷地感受它周圍的環(huán)境變化并且只利用它過去的經(jīng)驗來尋找最優(yōu)點(diǎn)，具有較強(qiáng)的簡單性、魯棒性.但基本BCA性能只和基本的遺傳算法相當(dāng)，在某些情況下性能還要比一些改進(jìn)的遺傳算法差.李威武等在BCA基礎(chǔ)上提出了BCC算法［52］，這種算法將群體智能的思想引入到BCA，使用多條細(xì)菌組成的菌群進(jìn)行尋優(yōu).BCC算法雖然提高了BCA的優(yōu)化能力，但必須使用大量細(xì)菌才能使算法的優(yōu)化能力有所高，文獻(xiàn)［53］借鑒了微遺傳算法的思想，將之應(yīng)用于菌群算法，提出了一種微細(xì)菌群趨藥性(M－BCC)算法.在M－BCC算法中有2個菌群，一個菌群是尋優(yōu)菌群，另一個菌群是庫存菌群.M－BCC算法在尋優(yōu)能力方面要優(yōu)于BCC算法.文獻(xiàn)［54－55］分別對該種算法進(jìn)行了簡單綜述和改進(jìn)研究.

1.1.2 蜂群算法

蜂群也是一種典型的群體昆蟲，與其他社會昆蟲有類似的結(jié)構(gòu).一些研究人員提出模擬蜜蜂群體的特殊智能行為的模型，應(yīng)用于組合優(yōu)化問題［56－64］.Tereshko 把蜂群看成動態(tài)系統(tǒng)，搜集來自環(huán)境的信息，根據(jù)這些信息調(diào)節(jié)其行為［56］.Tereshko和Loengarov研究了一種基于蜜蜂覓食思想的機(jī)器人群體協(xié)同機(jī)制.實驗顯示類昆蟲機(jī)器人在實際機(jī)器人任務(wù)中是成功的.他們開發(fā)了覓食選擇的最小模型，導(dǎo)致集體智能的涌現(xiàn).該系統(tǒng)由食物源、工蟻和非工蟻3個基本組成，定義了2個行為模式:恢復(fù)食物源和放棄食物源［57－58］.Tereshko 還提出在求解復(fù)雜交通和運(yùn)輸問題采用群智能開發(fā)人工系統(tǒng)［59－60］以及蜂群優(yōu)化元啟發(fā)算法，能求解組合優(yōu)化問題以及不確定組合問題［61］.Drias等人引入一個新的智能方法或者元啟發(fā)方法，稱為蜂群優(yōu)化(bees swarm optimization，BSO)，并用它解決最大權(quán)滿足問題(max－sat)［62］.類似地，Benatchba 等人引入基于蜜蜂繁殖過程的元啟發(fā)解決 3－sat問題［63］.Wedde等人受到蜂蜜過程、交流和評價方法的啟發(fā)提出一個新的路徑算法，稱為 BeeHive［64］.在該算法中，蜜蜂主體通過稱為覓食區(qū)的網(wǎng)絡(luò)區(qū)域巡游，在它們的路徑上，網(wǎng)絡(luò)狀態(tài)的信息不斷分配，用于更新局部路由表.

上述都是組合優(yōu)化問題.有3個連續(xù)優(yōu)化算法，基于蜂群算法的智能性［65－67］.Yang［65］開發(fā)了虛擬蜜蜂算法(VBA)優(yōu)化二維數(shù)值函數(shù)，算法產(chǎn)生一群虛擬蜜蜂，通過這些蜜蜂的相互作用強(qiáng)度獲得問題的解.Pham等［66］提出應(yīng)用幾個控制參數(shù)的蜜蜂算法.對于優(yōu)化多變量和多模態(tài)函數(shù)，Karaboga［67］提出可人工蜂群算法(ABC)，Basturk和Karaboga在有限測試問題上比較了 ABC 和 GA［68］、PSO 和 PS－EA［69］以及DE、PSO和EA的性能［70］.ABC算法已經(jīng)應(yīng)用到約束優(yōu)化問題［71］、神經(jīng)網(wǎng)絡(luò)訓(xùn)練［72－73］、設(shè)計 IIR 濾波器［74］和葉約束最小生成樹問題［75］.文獻(xiàn)［76］將ABC算法與遺傳算法和其他群智能算法在50個不同類型函數(shù)問題上進(jìn)行了大規(guī)模全面比較和分析，結(jié)果顯示ABC算法性能好于或者近似其他群智能算法，優(yōu)勢在于算法控制參數(shù)較少.

1.1.3 生物地理優(yōu)化算法

生物地理優(yōu)化算法(biogeography－based optimization，BBO)是美國學(xué)者Simon于2008年正式提出的一種新型優(yōu)化算法，是一種新的生物地理學(xué)啟發(fā)算法，用以解決全局最優(yōu)解［27］.它主要通過物種的遷移算子來實現(xiàn)信息資源共享，BBO是在生物地理學(xué)的數(shù)學(xué)模型基礎(chǔ)上實現(xiàn)的一種全局性優(yōu)化方法.

文獻(xiàn)［27］介紹了如何基于生物地理學(xué)的基本理論設(shè)計該優(yōu)化算法，給出了算法的基本理論框架和步驟.在所給出的8個典型函數(shù)和一個飛機(jī)發(fā)動機(jī)傳感器選擇的實際問題上進(jìn)行的測試表明，該算法雖然結(jié)構(gòu)比較簡單，但在多數(shù)測試問題上表現(xiàn)均優(yōu)于現(xiàn)有的遺傳算法、粒子群算法、蟻群算法等其他7個常用的優(yōu)化算法.文獻(xiàn)［77］提出了對立生物地理學(xué)優(yōu)化算法.馬海平［78］推廣了生物地理理論中的物種平衡數(shù)，探討了6種不同的遷移模型，通過實驗表明正弦遷移曲線性能最優(yōu).龔文銀等［79］擴(kuò)展了原有的BBO，提出一種實數(shù)編碼的BBO方法，同時引進(jìn)鄰域搜索算子.杜大偉等［80］融合進(jìn)化策略，同時提出一種設(shè)定閾值的移民拒絕方法.龔文銀等還將BBO融入DE，提出一種混合的差異進(jìn)化方法，該方法有效地結(jié)合了DE的探索能力和BBO的開采能力，另外也研究了種群的規(guī)模、維數(shù)、不同的變異方案和自適應(yīng)控制參數(shù)對該混合方法的影響［81］.馬海平［82］推廣了生物地理理論中的物種平衡數(shù)，討論了4種不同的遷移模型，通過實驗表明線性遷移率比常數(shù)遷移率的優(yōu)化效果更好.Dan Simon對BBO進(jìn)行了簡化，提出了3種簡化的BBO算法理論模型，對群體進(jìn)行概率分析，證明了算法在不同簡化形式下得到最優(yōu)解所需要的代數(shù)和期望的改進(jìn)量，而且這些量都與群體數(shù)量相關(guān)［83］，發(fā)展了BBO的馬爾可夫分析，對比了BBO和簡單遺傳算法的馬爾可夫分析，對精英策略的選擇也進(jìn)行了討論［84］.在BBO應(yīng)用方面，文獻(xiàn)［85］提出利用BBO進(jìn)行天線陣列分析的算法.文獻(xiàn)［86］則提出了量子與生物地理學(xué)算法結(jié)合的新算法.文獻(xiàn)［87］采用群計算技術(shù)處理圖像分類，文中使用一個新的群數(shù)據(jù)聚類方法，該方法基于人工蜜蜂花簇授粉進(jìn)行衛(wèi)星圖像像素的聚類，使用該方法獲得了高精確度衛(wèi)星圖像分類.文獻(xiàn)［88］利用該算法解決經(jīng)濟(jì)負(fù)載分配問題.本文作者將BBO算法用于求解TSP問題，通過多個旅行商(TSP)經(jīng)典測試問題證明生物地理學(xué)思想是一種求解TSP問題新的有效手段［89］.

1.1.4 群體智能發(fā)展問題

自然計算的啟發(fā)源于微小的細(xì)菌、活躍的蜜蜂，發(fā)展到大規(guī)模動物遷移，并已經(jīng)開發(fā)出相應(yīng)的有效算法.上述多種群體智能算法在理論和應(yīng)用方面發(fā)展程度不一，但都遠(yuǎn)未達(dá)到成熟階段.所有群體智能算法的一個共同特征是候選解以群體形式向著搜索空間中更好的解區(qū)域移動，共同挑戰(zhàn)是如何結(jié)合生物群智能以加速向最優(yōu)解收斂，避免局部最優(yōu)解，這也是所有自然計算優(yōu)化求解的共性問題.群體智能發(fā)展主要有以下幾個方面的問題值得關(guān)注:

1)觀察和發(fā)現(xiàn)生物群體中新的行為模式，借鑒生物學(xué)成果進(jìn)行建模和分析，以進(jìn)一步改進(jìn)現(xiàn)有算法和開發(fā)新的SI算法.比如生物學(xué)上對一種趨磁性細(xì)菌的研究的關(guān)注［90］.

2)數(shù)學(xué)理論基礎(chǔ)相對薄弱，缺乏具備普遍意義的理論性分析.

3)充分發(fā)揮其固有的強(qiáng)并行性，與最新計算軟硬件技術(shù)尤其是嵌入式系統(tǒng)相結(jié)合，服務(wù)于實際應(yīng)用.

4)同其他的進(jìn)化算法一樣，群體智能也是概率算法，對于解決實際問題而言存在可靠性方面的風(fēng)險.

5)學(xué)習(xí)、推理、知識處理在群體智能中的應(yīng)用研究.

1.2 分子計算

分子計算是一個跨學(xué)科的研究領(lǐng)域.這里的計算不只局限于狹義的算法，而是泛指在自然界中物理、化學(xué)以及生物分子水平上研究新的計算模式和方法.分子計算就是試圖研究分子在信息處理方面的計算能力.分子計算思想直到1994年Adleman對一般目的的DNA分子計算機(jī)方面取得突破性進(jìn)展［17］，才被證實.

1.2.1 DNA計算

DNA計算的研究內(nèi)容包括:DNA計算的通用模型、DNA鏈大規(guī)模并行性計算模型、不同自然發(fā)生結(jié)構(gòu)的DNA計算模型(尤其是循環(huán)和其他非線性結(jié)構(gòu))、在細(xì)胞層次上利用自然發(fā)生的生物操作的分子計算模型［90］.

DNA計算模型主要劃分為非限制性模型和限制型模型.非限制模型的操作對象是單個DNA串(基因)，而限制型模型的操作對象是DNA串的狀態(tài)集合(染色體).許多研究學(xué)者不僅研究了各種DNA算法來提高DNA的計算能力和降低其復(fù)雜性，而且也提出了與電子計算模型對應(yīng)的分子模型的DNA算法，如DNA加、DNA算術(shù)與邏輯運(yùn)算、分子矩陣乘和因式分解法等.利用DNA的分子計算的優(yōu)點(diǎn)是每個DNA分子可以作為一個單獨(dú)的處理器功能，這意味著極大加快了解決復(fù)雜問題的速度［91］.

DNA分子計算的優(yōu)勢還在于其遠(yuǎn)遠(yuǎn)超越電子計算的存儲容量以及極小的能量消耗.

文獻(xiàn)［92］提出一種DNA計算啟發(fā)計算模型，可以在液體環(huán)境中漂浮的雙鏈結(jié)構(gòu)上進(jìn)行計算，通過類似DNA計算的重寫規(guī)則實現(xiàn)，并提出利用膜計算作為實現(xiàn)這些規(guī)則的生物技術(shù)手段.

DNA計算主要問題集中在DNA計算的形式模型、復(fù)雜問題求解、DNA的計算復(fù)雜性、DNA計算機(jī)實現(xiàn)(比如如何降低試管操作的復(fù)雜性)等多方面.可以借用DNA機(jī)制與自然啟發(fā)的計算結(jié)合或融合，但如果DNA算法只在電子計算機(jī)上實現(xiàn)，顯然失去了開發(fā)這種計算模式的生物優(yōu)勢和意義.

1.2.2 從計算觀點(diǎn)看蛋白質(zhì)

蛋白質(zhì)作為神經(jīng)元的受體和神經(jīng)元介質(zhì)控制大腦的電子活動，也是免疫系統(tǒng)的主要元素.從計算觀點(diǎn)看，現(xiàn)有所有的生物系統(tǒng)的信息基礎(chǔ)由統(tǒng)一的編碼——一個縮氨酸表組成，其中的詞就是蛋白質(zhì)分子.在計算機(jī)術(shù)語中，可以說基因編碼是軟件(指導(dǎo)或者編程)，而蛋白質(zhì)看作硬件(執(zhí)行程序的生物物理裝置)［93］.

雖然基因編碼蛋白質(zhì)非常簡單，但這些生物物理機(jī)制不容易發(fā)現(xiàn).存儲遺傳編碼的DNA雙螺旋結(jié)構(gòu)的空間結(jié)構(gòu)是由同一平面中非常精確的分子形態(tài)之間的弱相互作用形成的.空間結(jié)構(gòu)是生物分子中幾何對應(yīng)的最顯著的例子之一.在蛋白質(zhì)情況，這個層次的理解還沒有達(dá)到.但如下原理是顯然的［94］:1)蛋白質(zhì)的空間配置由其氨基酸(字母)線性序列(詞)組成;2)空間配置決定任何蛋白質(zhì)的功能.

在編碼和蛋白質(zhì)配置之間的第1個對應(yīng)是原初形式由自我組裝或者折疊機(jī)制確定.一個蛋白質(zhì)的功能和空間配置之間的第2個對應(yīng)是由分子識別機(jī)制實現(xiàn)的，如雙螺旋結(jié)構(gòu)，這些機(jī)制基本基于蛋白質(zhì)分子的不同部分之間和不同蛋白質(zhì)分子之間的弱相互作用.

自我裝配(或者折疊)是蛋白質(zhì)分子鏈的能力.蛋白質(zhì)以獨(dú)特的、精確的方式利用重疊能力調(diào)節(jié)自身結(jié)構(gòu)適應(yīng)自身功能.折疊機(jī)制確保一個蛋白質(zhì)分子的獨(dú)特性質(zhì).這個獨(dú)特性編碼表現(xiàn)在蛋白質(zhì)鏈靈活的連接變化中.這些特征確保一個蛋白質(zhì)分子的折疊更迅速無誤，以提供具有必要的功能和靈活性的蛋白質(zhì).

蛋白質(zhì)能選擇性識別合適的模式或者拒絕不合適的模式，這種識別能力能夠改變其空間結(jié)構(gòu)，這個現(xiàn)象稱為變構(gòu)效應(yīng).由于變構(gòu)效應(yīng)，蛋白質(zhì)有時能結(jié)合以前不能結(jié)合的一個蛋白質(zhì)或者另一個分子，這樣能夠結(jié)合新蛋白質(zhì)形成所謂的分子環(huán)或免疫網(wǎng)絡(luò)［95］.

目前，關(guān)于蛋白質(zhì)計算的研究并不多，有許多空白點(diǎn)值得挖掘，像DNA計算等其他分子計算一樣，有希望成為未來分子計算的研究熱點(diǎn).文獻(xiàn)［96］利用概率轉(zhuǎn)換樹對模擬蛋白質(zhì)計算進(jìn)行了研究，提出了一種新的通用的計算技術(shù)，基于蛋白質(zhì)相互作用的仿真，設(shè)計大規(guī)模并行分布式概率計算方法，并用于特征圖象識別.文獻(xiàn)［97］將DNA計算與蛋白質(zhì)特性結(jié)合起來，證明蛋白質(zhì)可以表示DNA計算所得到的解.

1.2.3 分子計算現(xiàn)狀

自然界的生命系統(tǒng)層次簡單地分為分子、細(xì)胞、組織(尤其是腦)、個體、社會和生態(tài)系統(tǒng)，每個層次都是計算生命科學(xué)研究的主題和目標(biāo).分子計算也屬于“計算生命科學(xué)”這個研究領(lǐng)域的一部分.計算生命科學(xué)的目的是從計算理論觀點(diǎn)理解生命系統(tǒng)，并應(yīng)用這個研究結(jié)果到生物工程.這里，分子計算考慮如何建立人工系統(tǒng)，研究生命系統(tǒng)的最基本層次.

從計算角度，分子計算重點(diǎn)在于研究分子的計算能力，尤其是生物分子的計算能力，以便利用其實現(xiàn)信息處理，希望信息處理運(yùn)算更快、更小(納米尺度)，以及提高成本、效率(節(jié)省能量)，也希望出現(xiàn)新的信息處理計算模型，基于新的計算模型設(shè)計不同類型的計算機(jī).分子計算考慮的不僅是計算機(jī)也包含其他應(yīng)用，如納米機(jī)器、微機(jī)械、生物系統(tǒng)中的信息處理等.復(fù)雜納米機(jī)構(gòu)的自治信息也被認(rèn)為是一種計算形式，這種分子自組織也是分子計算的重要主體之一.這樣的技術(shù)是分子電子的基礎(chǔ)，分子計算在設(shè)計一般分子計算機(jī)中更基礎(chǔ).在美國，生物分子計算協(xié)會在DARPA和NSF支持下成立于1997年.協(xié)會不僅研究高性能大規(guī)模并行性分子計算，也研究利用在納米尺度上的反應(yīng)節(jié)省能量的計算.

納米制作裝配技術(shù)是分子計算應(yīng)用中活躍的領(lǐng)域，被認(rèn)為是納米技術(shù)的一部分.由于DNA是流行的分子工具，人們稱它為DNA納米技術(shù).Winfree提出的DNA瓦片就是這樣一種具有DNA的納米技術(shù)(DNA納米技術(shù)).在一個DNA瓦片鏈末端含有可變序列，這些瓦片能自集合為規(guī)模模式，而且能成為一個在單鏈末端實現(xiàn)的特殊算法指定的結(jié)構(gòu).這個形式的自集合可用于設(shè)計一個模板，取代分子電子學(xué)中的分子邏輯門［98］.

另一個有前景的分子計算應(yīng)用是基因分析，如DNA指紋.在美國生物分子計算協(xié)會的研究中，應(yīng)用分子計算智能測量技術(shù)提高了DNA芯片的性能.

在歐洲，Rozenberg建立了分子計算協(xié)會，總部在Leiden的自然計算中心，許多歐洲研究組織參與到該協(xié)會.歐洲的研究組織突出強(qiáng)調(diào)分子計算的理論方面，特別是與形式語言理論有關(guān)的圖靈計算能力和分子反應(yīng)的計算復(fù)雜性得到積極研究.主要研究內(nèi)容及結(jié)果有:Yokomori研究組基于新的計算范例得到許多理論結(jié)果，如拼接系統(tǒng)和自組織.尤其是他們提出稱為“計算=自我集合(assembly)+轉(zhuǎn)換”的新計算模式，闡明了分子的固有計算能力.分子計算分析及其設(shè)計策略:為了幫助分子算法和反應(yīng)系統(tǒng)的實驗設(shè)計，Hagiya、Nishikawa、Arita 和 Rose 仿真研究了分子計算的計算復(fù)雜性、反應(yīng)機(jī)制和序列設(shè)計，尤其是虛擬核酸仿真器，能夠在計算機(jī)中復(fù)現(xiàn)分子計算，序列設(shè)計的標(biāo)準(zhǔn)也得到積極研究.

日本科學(xué)促進(jìn)協(xié)會早在1996年就開始從不同角度研究分子計算機(jī)的理論和建設(shè)，如通過生物啟發(fā)的自適應(yīng)系統(tǒng)來研究廣泛的進(jìn)化計算.其他正在進(jìn)行的相關(guān)研究包括:人工細(xì)胞設(shè)備、化學(xué)信息芯片，該項技術(shù)是高性能和大規(guī)模分子計算不可缺少的;生命信息處理器和外部環(huán)境接口系統(tǒng)的設(shè)計和制作，重點(diǎn)是信號轉(zhuǎn)換，尤其是細(xì)胞膜受體.在其生物化學(xué)方法中，細(xì)胞膜蛋白質(zhì)期望作為未來細(xì)胞計算機(jī)的輸入輸出設(shè)備，信號轉(zhuǎn)換的功能就是活細(xì)胞中的計算.

目前，國外的上述研究組織已經(jīng)開始長期的積極交流計劃，包括分子記憶等幾個聯(lián)合研究項目正在進(jìn)行中［99］.國內(nèi)在這方面的研究成果還不多見.

1.2.4 分子計算的問題

分子計算是對量子計算的補(bǔ)充，尋求在單個分子內(nèi)讀寫、處理信息的方法.目前的研究結(jié)果使人們不再相信DNA計算機(jī)將比傳統(tǒng)數(shù)字計算機(jī)更快地解決NP完全問題.現(xiàn)代計算機(jī)能沒有誤差地解決超過幾百個變量的可滿足性問題.要達(dá)到同樣的速度和質(zhì)量，DNA計算機(jī)要在算法及執(zhí)行上經(jīng)歷不可估量的量的突破.

研究人員現(xiàn)在認(rèn)識到用分子計算機(jī)與數(shù)字計算機(jī)競爭不是好主意，把NP完全問題僅看作評估分子計算機(jī)的測試基準(zhǔn).因此將分子計算機(jī)與數(shù)字計算機(jī)相比較是過時的思想.分子計算應(yīng)該從基本的理論到應(yīng)用都得到廣泛研究，目的應(yīng)該是實現(xiàn)分子尺度上的信息處理機(jī)制.

1.3 細(xì)胞膜計算

細(xì)胞膜計算是由Paun開創(chuàng)的一個新領(lǐng)域，是自然計算的一個新分支.它是一種受活細(xì)胞功能的啟發(fā)的新計算模式，可以看做是受生物細(xì)胞啟發(fā)的計算范例.更準(zhǔn)確地說，它是一種基于細(xì)胞膜系統(tǒng)的分布式并行計算系統(tǒng)(也稱為P系統(tǒng)).細(xì)胞膜結(jié)構(gòu)定義的區(qū)域中，有一系列對象根據(jù)一個給定規(guī)則進(jìn)化并相互作用，計算的結(jié)果通常是在給定時間后系統(tǒng)的全局狀態(tài).細(xì)胞膜計算開始于1998年，Paun發(fā)表的文章《利用細(xì)胞膜計算》是這個新領(lǐng)域的起點(diǎn)標(biāo)志［100］.

如圖2所示，一個細(xì)胞膜計算系統(tǒng)是一個從活細(xì)胞處理不同區(qū)域結(jié)構(gòu)的化學(xué)化合物的方式中抽象出來的計算模型.在細(xì)胞膜定義的區(qū)域中，有根據(jù)給定規(guī)則進(jìn)化的對象.這些對象可用符號或者符號字符串描述.前者是一種多樣性問題，也就是細(xì)胞膜結(jié)構(gòu)區(qū)域中具有的多個要處理的對象集合，后者是指可以用字符串語言研究這些對象集合或者多字符串的集合表示［19］.

圖2 膜結(jié)構(gòu)Fig.2 Structure of membrane

細(xì)胞膜計算研究內(nèi)容包括不同的控制對象從一個區(qū)域到另一個區(qū)域的轉(zhuǎn)換方法以及規(guī)則應(yīng)用方法，例如溶解、分裂、產(chǎn)生或者移動細(xì)胞膜.組織細(xì)胞膜系統(tǒng)、神經(jīng)細(xì)胞膜系統(tǒng)和群細(xì)胞膜系統(tǒng)也正在研究中.

這些方法中的一些改進(jìn)產(chǎn)生的通用計算系統(tǒng)，還有具有增強(qiáng)的并行性的改進(jìn)方法，能夠解決多項式時間NP完全問題.

不同形式的細(xì)胞膜系統(tǒng)統(tǒng)稱為P系統(tǒng)，P系統(tǒng)也可以是所有沒有應(yīng)用于實際的細(xì)胞膜系統(tǒng)理論模型［18］.目前有許多P系統(tǒng)已經(jīng)公式化，但從理論和實際應(yīng)用角度有更多問題還需要研究［101］.主要集中在證明具有較少數(shù)量的細(xì)胞膜系統(tǒng)的計算通用性，用于解決諸如布爾滿足問題、旅行商問題等NP難問題，近 2年在圖像處理［102］、大氣環(huán)境建模［103］等領(lǐng)域得到應(yīng)用.文獻(xiàn)［104］提出一種膜計算優(yōu)化調(diào)度算法，將膜計算啟發(fā)的優(yōu)化算法用于汽油混合調(diào)度.P系統(tǒng)還可以用于解釋活細(xì)胞中的自然過程，理論上可以硬件實現(xiàn).其他類型的應(yīng)用包括計算機(jī)圖形學(xué)、密碼學(xué)、優(yōu)化等領(lǐng)域［105］.

2 化學(xué)反應(yīng)計算

人工化學(xué)是人工生命的一個子領(lǐng)域，研究生命的基本機(jī)制以及組織的起源和進(jìn)化.主要有3個方向:

1)建模，包括生物系統(tǒng)、進(jìn)化系統(tǒng)、社會系統(tǒng)等領(lǐng)域;

2)信息處理，自然界的許多化學(xué)過程可以解釋為執(zhí)行計算的過程，如控制細(xì)菌運(yùn)動的化學(xué)反應(yīng)網(wǎng)絡(luò)、神經(jīng)信息處理、基因調(diào)節(jié)、DNA轉(zhuǎn)譯與轉(zhuǎn)換、變異、重組、免疫系統(tǒng)等，化學(xué)系統(tǒng)的組合性質(zhì)可以通過實際的化學(xué)計算，即利用實際的分子進(jìn)行計算，如DNA計算.人工化學(xué)計算是化學(xué)引喻作為設(shè)計新硬件和軟件結(jié)構(gòu)的范例.化學(xué)系統(tǒng)可做為信息處理器.

3)領(lǐng)域是優(yōu)化，利用人工化學(xué)范例發(fā)現(xiàn)組合問題的解.與進(jìn)化計算密切聯(lián)系，進(jìn)化算法可看作是特殊的人工化學(xué)系統(tǒng).形式上，人工化學(xué)可定義為一個三元組(M，R，A)，其中M是人工分子集合，R是描述分子之間相互作用的規(guī)則集合，A是驅(qū)動系統(tǒng)的算法.M中的分子可以是抽象的符號、字符串、二進(jìn)制位符串等.文獻(xiàn)［33］提出了基于人工化學(xué)系統(tǒng)的旅行商問題求解算法.文獻(xiàn)［106］提出了首個化學(xué)反應(yīng)啟發(fā)的優(yōu)化算法(chemical reaction optimization)，仿真結(jié)果證明該類算法與現(xiàn)有的優(yōu)化算法相比有很強(qiáng)的競爭力，成為一種新的優(yōu)化算法.

表1 自然計算原型與人工模型對照［107］Table 1 Comparison of natural computing and original type

3 結(jié)論與展望

本文對目前自然計算的幾種典型范例和未來具有發(fā)展?jié)摿Φ难芯口厔葸M(jìn)行綜述與分析，包括群體智能、分子計算、細(xì)胞計算和化學(xué)計算，涉及分子、細(xì)胞和生物社會群體等生物乃至化學(xué)領(lǐng)域，當(dāng)然，物理啟發(fā)的計算也是自然計算的一個重要內(nèi)容，限于篇幅，沒有過多展開敘述.如果從更廣義的角度把人類社會與人類思維看作是自然界的一部分，從表1可以看出，目前自然計算的啟發(fā)原型多種多樣，從無機(jī)物到有機(jī)物，從自然界到人類社會，從人腦到細(xì)胞和分子，在范圍、尺度、內(nèi)容、形式上都有很大差別，在各種啟發(fā)原型上發(fā)展的具體技術(shù)則多數(shù)表現(xiàn)為現(xiàn)代計算機(jī)中的算法、邏輯語言等.應(yīng)用領(lǐng)域則存在交叉，比如都可用于智能信息處理、優(yōu)化等領(lǐng)域，許多技術(shù)本身就屬于人工智能的分支.按照表1中的模式，未來出現(xiàn)其他新型的自然計算模型是肯定的.由于這些原因，目前還沒有關(guān)于自然計算的統(tǒng)一理論、方法、原理、技術(shù).

未來自然計算主要從理論、應(yīng)用和學(xué)科交叉幾個方面展開研究工作，在注重理論研究的同時，更應(yīng)該將研究的重點(diǎn)放在應(yīng)用產(chǎn)品研發(fā)和與其他學(xué)科交叉融合上.

1)要加強(qiáng)自然計算工程技術(shù)可行性研究.只有加強(qiáng)自然計算工程技術(shù)開發(fā)方法研究，建立自然計算工程技術(shù)可行性論證理論，才能盡可能降低開發(fā)風(fēng)險.到目前為止，大多數(shù)自然計算技術(shù)開發(fā)的投入和產(chǎn)出都不成正比，更談不上成為高新技術(shù)的支柱型產(chǎn)業(yè).在不斷研究新的算法同時，研究人員也應(yīng)妥善認(rèn)真考慮這個問題.

2)以硅為基礎(chǔ)的計算機(jī)對人類的工作、娛樂、交流產(chǎn)生了巨大影響，對社會經(jīng)濟(jì)、文化的影響也是有目共睹.但是今天的計算機(jī)有其物理空間上的局限性.因此，研究替代現(xiàn)有計算機(jī)系統(tǒng)的自然計算系統(tǒng)意義重大.

3)自然計算是一個龐大的研究領(lǐng)域，有許多具體的研究方向和子領(lǐng)域，需要來自數(shù)學(xué)、物理、化學(xué)、生物等基礎(chǔ)學(xué)科以及基因、電子、信息、納米領(lǐng)域?qū)＜业耐献?，更好地促進(jìn)自然計算的發(fā)展.面對千差萬別的啟發(fā)原型，建立自然計算的統(tǒng)一模型和理論，目前看還不現(xiàn)實，但在具體的自然計算分支中尋求基本的理論、算法模型應(yīng)該是可行的.

當(dāng)前科學(xué)發(fā)展的一個重要特征是，不同學(xué)科的技術(shù)和概念之間不斷地雙向流動甚至多重交叉流動，這樣一個趨勢意味著新的計算方法的突破不再是盲目的，而是有方向性的、必然的.因此綜合利用、控制論、信息論、協(xié)同論、耗散論、復(fù)雜系統(tǒng)等現(xiàn)代理論以及其他新理論研究自然計算理論是必要的.21世紀(jì)的新科學(xué)哲學(xué)觀念表明，在系統(tǒng)層次上，不同學(xué)科之間的邊界必須被超越，甚至被推翻.實際上，系統(tǒng)生物學(xué)的發(fā)展正不斷推動生物學(xué)、工程和計算機(jī)科學(xué)的進(jìn)步.這個過程中的某個步驟可能促使我們重新審視自然啟發(fā)的計算或自然計算，可能自下而上重新發(fā)明新的計算方法，每個學(xué)科都可能做出自己的貢獻(xiàn)，為人類解決能源、信息、材料、人工智能等重大領(lǐng)域的問題提供更有效的手段.

［1］GONG Maoguo，JIAO Licheng，DU Haifeng，et al.Multiobjective immune algorithm with nondominated neighborbased selection［J］.Evo Comput，2008，16(2):225－255.

［2］CHEN Tianhi，TANG Ke，CHEN Guoliang，et al.Analysis of computational time of simple estimation of distribution algorithms［J］.IEEE Trans on Evolutionary Computation，2010，14(1):1－22.

［3］WANG Y.Differential evolution with composite trial vector generation strategies and control parameters［J］.IEEE Trans on Evolutionary Computation，2011，15(1):55－67.

［4］CHEN Weineng，ZHANG Jun，CHUNG H S H，et al.A novel set－based particle swarm optimization method for discrete optimization problems［J］.IEEE Transactions on Evolutionary Computation，2010，14(2):278－300.

［5］崔遜學(xué).多目標(biāo)進(jìn)化算法及其應(yīng)用［M］.北京:國防工業(yè)出版社，2006:1－10.

［6］鄭金華.多目標(biāo)進(jìn)化算法及其應(yīng)用［M］.北京:科學(xué)出版社，2007:1－10.

［7］中國科學(xué)技術(shù)協(xié)會.智能科學(xué)與技術(shù)學(xué)科發(fā)展報告［R］.北京:中國科學(xué)技術(shù)出版社，2010.

［8］馬義德，李廉，王亞馥，等.脈沖耦合神經(jīng)網(wǎng)絡(luò)原理及其應(yīng)用［M］.北京:科學(xué)出版社，2006:1－25.

［9］ZHOU Z H，WU J X，JIANG Y，et al.Genetic algorithm based selective neural network ensemble［C］//Proc of the 17th International Joint Conference on Artificial Intelligence(IJCAI＇01).Seattle，USA，2001，2:797－802.

［10］史忠植.神經(jīng)網(wǎng)絡(luò)［M］.北京:高等教育出版社，2009:1－205.

［11］LIU Y M，CHEN G Q，YING M S.Fuzzy logic，soft computing and computational intelligence［M］.Berlin:Springer－Verlag，2005:1－10.

［12］DORIGO M，MANIEZZO V，COLORNI A.The ant system:optimization by a colony of cooperating agents［J］.IEEE Trans Sys，Man，and Cybernetics，1996，26(1):1－13.

［13］KENNEDY J，EBERHART R.Particle swarm optimization［C］//IEEE Int Conf on Neural Networks.Piscataway，USA，1995:1942－1948.

［14］王磊，潘進(jìn)，焦李成.基于免疫策略的進(jìn)化算法［J］.自然科學(xué)進(jìn)展，2000，10(5):451－455.

WANG Lei，PAN Jin，JIAO Licheng.Evolutionary algorithm based on immune strategy［J］.Progress of Nature Science，2000，10(5):451－455.

［15］HUANG S J.An immune－based optimization method to capacitor placement in a radial distribution system［J］.IEEE Trans on Power Delivery，2000(15):744－749.

［16］DURHAM W.Co－evolution:genes，culture，and human diversity［M］.Palo Alto，USA:Stanford University Press，1994:35－45.

［17］ADLEMAN L M.Molecular computation of solutions to combinatorial problems［J］.Science，1994，226(11):1021－1024.

［18］PAUN A，PAUN G.The power of communication:p systems with symport/antiport［J］.New Generation Computing，2002，20(3):295－305.

［19］PAUN G.Membrane computing:an introduction［M］.Berlin:Springer－Verlag，2002:1－10.

［20］ONG Y S，LIM M H，CHEN X S.Memetic computation:past，present ＆ future［J］.IEEE Computational Intelligence Magazine，2010(5):24－32.

［21］SHI Y，EBERHART R.Evolutionary computation proceedings［C］//IEEE World Congress on Compu Intel.New York，USA，1998:69－73.

［22］莫宏偉，左興權(quán)，畢曉君.人工免疫系統(tǒng)研究進(jìn)展［J］.智能系統(tǒng)學(xué)報，2009，4(1):23－29.

MO Hongwei，ZUO Xingquan，BI Xiaojun.Research on development of artificial immune systems［J］.CAAI Transations on Intelligent Systems，2009，4(1):23－29.

［23］李曉磊，邵之江，錢積新.一種基于動物自治體的尋優(yōu)模式魚群算法［J］.系統(tǒng)工程理論與實踐，2002，22(11):32－38.

LI Xiaolei，SHAO Zhijiang，QIAN Jixin.A fish school optimization algorithm based on animal autonomous［J］.Theory and Practice of System Engineering，2002，22(11):32－38.

［24］BASTOS F，CARMELO J A，LIMA N，De FERNANDO B.A novel search algorithm based on fish school behavior［C］//2008 IEEE Int Conf on Systems，Man，and Cybernetics(SMC 2008).Singapore，2002，22(11):32－38.

［25］MüELLER S，MARCHETTO J，AIRAGHI S，KOUMOUTSAKOS P.Optimization based on bacterial chemotaxis［J］.IEEE Trans on Evolutionary Computation，2002，6(1):16－29.

［26］TERESHKO V.Reaction－diffusion model of a honeybee colony’s foraging behaviour［J］.Parallel Problem Solving from Nature，2000，Computer Science，2000，1917:807－816.

［27］SIMON D.Biogeography－based optimization［J］.IEEE Transactions on Evolutionary Computation，2008，12(6):702－713.

［28］DAI Chaohua，ZHU Yufeng，CHEN W R.Seeker optimization algorithm:a novel stochastic search algorithm for global numerical optimization［J］.Journal of Systems Engineering and Electronics，2011，21(2):300－311.

［29］YANG Yan，ZHOU Yongquan，GONG Qiaoqiao.Hybrid artificial glowworm swarm optimization algorithm for solving system of nonlinear equations［J］.Journal of Computational Information Systems，2010，6(10):3431－3438.

［30］MEHRABIAN A R，LUCAS C.A novel numerical optimization algorithm inspired from weed colonization［J］.Ecological Informatics，2006(1):355－366.

［31］YANG Shuyuan，WANG Min，JIAO Licheng.Quantum particle swarm optimization［C］//Proc of IEEE Congress on Evolution Computation.Washington，DC，USA，2004:320－324.

［32］YUCHI M，KIM J H.Ecology－inspired evolutionary algorithm using feasibility－based grouping for constrained optimization［C］//Proc of the IEEE Congress on Evolutionary Computation.Edinburgh，UK，2005:1455－1461.

［33］JADERICK P P，MICHAEL J M，MENDOZA M，et al.Solving symmetric and asymmetric TSPs by artificial chemistry［C］//Philippine Computing Science Congress.Philippine，2004:1－7.

［34］PATON R.Computing with biological metaphors［M］.London:Chapman ＆ Hall，2001:1－5.

［35］KIRKPATRICK S，GELATT C D，VECCHI M P.Optimization by simulated annealing［J］.Science，1983，220(4598):671－680.

［36］SHOR P W.Algorithm for quantum computation:discrete logarithms and factoring［C］//Proc of 35th Annual Symposium on Foundations of Computer Science.New Mexico，USA:IEEE Computer Society Press，1994:124－134.

［37］TAYARANI M H N，AKBARZADEH M R T.Magnetic optimization algorithms a new synthesis［C］//IEEE Congress on Evolutionary Computation.Hong Kong，China，2008:2659－2665.

［38］De CASTRO L N.Fundamentals of natural computing［M］.Champman＆ Hall/CRC.Florida，USA，2006:3－20.

［39］BONABEAU E，DORIGO M，THERAULAZ G.Swarm intelligence:from natural to artificial systems［M］.New York，USA:Oxford University Press，1999:2－15.

［40］MüELLER S，MARCHETTO J，AIRAGHI S，KOUMOUTSAKOS P.Optimization based on bacterial chemotaxis［J］.IEEE Trans on Evolutionary Computation，2002，6(1):16－29.

［41］PASSINO K M.Biomimicry of bacterial foraging for distributed optimization and control［J］.IEEE Control Syst Mag，2002，22(3):52－67.

［42］TANG W J，WU Q H，SAUNDERS J R.A novel model for bacteria foraging in varying environments［C］//Proc ICCSA.Berlin，Springer－Verlag，2006:556－565.

［43］ACHARYA D P，PANDA G，MISHRA S，et al.Bacteria foraging based independent component analysis［C］//Proc Int Conf Comput Intell Multimedia Applicat.Piscataway，USA:IEEE Press，2007:527－531.

［44］DASGUPTA S，ABRAHAM D A.Adaptive computational chemotaxis in bacterial foraging optimization:an analysis［J］.IEEE Tran on Evo Comput，2009，13(4):919－942.

［45］KIM D H，ABRAHAM A，CHO J H.A hybrid genetic algorithm and bacterial foraging approach for global optimization［J］.Inform Sci，2007，177(18):3918－3937.

［46］MISHRA S.A hybrid least square－fuzzy bacterial foraging strategy for harmonic estimation［J］.IEEE Trans Evol Comput，2005，9(1):61－73.

［47］BISWAS A，DASGUPTA S，DAS S，ABRAHAM A.Synergy of PSO and bacterial foraging optimization:a comparative study on numerical benchmarks［C］//Proc 2nd Int Symp Hybrid Artificial Intell Syst(HAIS)Advances Soft Computing Ser. ［S.l.］，Springer－Verlag，ASC，2007:255－263.

［48］PASSINO K M.Biomimiery of bacterial foraging for distributed optimization and control［J］.IEEE Control System Magazine，2002(6):52－67.

［49］MAJHI R，PANDA G，SAHOO G.Efficient prediction of stock market indices using adaptive bacterial foraging optimization(ABFO)and BFO based techniques［J］.Expert Systems with Applications，2009，36(6):10097－10104.

［50］LI M S，TANG W J，TANG W H，et al.Bacteria foraging algorithm with varying population for optimal power fow［C］//Proc Applications of Evolutionary Computing 2007.Berlin，Springer－Verlag，2007:32－41.

［51］MO Hongwei，YIN Yujing.Image segmentation based on bacterial foraging and FCM algorithm［J］.International Journal of Swarm Intelligence Research，2011，2(3):16－29.

［52］李威武，王慧，鄒志君，等.基于細(xì)菌群體趨藥性的函數(shù)優(yōu)化方法［J］.電路與系統(tǒng)學(xué)報，2005，10(1):58－63.

LI Weiwu，WANG Hui，ZOU Zhijun，et al.Function optimization based on bacterial chemotaxis［J］.Journal of E－lectrical Circuit and System，2005，10(1):58－63.

［53］呂慧顯.基于微細(xì)菌群體趨藥性的函數(shù)優(yōu)化算法［J］.青島大學(xué)學(xué)報:工程技術(shù)版，2009，24(1):19－26.

Lü Huixian.Function optimization based on micro bacterial chemotaxis［J］.Journal of Qingdao University:Engineering，2009，24(1):19－26.

［54］曹黎俠，張建科.細(xì)菌趨藥性算法理論及應(yīng)用研究進(jìn)展［J］. 計算機(jī)工程與應(yīng)用，2006，42(1):44－46.

CAO Lixia，ZHANG Jianke.Research development of theory and application of bacterial chemotaxis algorithm［J］.Computer Engineering and Application，2006，42(1):44－46.

［55］張煜東，吳樂南.多態(tài)細(xì)菌趨藥性優(yōu)化［J］.計算機(jī)工程與應(yīng)用，2009，45(18):6－11.

ZHANG Yudong，WU Lenan.Multimodal bacterial chemotaxis optimization［J］.Computer Engineering and Application，2009，45(18):6－11.

［56］TERESHKO V.Reaction－diffusion model of a honeybee colony＇s foraging behaviour［M］.Berlin:Springer－Verlag，2000:807－816.

［57］TERESHKO V，LEE T.How information mapping patterns determine foraging behaviour of a honeybee colony［J］.Open Systems and Information Dynamics，2002(9):181－193.

［58］TERESHKO V，LOENGAROV A.Collective decisionmaking in honeybee foraging dynamics［J］.Computing and Information systems Journal，2005，9(3):1－7.

［59］TEODOROVIC D.Transport modeling by multi－agent systems:a swarm intelligence approach［J］.Transportation Planning and Technology，2003，26(4):289－312.

［60］LUCIC P，TEODOROVIC D.Transportation modeling:an artificial life approach［C］//ICTAI，Washington，DC，USA，2002:216－223.

［61］PHAM D T，GHANBARZADEH A，KOC E，et al.The bees algorithm—a novel tool for complex optimisation problems［C］//Proceedings of the 2nd Virtual International Conference on Intelligent Production Machines and Systems(IPROMS 2006).Cardiff，UK:Elsevier，2006:454－459.

［62］DRIAS H，SADEG S，YAHI S.Cooperative bees swarm for solving the maximum weighted satisfiability problem，computational intelligence and bioinspired systems［C］//8th International Workshop on Artificial Neural Networks(IWANN 2005).Vilanova，Barcelona，Spain，2005:8－10.

［63］BENATCHBA K，ADMANE L，KOUDIL M.Using bees to solve a data－mining problem expressed as a max－sat one［C］//First International Work－Conference on the Interplay Between Natural and Artificial Computation(IWINAC 2005).Palmas，Canary Islands，Spain，2005:15－18.

［64］WEDDE H F，F(xiàn)AROOQ M，ZHANG Y.Beehive:an efficient fault－tolerant routing algorithm inspired by honeybee behavior，ant colony，optimization and swarm intelligence［C］//4th International Workshop ANTS 2004.Brussels，Belgium，2004:5－8.

［65］YANG X S.Engineering optimizations via nature－inspired virtual bee algorithms［C］//Artificial Intelligence and Knowledge Engineering Applications:A Bioinspired Approach，Lecture Notes in Computer Science.Berlin/Heidelberg:Springer－Verlag.2005，3562:317－323.

［66］PHAM D T，GHANBARZADEH A，KOC E，et al.The bees algorithm［R］.［S.l.］，Manufacturing Engineering Centre，Cardiff University，2005.

［67］KARABOGA D.An idea based on honeybee swarm for numerical optimization TR06［R］. ［S.l.］，Computer Engineering Department，Engineering Faculty，Erciyes University，2005.

［68］BASTURK B，KARABOGA D.An artificial bee colony(ABC)algorithm for numeric function optimization［C］//IEEE Swarm Intelligence Symposium 2006.Indianapolis，USA，2006:45－50.

［69］KARABOGA D，BASTURK B A.A powerful and efficient algorithm for numerical function optimization:artificial bee colony(ABC)algorithm［J］.Journal of Global Optimization，2007，39(3):459－471.

［70］KARABOGA D，BASTURK B.On the performance of artificial bee colony(abc)algorithm［J］.Applied Soft Computing，2008，8(1):687－697.

［71］KARABOGA D，BASTURK B.Artificial bee colony(ABC)optimization algorithm for solving constrained optimization problems［M］.Berlin:Springer－Verlag，2007:789－798.

［72］KARABOGA D，AKAY B B，OZTURK C.Artificial bee colony(ABC)optimization algorithm for training feed－forward neural networks［C］//Modeling Decisions for Artificial Intelligence.Berlin:Springer－Verlag，2007:318－329.

［73］KARABOGA D，AKAY B B.An artificial bee colony(ABC)algorithm on training artificial neural networks［C］//15th IEEE Signal Processing and Communications Applications.Eskisehir，Turkey，2007:1－4.

［74］KARABOGA N.A new design method based on artificial bee colony algorithm for digital IIR filters［J］.Journal of The Franklin Institute，2009，346(4):328－348.

［75］ALOK S.An artificial bee colony algorithm for the leafconstrained minimum spanning tree problem［J］.Applied Soft Computing，2009，9(2):625－631.

［76］DERVIS K，BAHRIYE A.A comparative study of artificial bee colony algorithm［J］.Applied Mathematics and Computation，2009(214):108－132.

［77］ERGEZER M，SIMON D，DU Dawei.Oppositional biogeography－based optimization［J］.Journal of Systems，Man，and Cybernetics，2009，39(5):1035－1040.

［78］MA Haiping.An analysis of the behavior of migration models for biogeography－based optimization［J］.Information Sciences，2010，180(18):3444－3464.

［79］GONG Wenyin，CAI Zhihua，LING Charlexin，et al.A real－coded biogeography－based optimization with neighborhood search operator［J］.Applied Mathematics and Computation，2010，216(9):2749－2758.

［80］DU D W，SIMON D，ERGEZER M.Biogeography－based optimization combined with evolutionary strategy and immigration refusal［C］//Proc of the IEEE Conference on Systems，Man，and Cybernetics.SanAntonio，Texas，2005:1023－1028.

［81］GONG Wenyin，CAI Zhihua，LING Ccharlexin.DE/BBO:a hybrid differential evolution with biogeographybased optimization for global numerical optimization［J］.Soft Computing，2011，5(4):645－665.

［82］MA H，NI S，SUN M.Equilibrium species counts and migration model tradeoffs for biogeography－based optimization［C］//Proc of the IEEE Conference on Decision and Control.Shanghai，China，2009:3306－3310.

［83］SIMON D.A probabilistic analysis of a simplified biogeography－based optimization algorithm［EB/OL］.［2009－02－11］.http://academic.csuohio.edu/simond/bbo/simplified.

［84］SIMON D，ERGEZER M，DU D.Population distributions in biogeography－based optimization algorithms with elitism［C］//Proc of the IEEE Conference on Systems，Man，and Cybernetics.San Antonio，USA，2009:1017－1022.

［85］SINGH U，KUMAR H，KAMAL T S.Linear array synthesis using biogeography based optimization［J］.Progress in Electromagnetics Research，2010，11:25－37.

［86］TAN Lixiang，GUO Li.Quantum and biogeography based optimization for a class of combinatorial optimization［C］//GEC＇09.［S.l.］，2009:969－972.

［87］NAVDEEP K，JOHAL S，KUNDRA S H.A hybrid FPAB/BBO algorithm for satellite image classification［J］.International Journal of Computer Applications，2010，6(5):31－36.

［88］ANIRUDDHA B，CHATTOPADHYAY P K.Solving complex economic load dispatch problems using biogeographybased optimization［J］.Expert Systems with Applications，2010，37(5):3605－3615.

［89］MO Hongwei，XU Lifang.Biogeography migration algorithm for traveling salesman problem［J］.International Journal of Intelligent Computing and Cybernetics，2011，4(3):311－330.

［90］PAN Yongxin，LIN Wei，LI Jinhua，et al.Reduced efficiency of magnetotaxis in magnetotactic coccoid bacteria in higher than geomagnetic fields［J］.Biophysical Journal，2009，97:986－991.

［91］PAUN G，ROZENBERG G，SALOMAA A.DNA computing:new computing paradigms［M］.Berlin:Springer－Verlag，1998:1－12.

［92］FRANCOA G，MARGENSTERN M.A DNA computing inspired computational model［J］.Theoretical Computer Science，2008(404):88－96.

［93］RAMAKRISHNAN N，BHALLA U S，TYSON J J.Computing with proteins［J］.Computer，2009，42(1):47－56.

［94］TRINCA?D，RAJASEKARAN S.Coping with diffraction effects in protein－based computing through a specialized approximation algorithm with constant overhead［C］//2010 10th IEEE Conference on Nanotechnology(IEEE－NANO).Seoul，Korea，2010:802－805.

［95］PANCHENKOA，PRZYTYCKA T.Protein－protein interactions＆ networks［M］.Computing Methods for Identification，Analysis ＆ Prediction.Berlin:Springer，2010:6－10.

［96］EICHELBERGER C N，NAJARIAN K.Simulating protein computing:character recognition via probabilistic transition trees［C］//IEEE International Conference on Granular Computing.［S.l.］，2006:101－105.

［97］HENKEL V C，RENO S B，CRINA I A，et al.Protein output for DNA computing［J］.Natural Computing，2005，4(1):1－10.

［98］ANDY A.Molecular computing:aromatic arithmetic［J］.Nature Physics，2010，6:325－326.

［99］HAMEL J S.A thermodynamic turing machine:artificial molecular computing using classical reversible logic Switching networks［EB/OL］.［2010－11－25］.http://arxiv.org/abs/0904.3273.3273v2，2009.

［100］PAUN G，ROZENBERG G，SALOMAA A.DNA computing－new computing paradigms［M］.Berlin:Springer－Verlag，1998:3－9.

［101］GARCA－QUISMONDO M，GUTIERREZ－ESCUDERO R，PEREZ－HURTA－DO I，et al.An overview of P－Lingua 2.0［J］.Lecture Notes in Computer Science，2010(5957):264－288.

［102］CHRISTINAL H A，DIAZ－PERNIL D，REAL P.Segmentation in 2－D and 3－D image using tissue－like P system［J］.Lecture Notes in Computer Science，2009(5856):169－176.

［103］ESCUELA G，HINZE T，DITTRICH P，et al.Modelling modified atmosphere packaging for fruits and vegetables using membrane systems［C］//Proc of the Third International Conference on Bio－inspired Systems and Signal Processing.Valencia，Spain:INSTICC Press，2010:306－311.

［104］ZHAO J ，WANG N.A bio－inspired algorithm based on membrane computing and its application to gasoline blending scheduling［J］.Computers and Chemical Engineering，2011，35(2):272－283.

［105］PAUN G.A quick introduction to membrane computing［J］.The Journal of Logic and Algebraic Programming，2010(79):291－294.

［106］LAM A Y S，LI V O K.Chemical－reaction－inspired metaheuristic for optimization［J］.IEEE Trans on Evolutionary Computation，2010，14(3):381－400.

莫宏偉，男，1973年生，教授，博士生導(dǎo)師，主要研究方向為自然計算與人工免疫系統(tǒng)、人工智能與智能系統(tǒng)、機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘.

Research advance on natural computing

MO Hongwei
(College of Automation，Harbin Engineering University，Harbin 150001，China)

Natural computing is one of the important research areas in the field of computer science and artificial intelligence.It is a new research field which involves many disciplines following development spanning several decades.The aim of natural computing is to seek for the solution to difficult problems faced by humans from nature.Natural computing focused on evolution computing，artificial neural networks，and fuzzy systems in its early days.Over the last two decades，several new natural computing methods，such as swarm intelligence，artificial immune systems，and DNA computing have been proposed.In this paper，it presents research situations，development tendencies，and other matters surrounding new methods such as swarm intelligence were analyzed.Areas of future emphasis and direction in development were also pointed out.

natural computing;biology－inspired computing;swarm intelligence;molecular computing

TP3.05

A

1673－4785(2011)06－0544－12

10.3969/j.issn.1673－4785.2011.06.011

2011－04－01.

國家自然科學(xué)基金資助項目(61075113);黑龍江省青年學(xué)術(shù)骨干項目資助項目(1155G18);中央高?；究蒲袠I(yè)務(wù)自由探索基金資助項目(HEUCF110441).

莫宏偉.E－mail:honwei2004@126.com.