人工智能入門 課件 劉峽壁6.群智能、7.總結

群智能AI:SI2大綱什么是群智能(SI)?

模擬SI進行搜索

-蟻群優(yōu)化算法（ACO）-粒子群優(yōu)化算法（PSO）AI:SI3PartⅠ:什么是SI?KevinKelly:“這些不起眼的組件，只要正確地組合在一起，就能產(chǎn)生出人意料的智能效果?！笔裁词侨褐悄?？AI:SI4盡管自然界中的一些社會系統(tǒng)是由簡單的個體組成的，但它們可以表現(xiàn)出一種智能的集體行為。問題的智能解決方案自然地從這些個體的自組織和交流中產(chǎn)生。這些系統(tǒng)提供了重要的技術，可用于開發(fā)人工智能系統(tǒng)。自然之美AI:SI5自然界和社會中的集體行為的例子這可以被視為多智能體系統(tǒng)。AI:SI6涌現(xiàn)Goldstein：“在復雜系統(tǒng)的自組織過程中，新奇、一致的結構、模式和性質的產(chǎn)生?！蹦铩どw爾曼：“從深層次的簡單性中產(chǎn)生的表面復雜性”Bottom-upbehavior:“遵循簡單規(guī)則的簡單代理產(chǎn)生復雜的結構/行為。代理不遵循來自領導者的命令。”白蟻“大教堂”土堆是由白蟻群體建造的：這是自然界中涌現(xiàn)的一個經(jīng)典例子AI:SI7生物學動機：昆蟲社會社會性昆蟲的群體能夠從刻板、不可靠、不智能且簡單的昆蟲個體中實現(xiàn)靈活、可靠、智能和復雜的系統(tǒng)層面性能。

昆蟲遵循簡單規(guī)則，使用簡單的局部通信（氣味軌跡、聲音、觸覺）并且計算需求低。全局結構（例如，巢穴）可靠地由許多不可靠的個體行動涌現(xiàn)出來。AI:SI8生物學動機：群落、畜群和魚群在80年代末，克雷格·雷諾茲創(chuàng)建了一個名為“Boids”的動物運動模型。它根據(jù)三條簡單規(guī)則產(chǎn)生非常逼真的運動，這些規(guī)則定義了boid的轉向行為。這個模型及其變種已被用于驅動電影中的鳥、昆蟲、人、魚、羚羊等的動畫效果（例如，《蝙蝠俠歸來》、《獅子王》）AI:SI9Boid規(guī)則分離：轉向以避免擁擠的本地群體成員優(yōu)先于其他規(guī)則的基本規(guī)則在避免與環(huán)境中的其他物體發(fā)生碰撞時也很有用。對齊：朝向本地同群伙伴的平均航向和速度轉向強制保持凝聚，以保持同群伙伴在一起。也有助于避免碰撞。凝聚力：轉向以朝向本地同群伙伴的平均位置移動畜群邊緣的代理更容易受到捕食者的攻擊有助于保持畜群在一起AI:SI10一個應用：《獅子王》Videofrom:/471/current/notes/AI:SI群體智能

群體智能（SI）是一種基于對去中心化、自組織系統(tǒng)中的集體行為的研究的人工智能技術。1989年，Beni、Hackwood和Wang在細胞機器人系統(tǒng)的背景下首次使用了“群體智能”這一表述，用于描述簡單機械代理的自組織行為。后來，該術語擴展為包括“任何受社會昆蟲群落和其他動物群體集體行為啟發(fā)的算法設計或分布式問題解決設備的嘗試”[Bonabeau、Dorigo和Theraulaz，1999]。11AI:ANN12群體智能（續(xù)）群體智能系統(tǒng)通常由相互之間以及與環(huán)境進行局部交互的大量簡單代理組成。雖然通常不存在決定個體代理應如何行為的集中控制結構，但這些代理之間的局部交互往往會導致全局行為的涌現(xiàn)。有時被稱為“集體智能”AI:SI13群體智能的組成部分代理：

與世界和其他代理（直接或間接）進行交互簡單的行為

例如：螞蟻、白蟻、蜜蜂、黃蜂通信：

