人工智能入門 課件全套 劉峽壁 1.緒論、2.人工神經網(wǎng)絡與機器學習 -7 總結

人工智能入門γνωθισεαυτ?ν(認識你自己)AI:Introduction2AI:Introduction2大綱什么是人工智能(AI)?

什么是思考？人工機器能否以及是否應該達到自我思考的程度？人工智能發(fā)展簡史人工智能實現(xiàn)途徑AI:Introduction3PartⅠ:什么是人工智能？AI:Introduction4

“使真正的機器表現(xiàn)得像科幻電影中的那些機器一樣”--RussellBeale請仔細觀看視頻，思考什么是人工智能？人工智能是通過智能機器延伸、增強人類改造自然和治理社會能力的新興技術。AI:Introduction5“有多少專家，就會有多少種關于智能的說法.”

--R.J.Sternberg什么是人工智能？？AI:Introduction6

什么是人工智能？Perception行為能力問題求解能力推理能力學習能力社交能力創(chuàng)造力感知能力AI:Introduction7AI:Introduction7什么是人工智能？？理解并創(chuàng)造智能實體多學科交叉計算機科學，哲學

，心理學，語言學，神經學，……包含多個子領域認知科學，自然語言處理，機器學習，模式識別，計算機視覺，數(shù)據(jù)挖掘，……AI:Introduction8AI:Introduction8如何衡量機器是否具有智能？兩種觀點強調外在表現(xiàn)(弱人工智能)機器是否具有智能的行為?圖靈測試強調內在機制(強人工智能)機器是否真正在思考?J.R.Searle

的中文屋思想實驗AI:Introduction9AI:Introduction9圖靈測試機器如何表現(xiàn)出智能？圖靈(1950)《計算機器與智能》具有可操作性的機器智能測試:模擬試驗為了通過圖靈測試，需要突破人工智能中的許多重要問題，如知識表示，推理，自然語言理解，機器學習等AI:Introduction10AI:Introduction10中文屋實驗一個不懂中文的人呆在一間密閉的屋子里，他有一本記錄中文處理規(guī)則的書。屋外的測試者從門縫塞給他中文紙條。

他在書中查找處理這些中文語句的規(guī)則。

根據(jù)規(guī)則將一些中文字符抄在紙條上作為對相應語句的回答。

呆在屋內的人顯然不理解他所處理的中文。

所以，賽爾勒提出(1980):

-不存在具有理解能力的計算機程序

-賦予非生物機器以智能是語無倫次AI:Introduction11AI:Introduction11人工智能的目標遠期目標揭示人類智能的根本機理，用智能機器去模擬、延伸、擴展人類智能，實現(xiàn)腦力勞動的自動化近期目標制造智能機器,尤其是具有智能的計算機程序.提供輔助性的智能工具以幫助人們解決一些具體問題AI:Introduction12“智能”正在變得越來越流行：AI:Introduction13AI:Introduction13人工智能與計算機科學部分類似于數(shù)學與物理的關系

計算機科學關注信息處理的一般理論,并為實現(xiàn)人工智能提供計算工具,但是這些不是人工智能關注的重點.人工智能對于計算機科學的發(fā)展具有重大影響.

AI:Introduction14PartⅡ:人工智能發(fā)展簡史AI:Introduction15AI:Introduction15人工智能孕育期哲學

邏輯,推理方法,思維機器,學習的基礎,語言,理性數(shù)學

形式邏輯符號化,計算理論,可判定性,可處理性,概率經濟效用,決策論神經科學

思維活動的物質性心理學

感知,控制,實驗技術計算機科學

構造更快的計算機控制論

制造能夠隨著時間的推移最優(yōu)化其目標的系統(tǒng)語言學

知識表示，語法AI:Introduction16AI:Introduction16人工智能發(fā)展期1943 麥克洛奇和皮茲：大腦的布爾電路模型1950 圖靈的“計算機器與智能”1956達特茅斯會議：正式采用名稱“人工智能”1952-69 迅速發(fā)展，過于樂觀1950s 早期的人工智能程序，包括塞繆爾的西洋跳棋程序，Newell 和Simon的定理證明程序，Gelernter的幾何引擎1965魯賓遜歸結演繹推理1966-73 出現(xiàn)了計算復雜性問題，神經網(wǎng)絡的研究處于停滯等

1969-79 專家系統(tǒng)的早期開發(fā)1980- 人工智能走向實際應用1986- 神經網(wǎng)絡再次流行1987- 人工智能變成一門科學1995- 智能體概念的出現(xiàn)AI:Introduction17AI:Introduction17人工智能現(xiàn)狀深藍在1997年打敗了世界棋王卡斯帕洛夫證明了十幾年來未能解決的一個數(shù)學猜想（Robbins猜想）橫跨美國的汽車無人駕駛（從匹茨堡到圣地亞哥的路途中，98%的路程為自動駕駛）1991年海灣戰(zhàn)爭期間,美國軍方運用人工智能規(guī)劃程序實現(xiàn)后勤保障，涉及50000輛車輛以及人員NASA通過自動規(guī)劃程序控制宇航器的飛行PROVERB程序能比大多數(shù)人類更好地解決字謎游戲AI:Introduction18AI:Introduction18真實的故事DavidCohn：“雖然計算機已經能夠打敗世界上最好的棋手，我們卻仍然不能使其像4歲小孩一樣去思考?！?/p>

AaronSlomon：“我們現(xiàn)在才剛剛開始明白怎樣用機器處理信息，智能是什么，以及我們人類是什么?！?/p>

何不馬上開始人工智能探險之旅呢？AI:Introduction19AI:Introduction19PartⅢ:人工智能的實現(xiàn)途徑AI:Introduction20AI:Introduction20機器學習

“嬰兒機器”符號智能神經網(wǎng)絡行為智能進化計算

”人造生命”群智能人工智能的實現(xiàn)途徑AI:Introduction21AI:Introduction21機器學習Q.制造一個“嬰兒機器”，它通過讀書學習、從經驗中學習等手段逐步增長智力，這個想法如何？人們早在20世紀40年代就提出了這個設想，最終它將會得到實現(xiàn)。

但是就目前而言，人們對人類學習機理、方法以及如何實現(xiàn)等問題的認識還處于非常初級的階段，就連“嬰兒是如何從經驗中進行學習”的問題都知之甚少，更遑論其他。--JohnMcCarthyAI:Introduction22AI:Introduction22符號智能紐維爾和西蒙的“物理符號系統(tǒng)假說”機器對符號信息的處理就足以產生人工智能.人類智能的基礎是對符號信息的處理.目前，“物理符號系統(tǒng)假說”是否成立仍然是一個有爭議的問題.自上而下的人工智能實現(xiàn)策略AI:Introduction23AI:Introduction23問題求解

