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

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

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

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

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

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

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

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

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

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

呆在屋內(nèi)的人顯然不理解他所處理的中文。

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

-不存在具有理解能力的計(jì)算機(jī)程序

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

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

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

邏輯,推理方法,思維機(jī)器,學(xué)習(xí)的基礎(chǔ),語言,理性數(shù)學(xué)

形式邏輯符號(hào)化,計(jì)算理論,可判定性,可處理性,概率經(jīng)濟(jì)效用,決策論神經(jīng)科學(xué)

思維活動(dòng)的物質(zhì)性心理學(xué)

感知,控制,實(shí)驗(yàn)技術(shù)計(jì)算機(jī)科學(xué)

構(gòu)造更快的計(jì)算機(jī)控制論

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

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

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

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

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

“嬰兒機(jī)器”符號(hào)智能神經(jīng)網(wǎng)絡(luò)行為智能進(jìn)化計(jì)算

”人造生命”群智能人工智能的實(shí)現(xiàn)途徑AI:Introduction21AI:Introduction21機(jī)器學(xué)習(xí)Q.制造一個(gè)“嬰兒機(jī)器”，它通過讀書學(xué)習(xí)、從經(jīng)驗(yàn)中學(xué)習(xí)等手段逐步增長智力，這個(gè)想法如何？人們?cè)缭?0世紀(jì)40年代就提出了這個(gè)設(shè)想，最終它將會(huì)得到實(shí)現(xiàn)。

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

專家系統(tǒng)

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

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

M-P神經(jīng)元模型

感知器

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

應(yīng)用

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

-拓?fù)浣Y(jié)構(gòu)-學(xué)習(xí)方法神經(jīng)網(wǎng)絡(luò)AI:Introduction26AI:Introduction26行為智能布魯克斯(1991)<<沒有表示的智能>>

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

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

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

行為智能AI:Introduction28AI:Introduction28進(jìn)化計(jì)算生物進(jìn)化

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

模擬進(jìn)化

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

AI:Introduction29AI:Introduction29遺傳算法

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

進(jìn)化策略

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

與進(jìn)化策略很難區(qū)分。主要區(qū)別是僅利用重組實(shí)現(xiàn)解的改變。它將每個(gè)個(gè)體看做一個(gè)物種，而不是同一物種中的不同個(gè)體，因此每個(gè)父代個(gè)體產(chǎn)生一個(gè)子代個(gè)體。進(jìn)化計(jì)算AI:Introduction30AI:Introduction30群智能智能經(jīng)常被認(rèn)為是單個(gè)個(gè)體的行為。是因?yàn)槲覀冇兄腔鬯越M成社會(huì)呢？還是因?yàn)槲覀兇嬖谟谏鐣?huì)中所以有智慧呢？-智能可以在社交活動(dòng)中呈現(xiàn)出來.突現(xiàn)行為

–

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

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

自底向上AI

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

時(shí)間和空間上的累積

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

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

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

閾值型線性飽和線性S型函數(shù)雙曲正切函數(shù)高斯函數(shù)AI:ANN451.2人工神經(jīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)前饋型神經(jīng)網(wǎng)絡(luò)-沒有環(huán)-靜態(tài)結(jié)構(gòu)

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

漸進(jìn)式vs.批處理兩類

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

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

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

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

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

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

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

基于存儲(chǔ)的學(xué)習(xí)指導(dǎo)式學(xué)習(xí)

將外部指導(dǎo)者提供的知識(shí)形式轉(zhuǎn)化為可供執(zhí)行機(jī)構(gòu)直接使用的知識(shí)形式類比學(xué)習(xí)

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

演繹和歸納相結(jié)合歸納學(xué)習(xí)

1.人工神經(jīng)網(wǎng)絡(luò)

2.統(tǒng)計(jì)學(xué)習(xí)

3.決策樹

4.聚類

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

是目標(biāo)函數(shù)

一個(gè)數(shù)據(jù)是一個(gè)(x,f(x))對(duì)

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

h≈fAI:MachineLearning68監(jiān)督學(xué)習(xí)方法構(gòu)造

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

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

曲線擬合:AI:MachineLearning69監(jiān)督學(xué)習(xí)方法構(gòu)造

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

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

曲線擬合:AI:MachineLearning70監(jiān)督學(xué)習(xí)方法構(gòu)造

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

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

曲線擬合:AI:MachineLearning71監(jiān)督學(xué)習(xí)方法構(gòu)造

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

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

曲線擬合:AI:MachineLearning72監(jiān)督學(xué)習(xí)方法構(gòu)造

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

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

曲線擬合:AI:MachineLearning73監(jiān)督學(xué)習(xí)方法構(gòu)造

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

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

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

盲目搜索

啟發(fā)式搜索

AI:MachineLearning77總結(jié)學(xué)習(xí)是一個(gè)系統(tǒng)通過經(jīng)驗(yàn)來提高性能的過程。有學(xué)習(xí)能力的智能系統(tǒng)的四個(gè)要素：

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

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

–

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

j

將金片B從柱i移動(dòng)到柱

j

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

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

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

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

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

以狀態(tài)為節(jié)點(diǎn)，以狀態(tài)轉(zhuǎn)換函數(shù)為邊，構(gòu)成一個(gè)圖。步驟4

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

動(dòng)作?

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

動(dòng)作代價(jià)?

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

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

空格上、下、左、右移動(dòng)初始與目標(biāo)狀態(tài)?

如圖動(dòng)作代價(jià)?

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

