莫宏偉

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

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

莫宏偉

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

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

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

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

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

在上述3種經(jīng)典自然啟發(fā)的計(jì)算算法基礎(chǔ)上，從20世紀(jì)90年代起，基本每10年左右就會(huì)涌現(xiàn)一批新的自然計(jì)算方法，20世紀(jì)90年代初代表性的有蟻群算法(ant colony optimization，ACO)［12］、粒子群算法(particle swarm optimization，PSO)［13］、免疫算法［14－15］、文化算法［16］、DNA 計(jì)算［17］、細(xì)胞膜計(jì)算［18－19］、Memetic 算法［20］，前 2 種算法又形成一個(gè)新的自然計(jì)算分支——群體智能，其中粒子群算法影響最大［21］.2000年以后的10年，人工免疫系統(tǒng)發(fā)展迅速［22］，這一時(shí)期，人工魚群算法(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é)計(jì)算［33］等新方法不斷涌現(xiàn)，使自然計(jì)算家族不斷壯大.

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

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

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

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

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

1.1 群體智能

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

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

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

研究趨藥性算法的先驅(qū)是Brenermann及其同事［13］.基本BCA依賴于單個(gè)細(xì)菌的運(yùn)動(dòng)行為，它不斷地感受它周圍的環(huán)境變化并且只利用它過去的經(jīng)驗(yàn)來尋找最優(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個(gè)菌群，一個(gè)菌群是尋優(yōu)菌群，另一個(gè)菌群是庫存菌群.M－BCC算法在尋優(yōu)能力方面要優(yōu)于BCC算法.文獻(xiàn)［54－55］分別對該種算法進(jìn)行了簡單綜述和改進(jìn)研究.

1.1.2 蜂群算法

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

上述都是組合優(yōu)化問題.有3個(gè)連續(xù)優(yōu)化算法，基于蜂群算法的智能性［65－67］.Yang［65］開發(fā)了虛擬蜜蜂算法(VBA)優(yōu)化二維數(shù)值函數(shù)，算法產(chǎn)生一群虛擬蜜蜂，通過這些蜜蜂的相互作用強(qiáng)度獲得問題的解.Pham等［66］提出應(yīng)用幾個(gè)控制參數(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è)計(jì) IIR 濾波器［74］和葉約束最小生成樹問題［75］.文獻(xiàn)［76］將ABC算法與遺傳算法和其他群智能算法在50個(gè)不同類型函數(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］.它主要通過物種的遷移算子來實(shí)現(xiàn)信息資源共享，BBO是在生物地理學(xué)的數(shù)學(xué)模型基礎(chǔ)上實(shí)現(xiàn)的一種全局性優(yōu)化方法.

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

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

自然計(jì)算的啟發(fā)源于微小的細(xì)菌、活躍的蜜蜂，發(fā)展到大規(guī)模動(dòng)物遷移，并已經(jīng)開發(fā)出相應(yīng)的有效算法.上述多種群體智能算法在理論和應(yīng)用方面發(fā)展程度不一，但都遠(yuǎn)未達(dá)到成熟階段.所有群體智能算法的一個(gè)共同特征是候選解以群體形式向著搜索空間中更好的解區(qū)域移動(dòng)，共同挑戰(zhàn)是如何結(jié)合生物群智能以加速向最優(yōu)解收斂，避免局部最優(yōu)解，這也是所有自然計(jì)算優(yōu)化求解的共性問題.群體智能發(fā)展主要有以下幾個(gè)方面的問題值得關(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)并行性，與最新計(jì)算軟硬件技術(shù)尤其是嵌入式系統(tǒng)相結(jié)合，服務(wù)于實(shí)際應(yīng)用.

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

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

1.2 分子計(jì)算

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

1.2.1 DNA計(jì)算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2.4 分子計(jì)算的問題

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

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

1.3 細(xì)胞膜計(jì)算

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)論與展望

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

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

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

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

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

當(dāng)前科學(xué)發(fā)展的一個(gè)重要特征是，不同學(xué)科的技術(shù)和概念之間不斷地雙向流動(dòng)甚至多重交叉流動(dòng)，這樣一個(gè)趨勢意味著新的計(jì)算方法的突破不再是盲目的，而是有方向性的、必然的.因此綜合利用、控制論、信息論、協(xié)同論、耗散論、復(fù)雜系統(tǒng)等現(xiàn)代理論以及其他新理論研究自然計(jì)算理論是必要的.21世紀(jì)的新科學(xué)哲學(xué)觀念表明，在系統(tǒng)層次上，不同學(xué)科之間的邊界必須被超越，甚至被推翻.實(shí)際上，系統(tǒng)生物學(xué)的發(fā)展正不斷推動(dòng)生物學(xué)、工程和計(jì)算機(jī)科學(xué)的進(jìn)步.這個(gè)過程中的某個(gè)步驟可能促使我們重新審視自然啟發(fā)的計(jì)算或自然計(jì)算，可能自下而上重新發(fā)明新的計(jì)算方法，每個(gè)學(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é)會(huì).智能科學(xué)與技術(shù)學(xué)科發(fā)展報(bào)告［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é)報(bào)，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］李曉磊，邵之江，錢積新.一種基于動(dòng)物自治體的尋優(yōu)模式魚群算法［J］.系統(tǒng)工程理論與實(shí)踐，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é)報(bào)，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é)報(bào):工程技術(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ì)算機(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ì)算機(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)師，主要研究方向?yàn)樽匀挥?jì)算與人工免疫系統(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é)基金資助項(xiàng)目(61075113);黑龍江省青年學(xué)術(shù)骨干項(xiàng)目資助項(xiàng)目(1155G18);中央高校基本科研業(yè)務(wù)自由探索基金資助項(xiàng)目(HEUCF110441).

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