代理如何相互交互

例如：螞蟻的信息素

單個代理的簡單行為+一組代理之間的通信=該組代理的涌現(xiàn)復雜行為AI:ANN14間接通信信號傳播：-一個代理發(fā)送一個信號，該信號被廣播到環(huán)境中，并且其強度隨著距離的減小而減小。-在點x處，信號可能有以下強度之一：V(x)=V(x0)/dist(x,x0)V(x)=V(x0)/dist(x,x0)2

路徑-代理留下“放射性碎屑”形成路徑-一個代理跟隨路徑，使路徑逐漸變淡，直到消失AI:SI15間接通信黑板系統(tǒng)-一個公共區(qū)域（共享內(nèi)存），代理可以在其中交換信息、數(shù)據(jù)和知識。-黑板=強大的分布式知識計算范例-代理=知識源（KS）

IntelligentAgentsIntelligentAgentsIntelligentAgentsBlackboardMessageReplyAgentsIntelligentAgentsIntelligentAgentsIntelligentAgentsIntelligentAgentsIntelligentAgentsIntelligentAgentsAI:SI16直接通信Actor語言一個Actor執(zhí)行一系列動作以回復接收到的消息言語行為理論言語行為具有以下三個方面：Locution=說話者的物理表達Illocution=說話者話語的意圖意義（施為）Perlocution=Locution產(chǎn)生的動作例如：張告訴李：“請把門關上”。

locution

illocutioncontent perlocution：門關上了（希望如此?。〢I:ANN17群智能特點分布式，沒有中央控制或數(shù)據(jù)源通信有限沒有（顯式的）環(huán)境模型感知環(huán)境（感知）能夠應對環(huán)境變化。

群體智能與人類有關嗎？AI:SI18PartⅡ-Ⅲ：如何模擬群體智能進行搜索？示例1：螞蟻-->蟻群優(yōu)化算法（ACO）示例2：鳥群-->粒子群優(yōu)化算法（PSO）AI:SI19PartⅡ蟻群優(yōu)化算法（ACO）AI:SI20螞蟻

單個螞蟻是具有有限記憶并且能夠執(zhí)行簡單動作的簡單昆蟲。個體螞蟻是具有有限記憶并能執(zhí)行簡單動作的簡單昆蟲。然而，一個螞蟻群能夠展現(xiàn)出復雜的集體行為，為問題提供智能解決方案搬運大型物品搭建橋梁尋找從巢穴到食物源的最短路線，根據(jù)距離和易接近性對食物源進行優(yōu)先排序。AI:ANN21螞蟻此外，在蟻群中，每只螞蟻都有其規(guī)定任務，但如果集體需要，螞蟻可以切換任務。

在巢外，螞蟻可以執(zhí)行以下四種任務：覓食：尋找和獲取食物巡邏：尋找食物來源垃圾清理工作：對巢內(nèi)垃圾進行分類巢穴維護工作：建造和清理巢穴

螞蟻是否執(zhí)行某項任務取決于：環(huán)境物理狀態(tài)：如果巢的一部分受損，會有更多的螞蟻進行巢穴維護工作來修復它與其他螞蟻的社會互動

