群體編程技術(shù)發(fā)展研究

趙冰陽(yáng)

0 引言

群體智能這個(gè)概念來(lái)自對(duì)自然界中昆蟲群體的觀察，群體通過(guò)協(xié)作表現(xiàn)出的宏觀智能行為特征被稱為群體智能（swarm intelligence）。在計(jì)算機(jī)領(lǐng)域中，把一群具有計(jì)算和通信能力，在復(fù)雜物理環(huán)境中，完成特定任務(wù)的設(shè)備集合為群體（swarm）。對(duì)設(shè)備群體的行為預(yù)測(cè)和控制稱為群體智能。群體智能的概念自1989年提出以來(lái)，各方面都出現(xiàn)了進(jìn)展。

在算法方面， Dorigo在2004 年提出了由對(duì)受蟻群行為啟 ACO（Ant colony optimization）算法， Karaboga 在 2005年提出了受蜂群行為啟發(fā)的 ABC（Artificial bee colony algorithm）算法。PSO（particle swam optimization）算法由Eberhart博士和Kennedy博士基于鳥群覓食行為而提出，該算法概念簡(jiǎn)明、實(shí)現(xiàn)方便、收斂速度快、參數(shù)設(shè)置少，是 一種高效的搜索算法，近年來(lái)受到學(xué)術(shù)界的廣泛重視。

在硬件平臺(tái)方面，MEMS技術(shù)發(fā)展迅速。伯克利在99年就已經(jīng)制造出毫米級(jí)別的機(jī)器人，這種機(jī)器人自我供電，擁有計(jì)算和通信能力，非常適合作為群體中的節(jié)點(diǎn)設(shè)備。

在編程方面，面對(duì)群體計(jì)算中的種種問(wèn)題，人們的解決方式與1950解決傳統(tǒng)編程中問(wèn)題的方法相似。針對(duì)某種特定設(shè)備和特定環(huán)境，研究者都需要費(fèi)力的去開發(fā)相關(guān)的程序，并且花大量的時(shí)間和經(jīng)歷反復(fù)測(cè)試以保證其性能。然而設(shè)備和需求一旦改變，就需要花大量經(jīng)歷重新進(jìn)行開發(fā)和測(cè)試。這樣的開發(fā)方式越來(lái)越無(wú)法跟上設(shè)備更新的速度。隨著設(shè)備的價(jià)格越來(lái)越低而性能愈發(fā)強(qiáng)大，開發(fā)程序的開銷開始代替設(shè)備開銷，成了開發(fā)大規(guī)模群體程序的主要開銷。開發(fā)者需要一套規(guī)范化的語(yǔ)言，開發(fā)方法和開發(fā)工具來(lái)應(yīng)對(duì)群體程序開發(fā)的需求。群體編程語(yǔ)言需要能夠描述一個(gè)群體的整體行為整體行而不過(guò)多的去關(guān)注每一個(gè)設(shè)備區(qū)實(shí)現(xiàn)這個(gè)過(guò)程的細(xì)節(jié)。它還需要讓開發(fā)者在開發(fā)測(cè)試，以及使用的過(guò)程中能對(duì)非功能性屬性比如能源消耗進(jìn)行監(jiān)控和調(diào)配。同時(shí)，研究者希望這種開發(fā)工程具有強(qiáng)大的可移植性以應(yīng)對(duì)環(huán)境和設(shè)備的變化。

1 群體編程及語(yǔ)言的定義

群體的特性決定了群體編程語(yǔ)言與傳統(tǒng)編程語(yǔ)言相比擁有自己的特性：

(1)分布性

群體是由海量的設(shè)備組成的，這些設(shè)備各自擁有一定的計(jì)算，存儲(chǔ)和通信能力。群體程序的目的為了讓群體中的所有設(shè)備協(xié)作完成一個(gè)共同目標(biāo)。然而這些個(gè)體為了完成群體目標(biāo)所做的動(dòng)作又是不同的。如果以傳統(tǒng)方式逐個(gè)進(jìn)行編程，從時(shí)間花銷和工作量上看都是低效的。通過(guò)分布式計(jì)算的任務(wù)分發(fā)方式（例如map reduce）的思路可以改善這個(gè)問(wèn)題。但是個(gè)體間互動(dòng)的性質(zhì)無(wú)法通過(guò)簡(jiǎn)單的任務(wù)分配來(lái)反映。比如一個(gè)散布操作，要把很多個(gè)體散布在一個(gè)區(qū)域中并且保證每?jī)蓚€(gè)個(gè)體的距離都大于d。利用傳統(tǒng)式分布式編程很難在有效時(shí)間給出這個(gè)問(wèn)題的解。

