人工智能通識(shí)教程 第2版 課件 第13章 群體智能

第2版人工智能通識(shí)教程第13章周蘇教授QQ：81505050群體智能導(dǎo)讀案例：無(wú)人機(jī)最快圈速：算法控制戰(zhàn)勝專業(yè)駕駛員基于蘇黎世大學(xué)研究人員開發(fā)了一種新算法，讓自主飛行的四旋翼飛行器計(jì)算出充分考慮無(wú)人機(jī)局限性的時(shí)間最優(yōu)軌跡，并首次在無(wú)人機(jī)競(jìng)賽中戰(zhàn)勝兩名人類駕駛員。01向蜜蜂學(xué)習(xí)群體智能02什么是群體智能03典型算法模型04群體智能背后的故事目錄/CONTENTS05群體智能的應(yīng)用06群體智能的發(fā)展對(duì)群體智能（又稱群集智能）的研究源于對(duì)螞蟻、蜜蜂等社會(huì)性昆蟲群體行為的研究，最早被用在細(xì)胞機(jī)器人系統(tǒng)的描述中。群體具有自組織性，它的控制是分布式的，不存在中心控制。群體智能的算法主要有智能蟻群算法和粒子群算法。智能蟻群算法包括蟻群優(yōu)化算法、蟻群聚類算法和多機(jī)器人協(xié)同合作系統(tǒng)。蟻群優(yōu)化算法和粒子群優(yōu)化算法在求解實(shí)際問題時(shí)應(yīng)用最為廣泛。第13章群體智能PART01向蜜蜂學(xué)習(xí)群體智能蜜蜂是自然界中被研究的時(shí)間最長(zhǎng)的群體智能動(dòng)物之一。蜜蜂在進(jìn)化過程中首先形成了大腦以處理信息，但是在某種程度上它們的大腦不能太大，這大概因?yàn)樗鼈兪秋w行動(dòng)物，腦袋小能夠減輕飛行負(fù)擔(dān)。事實(shí)上，蜜蜂的大腦比一粒沙子還要小，其中只有不到一百萬(wàn)個(gè)神經(jīng)元。相比之下，人類大約有850億個(gè)神經(jīng)元。不管你有多聰明，把它除以85000，這就是一只蜜蜂的智慧。13.1向蜜蜂學(xué)習(xí)群體智能所以，一只蜜蜂是一個(gè)非常非常簡(jiǎn)單的有機(jī)體，但它們也有非常困難的問題需要解決，這也是關(guān)于蜜蜂被研究最多的一個(gè)問題——選擇筑巢地點(diǎn)。通常一個(gè)蜂巢內(nèi)有1萬(wàn)只蜜蜂，并且隨著蜜蜂數(shù)量的壯大，它們每年都需要一個(gè)新家。它們的筑巢地點(diǎn)可能是空樹干里面的一個(gè)洞，也可能在建筑物某一側(cè)。因此，蜜蜂群體需要找到合適的筑巢地點(diǎn)。這聽起來(lái)好像很簡(jiǎn)單，但對(duì)于蜜蜂來(lái)說，這是一個(gè)關(guān)乎蜂群生死的決定。它們選擇的筑巢地點(diǎn)越好，對(duì)物種生存就會(huì)越有利。13.1向蜜蜂學(xué)習(xí)群體智能為了解決這個(gè)問題，蜜蜂形成了蜂群思維，或者說群體智能，而第一步就是它們需要關(guān)于周圍世界的信息。因此，蜂群會(huì)先派出數(shù)百只偵察蜜蜂到外面約78平方千米的地方進(jìn)行搜索，尋找它們可以筑巢的潛在地點(diǎn)，這是數(shù)據(jù)收集階段。圖13-5一群蜜蜂聚集在一棵樹上，偵察蜂外出尋找新巢址13.1向蜜蜂學(xué)習(xí)群體智能然后，這些偵察蜜蜂把信息帶回蜂群，接下來(lái)，就是最困難的部分：它們要做出決定，在找到的幾十個(gè)潛在地點(diǎn)中挑選出最好的。蜜蜂們非常挑剔，它們需要找到一個(gè)能滿足一系列條件的新住所。新房子必須足夠大，可以儲(chǔ)存冬天所需的蜂蜜；通風(fēng)要足夠好，這樣在夏天能保持涼爽；需要能夠隔熱，以便在寒冷的夜晚保持溫暖；需要保護(hù)蜜蜂不受雨水的影響，但也需要有充足水源。當(dāng)然，還需要有良好的地理位置，接近好的花粉來(lái)源。13.1向蜜蜂學(xué)習(xí)群體智能這是一個(gè)復(fù)雜多變量問題。事實(shí)上，研究這些數(shù)據(jù)的人會(huì)發(fā)現(xiàn)，人類尋找這個(gè)多變量?jī)?yōu)化問題的最佳解決方案都是非常困難的。換成類似具有挑戰(zhàn)性的人類的問題，比如為新工廠選取廠址，或者為開設(shè)新店選取完美的店址，或者定義新產(chǎn)品的完美特性，這些問題都很難找到一個(gè)十全十美的解決方案。然而，生物學(xué)家的研究表明，蜜蜂常常能夠從所有可用的選項(xiàng)中選出最佳的解決方案，或者選擇第二好的解決方案。這是很了不起的。事實(shí)上，通過群體智能一起工作，蜜蜂能夠作出一個(gè)優(yōu)化的決定，而比蜜蜂大腦強(qiáng)大85000倍的人腦，卻很難做到這一點(diǎn)。13.1向蜜蜂學(xué)習(xí)群體智能那么蜜蜂們是怎么做到的呢？它們形成了一個(gè)實(shí)時(shí)系統(tǒng)，在這個(gè)系統(tǒng)中，它們可以一起處理數(shù)據(jù)，并在最優(yōu)解上匯聚在一起。這是大自然的造化，蜜蜂想出了絕妙的辦法，它們通過振動(dòng)身體來(lái)處理數(shù)據(jù)，實(shí)現(xiàn)這一過程，生物學(xué)家把這叫做“搖擺舞”。生物學(xué)家剛開始研究蜂巢的時(shí)候，他們看到這些蜜蜂在做一些看起來(lái)像是在跳舞的事情，它們振動(dòng)自己的身體，這些振動(dòng)所產(chǎn)生的信號(hào)代表它們是否支持某個(gè)特定的筑巢地點(diǎn)。成百上千的蜜蜂同時(shí)振動(dòng)它們的身體時(shí)，基本上就是一個(gè)多維的選擇問題。13.1向蜜蜂學(xué)習(xí)群體智能它們揣度每個(gè)決定，探索所有不同的選擇，直到在某個(gè)解決方案中能夠達(dá)成一致，而這幾乎總是最優(yōu)或者次優(yōu)的解決方案，并且能夠解決單個(gè)大腦無(wú)法解決的問題。這是關(guān)于群體智能最著名的例子，我們也看到同樣的過程發(fā)生在鳥群或者魚群中，它們的群體智能大于個(gè)體。13.1向蜜蜂學(xué)習(xí)群體智能利用這一方式，我們來(lái)考慮一大群游客在曼哈頓找一家優(yōu)質(zhì)酒店。假設(shè)大部分游客都年老體弱，無(wú)法長(zhǎng)途行走。首先，在中央公園的演奏臺(tái)建立一個(gè)臨時(shí)基地，接著，派出體力最好的成員到處巡查，隨后他們回到演奏臺(tái)并互相比較筆記。聽到有更好的酒店選擇時(shí)，他們?cè)俅吻巴鶎?shí)地考察。最后，大家達(dá)成共識(shí)，所有人再集體前往目標(biāo)酒店辦理入住。13.1向蜜蜂學(xué)習(xí)群體智能曼哈頓的街道有兩種命名方式，街常為東西走向，而道常為南北走向，所以偵察兵回來(lái)的時(shí)候，只需要說明該酒店最接近哪條街哪條道，大家就可以明白。任何時(shí)間，偵察兵的定位都可以用兩個(gè)數(shù)字來(lái)表示：街和大道。如果用數(shù)學(xué)語(yǔ)言表示，就是X和Y。假如需要的話，我們還可以在演奏臺(tái)準(zhǔn)備一張坐標(biāo)紙，追蹤每一個(gè)偵察兵的行走路線，以此定位酒店位置。偵察兵在曼哈頓街道上尋找最佳酒店就如同在XY坐標(biāo)軸上尋找最優(yōu)值一樣。13.1向蜜蜂學(xué)習(xí)群體智能所謂集群機(jī)器人或者人工蜂群智能，就是讓許多簡(jiǎn)單的物理機(jī)器人協(xié)作。就像昆蟲群體一樣，機(jī)器人會(huì)根據(jù)集群行為行動(dòng)，它們會(huì)在環(huán)境中導(dǎo)航，與其他機(jī)器人溝通。與分散機(jī)器人系統(tǒng)不同，集群機(jī)器人會(huì)用到大量的機(jī)器人個(gè)體，它是一個(gè)靈活的系統(tǒng)。拉迪卡·納格帕爾領(lǐng)導(dǎo)的團(tuán)隊(duì)以及其他許多科研機(jī)構(gòu)都在研究這門技術(shù)。此技術(shù)未來(lái)獲得成功，集群機(jī)器人會(huì)展示出巨大的潛力，影響醫(yī)療保健、軍事等行業(yè)。機(jī)器人越來(lái)越小，未來(lái)我們也許可以讓大量納米機(jī)器人以群蜂的形式協(xié)調(diào)工作，在微機(jī)械、人體內(nèi)執(zhí)行任務(wù)。13.1向蜜蜂學(xué)習(xí)群體智能PART02什么是群體智能群體智能的概念來(lái)自對(duì)自然界中一些社會(huì)性昆蟲，如螞蟻、蜜蜂等的群體行為的研究。單只螞蟻的智能并不高，它看起來(lái)不過是一段長(zhǎng)著腿的神經(jīng)節(jié)而已。不過，幾只螞蟻湊到一起，就可以一起往蟻穴搬運(yùn)路上遇到的食物。如果是一群螞蟻，它們就能協(xié)同工作，建起堅(jiān)固、漂亮的巢穴，一起抵御危險(xiǎn)，撫養(yǎng)后代。社會(huì)動(dòng)物以一個(gè)統(tǒng)一的動(dòng)態(tài)集體工作時(shí)，其群體涌現(xiàn)出的解決問題和做出決策的智慧會(huì)超越大多數(shù)單獨(dú)成員，如蟻群搭橋、鳥群覓食、蜂群筑巢等，這一過程在生物學(xué)上被稱為“群體智能”。13.2什么是群體智能人類可以形成群體智能嗎？人類并沒有進(jìn)化出群集的能力，因?yàn)槿祟惾鄙偻愑糜诮?shí)時(shí)反饋循環(huán)的敏銳連接（比如螞蟻的觸角），這種連接是高度相關(guān)的，被認(rèn)為是一個(gè)“超級(jí)器官”。通過這么做，這些生物能夠進(jìn)行最優(yōu)選擇，這要遠(yuǎn)比獨(dú)立個(gè)體的選擇能力要強(qiáng)得多。13.2什么是群體智能在某個(gè)群體中，若存在眾多無(wú)智能的個(gè)體，它們通過相互之間的簡(jiǎn)單合作所表現(xiàn)出來(lái)的群居性生物的智能行為是分布式控制的，具有自組織性?！叭后w智能”作為計(jì)算機(jī)專業(yè)術(shù)語(yǔ)最早是在1989年由赫拉多等提出的，用來(lái)描述電腦屏幕上細(xì)胞機(jī)器人的自組織算法所具有的分布控制、去中心化的智能行為。早期學(xué)者主要專注于群體行為特征規(guī)律的研究，并提出了一系列具有群體智能特征的算法，如蟻群優(yōu)化算法在解決“旅行商問題”等數(shù)學(xué)難題上得到了較好的應(yīng)用。13.2.1群體人工智能技術(shù)如今，人類群體、大數(shù)據(jù)、物聯(lián)網(wǎng)已經(jīng)實(shí)現(xiàn)了廣泛和深度的互聯(lián)，群體智能的發(fā)展方向逐漸轉(zhuǎn)移到人、機(jī)、物融合的方向上來(lái)。在具體實(shí)現(xiàn)上，智能計(jì)算模式逐漸從“以機(jī)器為中心”的模式走向“群體計(jì)算回路”，智能系統(tǒng)開發(fā)也從封閉和計(jì)劃走向了開放和競(jìng)爭(zhēng)。13.2.1群體人工智能技術(shù)人類可以做到把個(gè)人的思考組合起來(lái)，讓它們形成一個(gè)統(tǒng)一的動(dòng)態(tài)系統(tǒng)，以做出更好的決策、預(yù)測(cè)、評(píng)估和判斷。人類群集已經(jīng)被證明在預(yù)測(cè)體育賽事結(jié)果、金融趨勢(shì)甚至是奧斯卡獎(jiǎng)得主這些事件上的準(zhǔn)確率超過了個(gè)體專家。例如，群體人工智能技術(shù)能讓群體組成實(shí)時(shí)的線上系統(tǒng)，把世界各地的人作為“人類群集”連接起來(lái)，這是一個(gè)人類實(shí)時(shí)輸入和眾多AI算法的結(jié)合。群體人工智能結(jié)合人類參與者的知識(shí)、智慧、硬件和直覺，并把這些要素組合成一個(gè)統(tǒng)一的新智能，能生成最優(yōu)的預(yù)測(cè)、決策、洞見和判斷。13.2.1群體人工智能技術(shù)依賴于每個(gè)格子單元（細(xì)胞）的幾條簡(jiǎn)單運(yùn)動(dòng)規(guī)則，可以使細(xì)胞集合的運(yùn)動(dòng)表現(xiàn)出超常的智能行為。群體智能不是簡(jiǎn)單的多個(gè)體的集合，而是超越個(gè)體行為的一種更高級(jí)表現(xiàn)，這種從個(gè)體行為到群體行為的演變過程往往極其復(fù)雜，以至于往往無(wú)法預(yù)測(cè)。13.2.1群體人工智能技術(shù)群體智能有兩種機(jī)制：（1）自上而下有組織的群體智能行為。這種機(jī)制會(huì)形成一種分層有序的組織架構(gòu)。自上而下的群體智能形成機(jī)制是在問題可分解的情況下，不同個(gè)體之間通過蜂群算法集成進(jìn)行合作，進(jìn)而達(dá)到高效解決復(fù)雜問題的機(jī)制。美國(guó)美國(guó)國(guó)防部高級(jí)研究計(jì)劃局正在開展的“進(jìn)攻性蜂群戰(zhàn)術(shù)”（OFFSET）項(xiàng)目，就是通過自上而下的群體智能機(jī)制將群體智能推向?qū)崙?zhàn)化水平。德國(guó)國(guó)防軍也運(yùn)用自上而下的群體智能機(jī)制開發(fā)無(wú)人機(jī)蜂群戰(zhàn)術(shù)級(jí)人工智能快速?zèng)Q策系統(tǒng)。13.2.2群體智能的兩種機(jī)制（2）自下而上自組織的群體智能涌現(xiàn)。這種機(jī)制可使群體涌現(xiàn)出個(gè)體不具有的新屬性，而這種新屬性正是個(gè)體之間綜合作用的結(jié)果。美國(guó)科技作家凱文·凱利在《失控：全人類的最終命運(yùn)和結(jié)局》中提到：“一種由無(wú)數(shù)默默無(wú)聞的零件，通過永不停歇的工作，而形成的緩慢而寬廣的創(chuàng)造力”，這就是群體智能涌現(xiàn)的過程。例如由多個(gè)簡(jiǎn)單機(jī)器人組成的群體機(jī)器人系統(tǒng)，通過“分布自組織”的協(xié)作，可以完成單個(gè)機(jī)器人無(wú)法完成或難以完成的工作。13.2.2群體智能的兩種機(jī)制基于群體智能的技術(shù)可用于許多應(yīng)用程序。各國(guó)正在研究用于控制無(wú)人駕駛車輛的群體技術(shù)，歐洲航天局正在考慮用于自組裝和干涉測(cè)量的軌道群，美國(guó)宇航局正在研究使用群體技術(shù)進(jìn)行行星測(cè)繪等。安東尼·劉易斯和喬治·貝基1992年撰寫的論文中，討論了使用群體智能來(lái)控制體內(nèi)納米機(jī)器人，以殺死癌癥腫瘤的可能性。相反，里菲和阿伯使用隨機(jī)擴(kuò)散搜索來(lái)幫助定位腫瘤。群體智能也已應(yīng)用于數(shù)據(jù)挖掘等領(lǐng)域，例如DoRoO等人和惠普在20世紀(jì)90年代中期以來(lái)研究了基于螞蟻的路由算法在電信網(wǎng)絡(luò)中的應(yīng)用。13.2.3基本原則與特點(diǎn)米洛納斯（1994年）提出了群體智能應(yīng)該遵循的五條基本原則，分別為：（1）鄰近原則，群體能夠進(jìn)行簡(jiǎn)單的空間和時(shí)間計(jì)算；（2）品質(zhì)原則，群體能夠響應(yīng)環(huán)境中的品質(zhì)因子；（3）多樣性反應(yīng)原則，群體的行動(dòng)范圍不應(yīng)該太窄；（4）穩(wěn)定性原則，群體不應(yīng)在每次環(huán)境變化時(shí)都改變自身的行為；（5）適應(yīng)性原則，在所需代價(jià)不太高的情況下，群體能夠在適當(dāng)?shù)臅r(shí)候改變自身的行為。13.2.3基本原則與特點(diǎn)這些原則說明實(shí)現(xiàn)群體智能的智能主體必須能夠在環(huán)境中表現(xiàn)出自主性、反應(yīng)性、學(xué)習(xí)性和自適應(yīng)性等智能特性。但是，這并不代表群體中的每個(gè)個(gè)體都相當(dāng)復(fù)雜，恰恰相反，就像單只螞蟻智能不高一樣，組成群體的每個(gè)個(gè)體都只具有簡(jiǎn)單智能，它們通過相互之間的合作表現(xiàn)出復(fù)雜的智能行為。13.2.3基本原則與特點(diǎn)可以這樣說，群體智能的核心是由眾多簡(jiǎn)單個(gè)體組成的群體，能夠通過相互之間的簡(jiǎn)單合作來(lái)實(shí)現(xiàn)某一功能，完成某一任務(wù)。其中，“簡(jiǎn)單個(gè)體”是指單個(gè)個(gè)體只具有簡(jiǎn)單的能力或智能，而“簡(jiǎn)單合作”是指?jìng)€(gè)體和與其鄰近的個(gè)體進(jìn)行某種簡(jiǎn)單的直接通信或通過改變環(huán)境間接與其他個(gè)體通信，從而可以相互影響、協(xié)同動(dòng)作。13.2.3基本原則與特點(diǎn)群體智能具有以下特點(diǎn)：（1）控制是分布式的，不存在中心控制。因而它更能夠適應(yīng)當(dāng)前網(wǎng)絡(luò)環(huán)境下的工作狀態(tài)，并且具有較強(qiáng)的魯棒性，即不會(huì)由于某一個(gè)或幾個(gè)個(gè)體出現(xiàn)故障而影響群體對(duì)整個(gè)問題的求解。（2）群體中的每個(gè)個(gè)體都能夠改變環(huán)境，這是個(gè)體之間間接通信的一種方式，被稱為“激發(fā)工作”。由于群體智能可以通過非直接通信的方式進(jìn)行信息的傳輸與合作，因而隨著個(gè)體數(shù)目的增加，通信開銷的增幅較小，因此，它具有較好的可擴(kuò)充性。13.2.3基本原則與特點(diǎn)（3）群體中每個(gè)個(gè)體的能力或遵循的行為規(guī)則非常簡(jiǎn)單，因而群體智能具有簡(jiǎn)單性特點(diǎn)。（4）群體表現(xiàn)出的復(fù)雜行為是通過簡(jiǎn)單個(gè)體交互過程突現(xiàn)出來(lái)的智能，群體具有自組織性。13.2.3基本原則與特點(diǎn)PART03典型算法模型群體智能算法可以分成兩個(gè)方面：對(duì)生物進(jìn)行模擬的群體智能和對(duì)非生物（煙花、磁鐵、頭腦風(fēng)暴等）進(jìn)行模擬的群體智能，針對(duì)群體智能的研究已經(jīng)取得了許多重要的結(jié)果。1991年意大利學(xué)者多里戈提出蟻群優(yōu)化理論，1995年，肯尼迪等學(xué)者提出粒子群優(yōu)化算法，此后群體智能研究迅速展開。蟻群優(yōu)化（ACO）和粒子群優(yōu)化（PSO）是兩種最廣為人知的“群體智能”算法。從基礎(chǔ)層面上來(lái)看，這些算法都使用了多智能體。每個(gè)智能體執(zhí)行非?；A(chǔ)的動(dòng)作，合起來(lái)就是更復(fù)雜、更即時(shí)的動(dòng)作，可用于解決問題。蟻群優(yōu)化與粒子群優(yōu)化這二者的目的都是執(zhí)行即時(shí)動(dòng)作，但采用的方式不同。13.3典型算法模型蟻群優(yōu)化與真實(shí)蟻群類似，利用信息激素指導(dǎo)單個(gè)智能體走最短的路徑。最初，隨機(jī)信息激素在問題空間中初始化，單個(gè)智能體開始遍歷搜索空間，邊走邊灑下信息激素。信息激素在每個(gè)時(shí)間步中按一定速率衰減。單個(gè)智能體根據(jù)前方的信息激素強(qiáng)度決定遍歷搜索空間的路徑。某個(gè)方向的信息激素強(qiáng)度越大，智能體越可能朝這個(gè)方向前進(jìn)。全局最優(yōu)方案就是具備最強(qiáng)信息激素的路徑。13.3典型算法模型粒子群優(yōu)化更關(guān)注整體方向。多個(gè)智能體初始化，并按隨機(jī)方向前進(jìn)。每個(gè)時(shí)間步中，每個(gè)智能體都需要就是否改變方向作出決策，決策基于全局最優(yōu)解的方向、局部最優(yōu)解的方向和當(dāng)前方向。新方向通常是以上三個(gè)值的最優(yōu)“權(quán)衡”結(jié)果。13.3典型算法模型螞蟻生活在一個(gè)十分高效并且秩序井然的群體之中，它們幾乎總是以最高效的姿態(tài)來(lái)完成每件事。它們修建蟻巢來(lái)保證最佳溫度和空氣流通；它們確定食物位置后能夠確定最佳路徑，并以最快的速度趕到。有人可能會(huì)認(rèn)為這是由于某些中央權(quán)力中心，比如蟻后，在管控它們的所有行動(dòng)。事實(shí)上，這樣的權(quán)力中心并不存在，蟻后不過是產(chǎn)卵的“機(jī)器”而已，每一只螞蟻都是自主的獨(dú)立個(gè)體。13.3.1蟻群算法螞蟻在尋找食物時(shí)，一開始會(huì)漫無(wú)目的地到處走動(dòng)，直到發(fā)現(xiàn)另一只螞蟻帶著食物返回巢穴時(shí)留下的信息素蹤跡，然后，它就開始沿著蹤跡行走。信息素越強(qiáng)，追蹤的可能性越大。在找到食物后它將返回巢穴，留下自己的蹤跡。如果該地還有大量食物，許多螞蟻也會(huì)按照該路徑來(lái)回往復(fù)，蹤跡將變得越來(lái)越鮮明，對(duì)路過的螞蟻的吸引力也會(huì)越來(lái)越大。不過，偶爾會(huì)有一些螞蟻因?yàn)檎也坏桔欅E而選擇了不同的路徑。如果新路徑更短，那么大量的螞蟻將在這條蹤跡上留下越來(lái)越多的信息素，舊路徑上的信息素就將逐漸蒸發(fā)。隨著時(shí)間的流逝，螞蟻們選擇的路徑會(huì)越來(lái)越接近最佳路徑。13.3.1蟻群算法蟻群能夠搭建身體浮橋跨越缺口地形并不是偶然事件。一個(gè)蟻群可能在同時(shí)搭建超過50只螞蟻組成的橋梁，每個(gè)橋梁從1只螞蟻到50只螞蟻不等。螞蟻不僅可以建造橋梁，而且能夠有效評(píng)估橋梁的成本和效率之間的平衡，比如在V字形道路上，蟻群會(huì)自動(dòng)調(diào)整到合適的位置建造橋梁，既不是靠近V頂點(diǎn)部分，也不是V開口最大的部分。圖13-7螞蟻建造橋梁13.3.1蟻群算法生物學(xué)家對(duì)蟻群橋梁研究的算法表明，每只螞蟻并不知道橋梁的整體形狀，它們只是在遵循兩個(gè)基本原則：（1）如果我身上有其他螞蟻經(jīng)過，那么我就保持不動(dòng)；（2）如果我身上螞蟻經(jīng)過的頻率低于某個(gè)閾值，我就加入行軍，不再充當(dāng)橋梁。13.3.1蟻群算法數(shù)十只螞蟻可以一起組成“木”筏渡過水面。當(dāng)蟻群遷徙的時(shí)候，整個(gè)木筏可能包含數(shù)萬(wàn)只或更多螞蟻。每只螞蟻都不知道木筏的整體形狀，也不知道木筏將要漂流的方向。但螞蟻之間非常巧妙的互相連接，形成一種透氣不透水的三維立體結(jié)構(gòu)，即使完全沉在水里的底部螞蟻也能生存。而這種結(jié)構(gòu)也使整個(gè)木筏包含超過75%空氣體積，所以能夠順利的漂浮在水面。13.3.1蟻群算法蟻群在地面形成非常復(fù)雜的尋找食物和搬運(yùn)食物的路線，似乎整個(gè)集體總是能夠找到最短的搬運(yùn)路線，然而每只螞蟻并不知道這種智能是如何形成的。用樟腦丸在螞蟻經(jīng)過的路線上涂抹會(huì)導(dǎo)致螞蟻迷路，這是因?yàn)檎聊X的強(qiáng)烈氣味嚴(yán)重干擾了螞蟻生物信息素的識(shí)別。13.3.1蟻群算法蟻群具有復(fù)雜的等級(jí)結(jié)構(gòu)，蟻后可以通過特殊的信息素影響到其他螞蟻，甚至能夠調(diào)節(jié)其他螞蟻的生育繁殖。但蟻后并不會(huì)對(duì)工蟻下達(dá)任何具體任務(wù)，每個(gè)螞蟻都是一個(gè)自主的單位，它的行為完全取決于對(duì)周邊環(huán)境的感知和自身的遺傳編碼規(guī)則。盡管缺乏集中決策，但蟻群仍能表現(xiàn)出很高的智能水平，這種智能就稱為分布式智能。13.3.1蟻群算法不僅螞蟻，幾乎所有膜翅目昆蟲都表現(xiàn)出很強(qiáng)的群體智能行為，另一個(gè)知名的例子就是蜂群。蟻群和蜂群被廣泛的認(rèn)為是具有真社會(huì)化屬性的生物種群，這是指它們具有以下三個(gè)特征：（1）繁殖分工。種群內(nèi)分為能夠繁殖后代的單位和無(wú)生育能力的單位，前者一般為女王和王，后者一般為工蜂、工蟻等。（2）世代重疊。即上一代和下一代共同生活，這也決定了下一個(gè)特征。（3）協(xié)作養(yǎng)育。種群?jiǎn)挝还餐瑓f(xié)作養(yǎng)育后代。這個(gè)真社會(huì)化屬性和人類的社會(huì)化屬性并不是同一概念。13.3.1蟻群算法受到自然界中螞蟻群的社會(huì)性行為的啟發(fā)，由M.多里戈等人于1991年首先提出了蟻群算法，它模擬了實(shí)際蟻群尋找食物的過程?？茖W(xué)家們創(chuàng)建了蟻群優(yōu)化（AOC）算法。13.3.1蟻群算法我們可以利用群體智能來(lái)設(shè)計(jì)一組機(jī)器人，每個(gè)機(jī)器人本身配置十分簡(jiǎn)單，僅需要了解自身所處的局部環(huán)境，通常也只與附近的其他機(jī)器人進(jìn)行溝通。每個(gè)設(shè)備都是自主運(yùn)行的，不需要中央智能來(lái)發(fā)布指令，就像我們?cè)诎蒹w系結(jié)構(gòu)時(shí)說到的機(jī)器人一樣，每個(gè)獨(dú)立個(gè)體只知道自己對(duì)世界的感知，這可以幫助建立強(qiáng)大穩(wěn)固的行為，可以自主適應(yīng)環(huán)境的變化。在擁有大量編程一致的同款機(jī)器人之后，就可以實(shí)現(xiàn)更大的彈性，因?yàn)橐恍〔糠謧€(gè)體的操作失誤并不會(huì)對(duì)整體的效能產(chǎn)生大的影響。13.3.1蟻群算法這類與螞蟻行為十分相似的機(jī)器人可以用于查找并移除地雷，或是在災(zāi)區(qū)搜尋傷亡人員。螞蟻利用信息素來(lái)給巢穴內(nèi)的其他成員留下信號(hào)，但感知信息素對(duì)機(jī)器人來(lái)說并不容易（雖然已經(jīng)可以實(shí)現(xiàn)），機(jī)器人利用的是燈光、聲響或是短程無(wú)線電。目前，蟻群算法已在組合優(yōu)化問題求解，以及電力、通信、化工、交通、機(jī)器人、冶金等多個(gè)領(lǐng)域中得到應(yīng)用，都表現(xiàn)出了令人滿意的性能。13.3.1蟻群算法想象一下在遠(yuǎn)足登山區(qū)有大量機(jī)器人的場(chǎng)景。在沒有其他事情要做的時(shí)候，它們就會(huì)站在視野范圍內(nèi)其他機(jī)器人的中間位置，這也意味著可以做到在該區(qū)域內(nèi)均勻分布。它們能夠注意到嘈雜的噪聲及揮動(dòng)的手勢(shì)，所以遇到困難的背包客就可以向它們尋求幫助。13.3.2搜索機(jī)器人如果有需要緊急服務(wù)的請(qǐng)求，則可以從一個(gè)機(jī)器人傳遞到另一個(gè)機(jī)器人，直到傳遞到能接收無(wú)線電或手機(jī)信號(hào)的機(jī)器人那里。假如需要運(yùn)送受傷的背包客，更多的機(jī)器人也可以前來(lái)提供幫助，其他機(jī)器人則將移動(dòng)位置來(lái)保證區(qū)域覆蓋度。比起包容體系結(jié)構(gòu)，所有這些操作都可以在機(jī)器人數(shù)量更少的情況下完成。13.3.2搜索機(jī)器人換一種方式，我們考慮利用一組四軸飛行器來(lái)保證背包客的安全。這些飛行器將以集群的方式在特定區(qū)域內(nèi)巡查，尤其關(guān)注背包客們常穿的亮橙色。在某些難以察覺的地方可能有人受傷，一旦有飛行器注意到了那抹橙色就會(huì)立刻轉(zhuǎn)向該地點(diǎn)。飛行器在背包客頭頂盤旋時(shí)，每一架都會(huì)以稍稍不同的有利位置進(jìn)行觀察，慢慢地，越來(lái)越多的飛行器就會(huì)發(fā)現(xiàn)傷員。很快，整個(gè)飛行器集群就將在某地低空盤旋，也就意味著它們已經(jīng)成功確定了可能的事故地點(diǎn)。這時(shí)就需要利用到其他人工智能技術(shù)，比如，自然語(yǔ)言理解、手勢(shì)識(shí)別和圖像識(shí)別，但很明顯，這些如今都不是什么棘手的問題。13.3.2搜索機(jī)器人另一類經(jīng)常被模仿的群體行為是鳥類的群集。當(dāng)整個(gè)群體需要集體移動(dòng)但又需要尋找特定目標(biāo)時(shí)，就可以利用這種技術(shù)，而創(chuàng)建個(gè)體集群的規(guī)則十分簡(jiǎn)單。13.3.3微粒群（鳥群）優(yōu)化算法（1）跟緊群體內(nèi)其他成員。（2）以周邊成員的平均方向作為飛行方向。（3）與其他成員和障礙物保持安全距離。如果我們?cè)O(shè)置向某個(gè)目標(biāo)偏轉(zhuǎn)的趨勢(shì)，整個(gè)集群都將根據(jù)趨勢(shì)行進(jìn)。13.3.3微粒群（鳥群）優(yōu)化算法鳥類在群體飛行中往往能表現(xiàn)出一種智能的簇?fù)韰f(xié)同行為，尤其是在長(zhǎng)途遷徙過程中，以特定的形狀組隊(duì)飛行可以充分利用互相產(chǎn)生的氣流，從而減少體力消耗。常見的簇?fù)眸B群是遷徙的大雁，它們數(shù)量不多，往往排成一字型或者人字形，據(jù)科學(xué)估計(jì)，這種隊(duì)形可以讓大雁減少15~20%的體力消耗。體型較小的歐椋鳥組成的鳥群的飛行則更富于變化，它們往往成千上萬(wàn)只一起在空中飛行，呈現(xiàn)出非常柔美的群體造型。13.3.3微粒群（鳥群）優(yōu)化算法基于三個(gè)簡(jiǎn)單規(guī)則，鳥群就可以創(chuàng)建出極復(fù)雜的交互和運(yùn)動(dòng)方式，形成奇特的整體形狀，繞過障礙和躲避獵食者：（1）分離，和臨近單位保持距離，避免擁擠碰撞（2）對(duì)齊，調(diào)整飛行方向，順著周邊單位的平均方向飛行（3）凝聚，調(diào)整飛行速度，保持在周邊單位的中間位置鳥群沒有中央控制，實(shí)際上每只鳥都是獨(dú)立自主的，只考慮其周邊球形空間內(nèi)的5~10只鳥的情況。13.3.3微粒群（鳥群）優(yōu)化算法魚群的群體行為和鳥群非常相似。金槍魚、鯡魚、沙丁魚等很多魚類都成群游行，這些魚總是傾向于加入數(shù)量大的、體型大小與自身更相似的魚群，所以有的魚群并不是完全由同一種魚組成。群體游行不僅可以更有效利用水動(dòng)力減少成員個(gè)體消耗，而且更有利于覓食和生殖，以及躲避捕食者的獵殺。魚群中的絕大多數(shù)成員都不知道自己正在游向哪里。魚群使用共識(shí)決策機(jī)制，個(gè)體的決策會(huì)不斷地參照周邊個(gè)體的行為進(jìn)行調(diào)整，從而形成集體方向。13.3.3微粒群（鳥群）優(yōu)化算法在哺乳動(dòng)物中也常見群體行為，尤其是陸上的牛、羊、鹿，或者南極的企鵝。遷徙和逃脫獵殺時(shí)候，它們能表現(xiàn)出很強(qiáng)的集體意志。研究表明，畜群的整體行為很大程度上取決于個(gè)體的模仿和跟風(fēng)行為，而遇到危險(xiǎn)的時(shí)候，則是個(gè)體的自私動(dòng)機(jī)決定了整體的行為方向。13.3.3微粒群（鳥群）優(yōu)化算法細(xì)菌和植物也能夠以特殊的方式表現(xiàn)出群體智能行為。培養(yǎng)皿中的枯草芽孢桿菌根據(jù)營(yíng)養(yǎng)組合物和培養(yǎng)基的粘度，整個(gè)群體從中間向四周有規(guī)律的擴(kuò)散遷移，形成隨機(jī)但非常有規(guī)律的數(shù)值型狀態(tài)。而植物的根系作為一個(gè)集體，各個(gè)根尖之間存在某種通信，遵循范圍最大化且互相保持間隔的規(guī)律生長(zhǎng)，進(jìn)而能夠最有效的利用空間吸收土壤中的養(yǎng)分。13.3.3微粒群（鳥群）優(yōu)化算法粒群優(yōu)化算法最早是由肯尼迪和埃伯哈特于1995年提出的，是一種基于種群尋優(yōu)的啟發(fā)式搜索算法，其基本概念源于對(duì)鳥群群體運(yùn)動(dòng)行為的研究。在微粒群優(yōu)化算法中，每個(gè)微粒代表待求解問題的一個(gè)潛在解，它相當(dāng)于搜索空間中的一只鳥，其“飛行信息”包括位置和速度兩個(gè)狀態(tài)量。每個(gè)微粒都可獲得其鄰域內(nèi)其他微粒個(gè)體的信息，并可根據(jù)該信息以及簡(jiǎn)單的位置和速度更新規(guī)則，改變自身的狀態(tài)量，以便更好地適應(yīng)環(huán)境。隨著這一過程的進(jìn)行，微粒群最終能夠找到問題的近似最優(yōu)解。13.3.3微粒群（鳥群）優(yōu)化算法由于微粒群優(yōu)化算法概念簡(jiǎn)單，易于實(shí)現(xiàn)，并且具有較好的尋優(yōu)特性，因此它在短期內(nèi)得到迅速發(fā)展，目前已在許多領(lǐng)域中得到應(yīng)用，如電力系統(tǒng)優(yōu)化、TSP問題求解、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、交通事故探測(cè)、參數(shù)辨識(shí)、模型優(yōu)化等。奧斯卡技術(shù)獎(jiǎng)的獲得者，計(jì)算機(jī)圖形學(xué)家克雷格·雷諾茲在1986年開發(fā)了Boids鳥群算法，這種算法僅僅依賴分離、對(duì)齊、凝聚三個(gè)簡(jiǎn)單規(guī)則就實(shí)現(xiàn)各種動(dòng)物群體行為的模擬。13.3.3微粒群（鳥群）優(yōu)化算法在討論遺傳算法時(shí)，我們用一組稱作“基因”的數(shù)字來(lái)代表群體中的每個(gè)獨(dú)立個(gè)體，通過改變這些數(shù)字直到它們能夠代表最優(yōu)個(gè)體為止。就同樣的數(shù)字而言，利用群體智能技術(shù)，我們不再將它們看做染色體上的基因，而是看做圖表或地圖等空間上的位置。隨著每個(gè)獨(dú)立個(gè)體空間位置的變化，數(shù)字相應(yīng)地發(fā)生改變，就像你走在曼哈頓大街上，代表你所在位置的街道數(shù)字發(fā)生改變一樣。我們的搜索不再是固定個(gè)體的進(jìn)化過程，而是不同個(gè)體的旅程?？梢允褂萌魏斡脕?lái)搜索位置的技術(shù)，例如螞蟻覓食、蜜蜂群集或是鳥類聚集，而完全不用建造任何機(jī)器人。13.3.4沒有機(jī)器人的集群PART04群體智能背后的故事在公園我們經(jīng)?？吹匠扇旱镍B兒在樹木上空飛旋，它們遲早會(huì)落在建筑的突出物上休息，之后在受了什么驚擾后又動(dòng)作一致地再度起飛。13.4群體智能背后的故事這群鳥中并沒有領(lǐng)導(dǎo)，沒有一只鳥兒會(huì)指示其他鳥兒該做什么，相反，它們各自密切注意身邊的同伴。在空中飛旋時(shí)，全都遵循簡(jiǎn)單規(guī)則，這些規(guī)則構(gòu)成了另一種群體智能，它與決策的關(guān)系不大，主要是用來(lái)精確協(xié)調(diào)行動(dòng)。研究計(jì)算機(jī)制圖的克雷格·雷諾茲對(duì)這些規(guī)則感到好奇，他在1986年設(shè)計(jì)了一個(gè)看似簡(jiǎn)單的導(dǎo)向程序，叫做“擬鳥”。13.4群體智能背后的故事在這個(gè)模擬程序中，一種模仿鳥類的物體（擬鳥）接收到三項(xiàng)指示：（1）避免擠到附近的擬鳥；（2）按附近擬鳥的平均走向飛行；（3）跟緊附近的擬鳥。13.4群體智能背后的故事程序運(yùn)行結(jié)果呈現(xiàn)在電腦屏幕上時(shí)，模擬出令人信服的鳥群飛舞效果，包括逼真的、無(wú)法預(yù)測(cè)的運(yùn)動(dòng)。當(dāng)時(shí)，雷諾茲正在尋求能在電視和電影中制造逼真動(dòng)物特效的辦法。1992年的《蝙蝠俠歸來(lái)》是第一部利用他的技術(shù)制作的電影，其中模擬生成了成群的蝙蝠和企鵝。后來(lái)他在索尼公司從事電子游戲領(lǐng)域的研究，例如用一套算法實(shí)時(shí)模擬數(shù)量達(dá)1.5萬(wàn)的互動(dòng)的鳥、魚或人。雷諾茲展示了自組織模型在模仿群體行為方面的力量，這也為機(jī)器人工程師開辟了新路。如果能讓一隊(duì)機(jī)器人像一群鳥般協(xié)調(diào)行動(dòng)，就比單獨(dú)的機(jī)器人有優(yōu)勢(shì)得多。13.4群體智能背后的故事賓夕法尼亞大學(xué)的機(jī)械工程教授維賈伊·庫(kù)馬爾說：“觀察生物界中數(shù)目龐大的群體，很難發(fā)現(xiàn)其中哪一個(gè)承擔(dān)中心角色。一切都是高度分散的：成員并不都參與交流，根據(jù)本地信息采取行動(dòng)；它們都是無(wú)名的，不必在乎誰(shuí)去完成任務(wù)，只要有人完成就行。要從單個(gè)機(jī)器人發(fā)展到多個(gè)機(jī)器人合作，這三個(gè)思路必不可少?！?3.4群體智能背后的故事?lián)吧鷦?dòng)物專家卡斯滕·霍耶爾在2003年的觀察，陸地動(dòng)物的群體行為也與魚群相似。那年，他和妻子利恩·阿利森跟著一大群北美馴鹿旅行了五個(gè)月，行程超過1500公里，記錄了它們的遷徙過程。遷徙從加拿大北部育空地區(qū)的冬季活動(dòng)范圍起始，到美國(guó)阿拉斯加州北極國(guó)家野生動(dòng)物保護(hù)區(qū)的產(chǎn)犢地結(jié)束。13.4群體智能背后的故事卡斯滕說：“這很難用語(yǔ)言形容。鹿群移動(dòng)時(shí)就像云影漫過大地，或者一大片多米諾骨牌同時(shí)倒下并改變著方向。好像每頭鹿都知道它周邊的同伴要做什么。這不是出于預(yù)計(jì)或回應(yīng)，也沒有因果關(guān)系，它們自然而然就這樣行動(dòng)?！?3.4群體智能背后的故事一天，正當(dāng)鹿群收窄隊(duì)形、穿過森林邊界線上的一條溪谷時(shí)，卡斯滕和利恩看見一只狼偷襲過去。鹿群做出了經(jīng)典的群體防御反應(yīng)?？ㄋ闺f：“那只狼一進(jìn)入鹿群外圍的某一特定距離，鹿群就驟然提高了警惕。這時(shí)每頭鹿都停下不動(dòng)，完全處于戒備狀態(tài)，四下張望?！崩怯窒蚯白吡?00米，突破了下一個(gè)限度?！半x狼最近的那頭鹿轉(zhuǎn)身就跑，這反應(yīng)就像波浪一樣掃過整個(gè)鹿群，于是所有的鹿都跑了起來(lái)。13.4群體智能背后的故事之后逃生行動(dòng)進(jìn)入另一階段。鹿群后端與狼最接近的那一小群馴鹿就像條毯子般裂開，散成碎片，這在狼看來(lái)一定是極度費(fèi)解的?！崩且粫?huì)兒追這頭鹿，一會(huì)兒又追那頭，每換一次追擊目標(biāo)都會(huì)被甩得更遠(yuǎn)。最后，鹿群翻過山嶺，脫逃而去，而狼留在那兒氣喘吁吁，大口吞著雪。每頭馴鹿本來(lái)都面臨著絕大的危險(xiǎn)，但鹿群的躲避行動(dòng)所表現(xiàn)的卻不是恐慌，而是精準(zhǔn)。每頭馴鹿都知道該什么時(shí)候跑、跑往哪個(gè)方向，即便不知道為什么要這樣做。沒有領(lǐng)袖負(fù)責(zé)鹿群的協(xié)調(diào)，每頭鹿都只是在遵循著幾千年來(lái)應(yīng)對(duì)惡狼襲擊而演化出來(lái)的簡(jiǎn)單規(guī)則。13.4群體智能背后的故事這就是群體智能的美妙魅力。無(wú)論我們討論的是螞蟻、蜜蜂、鴿子、還是北美馴鹿，智慧群體的組成要素——分散控制、針對(duì)本地信息行動(dòng)、簡(jiǎn)單的經(jīng)驗(yàn)法則——加在一起，就構(gòu)成了一套應(yīng)對(duì)復(fù)雜情況的精明策略。13.4群體智能背后的故事最大的變化可能體現(xiàn)在互聯(lián)網(wǎng)上。谷歌利用群體智能來(lái)查找你的搜索內(nèi)容。當(dāng)你鍵入一條搜索時(shí)，谷歌會(huì)在它的索引服務(wù)器上考查數(shù)十億網(wǎng)頁(yè)，找出最相關(guān)的，然后按照它們被其他網(wǎng)頁(yè)鏈接的次數(shù)進(jìn)行排序，把鏈接當(dāng)作投票來(lái)計(jì)數(shù)（最熱門的網(wǎng)站還有加權(quán)票數(shù)，因?yàn)樗鼈兛煽啃愿撸?。得到最多票?shù)的網(wǎng)頁(yè)被排在搜索結(jié)果列表的最前面。谷歌說，它通過這種方式，“利用網(wǎng)絡(luò)的群體智能來(lái)決定一個(gè)網(wǎng)頁(yè)的重要性”。13.4群體智能背后的故事網(wǎng)絡(luò)百科（維基、百度等）是一類免費(fèi)的合作性百科全書，辦得十分成功，其中有200多種語(yǔ)言寫成的數(shù)以百萬(wàn)計(jì)的文章，世間萬(wàn)物無(wú)不涉及，每一詞條均可由任何人撰寫、編輯。麻省理工學(xué)院集體智能中心的托馬斯·馬隆說：“如今可以讓數(shù)目龐大的人群以全新的方式共同思考，這在幾十年前我們連想都想不到。要解決我們?nèi)鐣?huì)面臨的問題，如醫(yī)療保健或氣候變化，沒有一個(gè)人的知識(shí)是夠用的。但作為集體，我們的知識(shí)量遠(yuǎn)比迄今為止我們所能利用的多得多?！?3.4群體智能背后的故事這種想法突出反映了關(guān)于群體智能的一個(gè)重要真理：人群只有在每個(gè)成員做事盡責(zé)、自主決斷的時(shí)候，才會(huì)發(fā)揮出智慧。群體內(nèi)的成員如果互相模仿，盲從于潮流，或等著別人告訴自己該做什么，這個(gè)群體就不會(huì)很聰明。若要一個(gè)群體擁有智慧，無(wú)論它是由螞蟻還是律師組成，都得依靠成員們各盡其力。我們有些人往往懷疑，值不值得把那只多余的瓶子拿去回收，來(lái)減輕我們對(duì)地球的壓力。而事實(shí)是：我們的一舉一動(dòng)都事關(guān)重大，即使我們看不出其中玄機(jī)。13.4群體智能背后的故事蜜蜂專家托馬斯·西利說：“蜜蜂跟你我一樣，從來(lái)看不到多少全局。我們誰(shuí)都不知道社會(huì)作為一個(gè)總體需要什么，但我們會(huì)看看周圍，說，哦，他們需要人在學(xué)校當(dāng)義工，給社區(qū)修剪草坪，或者在政治宣傳活動(dòng)中幫忙。”假如你要在一個(gè)充滿復(fù)雜性的世界中尋找行為榜樣，不妨去仿效蜜蜂吧。13.4群體智能背后的故事PART05群體智能的應(yīng)用目前國(guó)外對(duì)群體智能的應(yīng)用側(cè)重于底層技術(shù)領(lǐng)域，如集群結(jié)構(gòu)框架、集群控制與優(yōu)化、集群任務(wù)管理與協(xié)同等，國(guó)內(nèi)則主要側(cè)重于應(yīng)用領(lǐng)域，如集群路徑實(shí)時(shí)規(guī)劃、集群自主編隊(duì)與重構(gòu)、集群智能協(xié)同決策等。隨著群體智能在現(xiàn)實(shí)場(chǎng)景的深入應(yīng)用，將有力促進(jìn)產(chǎn)業(yè)智能化和提高產(chǎn)業(yè)競(jìng)爭(zhēng)力。另外，群體智能也正在深刻影響著軍事領(lǐng)域，使戰(zhàn)爭(zhēng)形態(tài)加速向智能化演變，與之相應(yīng)的戰(zhàn)爭(zhēng)觀也發(fā)生了嬗變。13.5群體智能的應(yīng)用（1）蜂群協(xié)同系統(tǒng)。美國(guó)的“進(jìn)攻性蜂群戰(zhàn)術(shù)”（OFFSET）項(xiàng)目探索未來(lái)的小單位步兵部隊(duì)將是由小型無(wú)人機(jī)系統(tǒng)（UASs）或小型無(wú)人地面車輛系統(tǒng)（UGSs）組成的“蜂群”，可在復(fù)雜的環(huán)境中完成多種任務(wù)。相關(guān)研究成果也將直接應(yīng)用到“馬賽