專家系統(tǒng)

知識工程搜索,表示,推理GPS,深藍,DENDRAL,CYC,……問題框架問題(CYC,Go,……)用大量的計算來代替理解符號智能AI:Introduction24AI:Introduction24神經網(wǎng)絡人類大腦的工作機制與機器有很大的不同大腦如何工作？

自下而上的人工智能實現(xiàn)策略生物神經網(wǎng)絡AI:Introduction25AI:Introduction25發(fā)展簡史

M-P神經元模型

感知器

霍普菲爾德網(wǎng)絡模型,B-P學習方法(Rumelhart&McClelland)

應用

識別,視覺,商業(yè),醫(yī)學,…….主要問題

-拓撲結構-學習方法神經網(wǎng)絡AI:Introduction26AI:Introduction26行為智能布魯克斯(1991)<<沒有表示的智能>>

機器蟲:艾倫(Allen),赫伯特(Herbert),成吉思(Genghis)-智能的基本構造單元是一些非常簡單的行為，更為復雜的行為是通過這些簡單行為的相互作用產生的。-首先應制造具有昆蟲一類低等生物智能水平的系統(tǒng)。

AI:Introduction27現(xiàn)場式人工智能

-構造不能與外界友好交互的無實體智能系統(tǒng)(traditional)-構造在真實環(huán)境中活動的智能系統(tǒng)(Nouvelle).

行為智能AI:Introduction28AI:Introduction28進化計算生物進化

-產生大量能夠適應不同環(huán)境的各種生物物種.

模擬進化

-在計算機上模擬生物進化過程,可以讓計算機通過進化的方式找到問題的解答。

AI:Introduction29AI:Introduction29遺傳算法

像DNA中的分子串一樣，用符號串編碼問題的解決方案。通過符號串的突變和重組找到好的解。

進化策略

用解的原始形式表示個體,主要用突變和選擇作為搜索算子，其中突變通常通過對問題的解向量進行正態(tài)隨機擾動實現(xiàn)；選擇則是按適應度排序方式進行.進化規(guī)劃

與進化策略很難區(qū)分。主要區(qū)別是僅利用重組實現(xiàn)解的改變。它將每個個體看做一個物種，而不是同一物種中的不同個體，因此每個父代個體產生一個子代個體。進化計算AI:Introduction30AI:Introduction30群智能智能經常被認為是單個個體的行為。是因為我們有智慧所以組成社會呢？還是因為我們存在于社會中所以有智慧呢？-智能可以在社交活動中呈現(xiàn)出來.突現(xiàn)行為

–

一個群體所表現(xiàn)出來的在其個體身上看不到的行為.群智能-模擬生物間的社會交往-由一組簡單智能體呈現(xiàn)出來的集體智慧AI:Introduction31群智能AI:Introduction32觀察鳥群和魚群能夠以和諧的方式一起運動，但其中沒有指揮員(領導)-是什么決定了沒有領導的群體的行為？蟻群能夠快速找到從它們的巢穴到食物源的最短路徑-同時還能處理許多復雜問題，如:維持城堡，修建巢穴，清理巢穴，進行重物的搬運，等等-單個螞蟻實際上是在進行盲目地、無記憶地隨機行走！無中央控制的分布式系統(tǒng)不僅有助于模擬，而且有助于解決優(yōu)化問題。AI:Introduction33AI:Introduction33群智能計算工具多智能體系統(tǒng)多個相互作用的智能體組成的系統(tǒng).應用于電腦游戲,網(wǎng)絡,交通,物流,等等。蟻群優(yōu)化算法1991(Dorigo)主要用于組合優(yōu)化問題粒子群優(yōu)化算法1995(Kennedy&Eberhart)更通用的優(yōu)化技術人工神經網(wǎng)絡與機器學習AI:ANN35大綱什么是人工神經網(wǎng)絡(ANN)?

多層感知器(MLP)-誤差反向傳播算法(B-P)機器學習的意義-學習策略監(jiān)督學習1、人工神經網(wǎng)絡01AI:ANN37PartⅠ:什么是ANN?AI:ANN38一個讓汽車學習自動駕駛的神經網(wǎng)絡T.M.Mitchell,MachineLearning,2006隱藏單元的權值AI:ANN39汽車自動駕駛的視頻AI:ANN401.1人工神經網(wǎng)絡將相互獨立的單元之間連接起來形成一種圖的結構，這樣的圖可能是有環(huán)的也可能是無環(huán)的，可能是有向圖也可能是無向圖.

自底向上AI

受生物神經系統(tǒng)的啟發(fā)，從結構上模擬仿真AI功能AI:ANN41生物神經系統(tǒng)

時間和空間上的累積

興奮和抑制圖片來源：http://kvhs.nbed.nb.ca/gallant/biology/neuron_structure.jpgAI:ANN42人工神經系統(tǒng)

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

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

閾值型線性飽和線性S型函數(shù)雙曲正切函數(shù)高斯函數(shù)AI:ANN451.2人工神經網(wǎng)絡拓撲結構前饋型神經網(wǎng)絡-沒有環(huán)-靜態(tài)結構

反饋型神經網(wǎng)絡結構-有環(huán)-動態(tài)結構(非線性動力系統(tǒng))AI:ANN46前饋網(wǎng)絡的一般結構反饋網(wǎng)絡的一般結構AI:ANN471.3人工神經網(wǎng)絡的學習方法神經網(wǎng)絡根據(jù)所處環(huán)境對它的刺激自適應的調整其網(wǎng)絡結構中的自由參數(shù).學習模型

漸進式vs.批處理兩類

監(jiān)督型vs.非監(jiān)督型AI:ANN48重要的神經網(wǎng)絡模型模型結構學習方法模型結構學習方法多層感知器前饋型網(wǎng)絡結構誤差修正玻爾茲曼機單層，反饋型網(wǎng)絡結構隨機性徑向基函數(shù)網(wǎng)絡多層，前饋型網(wǎng)絡結構誤差修正自適應共振理論兩層，反饋型網(wǎng)絡結構競爭型學習霍普菲爾德網(wǎng)絡單層，反饋型網(wǎng)絡結構外積Kohonen自組織特征映射網(wǎng)單層軟競爭學習AI:ANN49PartⅡ:多層感知器(MLP)AI:ANN502.1B-P神經網(wǎng)絡結構