(2)異步性

群體程序的執(zhí)行基本都是異步的，即每臺(tái)設(shè)備執(zhí)行哪個(gè)程序，執(zhí)行到哪一步，都是由設(shè)備本身和周圍環(huán)境決定的。群體程序執(zhí)行是保持同步十分困難。維護(hù)群體的同步性需要通過(guò)廣播的方式來(lái)調(diào)配各個(gè)設(shè)備的運(yùn)行狀態(tài)，信息的廣播由于產(chǎn)生的開銷非常大，在群體計(jì)算中式需要盡量避免的。

(3)環(huán)境敏感性

傳統(tǒng)程序分析中常常假設(shè)所有硬件正常工作，并且認(rèn)為環(huán)境因素具有可預(yù)測(cè)性。在群體編程中研究人員更多是面對(duì)客觀世界，氣候，生物和其他設(shè)備的動(dòng)作都會(huì)影響到程序的運(yùn)行。開發(fā)者試圖通過(guò)建模來(lái)模擬客觀事件的種種特性，以增強(qiáng)群體程序的魯棒性。但是考慮到客觀世界的不可預(yù)測(cè)性決定了研究者不可能預(yù)知所有意外情況。這要求群體程序具備一定的彈性（resiliancy），保證系統(tǒng)要在惡劣的環(huán)境影響中保證合理的健壯性，避免落入極端境地。

(4)能源敏感性

在傳統(tǒng)計(jì)算中時(shí)間和空間是兩大主要限制因素，編寫程序要在時(shí)間空間的占用上進(jìn)行權(quán)衡。然而在群體中，要考慮更多。比如在嵌入式移動(dòng)設(shè)備組成的群體中，設(shè)計(jì)者必須考慮能源因素。程序運(yùn)行的速度和結(jié)果精確度都必須跟能源消耗做出權(quán)衡。在群體程序語(yǔ)言設(shè)計(jì)中，必須對(duì)這些能源以及類似的非功能屬性進(jìn)行考量。

這樣一種分布式，異步性，環(huán)境敏感，能源敏感的程序設(shè)計(jì)方法就是群體編程。群體編程工具的設(shè)計(jì)目標(biāo)是：當(dāng)開發(fā)者想要讓某一個(gè)群體實(shí)現(xiàn)某個(gè)功能的時(shí)候，首先他利用群體編程語(yǔ)言將一些基本的群體操作進(jìn)行整合，設(shè)定相應(yīng)的參數(shù)；然后群體編程開發(fā)工具會(huì)把開發(fā)者編寫的高級(jí)群體程序分解為細(xì)節(jié)的動(dòng)作（這個(gè)過(guò)程類似于從高級(jí)語(yǔ)言到匯編語(yǔ)言），最后開發(fā)工具按要求分發(fā)這些任務(wù)給群體的各個(gè)成員節(jié)點(diǎn)，讓這些節(jié)點(diǎn)實(shí)現(xiàn)功能，完成任務(wù)。開發(fā)者不再需要對(duì)中間過(guò)程和每個(gè)節(jié)點(diǎn)上運(yùn)行的程序進(jìn)行考慮，大大提高程序編寫的效率。如圖1所示[1]：

圖1 群體編程的模型 （McEachrom 2002）

2 群體語(yǔ)言設(shè)計(jì)

為了開發(fā)一套群體編程的語(yǔ)言、方法和工具。必須先要解答任何語(yǔ)言設(shè)計(jì)中都要面對(duì)的幾大主要問(wèn)題。David Evans在2000年提出了群體編程的幾大核心問(wèn)題[2]：1如何規(guī)定群體程序的功能性指標(biāo)，2如何為環(huán)境和設(shè)備建模，3群體計(jì)算的元語(yǔ)是什么，4如何把群體編程中的元語(yǔ)操作結(jié)合組成一個(gè)完整的群體程序，5抽象級(jí)別問(wèn)題，6 如何實(shí)現(xiàn)和對(duì)群體程序進(jìn)行測(cè)試。這6個(gè)問(wèn)題其實(shí)可以歸結(jié)為兩個(gè)根本問(wèn)題：1元語(yǔ)操作與元語(yǔ)組合，2建模與評(píng)估。