交流（直接或間接）是必要的AI:ANN22螞蟻如何找到最短路徑？他們通過在其所走的路徑上留下信息素，建立了一個間接通信系統(tǒng)。孤立的螞蟻隨機移動，但當它發(fā)現(xiàn)信息素痕跡時，這只螞蟻有很大可能會決定沿著這條痕跡前進。覓食的螞蟻會在其路徑上留下信息素。當它找到食物來源時，它會返回巢穴并加強其痕跡。因此，其他螞蟻有更大的可能性開始跟隨這條痕跡，從而在其上留下更多的信息素。這個過程就像一個正反饋循環(huán)系統(tǒng)，因為一條痕跡上的信息素濃度越高，螞蟻開始沿著它旅行的可能性就越大。AI:SI23螞蟻如何找到最短路徑？這個過程就像一個正反饋循環(huán)系統(tǒng)，因為一條痕跡上的信息素濃度越高，螞蟻開始沿著它旅行的可能性就越大。B路上的信息素濃度將以比A路更高的速度增加，很快A路上的螞蟻將選擇跟隨B路。由于大多數(shù)螞蟻將不再走A路，并且由于信息素是易揮發(fā)的，A路上的痕跡將開始蒸發(fā)。只有最短的路線將保留下來！AI:SI24螞蟻群優(yōu)化模型每只人工螞蟻都是一個概率機制，用于構建問題的解決方案，使用以下方法：人工信息素沉積啟發(fā)式信息：信息素痕跡等真實螞蟻與人工螞蟻之間的區(qū)別：信息素只在構建出解決方案后才更新。其他機制AI:ANN25螞蟻群優(yōu)化模型構造螞蟻解決方案解決方案組件的隨機選擇規(guī)則。更新信息素用于增加與良好或有前途的解決方案相關聯(lián)的信息素值，并減少與不良解決方案相關聯(lián)的信息素值。通過信息素蒸發(fā)減少所有信息素值-->允許“遺忘”->有利于探索新區(qū)域增加與一組選定的良好解決方案相關聯(lián)的信息素水平-->使算法收斂到解決方案AI:ANN26蟻群系統(tǒng)（AS）：第一個蟻群優(yōu)化算法構造螞蟻解決方案

信息素的數(shù)量啟發(fā)式距離α、β常數(shù)AI:ANN27蟻群系統(tǒng)（AS）更新信息素蒸發(fā)率每只螞蟻在邊(i,j)上留下的信息素AI:ANN28對于旅行推銷員問題(TSP)的蟻群系統(tǒng)(AS)初始化將每只螞蟻放置在隨機選擇的城市中為每個螞蟻選擇下一個城市更多的城市需要訪問遍歷每只螞蟻返回初始城市使用每個螞蟻的旅行成本更新信息素水平打印最佳旅行yesNo停止準則yesNoB.Ombuki-Berman之后的流程圖：群體智能AI:ANN29TSP的簡單示例（4個城市）圖片來自OlleGallmo：群體智能AI:ANN30AS的擴展蟻群系統(tǒng)傾向于快速收斂這意味著它對找到的最佳解的利用程度太高，它應該更多地探索解空間信息素蒸發(fā)/更新規(guī)則（可能存在更好的規(guī)則）蟻群系統(tǒng)的擴展蟻群系統(tǒng)的精英策略(EAS)基于排名的蟻群系統(tǒng)(RANK)MAX-MIN蟻群系統(tǒng)(MMAS)蟻群系統(tǒng)(ACS)AI:ANN31PartⅢ:粒子群優(yōu)化算法(PSO)“再次，大自然為我們提供了一種處理信息的方法，既優(yōu)雅又靈活”AI:ANN32鳥群飛行在粒子群優(yōu)化中，“群”被定義為一組看似無序的移動個體集合，這些個體傾向于聚集在一起，而每個個體似乎都朝著隨機的方向移動。鳥群飛行是粒子群優(yōu)化在自然界中的最好例子之一。AI:ANN33鳥群飛行的建模鳥群飛行的同步性被認為是一種功能，鳥類努力保持自己與鄰居之間的最佳距離。鳥類和魚類通過調(diào)整自身的物理運動來避免捕食者、尋找食物和配偶。人類傾向于調(diào)整自己的信仰和態(tài)度，以符合社會同齡人的信仰和態(tài)度。人類在抽象的多維空間中自由變化。AI:ANN34從鳥類到粒子想象一個鳥群在一個只有一個食物源的區(qū)域。一只鳥不知道食物在哪里，但它知道它與食物的距離。最好的策略是跟隨離食物更近的鳥。粒子保存和傳播它們找到的最佳解決方案。AI:ANN35粒子群優(yōu)化的特點通過分配隨機位置和速度進行種群初始化；然后讓潛在的解通過超空間飛行。每個粒子跟蹤其在超空間中的“最佳”（最高適應度）位置。這被稱為個體粒子的“pBest”它被稱為種群中的“gBest”它被稱為定義鄰域中的“l(fā)Best”在每個時間步，每個粒子隨機地加速向其pBest和gBest（或lBest）移動。AI:ANN36粒子群優(yōu)化過程步驟1.在超空間中初始化種群。步驟2.評估個體粒子的適應度。步驟3.根據(jù)先前的最佳和全局（或鄰域）最佳修改速度。步驟4.根據(jù)某些條件終止。步驟5.轉到步驟2。AI:ANN37粒子是如何飛行的？gBest和pBest（lBest）的組合lBest可以是：社會性：周圍的粒子總是相同的，無論它們在空間中的位置如何地理性：周圍的粒子是距離最短的那些粒子全局PSO與局部PSOAI:ANN38粒子群優(yōu)化速度更新方程全局版本：其中k是維度，c1和c2是正的常數(shù)，rand()是隨機函數(shù)，w是慣性權重。對于鄰域版本，將pgk更改為plk。AI:ANN39全局PSO的速度更新方案。AI:ANN40PSO：相關問題控制速度（確定Vmax的最佳值）通常將最大速度設置為變量的動態(tài)范圍通常將c1和c2設置為2慣性權重影響全局和局部探索之間的權衡。好的方法是在運行過程中減小慣性權重（例如，在1000代中從0.9減小到0.4）。群集大小和鄰域大小。AI:ANN41PSO的優(yōu)點適應操作在速度上進行大多數(shù)其他方法在位置上進行操作。效果：PSO具有內(nèi)置的動力。粒子傾向于跳過最優(yōu)解-這是一個優(yōu)勢，因為無論如何都會記住最好的位置。概念簡單易于實現(xiàn)計算效率高對各種問題有效AI:ANN42PSO的一個應用-圖像注釋細化PSO用于優(yōu)化反饋神經(jīng)網(wǎng)絡，以結合關鍵詞之間的相似度測量。AI:ANN43PSO的一個應用-圖像注釋細化總結AI:Summary45理解并創(chuàng)造智能實體兩種觀點:弱AI(圖靈測試);強AI(中文屋實驗)六種途徑:符號智能；人工神經(jīng)網(wǎng)絡;機器學習;行為智能;進化計算;群智能。AI:Summary46S.J.RusselllandP.Norvig,“artificialintelligence:amodernapproach”.具有學習能力的智能系統(tǒng)的架構AI:Summary47大綱路線圖1:學習-神經(jīng)網(wǎng)絡-行為智能路線圖2:搜索-圖搜索-進化計算學習學習意味著變化AI:Summary49AI:MachineLearning49定義學習任務基于經(jīng)驗，根據(jù)性能準則，提升完成相應任務的性能任務:下跳棋性能:對于任意對手，取勝的概率