一種多層感知機,其中的激活函數(shù)采用S型函數(shù).AI:ANN51B-P學習算法學習方法

-輸入數(shù)據(jù)被前向輸入到隱含層,然后再輸入到輸出層

-誤差信息被反向傳播，從輸出層到隱含層再到輸入層Rumelhart&Meclelland,Nature,1986AI:ANN52B-P學習步驟Step1.在訓練集中選擇一種模式并將其輸入到網(wǎng)絡中Step2.計算輸入序列中輸入層，隱含層，輸出層神經元的激活情況.Step3.通過比較實際輸出與期望輸出，計算輸出神經元的誤差.Step4.用計算出來的誤差更新網(wǎng)絡中的所有權重，從而使全局誤差度量變小.Step5.重復上述Step1-Step5直到全局誤差小于一個給定的閾值.AI:ANN53B-P求導全局誤差度量理想輸出實際輸出平方誤差目標是最小化平方誤差,即達到最小均方誤差(MSE)2、機器學習02AI:MachineLearning55PartⅠ:機器學習的意義

AI:MachineLearning56機器學習什么？學習是系統(tǒng)中的變化，這種變化使系統(tǒng)在重復同樣工作或類似工作時，能夠做得更好。

西蒙機器學習研究如何使計算機程序自動根據(jù)經驗提升其性能。應用領域涵蓋從大量數(shù)據(jù)中發(fā)現(xiàn)一般規(guī)則的數(shù)據(jù)挖掘程序到自動學習用戶興趣的信息過濾系統(tǒng)等。TomM.MitchellAI:MachineLearning57定義學習的任務基于經驗，根據(jù)性能準則，提升完成相應任務的性能任務:下跳棋性能:對于任意對手，取勝的概率

經驗:以自己為對手，進行的練習任務:識別手寫字性能:被正確分類的字所占的比例經驗:經過人工標注的手寫字的數(shù)據(jù)庫任務:視覺傳感器自動駕駛性能:出錯前行駛的平均距離經驗:人類駕駛的時候記錄下來的一系列圖像和控制命令ExamplesAI:MachineLearning58為什么要進行機器學習？在環(huán)境事先未知時，學習至關重要(可用于開發(fā)能夠自動適應環(huán)境的系統(tǒng)). 比如，當設計者缺少關于環(huán)境的全部信息時學習是一個很有用的系統(tǒng)構建方法(可用于構建人工方式很難實現(xiàn)或者很昂貴的系統(tǒng)).比如,將系統(tǒng)暴露在真實的環(huán)境中自我提升而不是直接構建該系統(tǒng)。AI:MachineLearning59為什么要進行機器學習？（續(xù)）從龐大的數(shù)據(jù)庫里發(fā)掘新信息(數(shù)據(jù)挖掘)。商場購物數(shù)據(jù)分析(如：尿布和啤酒)醫(yī)學文本挖掘(如：偏頭痛和鈣)對于機器學習的研究可以幫助我們理解人類以及其他生物的學習方式。AI:MachineLearning60學習系統(tǒng)的評價實驗在不同的基準數(shù)據(jù)集上，采用交叉驗證試驗來比較各種不同的方法。收集評價系統(tǒng)性能的數(shù)據(jù)，如測試準確率、訓練時間、測試時間等。分析方法在統(tǒng)計顯著性上的不同。理論從數(shù)學上分析算法，為以下幾點提供理論支持：計算復雜性擬合訓練數(shù)據(jù)的能力樣本復雜性(得到一個準確的函數(shù)所需要的訓練數(shù)據(jù)的個數(shù))AI:MachineLearning61S.J.RusselllandP.Norvig,“artificialintelligence:amodernapproach”.具有學習能力的智能系統(tǒng)的架構AI:MachineLearning62學習機構學習機構的設計需要考慮：學習性能組件中的什么部分可利用什么反饋方式來學習這些部分怎樣表示性能組件？反饋類型: 監(jiān)督學習:每一個輸入數(shù)據(jù)都有對應的期望輸出非監(jiān)督學習:沒有輸入數(shù)據(jù)的期望輸出強化學習:通過獎懲學習AI:MachineLearning63學習策略機械式學習

基于存儲的學習指導式學習

將外部指導者提供的知識形式轉化為可供執(zhí)行機構直接使用的知識形式類比學習

利用不同領域知識的相似性AI:MachineLearning64學習策略（續(xù)）解釋學習

演繹和歸納相結合歸納學習

1.人工神經網(wǎng)絡

2.統(tǒng)計學習

3.決策樹

4.聚類

監(jiān)督非監(jiān)督AI:MachineLearning65機械式學習學習==存儲？存儲問題的解，當遇到相同的問題時進行檢索。存儲和計算的權衡AI:MachineLearning66PartⅡ:監(jiān)督學習AI:MachineLearning672.1什么是監(jiān)督學習？最簡單的形式:根據(jù)輸入數(shù)據(jù)學習一個函數(shù)f

是目標函數(shù)

一個數(shù)據(jù)是一個(x,f(x))對

問題:給定一個訓練數(shù)據(jù)集，找到一個函數(shù)h，以使

h≈fAI:MachineLearning68監(jiān)督學習方法構造

h，使h在訓練數(shù)據(jù)集上與f

吻合(如果對于所有的數(shù)據(jù)，h都與f吻合，則h與f是一致的。)如：

曲線擬合:AI:MachineLearning69監(jiān)督學習方法構造

h，使h在訓練數(shù)據(jù)集上與f

吻合(如果對于所有的數(shù)據(jù)，h都與f吻合，則h與f是一致的。)如：

曲線擬合:AI:MachineLearning70監(jiān)督學習方法構造

h，使h在訓練數(shù)據(jù)集上與f

吻合(如果對于所有的數(shù)據(jù)，h都與f吻合，則h與f是一致的。)如：

曲線擬合:AI:MachineLearning71監(jiān)督學習方法構造

h，使h在訓練數(shù)據(jù)集上與f

吻合(如果對于所有的數(shù)據(jù)，h都與f吻合，則h與f是一致的。)如：

曲線擬合:AI:MachineLearning72監(jiān)督學習方法構造

h，使h在訓練數(shù)據(jù)集上與f

吻合(如果對于所有的數(shù)據(jù)，h都與f吻合，則h與f是一致的。)如：

曲線擬合:AI:MachineLearning73監(jiān)督學習方法構造