2.1 元語(yǔ)操作與元語(yǔ)組合

元語(yǔ)是計(jì)算機(jī)程序設(shè)計(jì)中的基本單位，傳統(tǒng)計(jì)算理論的元語(yǔ)操作并不能直接映射到群體編程中去。即使是像過(guò)程調(diào)用和賦值這樣一些簡(jiǎn)單概念在群體編程中，都不能找到明顯的類比。群體編程環(huán)境中的元語(yǔ)與類庫(kù)需要抓住群體行為的特點(diǎn)與精髓并給出原則性的定義。在群體編程中的元語(yǔ)主要有：

散布：把設(shè)備在一塊區(qū)域中分散開來(lái)，要求最終狀態(tài)滿足沒有任意兩臺(tái)設(shè)備之間的距離小于某特定值d。

成簇：設(shè)備聚集成塊。最終狀態(tài)是幾乎所有設(shè)備都滿足條件在d范圍內(nèi)至少有n臺(tái)鄰居設(shè)備。

群移：群體的所有成員想同一個(gè)方向移動(dòng)而互不干擾，就像自然界中的遷徙行為，最終全部到達(dá)目的地。

掃描：用設(shè)備覆蓋一塊區(qū)域。目標(biāo)區(qū)域內(nèi)每一塊 r半徑的區(qū)域內(nèi)都至少有一臺(tái)設(shè)備出現(xiàn)過(guò)。

廣播：對(duì)群體內(nèi)的所有設(shè)備發(fā)送消息。

分播：對(duì)群體內(nèi)滿足條件的個(gè)體進(jìn)行消息發(fā)送。

通過(guò)元語(yǔ)的組合，就可以實(shí)現(xiàn)大量的功能。比如，一個(gè)搜救任務(wù)可以定義為由掃描和吸引操作的組合。

對(duì)以上每一種元語(yǔ)都有多種實(shí)現(xiàn)方式以權(quán)衡彈性（在惡劣環(huán)境和設(shè)備故障的影響下實(shí)現(xiàn)功能的好壞程度），效率（消耗資源的量），和速度（達(dá)到近似解的快慢程度）。

群體編程中的元語(yǔ)如何定義一直困擾著研究者。是否像傳統(tǒng)編程一樣，存在幾種有限的基本操作可以涵蓋所有的應(yīng)用？這個(gè)問(wèn)題還有待解決。但是就目前而言由于群體與生俱來(lái)的復(fù)雜性。即使給出很多基本的操作也不能確定能夠?qū)崿F(xiàn)所有的應(yīng)用目標(biāo)。

2.2 建模與評(píng)估

群體計(jì)算的環(huán)境敏感性決定了建模在群體編程中的重要程度。在為不同的環(huán)境建立模型和完善相應(yīng)的類庫(kù)的基礎(chǔ)上才能對(duì)對(duì)群體程序進(jìn)行測(cè)試，保證群體程序能夠正確實(shí)現(xiàn)功能。建立的模型如果不能準(zhǔn)確的反應(yīng)現(xiàn)實(shí)，群體程序的評(píng)估與測(cè)試就失去了參考價(jià)值。

建模中最關(guān)鍵的問(wèn)題是模型的粒度。設(shè)備和環(huán)境的屬性都是無(wú)窮多的。比如設(shè)備的移動(dòng)速度、體積大小、發(fā)射功率，物理環(huán)境中的氣候、生物等的影響都應(yīng)該被考慮到。理論上，建模的粒度越細(xì)，反應(yīng)現(xiàn)實(shí)的程度也就越高，模擬仿真的時(shí)候效果也會(huì)越好。但是過(guò)于細(xì)粒度的環(huán)境建模也會(huì)帶來(lái)顯著的開銷，采集數(shù)據(jù)的過(guò)程也是十分復(fù)雜的。所以必須在建模粒度方面做出權(quán)衡。