經(jīng)驗:以自己為對手，進行的練習任務:識別手寫字性能:被正確分類的字所占的比例經(jīng)驗:經(jīng)過人工標注的手寫字的數(shù)據(jù)庫任務:視覺傳感器自動駕駛性能:出錯前行駛的平均距離經(jīng)驗:人類駕駛的時候記錄下來的一系列圖像和對應控制命令AI:Summary50AI:NouvelleAI50學習中的信息反饋類型監(jiān)督學習學習需要的輸入輸出對已經(jīng)給定或者可以推導得到。非監(jiān)督學習沒有輸出的信息強化學習智能體在環(huán)境中作出行動，對于智能體的每一步行動，都會得到一個評價值，但是不被告知如何行動才可以正確的達到目標。AI:Summary51學習的實質函數(shù)估計三個問題1.怎樣假設函數(shù)形式?2.怎樣設計學習目標?3.怎樣發(fā)現(xiàn)最優(yōu)函數(shù)?AI:Summary52AI:ANN521.1怎樣假設函數(shù)形式?-1

M-P神經(jīng)元θx1x2xnyω1ω2ωn輸入輸出閾值McClloch與Pitts，《神經(jīng)活動中固有的思想邏輯運算》,1943f:激活函數(shù)g:整合函數(shù)AI:Summary53AI:ANN53整合函數(shù)加權求和

徑向距離AI:Summary54AI:ANN54激活函數(shù)