h，使h在訓練數(shù)據(jù)集上與f

吻合(如果對于所有的數(shù)據(jù)，h都與f吻合，則h與f是一致的。)如：

曲線擬合:奧坎木剃刀:優(yōu)先選擇符合數(shù)據(jù)的最簡單模型AI:MachineLearning74PartⅢ:非監(jiān)督學習：聚類AI:MachineLearning754.1什么是聚類？典型的非監(jiān)督學習只給出輸入數(shù)據(jù)，不給出期待的輸出根據(jù)數(shù)據(jù)之間的相似性，將數(shù)據(jù)分成幾個簇的過程。發(fā)現(xiàn)數(shù)據(jù)組并鑒別出數(shù)據(jù)中令人感興趣的數(shù)據(jù)分布AI:MachineLearning764.2劃分聚類方法根據(jù)給定的標準，把數(shù)據(jù)集劃分成k個子集（簇）。在所有可能的劃分中搜索最優(yōu)的劃分。

盲目搜索

啟發(fā)式搜索

AI:MachineLearning77總結學習是一個系統(tǒng)通過經驗來提高性能的過程。有學習能力的智能系統(tǒng)的四個要素：

評價機構,環(huán)境機構,執(zhí)行機構,學習機構AI:MachineLearning78學習策略包括機械式學習，指導式學習，類比學習，歸納學習，解釋學習。機械式學習存儲問題描述及其對應的正確解，當需要的時候進行檢索。AI:MachineLearning79監(jiān)督學習中，從輸入—輸出數(shù)據(jù)對中學習得到一個函數(shù)。

AI:MachineLearning80非監(jiān)督學習中，只有輸入數(shù)據(jù)，沒有輸入數(shù)據(jù)的期望輸出信息。聚類分析是按照數(shù)據(jù)間的相似性，對數(shù)據(jù)集進行分類的過程。劃分聚類和層次聚類是兩個基本策略。搜索與問題求解AI:SearchandProblemSolving82大綱什么是搜索?問題表示–狀態(tài)空間與與或圖

–

它們體現(xiàn)了兩種問題求解的思路!博弈搜索–極大極小算法–α-β剪枝AI:SearchandProblemSolving83PartⅠ:什么是搜索?AI:SearchandProblemSolving84Theseus怎樣找到逃出Minotaur的迷宮的路?Ariadne的線索:AI:SearchandProblemSolving85什么是搜索?以可以接受的計算代價，在問題所有解答中找出最優(yōu)解或可行解。理想的搜索算法：盡可能快地找到最優(yōu)解.求解的效果與效率之間存在矛盾完備性,最優(yōu)性,復雜性AI:SearchandProblemSolving86PartⅡ:問題表示AI:SearchandProblemSolving87例子:2-階梵塔問題初始狀態(tài)目標狀態(tài)1目標狀態(tài)2規(guī)則:1.每次移動一個金片2.大的金片不能放在小的金片上面.AI:SearchandProblemSolving88步驟1表示所有的狀態(tài),包括初始狀態(tài)和目標狀態(tài)初始狀態(tài)目標狀態(tài)步驟2表示狀態(tài)轉換函數(shù)AI:SearchandProblemSolving89將金片A從柱i移動到柱

j

將金片B從柱i移動到柱

j

所有函數(shù):步驟3構造狀態(tài)空間AI:SearchandProblemSolving90步驟4

搜索該圖以找到問題解答AI:SearchandProblemSolving912.1狀態(tài)空間S:狀態(tài)集合F:狀態(tài)轉換函數(shù)（或行動）的集合

C:狀態(tài)轉換函數(shù)代價的集合(如果不求最優(yōu)解，可以不考慮此因素)I:初始狀態(tài)集合G:目標狀態(tài)集合一個狀態(tài)空間對應于一個圖,其中從初始狀態(tài)到目標狀態(tài)的路徑就是問題的一個解。AI:SearchandProblemSolving92基于狀態(tài)空間的問題求解步驟1

表示所有狀態(tài)，標出其中的初始狀態(tài)和目標狀態(tài).步驟2

表示所有狀態(tài)轉換函數(shù)步驟3

以狀態(tài)為節(jié)點，以狀態(tài)轉換函數(shù)為邊，構成一個圖。步驟4

搜索該圖以發(fā)現(xiàn)對應于最優(yōu)解或可行解的路徑。AI:SearchandProblemSolving93例子:八數(shù)碼問題狀態(tài)?

動作?

初始與目標狀態(tài)?

動作代價?

AI:SearchandProblemSolving94例子:八數(shù)碼問題狀態(tài)?

數(shù)字與空格的位置動作?

空格上、下、左、右移動初始與目標狀態(tài)?

如圖動作代價?

每移動一下代價為1AI:SearchandProblemSolving95與或圖實現(xiàn)問題歸約的數(shù)據(jù)結構-每一個節(jié)點對應于一個問題-“與”節(jié)點=分解-“或”節(jié)點=轉換-端節(jié)點*終止節(jié)點=本原問題*其他端節(jié)點=不可解問題-可解節(jié)點與不可解節(jié)點

AI:SearchandProblemSolving96基于與或圖的問題求解找出一個解圖，它是代表原始問題求解方案的一個子圖步驟1.表示每個問題。步驟2.對問題進行歸約，用與或圖表示歸約過程。步驟3.從端節(jié)點向上回溯，直到根節(jié)點，標注各個節(jié)點可解或不可解。步驟4.如果根節(jié)點被標注為可解，輸出相應的解圖。AI:SearchandProblemSolving97例子:3-階梵塔問題初始狀態(tài)目標狀態(tài)AI:SearchandProblemSolving98步驟1.表示問題

問題狀態(tài):

原始問題:(1,1,1)(3,3,3)步驟2.問題歸約

將原始問題分解為:-子問題1=(1,1,1)(1,2,2)-子問題2=(1,2,2)(3,2,2)√-子問題3=(3,2,2)(3,3,3)

繼續(xù)分解子問題2和3

AI:SearchandProblemSolving99步驟3.搜索該圖，以決定根節(jié)點可解或不可解.步驟4.輸出整個圖作為解答.(如何解釋?)AI:SearchandProblemSolving100PartⅣ:博弈搜索圖片來自：/DL88250AI:SearchandProblemSolving1013.1博弈樹代表博弈過程的數(shù)據(jù)結構