一種思路是把群體程序的執(zhí)行看成是全局狀態(tài)的序列，每個(gè)全局狀態(tài)都包含了每個(gè)個(gè)體設(shè)備的狀態(tài)。個(gè)體設(shè)備的狀態(tài)包括了位置信息，內(nèi)部狀態(tài)信息和正在運(yùn)行的程序

問(wèn)題。群體程序的執(zhí)行狀態(tài)幾乎無(wú)時(shí)無(wú)刻都在變化，以至于只有無(wú)限細(xì)粒度的描述才能描述整個(gè)群體的行為。顯然，研究者不可能對(duì)無(wú)限多的狀態(tài)進(jìn)行分析。David Evans提出對(duì)全局狀態(tài)進(jìn)行歸類[2]，系統(tǒng)的狀態(tài)在全局狀態(tài)標(biāo)記未發(fā)生改變的前提下都可以認(rèn)為是不變的。這樣，一個(gè)群體程序的規(guī)定就可以通過(guò)全局狀態(tài)的時(shí)序邏輯來(lái)進(jìn)行定義。

群體程序的仿真測(cè)試是基于環(huán)境和設(shè)備建模的。良好的評(píng)估環(huán)節(jié)能夠幫助研究者在群體編程的研究中，更好的搭建和理解群體計(jì)算系統(tǒng)。就目前而言，相比已經(jīng)有著比較完善測(cè)試評(píng)估體系的傳統(tǒng)編程來(lái)說(shuō)，群體編程的測(cè)試還處在發(fā)展中。最初，研究者們通過(guò)已有的平臺(tái)（如 MATLAB）來(lái)做一些仿真測(cè)試。隨著需求的增加，也使用了一些其他領(lǐng)域的測(cè)試工具來(lái)進(jìn)行群體編程的仿真測(cè)試，比如最初用于無(wú)限通信的仿真工具GloMoSim。對(duì)群體程序的評(píng)估一般是由評(píng)估元語(yǔ)開始的。藉由評(píng)估環(huán)節(jié)來(lái)更好的理解和完善元語(yǔ)操作，進(jìn)而理解完善由元語(yǔ)組合成的簡(jiǎn)單的群體程序，最后循序漸進(jìn)達(dá)到對(duì)大型，復(fù)雜群體程序進(jìn)行研究的目的。

Cuvelier在2002年[3]Seth在2003年[4]分別在不同實(shí)驗(yàn)平臺(tái)上對(duì)于多種散布算法的效率進(jìn)行了評(píng)估，展示了群體編程研究的一些基本思路。

3 總結(jié)

使用群體編程的方法將大大提高對(duì)大規(guī)模環(huán)境敏感分布式系統(tǒng)編程的效率。在認(rèn)知網(wǎng)絡(luò)[5]，傳感網(wǎng)絡(luò)[6]，UAV無(wú)等。由于沒有時(shí)間同步性，全球狀態(tài)的粒度產(chǎn)生了很嚴(yán)重的人機(jī)控制[7]等領(lǐng)域都出現(xiàn)了對(duì)群體編程工具的所需求。語(yǔ)言設(shè)計(jì)是計(jì)算機(jī)科學(xué)中難度和挑戰(zhàn)最大的部分，目前對(duì)群體編程的研究還處在起始階段，許多有價(jià)值的問(wèn)題還有待今天的研究者來(lái)研究和完善。群體智能技術(shù)的前景已經(jīng)被公眾認(rèn)可，群體編程的語(yǔ)言、工具和理論的研究將大大的影響群體智能，群體計(jì)算技術(shù)的發(fā)展和實(shí)際應(yīng)用，對(duì)未來(lái)人們的生活產(chǎn)生深遠(yuǎn)的影響。

[1]Errol Charles McEachron. A SYSTEM [M]FOR SYNTHESIZING SWARM PROGRAMS. 2002.

[2]David Evans. Programming the Swarm. 2000.

[3]MJ Cuvelier . Communication Aware Swarm Dispersion Primitives. 2002.

[4]Ankush Seth. SCALABILITY AND COMMUNICATION WITHIN SWARM COMPUTING. 2003.

[5]M PERALTA, S MUKHOPADHYAY. COGNITIVE NETWORKS. 2009.

[6]K Shenai, S Mukhopadhyay - Microelectronics . Cognitive sensor networks. 2008.

[7]DM Hart, PA Craig-Hart-Aerospace Conference . Reducing swarming theory to practice for UAV control. 2004.