閾值型線性飽和線性S型函數(shù)雙曲正切函數(shù)高斯函數(shù)AI:Summary55AI:ANN55前饋網(wǎng)絡的一般結構反饋網(wǎng)絡的一般結構AI:Summary56AI:ANN56單層感知器閾值激活函數(shù)輸出單元相互獨立,即沒有共享的權重Rosenblatt,1957AI:Summary57（0,0）（1,-0.5）（1,1.5）（2,0.5）

class1

class24.11設計一個感知器，用于區(qū)分兩類數(shù)據(jù)，其中第一類數(shù)據(jù)是（1,1.5）和（2,0.5），第二類數(shù)據(jù)是（0,0）和（1,-0.5）輸入1輸入2輸出11.5020.500011-0.51w1w2yx1x2AI:Summary58滿足以上約束（只是一種可能）-1-1yx1x2-1AI:Summary59AI:ANN59多層感知器(MLP)層與層之間通常是全連接的隱含層單元的個數(shù)通常手動選擇AI:Summary60監(jiān)督學習:-使實際輸出與期望輸出之間的誤差最小

(BP)-最大化信息增益(IG)(決策樹)

強化學習:

使長期的累積收益最大非監(jiān)督學習:

使數(shù)據(jù)與聚類之間的距離最小

(聚類)1.2怎樣設計學習目標?AI:Summary61r(state,action)即時獎勵值Q(state,action)valuesV*(state)values100

0

0

100

G

0

0

0

0

0

0

0

0

0

90

81100

G

0

81

72

90

81

81

72

90

81

100

G

90100081901001.3怎樣發(fā)現(xiàn)最優(yōu)函數(shù)?

使用累計折扣收益，折扣率=0.981=0+0.9*90Q-學習算法AI:Summary62Q值例:Hanoi塔AI:Summary63補充題：以下GridWorld中，除了到達目標狀態(tài)（G）的動作獲得的即時獎勵為10以外，其余動作對應的即時獎勵皆為0。如采用折扣系數(shù)為0.8的累積折扣收益，請計算圖中的Q函數(shù)值，直接標注在圖中。G1086.41086.486.41086.4搜索(最優(yōu)化)01AI:Summary65什么是搜索?以可以接受的計算代價，在問題所有解答中找出最優(yōu)解或可行解。理想的搜索算法：盡可能快地找到最優(yōu)解。求解的效果與效率之間存在矛盾-完備性,最優(yōu)性,復雜性-盲目vs.啟發(fā),局部

vs.全局,可行

vs.最優(yōu).AI:Summary66數(shù)學和計算機科學中的核心主題確定性搜索-圖搜索隨機和基于群體的搜索-進化計算-群智能啟發(fā)式搜索方法AI:Summary67用于問題求解圖搜索算法的一般結構是不斷擴展頂點，直到發(fā)現(xiàn)目標頂點（狀態(tài)空間）或者確定初始頂點的可解性（與或圖）。).不同圖搜索算法的主要區(qū)別在于頂點的擴展順序不同。盲目搜索不考慮問題特性,包括廣度優(yōu)先搜索、深度優(yōu)先搜索、有界深度優(yōu)先搜索和迭代加深深度優(yōu)先搜索。啟發(fā)式搜索算法根據(jù)問題所提供的啟發(fā)式信息，用估價函數(shù)估計頂點的搜索效率，選擇估計效率最高的頂點進行擴展。2.1圖搜索AI:Summary68狀態(tài)空間vs.與/或圖狀態(tài)空間與/或圖AI:Summary692.5為什么采用與或圖表示法時，解決問題的答案對應于一個子圖，而不是一條路徑？答：因為與節(jié)點AI:Summary70A*算法是影響最大的，應用于狀態(tài)空間的啟發(fā)式搜索算法。它通過對估價函數(shù)施加一定約束，可以保證搜索到最優(yōu)解。可容許的啟發(fā)式函數(shù):如果對于每一個頂點n都有h(n)≤h*(n)，則該啟發(fā)式函數(shù)h(n)是可容許的。其中h*(n)表示從頂點n到目標頂點的最小代價。支配性:如果對于所有頂點都有

h2(n)≥h1(n)

，并且兩者都是可容許的，則h2