-2個玩家(MAX和MIN)-確定性的-輪流進行-零和的-信息完備AI:SearchandProblemSolving102游戲狀態(tài)：(K1,K2,….,Kn,MINorMAX)每堆錢幣個數(shù)當前走步方每次MIN或MAX選擇一堆錢幣并且把它分成數(shù)目不等的兩堆。

當MIN或MAX不能完成任務時,就輸了。

首先,n=1,k1=7,MIN為走步方例：分錢幣游戲AI:SearchandProblemSolving103(7,MIN)(6,1,MAX)(5,2,MAX)(4,3,MAX)(5,1,1,MIN)(4,2,1,MIN)(3,2,2,MIN)(3,3,1,MIN)(4,1,1,1,MAX)(3,2,1,1,MAX)(2,2,2,1,MAX)(3,1,1,1,1,MIN)(2,2,1,1,1,MIN)(2,1,1,1,1,1,MAX)分錢幣游戲的博弈樹MAX的必勝招?AI:SearchandProblemSolving104游戲中的每一步MAX

和

MIN

總是采取對自己最有利的行動。為了能夠勝利,MAX應該每一步選擇最有利的行動,同時認為

MIN

也會每一步都采取對MIN最好的行動(也就是說，對MAX最壞)

在想象對手為最強對手的情況下采取最好的行動！在結構上，博弈樹是與或圖！AI:SearchandProblemSolving105(7,MIN)(6,1,MAX)(5,2,MAX)(4,3,MAX)(5,1,1,MIN)(4,2,1,MIN)(3,2,2,MIN)(3,3,1,MIN)(4,1,1,1,MAX)(3,2,1,1,MAX)(2,2,2,1,MAX)(3,1,1,1,1,MIN)(2,2,1,1,1,MIN)(2,1,1,1,1,1,MAX)作為與或圖進行搜索作為與或圖進行搜索?AI:SearchandProblemSolving106

實際條件的限制

如中國象棋:共有

10160

種狀態(tài)。假設每秒搜索

103

個節(jié)點，需要

10145

年找到一個最優(yōu)走步。(最新估計宇宙年齡為

1010年)解決辦法

截斷策略:限制博弈樹的搜索深度

估價函數(shù):從MAX的角度出發(fā)估計博弈狀態(tài)，值越大，該狀態(tài)對MAX越有利。

3.2極大極小搜索AI:SearchandProblemSolving107選擇移動到具有最高極大極小值的位置!例：兩個玩家的游戲AI:SearchandProblemSolving108例:一字棋估價函數(shù):e(P)=e(+P)－e(-P)

對于對稱狀態(tài)只存儲其中一種e(P)＝6-4＝2AI:SearchandProblemSolving109MAX第一次走步AI:SearchandProblemSolving110MAX第二次走步AI:SearchandProblemSolving111最后狀態(tài)AI:SearchandProblemSolving1123.3α-β剪枝通過剪掉博弈樹中不必要的分支提高搜索的效率。使用深度限制搜索(DLS)策略AI:SearchandProblemSolving113α-β剪枝例1AI:SearchandProblemSolving114α-β剪枝例1AI:SearchandProblemSolving115α-β剪枝例1AI:SearchandProblemSolving116α-β剪枝例1AI:SearchandProblemSolving117α-β剪枝例1α-β剪枝例2AI:SearchandProblemSolving118S0ABCDFGHEIJKLMNPQRS4861580-64≥4≤1≤4＝45≥5＝4≥4≤0≥0＝0≤-6＝0≤0＝4＊＊＊＊＊＊AI:SearchandProblemSolving119什么是α-β?α

是MAX頂點倒推值的最小邊界如果

v

比α更小,MAX將不搜索它。

剪掉這一枝β

定義方式類似，但針對MIN節(jié)點AI:SearchandProblemSolving120確定性博弈程序現(xiàn)狀

西洋跳棋:1994年，Chinook終結了人類世界冠軍MarionTinsley長達40年的統(tǒng)治。

國際象棋:1997年，DeepBlue在六回合制比賽中打敗了人類世界冠軍GarryKasparov.

黑白棋:人類高手拒絕與機器比賽，因為機器下棋水平實在是太好了。

圍棋:人類高手同樣拒絕與機器比賽，因為機器下棋水平實在是太差了。AI:SearchandProblemSolving121深藍AI:SearchandProblemSolving122總結狀態(tài)空間-五個要素(S,F,C,I,G)-問題的解是從初始頂點到目標頂點的一條路徑與或圖-問題規(guī)約

-目標是確定根節(jié)點是否可解-問題的解是讓根節(jié)點可解的一個子圖AI:SearchandProblemSolving123搜索算法的效果和效率是一對矛盾。在設計和評價搜索算法時，需要綜合考慮算法的完備性、最優(yōu)性和復雜性。具體設計策略有盲目搜索與啟發(fā)式搜索之分，全局搜索和局部搜索之分，以及搜索最優(yōu)解和可行解之分。

圖搜索算法的一般結構是不斷擴展頂點，直到發(fā)現(xiàn)目標頂點（狀態(tài)空間）或者確定初始頂點的可解性（與或圖）?？偨YAI:SearchandProblemSolving124不同圖搜索算法的主要區(qū)別在于頂點的擴展順序不同。盲目搜索不考慮問題特性,包括廣度優(yōu)先搜索、深度優(yōu)先搜索、有界深度優(yōu)先搜索和迭代加深深度優(yōu)先搜索。啟發(fā)式搜索算法根據(jù)問題所提供的啟發(fā)式信息，用估價函數(shù)估計頂點的搜索效率，選擇估計效率最高的頂點進行擴展。A*算法是影響最大的，應用于狀態(tài)空間的啟發(fā)式搜索算法。它通過對估價函數(shù)施加一定約束，可以保證搜索到最優(yōu)解?？偨YAI:SearchandProblemSolving125博弈樹

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

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

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

在有界深度優(yōu)先搜索過程中，通過剪掉一些不必要的分枝達到提高搜索效率的目的?？偨Y進化計算01AI:EC127大綱生命對搜索方法的啟示什么是進化計算(EC)?進化算法(EA)遺傳算法進化規(guī)劃進化策略AI:EC128

一個啟發(fā)式搜索的新思路?進化計算確定還是隨機?若確實如此啟發(fā)式搜索（優(yōu)化）方法是數(shù)學和計算機科學的核心主題AI:EC129PartⅠ:生物對搜索的啟示AI:EC130Q.什么是搜索問題最好的解決方案?.人類的大腦

能產生“汽車,紐約,戰(zhàn)爭,等”

(afterDouglasAdams)