AI:SearchandProblemSolving96基于與或圖的問題求解找出一個(gè)解圖，它是代表原始問題求解方案的一個(gè)子圖步驟1.表示每個(gè)問題。步驟2.對(duì)問題進(jìn)行歸約，用與或圖表示歸約過程。步驟3.從端節(jié)點(diǎn)向上回溯，直到根節(jié)點(diǎn)，標(biāo)注各個(gè)節(jié)點(diǎn)可解或不可解。步驟4.如果根節(jié)點(diǎn)被標(biāo)注為可解，輸出相應(yīng)的解圖。AI:SearchandProblemSolving97例子:3-階梵塔問題初始狀態(tài)目標(biāo)狀態(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é)點(diǎn)可解或不可解.步驟4.輸出整個(gè)圖作為解答.(如何解釋?)AI:SearchandProblemSolving100PartⅣ:博弈搜索圖片來自：/DL88250AI:SearchandProblemSolving1013.1博弈樹代表博弈過程的數(shù)據(jù)結(jié)構(gòu)

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

當(dāng)MIN或MAX不能完成任務(wù)時(shí),就輸了。

首先,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

總是采取對(duì)自己最有利的行動(dòng)。為了能夠勝利,MAX應(yīng)該每一步選擇最有利的行動(dòng),同時(shí)認(rèn)為

MIN

也會(huì)每一步都采取對(duì)MIN最好的行動(dòng)(也就是說，對(duì)MAX最壞)

在想象對(duì)手為最強(qiáng)對(duì)手的情況下采取最好的行動(dòng)！在結(jié)構(gòu)上，博弈樹是與或圖！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)作為與或圖進(jìn)行搜索作為與或圖進(jìn)行搜索?AI:SearchandProblemSolving106

實(shí)際條件的限制

如中國象棋:共有

10160

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

103

個(gè)節(jié)點(diǎn)，需要

10145

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

1010年)解決辦法

截?cái)嗖呗?限制博弈樹的搜索深度

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

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

對(duì)于對(duì)稱狀態(tài)只存儲(chǔ)其中一種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頂點(diǎn)倒推值的最小邊界如果

v

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

剪掉這一枝β

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

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

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

黑白棋:人類高手拒絕與機(jī)器比賽，因?yàn)闄C(jī)器下棋水平實(shí)在是太好了。

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

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

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

表示博弈過程的數(shù)據(jù)結(jié)構(gòu)

在想象對(duì)手是最強(qiáng)對(duì)手的情況下采取最好的行動(dòng)，這在結(jié)構(gòu)上表現(xiàn)為與或圖極大極小算法

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

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

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

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

(afterDouglasAdams)

神經(jīng)計(jì)算

.進(jìn)化機(jī)制

導(dǎo)致人腦的產(chǎn)生(afterDarwinetal.)

進(jìn)化計(jì)算

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

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

重組前

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

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

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

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

AI:E傳物質(zhì):

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

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

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

一種棋局的懲罰:

對(duì)每一個(gè)皇后的懲罰值求和.

目標(biāo):使得懲罰值最小

最優(yōu)棋局:

懲罰值的倒數(shù)最大時(shí)8皇后問題:適應(yīng)度評(píng)價(jià)AI:EC142

突變:

交換兩個(gè)隨機(jī)選擇的點(diǎn)

(概率:80%)1234567812345678

重組:

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

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

或

目標(biāo)函數(shù)為每一個(gè)表型計(jì)算一個(gè)代表其適應(yīng)度的實(shí)數(shù)，這樣構(gòu)成了遺傳選擇的基礎(chǔ)因此該函數(shù)的判斷能力越大越好AI:EC152基因操作產(chǎn)生新的候選解

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

:例如挑選種群中一定數(shù)量適應(yīng)度最好的個(gè)體作為新的種群年齡準(zhǔn)則:

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

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

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

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

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

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

Pc

1發(fā)生(Pc

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

B.Two-pointcrossover

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

pmpm稱為

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

染色體長度）之間例如AI:EC165應(yīng)用例

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

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

和

p4

作為父代個(gè)體通過交叉和重組產(chǎn)生子代個(gè)體AI:EC174實(shí)例：子代選擇新一代個(gè)體為：AI:EC175對(duì)子代個(gè)體重復(fù)前面的操作重復(fù):F(p1)=-4F(p2)=-4

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

–

解;適應(yīng)度

–

目標(biāo);環(huán)境

–

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

?沒有表示和推理的智能

-學(xué)習(xí)強(qiáng)化學(xué)習(xí)-Q-學(xué)習(xí)AI:NouvelleAI181PartⅠ:智能體AI:NouvelleAI182機(jī)器人世界杯2008決賽

中國，蘇州到2050年，組建一個(gè)可以取勝人類足球冠軍隊(duì)的全自主機(jī)器人隊(duì)伍。

-AI:NouvelleAI183遠(yuǎn)程智能體實(shí)驗(yàn)(RAX)深空1號(hào)任務(wù)旨在驗(yàn)證技術(shù)；讓AI軟件成為航天器的主要指揮官；1999年5月進(jìn)行測試。

NANA,USa

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

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

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

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

行為

狀態(tài)fR

:狀態(tài)

行為

R如果fS

和fR

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

V*相似的新的函數(shù)如果智能體對(duì)Q進(jìn)行學(xué)習(xí)，將能夠在fS

和

fR

未知的情況下選擇最優(yōu)行動(dòng)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-值的計(jì)算

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

和

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

路徑學(xué)習(xí)器AI:NouvelleAI216總結(jié)行為智能沒有表示和推理的智能SituatedAI智能體弱概念和強(qiáng)概念結(jié)構(gòu)類型有慎思型

(BDI模型),反應(yīng)型

(包容結(jié)構(gòu),網(wǎng)絡(luò)結(jié)構(gòu)),and混合型

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

模擬SI進(jìn)行搜索

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

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

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

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

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

代理如何相互交互

例如：螞蟻的信息素

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