優(yōu)于h1,使用h2

搜索速度更快A*算法AI:Summary712.3請用狀態(tài)空間法求解農(nóng)夫過河問題，該問題是：一農(nóng)夫帶著一只狼、一只羊和一筐菜來到河邊，欲乘船到河對岸。但船太小，農(nóng)夫每次只能帶一樣東西過河。而在沒有農(nóng)夫看管的情況下，狼會吃羊，羊會吃菜。農(nóng)夫應該怎樣做，才能在沒有任何損失的情況下把所有東西帶到河對岸？2.13試用A*算法解決習題2.3中給出的農(nóng)夫過河問題。解：問題狀態(tài)表示為（a,b,c,d），其中a,b,c,d分別表示農(nóng)夫、狼，羊和菜的位置，1表示在左岸，0表示在右岸。則起始狀態(tài)為(1,1,1,1)，終止狀態(tài)為(0,0,0,0)。改變狀態(tài)的操作共八種，分別為：農(nóng)夫帶著{狼、羊、菜}從{左岸到右岸、右岸到左岸}。搜索路徑為：(1,1,1,1)

(0,1,0,1)

(1,1,0,1)

(0,0,0,1)

(1,0,1,1)

(0,0,1,0)

(1,0,1,0)

(0,0,0,0)

AI:Summary72h(x)=河左岸物體個數(shù)

或無窮大（≠人：狼、羊對應位不能相等；羊、菜對應位不能相等）(1,1,1,1)h=3f=3(0,0,1,1)h=∞f=∞(0,1,0,1)h=2f=3(0,1,1,0)h=∞f=∞(1,1,0,1)h=2f=4(0,0,0,1)h=1f=4(0,1,0,0)h=1f=4(1,0,0,1)h=∞f=∞(1,0,1,1)h=2f=6(1,1,0,0)h=∞f=∞(1,1,1,0)h=2f=6102345AI:Summary73(1,0,1,1)h=2f=6(0,0,1,0)h=1f=6(0,0,0,1)h=1f=6(1,0,1,0)h=1f=7(1,1,1,0)h=2f=8(0,0,0,0)h=0f=7h(x)=河左岸物體個數(shù)

或無窮大（≠人：狼、羊對應位不能相等；羊、菜對應位不能相等）續(xù)上圖6(1,0,0,1)h=∞f=∞7910(1,1,1,0)h=2f=68AI:Summary74博弈樹

表示博弈過程的數(shù)據(jù)結構

在想象對手是最強對手的情況下采取最好的行動，這在結構上表現(xiàn)為與或圖極大極小算法

-限制博弈樹的深度-評價博弈狀態(tài)-選擇移動到具有最高極大極小值的位置!α-β剪枝

在有界深度優(yōu)先搜索過程中，通過剪掉一些不必要的分枝達到提高搜索效率的目的。博弈搜索AI:Summary752.17極大極小搜索的思想基礎是什么？為什么博弈子樹的深度越深，計算機博弈水平越高？答：思想基礎是：假設對方為最強對手，在考慮對方每一步都作出最佳應對的情況下，也就是對自己最不利的情況下（極?。?，選擇能給自己帶來最大收益的一步（極大）。原因：子樹深度越深，表示思考的步數(shù)越多，從而能夠得到更好的結果。AI:Summary762.21設有如圖所示的一棵博弈樹，其中末一行的數(shù)字是葉頂點的靜態(tài)估值，請對該博弈樹作如下工作：用極小極大值法計算各節(jié)點的倒推值。利用-剪枝技術剪去不必要搜索的分枝。敘述剪枝發(fā)生在何處，即剪去了哪些分枝（在剪枝處用×在圖上做標記）。

AI:Summary77進化計算基于生物進化理論優(yōu)化行為—最優(yōu)解個體

–

解;適應度

–

目標;環(huán)境

–

問題EC的組成表示:個體和種群適應度估計:目標選擇:父代和子代基因操作:突變和/或重組初始化/終止條件2.2進化計算AI:Summary78AI:EC78進化算法構成tt+1突變重組繁殖選擇圖片來源IdaSprinkhuizen-Kuyper:Introductionto