神經計算

.進化機制

導致人腦的產生(afterDarwinetal.)

進化計算

AI:EC131達爾文進化基于群體的進化，而非個體的變化適者生存:有限的資源導致激烈的競爭,那些能最有效的占有資源的個體(最適應環(huán)境的個體)有更高的概率被繁殖下去(被選擇)AI:EC132達爾文進化多樣性引起變化:如果表現(xiàn)特征:有更高的概率被繁殖下去可以繼承則他們往往會形成更多的后代，從而導致新的組合特征.

隨機性的作用最優(yōu)的解不一定都能生存下去AI:EC133自然遺傳學遺傳信息需要通過有機體的DNA編碼遺傳下去基因的微小變化導致生物體的微小變化(如身高,頭發(fā)，顏色)對于一個特定的物種，其遺傳物質是基本相同的AI:EC134基因和基因組由DNA鏈編碼的基因稱為染色體在大多數(shù)細胞中，有兩條染色體排成雙螺旋結構(diploidy)一個個體的全部遺傳物質的集合稱為基因組AI:EC135個體遺傳物質改變的主要手段:重組從至少兩個父代個體中獲得遺傳物質產生新的個體,如,在一對染色體的交叉點上連接交換染色體:

重組前

重組后圖片來源BenPaechter:EvolutionaryComputing–APracticalIntroductionAI:EC136個體遺傳物質改變的主要手段:突變一些遺傳物質會發(fā)生輕微的改變，這個過程偶爾發(fā)生這意味著子代個體可能擁有父代個體所沒有的遺傳物質這種改變極有可能是災難性的AI:EC137進化理論突變,重組

新的遺傳物質或者新的組合.繁殖的越多則基因的性能可以得到更多的改進

好的基因得到更多被遺傳的機會壞的基因則會在遺傳的過程中減少在其生存環(huán)境中，有機體作為一個整體得到進化.采用進化的方法計算或求解問題能夠幫助我們找到問題的最優(yōu)解：進化計算AI:EC138PartⅡ:什么是進化計算?AI:EC139以這樣的方式放置8皇后一個8x8的棋盤上，他們不能互相卡到對方，例子:8皇后問題

[AfterA.E.EibenandJ.E.Smith,IntroductiontoEvolutionaryComputing]

AI:E傳物質:

一列數(shù)字1-8表現(xiàn)特性:

一個棋局配置Obviousmapping8皇后問題:表示AI:EC141一個皇后的懲罰:

它能卡住的皇后個數(shù).

一種棋局的懲罰:

對每一個皇后的懲罰值求和.

目標:使得懲罰值最小

最優(yōu)棋局:

懲罰值的倒數(shù)最大時8皇后問題:適應度評價AI:EC142

突變:

交換兩個隨機選擇的點

(概率:80%)1234567812345678

重組:

交叉(概率:100%)876425311352467887645123135628748皇后問題:遺傳算子5432126478AI:EC143父代選擇:挑選五個父代個體，并選擇其中最優(yōu)的兩個執(zhí)行重組操作生存選擇(替換策略)當一個新的子代個體要插入種群中時，選擇種群中將被替換的一個個體，選擇規(guī)則為:將種群中的個體按適應度降序排列將個體由高到低列舉替換排列中第一個適應度比當前子代適應度低的個體8皇后問題:選擇AI:EC144初始化:隨機終止:根據(jù)適應度的評價問題得到了解決或者循環(huán)迭代次數(shù)達到最大（比如10，000）8皇后問題:初始化\終止條件AI:EC1458皇后問題:總結注意：操作和參數(shù)的選擇不只有這一種可能AI:EC146生物進化與搜索的類比進化個體適應度環(huán)境搜索候選解解的質量待求解的問題AI:EC147進化算法構成tt+1突變重組繁殖選擇圖片來源IdaSprinkhuizen-Kuyper:Introductionto

EvolutionaryComputation,2000.AI:EC148進化機制遺傳增加了多樣性突變重組選擇減少了多樣性父代選擇：選擇用于繁殖的父代子代選擇：選擇保留下來的子代AI:EC149進化中的循環(huán)過程重組突變種群子代父代父代選擇子代選擇圖片來源BenPaechter:EvolutionaryComputing–APracticalIntroductionAI:EC150表示基因表示:編碼:表型=>基因(不一定是一一對應的)解碼:基因=>表型(必須是一一對應的)表型表示:問題的特定編碼AI:EC151進化(適應度)函數(shù)表示對種群（解）的要求，即質量函數(shù)

或

目標函數(shù)為每一個表型計算一個代表其適應度的實數(shù)，這樣構成了遺傳選擇的基礎因此該函數(shù)的判斷能力越大越好AI:EC152基因操作產生新的候選解

通常根據(jù)父代個體數(shù)分為兩類:=1:突變操作>1:重組操作=2:交叉操作有很多關于重組和突變重要性的爭論現(xiàn)在大多數(shù)進化算法兩者都有AI:EC153父代選擇機制個體作為父代的概率是根據(jù)其適應度得出來的高質量的解有更高的概率被作為父代個體出現(xiàn)，但它并不是一定會作為父代個體出現(xiàn)，即使是種群中最差的個體也不是完全沒有機會作為父代個體出現(xiàn)這種隨機性可以在一定程度上避免陷入局部最優(yōu)解.AI:EC154子代選擇或稱為替換策略從子代+父代的種群中產生新的種群的方法兩種方法適應度準則

:例如挑選種群中一定數(shù)量適應度最好的個體作為新的種群年齡準則:

產生和父代個體一樣多的子代個體，淘汰所有的父代個體AI:EC155初始化/終止條件初始化

通常采用隨機初始化的策略。終止條件

檢查每一代種群個體，看以下條件是否滿足：

達到給定的或期望的適應度達到最大的種群更新次數(shù)種群中的多樣性水平最小連續(xù)幾代更新都沒有使得種群中的適應度得到改進AI:EC156PartⅢ:進化算法AI:EC157主要進化算法遺傳算法(GA)J.Holland1962(AnnArbor,MI)進化規(guī)劃(EP)L.Fogel1962(SanDiego,CA)進化策略(ES)I.Rechenberg&H.-P.Schwefel1965(Berlin)遺傳規(guī)劃(GP)J.Koza1989(PaloAlto,CA)算法之間的相似性比差異更重要AI:EC158分類圖片來源:Introductionto

EvolutionaryComputationbyIdaSprinkhuizen-KuyperAI:EC159技術總結GAEPESGP表示基因型表現(xiàn)型表現(xiàn)型基因型突變√√√√重組√×√√父代選擇概率選擇確定選擇概率選擇概率選擇子代選擇排斥,確定混合，隨機混合，確定排斥，確定AI:EC1603.1遺傳算法(GA)Holland最初提出的遺傳算法現(xiàn)在被稱作簡單遺傳算法(SGA)現(xiàn)在還常常被用作新的遺傳算法的測試基準其他遺傳算法可能應用不同的:表示方法突變方法交叉方法選擇機制AI:EC161表示基因組通常被用來表示候選解定長二進制編碼(SGA)Holland傳統(tǒng)的

其收斂性有理論上的保證實值基因組人工進化收斂性的證明很困難AI:EC162貪婪選擇:選擇適應度最好的解按概率選擇:概率與適應度成正比例如采用輪盤賭的方法(SGA)GA操作:選擇例如適應度為：(2200,1800,1200,950,400,100)AI:EC163GA操作:交叉對于給定的父代個體，交叉以特定的概率

Pc

1發(fā)生(Pc

的典型范圍為(0.6,0.9))否則父代個體直接作為子代個體(克隆)例如,A.One-pointcrossover(SGA)

B.Two-pointcrossover

圖片來源:IntroductiontoStochasticSearchandOptimization(ISSO)byJ.C.SpallAI:EC164GA操作:突變獨立地改變每一個基因的概率

pmpm稱為

突變概率典型值介于（1/種群規(guī)模）和（1/

染色體長度）之間例如AI:EC165應用例

[AfterA.L.Nelson]在一個由方格組成的棋盤上找到兩點間的最優(yōu)路徑該生物體:占據(jù)一個方格能夠移動到最近鄰的方格目標:在最短的步驟內從灰色方格移動到綠色方格AI:EC166基因組例如:通過一個方向符號串表示一條路徑.方向的表示:北=00,東=10,南=11,西=01AI:EC167種群種群P

由一系列個體pn組成，N表示種群中擁有的個體數(shù)目AI:EC168適應度函數(shù)和選擇策略適應度函數(shù)距離目標的最短合法路徑:F(pn)=S(steps)父代選擇:貪婪算法AI:EC169基因改變交叉:單點交叉突變:位串點突變AI:EC170實例方格尺寸:4X4種群中個體數(shù)目:N=4基因編碼:16bits適應度函數(shù):F(p)=距離目標的方格數(shù)選擇策略:貪婪算法AI:EC171實例：初始化種群初始化種群P(0):4個隨機的16位串AI:EC172實例：適應度計算F(p1)=(8-8)–4=-4F(p2)=-5F(p3)=-6F(p4)=-4AI:EC173實例：選擇和更新選擇p1

和

p4

作為父代個體通過交叉和重組產生子代個體AI:EC174實例：子代選擇新一代個體為：AI:EC175對子代個體重復前面的操作重復:F(p1)=-4F(p2)=-4

F(p3)=0F(p4)=-4AI:EC176總結進化計算基于生物進化機制優(yōu)化行為—最優(yōu)解個體

–

解;適應度

–

目標;環(huán)境

–

問題EC的組成表示:個體和種群適應度估計:目標選擇:父代和子代基因操作:突變和/或重組初始化/終止條件AI:EC177總結EC的主要特征:并行性和隨機性易于應用主流進化算法遺傳算法進化規(guī)劃進化策略遺傳規(guī)劃AI:EC178總結遺傳算法表示:位串(基因型)突變:位交換重組:交叉父代選擇:根據(jù)適應度大小按概率選擇子代選擇:完全取代行為智能01AI:NouvelleAI180大綱智能體-結構

?沒有表示和推理的智能

-學習強化學習-Q-學習AI:NouvelleAI181PartⅠ:智能體AI:NouvelleAI182機器人世界杯2008決賽

中國，蘇州到2050年，組建一個可以取勝人類足球冠軍隊的全自主機器人隊伍。

-AI:NouvelleAI183遠程智能體實驗(RAX)深空1號任務旨在驗證技術；讓AI軟件成為航天器的主要指揮官；1999年5月進行測試。

NANA,USa

AI:NouvelleAI1841.1智能體定義RussellandNorvig:“能夠通過傳感器感知環(huán)境并根據(jù)環(huán)境做出行動的任何系統(tǒng)”AI:NouvelleAI185智能體的弱概念五個主要特點:現(xiàn)場性:工作在某種環(huán)境中，并能與環(huán)境進行交互自主性:在不用干涉的情況下自主運行主動性:在自身目標驅動下表現(xiàn)出主動的行為反應性:能感知外界環(huán)境并根據(jù)環(huán)境變化做出適當反應社會性:以其他智能體進行通信AI:NouvelleAI1861.2單智能體結構慎思型智能體:符號化表示和處理-IRMA,GRATE反應型智能體:感知-行為模式智能體系統(tǒng)-包容結構-網(wǎng)絡結構混合型智能體:可以直接對外界刺激作出反應，也可以在內部推理的基礎上采取行動-過程推理系統(tǒng)（PRS）-圖靈機模型-InteRRaPAI:NouvelleAI1871.2.2反應型結構反應型結構不需要使用符號表示外部環(huán)境狀態(tài)，也不需要復雜的符號推理。包容結構網(wǎng)絡結構沒有表示和推理的智能AI:NouvelleAI188包容結構麻省理工大學智能研究所的布魯克斯基于包容結構構造了一些機器人。由任務導向的行為模塊構成高層模塊有更多特殊任務單獨構建各個模塊高層模塊對低層模塊起到一定的控制作用，但這種影響對于低層模塊是不可見的，高層模塊只在需要時插入來抑制低層模塊的行為。沒有明確的推理甚至沒有模式匹配.在構造的初期生成智能體函數(shù)AI:NouvelleAI189布魯克斯包容結構圖解不同的智能體并行構建，但是以分級的形式決策行為。高層智能體能夠抑制低層智能體的輸出，并且接管行為的控制(b)一種應用：腿部移動控制腿向上或向下腿向前或向后霍爾克·克魯斯（HolkCruse）：作為控制系統(tǒng)的神經網(wǎng)絡（第二版），2006年包容結構AI:NouvelleAI190MIT布魯克斯的機器人Genghis:過去在機器人實驗室.目前在Smithsonian航空博物館.Cog:類人智能需要類似人的與外界交互方式Herbert:一個基于互動的可以收集飲料瓶的機器人

Allen:機器人實驗室的第一個移動機器人./projects/humanoid-robotics-group/AI:NouvelleAI191網(wǎng)絡結構動作單元的集合各個動作單元根據(jù)內部需求和外部激勵，競爭對智能體行為的控制。外部激勵:環(huán)境條件內部需求:通過鏈式結構:激活模塊增加其后續(xù)模塊的興奮性未激活模塊增加其前面模塊的興奮性所有模塊抑制其他競爭者的興奮性AI:NouvelleAI192網(wǎng)絡結構目標:保持文雅的同時解決口渴問題(即不讓嘴去主動靠近水杯，而是拿起水杯送到嘴)Maes:Theagentnetworkarchitecture,1991AI:NouvelleAI1931.2.3混合結構完全的慎思型和完全的反應型都不適合用來建立智能體。

結合二者:過程推理系統(tǒng)（PRS）圖靈機InteRRaPAI:NouvelleAI194圖靈機為動態(tài)變化的現(xiàn)實世界中的自主智能體設計三層:反應層:直接對外部激勵做出迅速的反應規(guī)劃層:制定規(guī)劃建模層:對外部世界狀態(tài)進行建模AI:NouvelleAI195圖靈機（續(xù)）每層直接與感知器和控制器相連任意兩層之間存在相互聯(lián)系每一層都有獨自的反應，在不同的層間發(fā)生沖突時：使用上下文觸發(fā)的控制規(guī)則解決.AI:NouvelleAI196圖靈機架構InnesA.Ferguson:TouringMachines:AutonomousAgentswithAttitudes,1992AI:NouvelleAI197InteRRaP分層的混合結構:在不同的層次上對環(huán)境進行建模存在不同層次的表示不同層次的知識和推理在垂直分層的結構中只有相鄰層之間存在通信行為層(與領域相關)規(guī)劃層(非社會性的目標驅動行為)協(xié)作層(社會行為，如聯(lián)合規(guī)劃等)AI:NouvelleAI198InteRRaP

結構/~chrender/Agenten/Agenten.htmlAI:NouvelleAI1991.3智能體的學習智能體要與動態(tài)變化的負責的外部環(huán)境進行交互，因此智能體需要進行自主學習。學習的基本思想如下：智能體感知到的知識不只是用來決定下一步行動，也用來提高智能體的能力，以在后面的行動中表現(xiàn)更佳。AI:NouvelleAI200學習類型監(jiān)督學習函數(shù)學習需要的輸入輸出對已經給定或者可以推導得到。非監(jiān)督學習沒有輸出的信息強化學習智能體在環(huán)境中作出行動，對于智能體的每一步行動，都會得到一個評價值，但是不被告知如何行動才可以正確的達到目標。√AI:NouvelleAI201PartⅡ:強化學習（RL）AI:NouvelleAI2023.1強化學習簡介強化學習是一種通過獎勵和懲罰來實現(xiàn)智能體的方式，無需指定完成何種任務.(Kaelbling,1996)智能體怎樣如何從成功和失敗中學習，從獎勵和懲罰中學習？基于試錯交互方式AI:NouvelleAI203強化學習模型Picture：R.Sutton:ReinforcementLearning:ATutorialAI:NouvelleAI204經典示例-房間里的機器人向上的行為:80%移動到了上方,10%移動到了左方,10%移動到了右方在[4,3]處獎勵為+1,在[4,2]處的獎勵為-1,其他步為0RussellandNorvig,ArtificialIntelligence:AModernApproach,2ededition,2006AI:NouvelleAI205經典示例–桿平衡在一個移動的平板車上面讓一個長桿平衡直立RussellandNorvig,ArtificialIntelligence:AModernApproach,2ededition,2006AI:NouvelleAI206不需要模型的方法:Q-學習算法學習V*(簡記為V*)對于任何狀態(tài)s，執(zhí)行向前搜索以選出最好的行動如果智能體已知下面函數(shù)將會得到很好的效果fS:狀態(tài)

行為

狀態(tài)fR

:狀態(tài)

行為

R如果fS

和fR

未知,將不能通過這種方式選擇下一步行為AI:NouvelleAI207Q-值定義一個與

V*相似的新的函數(shù)如果智能體對Q進行學習，將能夠在fS

和

fR

未知的情況下選擇最優(yōu)行動AI:NouvelleAI208r(狀態(tài),行為)立即收益值Q(狀態(tài),行為)值V*(狀態(tài))值100

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

9010008190100Q-值的計算

使用折扣收益，折扣因子為0.981=0+0.9*90AI:NouvelleAI209學習Q-值注意:Q

和

V*密切相關將Q寫成遞歸形式：使用Q-值問題:如何學習?問題:如何選擇最優(yōu)行為?AI:NouvelleAI210Q-學習步驟對于每一個<s,a>初始化Q-值觀察到當前狀態(tài)s重復以下步驟根據(jù)當前Q-函數(shù)選擇動作獲得獎勵r觀察到新的狀態(tài)s’令令s=s’AI:NouvelleAI211Q-學習舉例:漢諾塔/kardi/tutorial/ReinforcementLearning/Tower-of-Hanoi.htmAI:NouvelleAI212帶獎勵值的狀態(tài)圖AI:NouvelleAI213R矩陣初始QQ矩陣最終QQ矩陣更新AI:NouvelleAI214紅箭頭指示的是從起始節(jié)點到目標節(jié)點的最優(yōu)路徑實際上,圖中的Q值可以用于從圖中任何一個起始節(jié)點（不只是狀態(tài)1）通過最短路徑走到目標節(jié)點狀態(tài)圖里的解決路徑AI:NouvelleAI215Q-學習演示：

路徑學習器AI:NouvelleAI216總結行為智能沒有表示和推理的智能SituatedAI智能體弱概念和強概念結構類型有慎思型

(BDI模型),反應型

(包容結構,網(wǎng)絡結構),and混合型

(PRS,圖靈機，InteRRaP)AI:NouvelleAI217總結使用強化學習得到智能體不同于監(jiān)督學習和非監(jiān)督學習從獎勵和懲罰中學習試錯交互Q-學習群智能AI:SI219大綱什么是群智能(SI)?

模擬SI進行搜索

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

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

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

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

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

代理如何相互交互

例如：螞蟻的信息素

單個代理的簡單行為+一組代理之間的通信=該組代理的涌現(xiàn)復雜行為AI:ANN231間接通信信號傳播：-一個代理發(fā)送一個信號，該信號被廣播到環(huán)境中，并且其強度隨著距離的減