《人工智能》課程ppt課件

1、人 工 智 能.第一章 緒論1.1 人工智能的定義和開(kāi)展1.2 人類智能和人工智能1.3 人工智能的各種認(rèn)知觀1.4 人工智能的研討與運(yùn)用領(lǐng)域1.5 課程概要.1.1.1 人工智能的定義幾種定義 智能機(jī)器intelligent machine 人工智能學(xué)科 人工智能才干 人工智能擬人思想、行為 人工智能理性思想、行為 1.1 定義和開(kāi)展.1.1.2 人工智能的來(lái)源與開(kāi)展 孕育期1956年前 數(shù)理邏輯學(xué)科弗雷治、維納等 計(jì)算的新思想丘奇、圖靈 等 構(gòu)成期1956-1970年 1956年，第一次人工智能的研討會(huì) 1969年，第一屆國(guó)際人工智能結(jié)合會(huì)議 1970年，國(guó)際雜志創(chuàng)刊1.1 定義和開(kāi)展.1

2、.1.2 人工智能的來(lái)源與開(kāi)展開(kāi)展期1970年 進(jìn)一步研討AI根本原理方法和技術(shù) 進(jìn)展適用化研討 專家系統(tǒng)與知識(shí)工程 智能機(jī)器人 智能控制等 從“一枝獨(dú)秀到“百花齊放1.1 定義和開(kāi)展.1.2 人類智能和人工智能1.2.1 智能信息處置系統(tǒng)的假設(shè) 人是一種智能信息處置系統(tǒng) 物理符號(hào)系統(tǒng)的六種根本功能 物理符號(hào)系統(tǒng)的假設(shè) 推論一 推論二 推論三.1.2.1 智能信息處置系統(tǒng)的假設(shè) 人類的認(rèn)知行為具有不同層次 認(rèn)知生理學(xué) 認(rèn)知心思學(xué) 認(rèn)知信息學(xué) 認(rèn)知工程學(xué)1.2 人類智能和人工智能.1.2.2 人類智能的計(jì)算機(jī)模擬 機(jī)器智能可以模擬人類智能 智能計(jì)算機(jī) 下棋 定理證明 言語(yǔ)翻譯 新型智能計(jì)算機(jī) 神

3、經(jīng)計(jì)算機(jī)量子計(jì)算機(jī)1.2 人類智能和人工智能. 1.2.3 人工智能的研討目的 近期目的建造智能計(jì)算機(jī)替代人類的部分智力勞動(dòng) 遠(yuǎn)期目的用自動(dòng)機(jī)模擬人類的思想過(guò)程和智能行為1.2 人類智能和人工智能.1.3 人工智能的各種認(rèn)知觀 符號(hào)主義Symbolicism基于物理符號(hào)系統(tǒng)假設(shè)和有限合理性原理 銜接主義Connectionism基于神經(jīng)網(wǎng)絡(luò)及其間的銜接機(jī)制與學(xué)習(xí)算法 行為主義Actionism基于控制論及感知?jiǎng)幼餍涂刂葡到y(tǒng) .1.4 人工智能的研討及運(yùn)用領(lǐng)域 人工智能的根本技術(shù) 知識(shí)表示Knowledge Representation形狀空間法、問(wèn)題歸約法、謂詞邏輯法 推理搜索Searchin

4、g & Reasoning啟發(fā)式搜索、消解原理、不確定性推理 計(jì)算智能Computational Intelligence模糊計(jì)算、神經(jīng)計(jì)算、進(jìn)化計(jì)算 構(gòu)成技術(shù)系統(tǒng)與言語(yǔ)產(chǎn)生式系統(tǒng)、LISP言語(yǔ)、Prolog言語(yǔ).1.4.1 問(wèn)題求解 問(wèn)題的表示、分解、搜索、歸約等 進(jìn)展復(fù)雜的數(shù)學(xué)公式符號(hào)運(yùn)算求解1.4.2 邏輯推理與定理證明 經(jīng)過(guò)對(duì)現(xiàn)實(shí)數(shù)據(jù)庫(kù)的操作來(lái)證明定理 多種證明方法 幾何定理證明的“吳氏方法1.4 研討及運(yùn)用.1.4.3 自然言語(yǔ)了解 言語(yǔ) 自然言語(yǔ)、人造言語(yǔ)、機(jī)器言語(yǔ) “了解的規(guī)范1.4.4 自動(dòng)程序設(shè)計(jì) 根據(jù)不同目的描畫來(lái)編寫的計(jì)算機(jī)程序 促進(jìn)人工智能系統(tǒng)的開(kāi)展1.4 研討及運(yùn)用.

5、1.4.5 專家系統(tǒng) 是一個(gè)智能化的計(jì)算機(jī)程序系統(tǒng) 和傳統(tǒng)的計(jì)算機(jī)程序之間有本質(zhì)區(qū)別1.4.6 機(jī)器學(xué)習(xí) 是機(jī)器獲取智能的途徑 學(xué)習(xí)是一個(gè)有特定目的的知識(shí)獲取過(guò)程 學(xué)習(xí)的本質(zhì)是對(duì)信息的了解與運(yùn)用 有多種學(xué)習(xí)方法1.4 研討及運(yùn)用.1.4.7 神經(jīng)網(wǎng)絡(luò) 神經(jīng)計(jì)算機(jī) 在其它領(lǐng)域中的廣泛運(yùn)用1.4.8 機(jī)器人學(xué) 操作機(jī)器人 智能機(jī)器人 機(jī)器人的廣泛運(yùn)用 促進(jìn)人工智能的開(kāi)展1.4 研討及運(yùn)用.1.4.9 方式識(shí)別 是計(jì)算機(jī)對(duì)環(huán)境識(shí)別的需求 是對(duì)人類環(huán)境的感知模擬1.4.10 機(jī)器視覺(jué) 人類80以上的外部信息來(lái)自視覺(jué) 低層視覺(jué)與高層視覺(jué) 前沿研討領(lǐng)域 廣泛運(yùn)用1.4 研討及運(yùn)用.1.4.11 智能控制

6、驅(qū)動(dòng)智能機(jī)器自主地實(shí)現(xiàn)其目的的過(guò)程 是一個(gè)定性和定量的混合控制過(guò)程 是當(dāng)今自動(dòng)控制的最高程度1.4.12 智能檢索 是信息時(shí)代降臨的需求 智能檢索系統(tǒng)所面臨的三大問(wèn)題1.4 研討及運(yùn)用.1.4.13 智能調(diào)度與指揮 尋覓最正確調(diào)度和組合 NP完全類問(wèn)題的求解 軍事指揮系統(tǒng)等領(lǐng)域1.4.14 分布式人工智能與Agent 是傳統(tǒng)人工智能的延伸和擴(kuò)展 研討目的是創(chuàng)建一種能描畫自然系統(tǒng)和社會(huì)系統(tǒng)的準(zhǔn)確概念模型1.4 研討及運(yùn)用.1.4.15 計(jì)算智能與進(jìn)化計(jì)算 計(jì)算智能包括神經(jīng)計(jì)算、模糊計(jì)算、進(jìn)化計(jì)算等 進(jìn)化計(jì)算的實(shí)際根底是生物進(jìn)化論1.4.16 數(shù)據(jù)發(fā)掘與知識(shí)發(fā)現(xiàn) 知識(shí)獲取 數(shù)據(jù)庫(kù)知識(shí)發(fā)掘 數(shù)據(jù)庫(kù)中

7、知識(shí)發(fā)現(xiàn)的四個(gè)特征1.4 研討及運(yùn)用.1.4.17 人工生命 人工生命概念的提出 實(shí)際根底與研討方法 研討內(nèi)容1.4.18 系統(tǒng)與言語(yǔ)工具 計(jì)算機(jī)系統(tǒng)的一些概念得到開(kāi)展 新的編程言語(yǔ)與公用開(kāi)發(fā)工具1.4 研討及運(yùn)用.1.5 課程概要 簡(jiǎn)述人工智能的來(lái)源與開(kāi)展 概括地論述知識(shí)表示的各種主要方法 討論常用的搜索原理和推理求解技術(shù) 引見(jiàn)近期人工智能技術(shù)和方法的熱點(diǎn) 詳細(xì)地分析人工智能的主要運(yùn)用領(lǐng)域 表達(dá)人工智能的爭(zhēng)議與展望 .第二章 知識(shí)表示方法2.1 形狀空間法2.2 問(wèn)題歸約法2.3 謂詞邏輯法2.4 語(yǔ)義網(wǎng)絡(luò)法2.5 其他方法2.6 小結(jié).2.1形狀空間法State Space Represe

8、ntation問(wèn)題求解技術(shù)主要是兩個(gè)方面：?jiǎn)栴}的表示求解的方法形狀空間法形狀state算符operator形狀空間方法.2.1.1 問(wèn)題形狀描畫定義形狀：描畫某類不同事物間的差別而引入的一組最少變量q0，q1，qn的有序集合。算符：使問(wèn)題從一種形狀變化為另一種形狀的手段稱為操作符或算符。問(wèn)題的形狀空間：是一個(gè)表示該問(wèn)題全部能夠形狀及其關(guān)系的圖，它包含三種闡明的集合，即三元形狀S，F(xiàn)，G。2.1 形狀空間法.2. 形狀空間表示概念詳釋例如下棋、迷宮及各種游戲。OriginalStateMiddleStateGoalState2.1 形狀空間法.例:三數(shù)碼難題3 puzzle problem123

9、123123312312312初始棋局目的棋局2.1 形狀空間法.有向圖途徑代價(jià)圖的顯示闡明圖的隱示闡明2.1.2 形狀圖示法AB2.1 形狀空間法.2.1.3 形狀空間表示舉例產(chǎn)生式系統(tǒng)production system一個(gè)總數(shù)據(jù)庫(kù)：它含有與詳細(xì)義務(wù)有關(guān)的信息隨著運(yùn)用情況的不同，這些數(shù)據(jù)庫(kù)能夠簡(jiǎn)單，或許復(fù)雜。一套規(guī)那么：它對(duì)數(shù)據(jù)庫(kù)進(jìn)展操作運(yùn)算。每條規(guī)那么由左部鑒別規(guī)那么的適用性或先決條件以及右部描畫規(guī)那么運(yùn)用時(shí)所完成的動(dòng)作。一個(gè)控制戰(zhàn)略：它確定應(yīng)該采用哪一條適用規(guī)那么，而且當(dāng)數(shù)據(jù)庫(kù)的終止條件滿足時(shí)，就停頓計(jì)算。2.1 形狀空間法. 形狀空間表示舉例例：猴子和香蕉問(wèn)題2.1 形狀空間法.解題過(guò)

10、程 用一個(gè)四元表列W，x，Y，z來(lái)表示這個(gè)問(wèn)題形狀.這個(gè)問(wèn)題的操作算符如下：2 gotoU表示猴子走到程度位置U或者用產(chǎn)生式規(guī)那么表示為W，0，Y，z gotoU U，0，Y，z2.1 形狀空間法.pushboxV猴子把箱子推到程度位置V，即有W，0，W，z pushboxV V，0，V，zclimbbox猴子爬上箱頂，即有W，0，W，z climbbox W，1，W，z2.1 形狀空間法.grasp猴子摘到香蕉，即有c，1，c，0 grasp c，1，c，1 該初始形狀變換為目的形狀的操作序列為goto(b),pushbox(c),climbbox,grasp2.1 形狀空間法.(b，1，b

11、，0)U，0，b，0V，0，V，0c，1，c，0U，0，V，0c，1，c，1a，0，b，0目的形狀gotoUgotoUU=b，climbboxgotoUU=bpushboxV猴子和香蕉問(wèn)題的形狀空間圖gotoUU=V2.1 形狀空間法.猴子和香蕉問(wèn)題自動(dòng)演示： 猴子香蕉箱子 猴子香蕉箱子 Ha!Ha!2.1 形狀空間法.2.2 問(wèn)題歸約法Problem Reduction Representation子問(wèn)題1子問(wèn)題n原始問(wèn)題子問(wèn)題集本原問(wèn)題. 問(wèn)題歸約表示的組成部分：一個(gè)初始問(wèn)題描畫；一套把問(wèn)題變換為子問(wèn)題的操作符；一套本原問(wèn)題描畫。問(wèn)題歸約的本質(zhì)：從目的(要處理的問(wèn)題)出發(fā)逆向推理，建立子問(wèn)

12、題以及子問(wèn)題的子問(wèn)題，直至最后把初始問(wèn)題歸約為一個(gè)平凡的本原問(wèn)題集合。2.2 問(wèn)題規(guī)約法.2.2.1 問(wèn)題歸約描畫 Problem Reduction Description梵塔難題123CBA2.2 問(wèn)題規(guī)約法.解題過(guò)程3個(gè)圓盤問(wèn)題1231231231231231231231232.2 問(wèn)題規(guī)約法.多圓盤梵塔難題演示2.2 問(wèn)題規(guī)約法.2.2.2與或圖表示1.與圖、或圖、與或圖2.2 問(wèn)題規(guī)約法ABCD與圖ABC或圖.2.2 問(wèn)題規(guī)約法BCDEFGAHMBCDEFGAN.2.一些關(guān)于與或圖的術(shù)語(yǔ)2.2 問(wèn)題規(guī)約法HMBCDEFGAN父節(jié)點(diǎn)與節(jié)點(diǎn)弧線或節(jié)點(diǎn)子節(jié)點(diǎn)終葉節(jié)點(diǎn).3.定義2.2 問(wèn)題規(guī)

13、約法與或圖例子tttttttttab有解節(jié)點(diǎn)無(wú)解節(jié)點(diǎn)終葉節(jié)點(diǎn).不可解節(jié)點(diǎn)的普通定義沒(méi)有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。全部后裔為不可解的非終葉節(jié)點(diǎn)且含有或后繼節(jié)點(diǎn)，此非終葉節(jié)點(diǎn)才是不可解的。后裔至少有一個(gè)為不可解的非終葉節(jié)點(diǎn)且含有與后繼節(jié)點(diǎn)，此非終葉節(jié)點(diǎn)才是不可解的。與或圖構(gòu)成規(guī)那么2.2 問(wèn)題規(guī)約法.梵塔問(wèn)題歸約圖113 123 111 113 123 122 111 333 122 322 111 122 322 333 321 331 322 321 331 333 2.2 問(wèn)題規(guī)約法.2.3 謂詞邏輯法邏輯語(yǔ)句方式言語(yǔ)2.3.1 謂詞演算 1. 語(yǔ)法和語(yǔ)義根本符號(hào)謂詞符號(hào)、變量符號(hào)、函數(shù)

14、符號(hào)、 常量符號(hào)、括號(hào)和逗號(hào)原子公式.連詞和量詞(Connective &Quantifiers)連詞與及合取conjunction)或及析取disjunction蘊(yùn)涵Implication非Not量詞全稱量詞Universal Quantifiers)存在量詞 (Existential Quantifiers)2.3 謂詞邏輯法.2.3.2 謂詞公式原子公式的的定義：用P(x1，x2，xn)表示一個(gè)n元謂詞公式，其中P為n元謂詞，x1,x2,，xn為客體變量或變?cè)Ｍǔ０裀(x1,x2,xn)叫做謂詞演算的原子公式，或原子謂詞公式。分子謂詞公式可以用連詞把原子謂詞公式組成復(fù)合謂詞公式，并把它

15、叫做分子謂詞公式。2.3 謂詞邏輯法.適宜公式WFF，well-formed formulas適宜公式的遞歸定義適宜公式的性質(zhì)適宜公式的真值等價(jià)Equivalence)2.3 謂詞邏輯法.2.3.3 置換與合一置換概念假元推理全稱化推理綜合推理定義就是在該表達(dá)式中用置換項(xiàng)置換變量性質(zhì)可結(jié)合的不可交換的2.3 謂詞邏輯法.合一Unification)合一：尋覓項(xiàng)對(duì)變量的置換，以使兩表達(dá)式一致?？珊弦唬杭僭O(shè)一個(gè)置換s作用于表達(dá)式集Ei的每個(gè)元素，那么我們用Ei s來(lái)表示置換例的集。我們稱表達(dá)式集Ei是可合一的。2.3 謂詞邏輯法.2.4 語(yǔ)義網(wǎng)絡(luò)法 Semantic Network Represe

16、ntation語(yǔ)義網(wǎng)絡(luò)的構(gòu)造定義組成部分詞法構(gòu)造過(guò)程語(yǔ)義.表示占有關(guān)系和其它情況例： 小燕是一只燕子，燕子是鳥(niǎo)；巢-1是小燕的巢，巢-1是巢中的一個(gè)。選擇語(yǔ)義基元試圖用一組基元來(lái)表示知識(shí)，以便簡(jiǎn)化表示，并可用簡(jiǎn)單的知識(shí)來(lái)表示更復(fù)雜的知識(shí)。2.4 語(yǔ)義網(wǎng)絡(luò)法2.4. 1 二元語(yǔ)義網(wǎng)絡(luò)的表示.2.4.2 多元語(yǔ)義網(wǎng)絡(luò)的表示謂詞邏輯與語(yǔ)義網(wǎng)絡(luò)等效LIMINGMANISAISALIMING，MAN或 MANLIMING語(yǔ)義網(wǎng)絡(luò)謂詞邏輯2.4 語(yǔ)義網(wǎng)絡(luò)法.多元語(yǔ)義網(wǎng)絡(luò)表示的本質(zhì)把多元關(guān)系轉(zhuǎn)化為一組二元關(guān)系的組合，或二元關(guān)系的合取。R(X1，X2，Xn)R12(X1，X2)R13(X1，X3) R1n(X

17、1，Xn). Rn-1 n(Xn-1，Xn)可轉(zhuǎn)換為2.4 語(yǔ)義網(wǎng)絡(luò)法.2.4.3 銜接詞和量化的表示合取三元變?yōu)槎M合析取加注析取界限，并標(biāo)志DIS，以免引起混淆。否認(rèn)兩種表示方式：或標(biāo)注NEG界限。2.4 語(yǔ)義網(wǎng)絡(luò)法.蘊(yùn)涵在語(yǔ)義網(wǎng)絡(luò)中可用標(biāo)注ANTE和CONSE界限來(lái)表示蘊(yùn)涵關(guān)系。ANTE和CONSE界限分別用來(lái)把與先決條件(antecedent)及與結(jié)果(consequence)相關(guān)的鏈聯(lián)絡(luò)在一同。量化存在量化ISA鏈全稱量化分割法2.4 語(yǔ)義網(wǎng)絡(luò)法.2.5其他方法Others)框架Frame表示框架是一種構(gòu)造化表示法，通常采用語(yǔ)義網(wǎng)絡(luò)中的節(jié)點(diǎn)-槽-值表示構(gòu)造。劇本Script表示劇本

18、是框架的一種特殊方式，它用一組槽來(lái)描畫某些事件的發(fā)生序列。過(guò)程Procedure表示過(guò)程式表示就是將有關(guān)某一問(wèn)題領(lǐng)域的知識(shí)，連同如何運(yùn)用這些知識(shí)的方法，均隱式地表達(dá)為一個(gè)求解問(wèn)題的過(guò)程。.2.6 小結(jié)Summary本章所討論的知識(shí)表示問(wèn)題是人工智能研討的中心問(wèn)題之一。知識(shí)表示方法很多，本章引見(jiàn)了其中的7種，有圖示法和公式法，陳說(shuō)式表示和過(guò)程式表示等。.方法初始問(wèn)題算符目的結(jié)果 形狀 空間法 歸約法 謂詞邏輯法 語(yǔ)義網(wǎng)絡(luò)法形狀結(jié)點(diǎn)適宜公式結(jié)點(diǎn)算符弧 子句集set of clause置換合一消解反演鏈目的形狀結(jié)點(diǎn)根結(jié)點(diǎn)目的網(wǎng)絡(luò)解答途徑 path解答樹(shù) treenil語(yǔ)義網(wǎng)絡(luò)知識(shí)表示方法間的關(guān)系.第

19、三章 搜索推理技術(shù)3.6 產(chǎn)生式系統(tǒng)3.7 系統(tǒng)組織技術(shù)3.8 不確定性推理3.9 非單調(diào)推理3.10 小結(jié)3.1 圖搜索戰(zhàn)略3.2 盲目搜索3.3 啟發(fā)式搜索3.4 消解原理3.5 規(guī)那么演繹系統(tǒng).3.1 圖搜索戰(zhàn)略 圖搜索控制戰(zhàn)略一種在圖中尋覓途徑的方法。圖中每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)形狀，每條連線對(duì)應(yīng)一個(gè)操作符。這些節(jié)點(diǎn)和連線(即形狀與操作符)又分別由產(chǎn)生式系統(tǒng)的數(shù)據(jù)庫(kù)和規(guī)那么來(lái)標(biāo)志。求得把一個(gè)數(shù)據(jù)庫(kù)變換為另一數(shù)據(jù)庫(kù)的規(guī)那么序列問(wèn)題就等價(jià)于求得圖中的一條途徑問(wèn)題。圖搜索過(guò)程圖.開(kāi)場(chǎng)把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表n為目的節(jié)點(diǎn)嗎？把n的后繼節(jié)點(diǎn)放入

20、OPEN表的末端，提供前往節(jié)點(diǎn)n的指針修正指針?lè)较蛑嘏臤PEN表失敗勝利圖3.1 圖搜索過(guò)程框圖是是否否3.1 圖搜索戰(zhàn)略.3.2 盲目搜索 特點(diǎn)：不需重排OPEN表種類：寬度優(yōu)先、深度優(yōu)先、等代價(jià)搜索等。3.2.1 寬度優(yōu)先搜索 定義 以接近起始節(jié)點(diǎn)的程度逐層擴(kuò)展節(jié)點(diǎn)的搜索方法。 特點(diǎn)： 一種高代價(jià)搜索，但假設(shè)有解存在，那么必能找到它。 算法.開(kāi)場(chǎng)把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表能否有后繼節(jié)點(diǎn)為目的節(jié)點(diǎn)？擴(kuò)展n，把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供前往節(jié)點(diǎn)n的指針失敗勝利圖3.2 寬度優(yōu)先算法框圖是否是否3.2 盲目搜索. 例子八數(shù)碼難

21、題8-puzzle problem 1238456712384567目的形狀初始形狀規(guī)定：將牌移入空格的順序?yàn)椋簭目崭褡筮呴_(kāi)場(chǎng)順時(shí)針旋轉(zhuǎn)。不許斜向挪動(dòng)，也不前往先輩節(jié)點(diǎn)。從圖可見(jiàn)，要擴(kuò)展26個(gè)節(jié)點(diǎn)，共生成46個(gè)節(jié)點(diǎn)之后才求得解目的節(jié)點(diǎn)。3.2 盲目搜索.1238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345圖3.4 八數(shù)碼難題的寬度優(yōu)先搜索樹(shù)1345612384567123845671238456712384

22、56712384567232425262712367822123845671238456712384567123845671238456712384567123845671415161718192021123845673.2 盲目搜索.3.2.2 深度優(yōu)先搜索 定義 首先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點(diǎn)。 算法 防止搜索過(guò)程沿著無(wú)益的途徑擴(kuò)展下去，往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度深度界限。 與寬度優(yōu)先搜索算法最根本的不同在于：將擴(kuò)展的后繼節(jié)點(diǎn)放在OPEN表的前端。算法框圖見(jiàn)教材3.2 盲目搜索.3.2.3 等代價(jià)搜索 定義 是寬度優(yōu)先搜索的一種推行，不是沿著等長(zhǎng)度途徑斷層進(jìn)展擴(kuò)展，而是沿著等代價(jià)途

23、徑斷層進(jìn)展擴(kuò)展。 搜索樹(shù)中每條銜接弧線上的有關(guān)代價(jià),表示時(shí)間、間隔等破費(fèi)。 算法 假設(shè)一切銜接弧線具有相等代價(jià)，那么簡(jiǎn)化為寬度優(yōu)先搜索算法。3.2 盲目搜索.開(kāi)場(chǎng)把S放入OPEN表OPEN表為空表？把具有最小g(i)值的節(jié)點(diǎn)i從OPEN表移至CLOSED表能否有后繼節(jié)點(diǎn)為目的節(jié)點(diǎn)？失敗勝利圖3.2 等代價(jià)搜索算法框圖是否是否令g(s)=0S能否目的節(jié)點(diǎn)？是勝利擴(kuò)展i，計(jì)算其后繼節(jié)點(diǎn)j的g(j)，并把后繼節(jié)點(diǎn)放入OPEN表否3.2 盲目搜索.3.3 啟發(fā)式搜索特點(diǎn)：重排OPEN表，選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展種類：有序搜索、A*算法等3.3.1 啟發(fā)式搜索戰(zhàn)略和估價(jià)函數(shù)盲目搜索能夠帶來(lái)組合爆炸啟發(fā)

24、式信息 用來(lái)加速搜索過(guò)程的有關(guān)問(wèn)題領(lǐng)域的特征信息。.估價(jià)函數(shù) 為獲得某些節(jié)點(diǎn)“希望的啟發(fā)信息，提供一個(gè)評(píng)定侯選擴(kuò)展節(jié)點(diǎn)的方法，以便確定哪個(gè)節(jié)點(diǎn)最有能夠在通向目的的最正確途徑上 。 f(n)表示節(jié)點(diǎn)n的估價(jià)函數(shù)值 運(yùn)用節(jié)點(diǎn)“希望程度估價(jià)函數(shù)值重排OPEN表3.3.2 有序搜索本質(zhì) 選擇OPEN表上具有最小f值的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。3.3 啟發(fā)式搜索.開(kāi)場(chǎng)把S放入OPEN表，計(jì)算估價(jià)函數(shù) f (s)OPEN表為空表？選取OPEN表中f值最小的節(jié)點(diǎn)i放入CLOSED表i為目的節(jié)點(diǎn)嗎？擴(kuò)展i，得后繼節(jié)點(diǎn)j，計(jì)算f(j)，提供前往節(jié)點(diǎn)i的指針，利用f(j)對(duì)OPEN表重新排序，調(diào)整親子關(guān)系及指針

25、失敗勝利圖3.9 有序搜索算法框圖是否是否3.3 啟發(fā)式搜索算法. 例子八數(shù)碼難題8-puzzle problem12384567目的形狀12384567初始形狀八數(shù)碼難題的有序搜索樹(shù)見(jiàn)以下圖：3.3 啟發(fā)式搜索.57145631238456712384567123845674662123845671238456712384567655123845671238456757123845671238456767123845675813245671238456757圖3.10 八數(shù)碼難題的有序搜索樹(shù)123846473.3 啟發(fā)式搜索.3.3.3 A*算法估價(jià)函數(shù)的定義：對(duì)節(jié)點(diǎn)n定義f*(n)=g*(

26、n)+h*(n) ,表示從S開(kāi)場(chǎng)約束經(jīng)過(guò)節(jié)點(diǎn)n的一條最正確途徑的代價(jià)。希望估價(jià)函數(shù)f 定義為：f(n)=g(n)+h(n) g是g*的估計(jì) ，h是h*的估計(jì)A*算法的定義：定義1 在GRAPHSEARCH過(guò)程中，假設(shè)第8步的重排OPEN表是根據(jù)f(x)=g(x)+h(x)進(jìn)展的，那么稱該過(guò)程為A算法。 定義2 在A算法中，假設(shè)對(duì)一切的x存在h(x)h*(x),那么稱h(x)為h*(x)的下界，它表示某種偏于保守的估計(jì)。 定義3 采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱為A*算法。當(dāng)h=0時(shí)，A*算法就變?yōu)橛行蛩阉魉惴ā?3.3 啟發(fā)式搜索.3.4 消解原理回想：原子公式atomic

27、formulas文字一個(gè)原子公式及其否認(rèn)。子句由文字的析取組成的適宜公式。消解對(duì)謂詞演算公式進(jìn)展分解和化簡(jiǎn)，消去一些符號(hào)，以求得導(dǎo)出子句。3.4.1 子句集的求取 步驟：共9步。. 例子: 將以下謂詞演算公式化為一個(gè)子句集(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)開(kāi)場(chǎng)：消去蘊(yùn)涵符號(hào) 只運(yùn)用和符號(hào)，以AB交換AB。(1) (x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)3.4 消解原理.(2) 減少否認(rèn)符號(hào)的轄域 每個(gè)否認(rèn)符號(hào)最多只用到一個(gè)謂詞符號(hào)上，并反復(fù)運(yùn)用狄摩根定律。(3) 對(duì)變量規(guī)范化 對(duì)啞元虛擬變量改名，以保證每個(gè)量詞有其本人獨(dú)一的啞元

28、。3.4 消解原理(2) (x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)(3) (x)P(x)(y)P(y)P(f(x,y)(w)Q(x,w)P(w).(4) 消去存在量詞 以Skolem函數(shù)替代存在量詞內(nèi)的約束變量，然后消去存在量詞化為前束形 把一切全稱量詞移到公式的左邊，并使每個(gè)量詞的轄域包括這個(gè)量詞后面公式的整個(gè)部分。 前束形=前綴 母式 全稱量詞串 無(wú)量詞公式(4) (x)P(x)(y)P(y)P(f(x,y)Q(x,g(x)P(g(x)式中，w=g(x)為一Skolem函數(shù)。(5) (x)(y)P(x)P(y)P(f(x,y)Q(x,g(x)P(g(x)3.4

29、 消解原理.把母式化為合取范式 任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否認(rèn)的析取的有限集組成的合取。(7) 消去全稱量詞 一切余下的量詞均被全稱量詞量化了。消去前綴，即消去明顯出現(xiàn)的全稱量詞。3.4 消解原理(6) (x)(y)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(7) P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x).(8) 消去連詞符號(hào) 用A,B替代(AB)，消去符號(hào)。最后得到一個(gè)有限集，其中每個(gè)公式是文字的析取。(9) 改換變量稱號(hào) 可以改換變量符號(hào)的稱號(hào)，使一個(gè)變量符號(hào)不出如今一個(gè)以上的子句中。3.4 消解原

30、理(8) P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(9) P(x1)P(y)Pf(x1,y)P(x2)Qx2,g(x2)P(x3)Pg(x3).3.4.2 消解推理規(guī)那么消解式的定義令L1，L2為兩恣意原子公式；L1和L2具有一樣的謂詞符號(hào)，但普通具有不同的變量。知兩子句L1和L2,假設(shè)L1和L2具有最普通合一，那么經(jīng)過(guò)消解可以從這兩個(gè)父輩子句推導(dǎo)出一個(gè)新子句()。這個(gè)新子句叫做消解式。 消解式求法取各子句的析取，然后消去互補(bǔ)對(duì)。3.4 消解原理.3.4.3 含有變量的消解式 要把消解推理規(guī)那么推行到含有變量的子句，必需找到一個(gè)作用于父輩子句的置換，使父輩子

31、句含有互補(bǔ)文字。 含有變量的子句之消解式 例子Px,f(y)Q(x)Rf(a),y Pf (f(a),zR(z，w)Q f (f(a) R(f(a)，y) R(f(y)，w) =f(f(a)/x,f(y)/z3.4 消解原理.3.4.4 消解反演求解過(guò)程消解反演 給出S，L否認(rèn)L，得L；把L添加到S中去；把新產(chǎn)生的集合L，S化成子句集；運(yùn)用消解原理，力圖推導(dǎo)出一個(gè)表示矛盾的空子句 例子儲(chǔ)蓄問(wèn)題 前提：每個(gè)儲(chǔ)蓄錢的人都獲得利息。 結(jié)論：假設(shè)沒(méi)有利息，那么就沒(méi)有人去儲(chǔ)蓄錢3.4 消解原理.(1規(guī)定原子公式： S(x,y) 表示 “x儲(chǔ)蓄y M(x) 表示 “x是錢 I(x) 表示 “x是利息 E(

32、x，y) 表示 “x獲得y(2用謂詞公式表示前提和結(jié)論：前提：(x)(y)(S(x,y)M(y)(y)(I(y)E(x,y)結(jié)論：(x)I(x) (x)(y)(M(y)S(x,y)(3) 化為子句形證明：3.4 消解原理.把前提化為子句形：1) S(x,y)M(y)I(f(x)2) S(x,y)M(y)E(x,f(x)把結(jié)論化為子句形：3) I(z)4) S(a,b)5) M(b)(4) 消解反演求NIL圖3.12 儲(chǔ)蓄問(wèn)題反演樹(shù)子句1子句3f (x)/zM(b)NIL子句5子句7子句4a/x,b/yS(x,y)M(y)子句63.4 消解原理.反演求解過(guò)程從反演樹(shù)求取答案步驟把由目的公式的否認(rèn)

33、產(chǎn)生的每個(gè)子句添加到目的公式否認(rèn)之否認(rèn)的子句中去。按照反演樹(shù)，執(zhí)行和以前一樣的消解，直至在根部得到某個(gè)子句止。用根部的子句作為一個(gè)回答語(yǔ)句。本質(zhì)把一棵根部有NIL的反演樹(shù)變換為根部帶有回 答語(yǔ)句的一棵證明樹(shù)。3.4 消解原理.3.5 規(guī)那么演繹系統(tǒng) 定義 基于規(guī)那么的問(wèn)題求解系統(tǒng)運(yùn)用IfThen規(guī)那么來(lái)建立，每個(gè)if能夠與某斷言(assertion)集中的一個(gè)或多個(gè)斷言匹配。有時(shí)把該斷言集稱為任務(wù)內(nèi)存，then部分用于規(guī)定放入任務(wù)內(nèi)存的新斷言。這種基于規(guī)那么的系統(tǒng)叫做規(guī)那么演繹系統(tǒng)。在這種系統(tǒng)中，通常稱每個(gè)if部分為前項(xiàng)，稱每個(gè)then部分為后項(xiàng)。 .3.5.1 規(guī)那么正向演繹系統(tǒng)定義 正向規(guī)

34、那么演繹系統(tǒng)是從現(xiàn)實(shí)到目的進(jìn)展操作的，即從情況條件到動(dòng)作進(jìn)展推理的，也就是從if到then的方向進(jìn)展推理的。 求解過(guò)程現(xiàn)實(shí)表達(dá)式的與或形變換 在基于規(guī)那么的正向演繹系統(tǒng)中，我們把現(xiàn)實(shí)表示為非蘊(yùn)涵方式的與或形，作為系統(tǒng)的總數(shù)據(jù)庫(kù)。3.5 規(guī)那么演繹系統(tǒng).現(xiàn)實(shí)表達(dá)式的與或圖表示Q(w,A)R(v)P(v)S(A,v)Q(w,A)R(v)P(v)S(A,v)R(v)P(v)S(A,v)R(v)P(v)圖3.15 一個(gè)現(xiàn)實(shí)表達(dá)式的與或樹(shù)表示3.5 規(guī)那么演繹系統(tǒng).與或圖的F規(guī)那么變換 這些規(guī)那么是建立在某個(gè)問(wèn)題轄域中普通陳說(shuō)性知識(shí)的蘊(yùn)涵公式根底上的。我們把允許用作規(guī)那么的公式類型限制為以下方式： L

35、W 式中：L是單文字；W為與或形的獨(dú)一公式。3.5 規(guī)那么演繹系統(tǒng).3.5.2 規(guī)那么逆向演繹系統(tǒng)定義 逆向規(guī)那么演繹系統(tǒng)是從then向if進(jìn)展推理的，即從目的或動(dòng)作向現(xiàn)實(shí)或情況條件進(jìn)展推理的。 求解過(guò)程目的表達(dá)式的與或方式與或圖的B規(guī)那么變換作為終止條件的現(xiàn)實(shí)節(jié)點(diǎn)的一致解圖3.5 規(guī)那么演繹系統(tǒng). 正向和逆向組合系統(tǒng)是建立在兩個(gè)系統(tǒng)相結(jié)合的根底上的。此組合系統(tǒng)的總數(shù)據(jù)庫(kù)由表示目的和表示現(xiàn)實(shí)的兩個(gè)與或圖構(gòu)造組成。這些與或圖構(gòu)造分別用正向系統(tǒng)的F規(guī)那么和逆向系統(tǒng)的B規(guī)那么來(lái)修正。3.5.3 規(guī)那么雙向演繹系統(tǒng)3.5 規(guī)那么演繹系統(tǒng).3.6 產(chǎn)生式系統(tǒng)定義：用來(lái)描畫假設(shè)干個(gè)不同的以一個(gè)根本概念為根

36、底的系統(tǒng)。這個(gè)根本概念就是產(chǎn)生式規(guī)那么或產(chǎn)生式條件和操作對(duì)的概念。本質(zhì)：在產(chǎn)生式系統(tǒng)中，論域的知識(shí)分為兩部分：用現(xiàn)實(shí)表示靜態(tài)知識(shí)，如事物、事件和它們之間的關(guān)系；用產(chǎn)生式規(guī)那么表示推理過(guò)程和行為。由于這類系統(tǒng)的知識(shí)庫(kù)主要用于存儲(chǔ)規(guī)那么，因此又把此類系統(tǒng)稱為基于規(guī)那么的系統(tǒng)。.3.6.1 產(chǎn)生式系統(tǒng)的組成控制戰(zhàn)略圖3.22 產(chǎn)生式系統(tǒng)的主要組成總數(shù)據(jù)庫(kù)產(chǎn)生式規(guī)那么3.6 產(chǎn)生式系統(tǒng).選擇規(guī)那么到執(zhí)行操作的步驟 1 匹配 把當(dāng)前數(shù)據(jù)庫(kù)與規(guī)那么的條件部分相匹配。 2 沖突 當(dāng)有一條以上規(guī)那么的條件部分和當(dāng)前數(shù)據(jù)庫(kù)相匹配時(shí)，就需求決議首先運(yùn)用哪一條規(guī)那么，這稱為沖突處理。 3 操作 操作就是執(zhí)行規(guī)那么的

37、操作部分。3.6 產(chǎn)生式系統(tǒng).3.6.2 產(chǎn)生式系統(tǒng)的推理 正向推理：從一組表示現(xiàn)實(shí)的謂詞或命題出發(fā)，運(yùn)用一組產(chǎn)生式規(guī)那么，用以證明該謂詞公式或命題能否成立。 逆向推理：從表示目的的謂詞或命題出發(fā)，運(yùn)用一組產(chǎn)生式規(guī)那么證明現(xiàn)實(shí)謂詞或命題成立，即首先提出一批假設(shè)目的，然后逐一驗(yàn)證這些假設(shè)。 雙向推理：雙向推理的推理戰(zhàn)略是同時(shí)從目的向現(xiàn)實(shí)推理和從現(xiàn)實(shí)向目的推理，并在推理過(guò)程中的某個(gè)步驟，實(shí)現(xiàn)現(xiàn)實(shí)與目的的匹配。3.6 產(chǎn)生式系統(tǒng).3.7 系統(tǒng)組織技術(shù)3.7.1 議程表系統(tǒng)組織技術(shù)首先將一個(gè)大系統(tǒng)或復(fù)雜系統(tǒng)中的知識(shí)劃分為一組相對(duì)獨(dú)立的模塊，然后思索各子模塊間在求解時(shí)的協(xié)作問(wèn)題。議程表是一個(gè)系統(tǒng)可以執(zhí)行

38、的義務(wù)表列。與每個(gè)義務(wù)有關(guān)的有兩件事，即提出該義務(wù)的理由和表示對(duì)該義務(wù)是有用的證據(jù)總權(quán)的評(píng)價(jià)。.3.7.2 黑板法黑板法由一組稱為知識(shí)資源(KS)的獨(dú)立模塊和一塊黑板組成求解系統(tǒng)。知識(shí)資源含有系統(tǒng)中專門領(lǐng)域的知識(shí)，而黑板那么是一切KS可以訪問(wèn)的公用數(shù)據(jù)構(gòu)造。3.7 系統(tǒng)組織技術(shù)3.7.3 -極小搜索法 提供了一種選擇最有希望假設(shè)的技術(shù)。.3.8 不確定性推理以模糊集實(shí)際為根底的方法以概率為根底的方法3.8.1 關(guān)于證據(jù)的不確定性 不確定性推理是研討復(fù)雜系統(tǒng)不完全性和不確定性的有力工具。有兩種不確定性，即關(guān)于證據(jù)的不確定性和關(guān)于結(jié)論的不確定性。.3.8.2 關(guān)于結(jié)論的不確定性 關(guān)于結(jié)論的不確定性

39、也叫做規(guī)那么的不確定性，它表示當(dāng)規(guī)那么的條件被完全滿足時(shí)，產(chǎn)生某種結(jié)論的不確定程度。3.8.3 多個(gè)規(guī)那么支持同一現(xiàn)實(shí)時(shí)的不確定性 基于模糊集實(shí)際的方法基于概率論的方法3.8 不確定性推理.3.9 非單調(diào)推理 定義 非單調(diào)推理用來(lái)處置那些不適宜用謂詞邏輯表示的知識(shí)。 它可以較好地處置不完全信息、不斷變化的情況以及求解復(fù)雜問(wèn)題過(guò)程中生成的假設(shè)，具有較為有效的求解效率。.3.9.1 缺省推理定義1：假設(shè)X不知道，那么得結(jié)論Y。定義2：假設(shè)X不能被證明，那么得結(jié)論Y。 定義3：假設(shè)X不能在某個(gè)給定的時(shí)間內(nèi)被證明，那么得結(jié)論Y。 3.9 非單調(diào)推理3.9.2 非單調(diào)推理系統(tǒng)正確性維持系統(tǒng)用以堅(jiān)持其它程

40、序所產(chǎn)生的命題 之間的相容性。一旦發(fā)現(xiàn)某個(gè)不相容，它就調(diào)出 本人的推理機(jī)制，面向從屬關(guān)系的回溯，并經(jīng)過(guò) 修正最小的信心集來(lái)消除不相容。.3.10 小結(jié) 經(jīng)典搜索推理技術(shù)圖搜索技術(shù)消解反演 高級(jí)搜索推理技術(shù)規(guī)那么演繹系統(tǒng)產(chǎn)生式系統(tǒng)系統(tǒng)組織技術(shù)不確定性推理非單調(diào)推理.第四章 計(jì)算智能(1)神經(jīng)計(jì)算模糊計(jì)算.4.1概述信息科學(xué)與生命科學(xué)的相互交叉、相互浸透和相互促進(jìn)是現(xiàn)代科學(xué)技術(shù)開(kāi)展的一個(gè)顯著特點(diǎn)。 計(jì)算智能涉及神經(jīng)網(wǎng)絡(luò)、模糊邏輯、進(jìn)化計(jì)算和人工生命等領(lǐng)域，它的研討和開(kāi)展正反映了當(dāng)代科學(xué)技術(shù)多學(xué)科交叉與集成的重要開(kāi)展趨勢(shì)。 .什么是計(jì)算智能 把神經(jīng)網(wǎng)絡(luò)NN歸類于人工智能AI能夠不大適宜，而歸類于計(jì)算

41、智能CI更能闡明問(wèn)題本質(zhì)。進(jìn)化計(jì)算、人工生命和模糊邏輯系統(tǒng)的某些課題，也都?xì)w類于計(jì)算智能。 計(jì)算智能取決于制造者manufacturers提供的數(shù)值數(shù)據(jù)，不依賴于知識(shí)；另一方面，人工智能運(yùn)用知識(shí)精品knowledge tidbits。人工神經(jīng)網(wǎng)絡(luò)該當(dāng)稱為計(jì)算神經(jīng)網(wǎng)絡(luò)。 4.1 概述.計(jì)算智能與人工智能的區(qū)別和關(guān)系 輸入人類知識(shí)()傳感輸入知識(shí)()傳感數(shù)據(jù)計(jì)算()傳感器C數(shù)值的A符號(hào)的B生物的輸入復(fù)雜性復(fù)雜性BNNBPRBIANNAPRAICNNCPRCI4.1 概述.AArtificial，表示人工的非生物的；BBiological，表示物理的化學(xué)的 ？生物的； CComputational，

42、表示數(shù)學(xué)計(jì)算機(jī) 計(jì)算智能是一種智力方式的低層認(rèn)知，它與人工智能的區(qū)別只是認(rèn)知層次從中層下降至低層而已。中層系統(tǒng)含有知識(shí)精品，低層系統(tǒng)那么沒(méi)有。4.1 概述.當(dāng)一個(gè)系統(tǒng)只涉及數(shù)值低層數(shù)據(jù)，含有方式識(shí)別部分，不運(yùn)用人工智能意義上的知識(shí)，而且可以呈現(xiàn)出：1計(jì)算順應(yīng)性；2計(jì)算容錯(cuò)性；3接近人的速度；4誤差率與人相近， 那么該系統(tǒng)就是計(jì)算智能系統(tǒng)。當(dāng)一個(gè)智能計(jì)算系統(tǒng)以非數(shù)值方式加上知識(shí)精品值，即成為人工智能系統(tǒng)。 4.1 概述.1960年威德羅和霍夫率先把神經(jīng)網(wǎng)絡(luò)用于自動(dòng)控制研討。60年代末期至80年代中期，神經(jīng)網(wǎng)絡(luò)控制與整個(gè)神經(jīng)網(wǎng)絡(luò)研討一樣，處于低潮。 80年代后期以來(lái)，隨著人工神經(jīng)網(wǎng)絡(luò)研討的復(fù)蘇和開(kāi)

43、展，對(duì)神經(jīng)網(wǎng)絡(luò)控制的研討也非常活潑。這方面的研討進(jìn)展主要在神經(jīng)網(wǎng)絡(luò)自順應(yīng)控制和模糊神經(jīng)網(wǎng)絡(luò)控制及其在機(jī)器人控制中的運(yùn)用上。4.2 神經(jīng)計(jì)算4.2.1 人工神經(jīng)網(wǎng)絡(luò)研討的進(jìn)展.人工神經(jīng)網(wǎng)絡(luò)的特性并行分布處置非線性映射經(jīng)過(guò)訓(xùn)練進(jìn)展學(xué)習(xí)順應(yīng)與集成硬件實(shí)現(xiàn)4.2 神經(jīng)計(jì)算.4.2.2 人工神經(jīng)網(wǎng)絡(luò)的構(gòu)造4.2 神經(jīng)計(jì)算-1W j 1X1X2Wj2X nW j n( )Yi圖4.2 神經(jīng)元模型. 圖4.2中的神經(jīng)元單元由多個(gè)輸入xi，i=1,2,.,n和一個(gè)輸出y組成。中間形狀由輸入信號(hào)的權(quán)和表示，而輸出為4.1 式中，j為神經(jīng)元單元的偏置，wji為銜接權(quán)系數(shù)。 n為輸入信號(hào)數(shù)目，yj為神經(jīng)元輸出，t為

44、時(shí)間，f( )為輸出變換函數(shù)，如圖4.3。 4.2 神經(jīng)計(jì)算.(a)xf(x)1x00圖4.3 神經(jīng)元中的某些變換激發(fā)函數(shù)(a) 二值函數(shù)(b) S形函數(shù) (c) 雙曲正切函數(shù)4.2 神經(jīng)計(jì)算(c)xf(x)1-1(b)f(x)x10.人工神經(jīng)網(wǎng)絡(luò)的根本特性和構(gòu)造人工神經(jīng)網(wǎng)絡(luò)是具有以下特性的有向圖： 對(duì)于每個(gè)節(jié)點(diǎn) i 存在一個(gè)形狀變量xi ； 從節(jié)點(diǎn) j 至節(jié)點(diǎn) i ，存在一個(gè)銜接權(quán)系統(tǒng)數(shù)wij； 對(duì)于每個(gè)節(jié)點(diǎn) i ，存在一個(gè)閾值 i；對(duì)于每個(gè)節(jié)點(diǎn) i ，定義一個(gè)變換函數(shù)fi ；對(duì)于最普通的情況，此函數(shù)取 方式。4.2 神經(jīng)計(jì)算.遞歸反響網(wǎng)絡(luò):在遞歸網(wǎng)絡(luò)中，多個(gè)神經(jīng)元互連以組織一個(gè)互連神經(jīng)網(wǎng)絡(luò)

45、，如圖4.4。圖4.4 反響網(wǎng)絡(luò)x1x2xnV1V2Vn輸入輸出x1x2xn4.2 神經(jīng)計(jì)算.前饋網(wǎng)絡(luò):前饋網(wǎng)絡(luò)具有遞階分層構(gòu)造，由同層神經(jīng)元間不存在互連的層級(jí)組成，如圖4.5。4.2 神經(jīng)計(jì)算x1x2輸入層輸出層隱層y1ynw11w1m圖4.5 前饋網(wǎng)絡(luò)反向傳播.人工神經(jīng)網(wǎng)絡(luò)的主要學(xué)習(xí)算法有師學(xué)習(xí)算法：可以根據(jù)期望的和實(shí)踐的網(wǎng)絡(luò)輸出對(duì)應(yīng)于給定輸入間的差來(lái)調(diào)整神經(jīng)元間銜接的強(qiáng)度或權(quán)。無(wú)師學(xué)習(xí)算法：不需求知道期望輸出。強(qiáng)化學(xué)習(xí)算法：采用一個(gè)“評(píng)論員來(lái)評(píng)價(jià)與給定輸入相對(duì)應(yīng)的神經(jīng)網(wǎng)絡(luò)輸出的優(yōu)度質(zhì)量因數(shù)。強(qiáng)化學(xué)習(xí)算法的一個(gè)例子是遺傳算法GA。4.2 神經(jīng)計(jì)算.人工神經(jīng)網(wǎng)絡(luò)的典型模型4.2 神經(jīng)計(jì)算.續(xù)

46、前表：4.2 神經(jīng)計(jì)算.4.2.4 基于神經(jīng)網(wǎng)絡(luò)的知識(shí)表示與推理 基于神經(jīng)網(wǎng)絡(luò)的知識(shí)表示 在這里，知識(shí)并不像在產(chǎn)生式系統(tǒng)中那樣獨(dú)立地表示為每一條規(guī)那么，而是將某一問(wèn)題的假設(shè)干知識(shí)在同一網(wǎng)絡(luò)中表示。例如，在有些神經(jīng)網(wǎng)絡(luò)系統(tǒng)中，知識(shí)是用神經(jīng)網(wǎng)絡(luò)所對(duì)應(yīng)的有向權(quán)圖的鄰接矩陣及閾值向量表示的。 4.2 神經(jīng)計(jì)算.基于神經(jīng)網(wǎng)絡(luò)的推理 基于神經(jīng)網(wǎng)絡(luò)的推理是經(jīng)過(guò)網(wǎng)絡(luò)計(jì)算實(shí)現(xiàn)的。把用戶提供的初始證據(jù)用作網(wǎng)絡(luò)的輸入，經(jīng)過(guò)網(wǎng)絡(luò)計(jì)算最終得到輸出結(jié)果。 普通來(lái)說(shuō)，正向網(wǎng)絡(luò)推理的步驟如下：把知數(shù)據(jù)輸入網(wǎng)絡(luò)輸入層的各個(gè)節(jié)點(diǎn)。利用特性函數(shù)分別計(jì)算網(wǎng)絡(luò)中各層的輸出。用閾值函數(shù)對(duì)輸出層的輸出進(jìn)展斷定，從而得到輸出結(jié)果。4.2 神

47、經(jīng)計(jì)算.定義4.1 模糊集合(Fuzzy Sets)論域U到0,1區(qū)間的任一映射 ，即 ，都確定U的一個(gè)模糊子集F； 稱為F的隸屬函數(shù)或隸屬度。在論域U中，可把模糊子集表示為元素u與其隸屬函數(shù) 的序偶集合，記為： (4.7)4.3 模糊計(jì)算4.3.1 模糊集合、模糊邏輯及其運(yùn)算.定義4.2 模糊支集、交叉點(diǎn)及模糊單點(diǎn)假設(shè)模糊集是論域U中一切滿足 的元素u構(gòu)成的集合，那么稱該集合為模糊集F的支集。當(dāng)u滿足 ，稱為交叉點(diǎn)。當(dāng)模糊支集為U中一個(gè)單獨(dú)點(diǎn)，且u滿足 那么稱模糊集為模糊單點(diǎn)。4.3 模糊計(jì)算.定義4.3 模糊集的運(yùn)算設(shè)A和B為論域U中的兩個(gè)模糊集，其隸屬函數(shù)分別為 和 ，那么對(duì)于一切 ，存

48、在以下運(yùn)算：A與B的并邏輯或記為 ，其隸屬函數(shù)定義為： (4.10)A與B的交邏輯與記為 ，其隸屬函數(shù)定義為： (4.11)A的補(bǔ)邏輯非記為 ，其傳送函數(shù)定義為： (4.12)4.3 模糊計(jì)算.定義4.4 直積笛卡兒乘積，代數(shù)積 假設(shè) 分別為論域 中的模糊集合，那么這些集合的直積是乘積空間 中一個(gè)模糊集合，其隸屬函數(shù)為： (4.13)定義4.5 模糊關(guān)系 假設(shè)U，V是兩個(gè)非空模糊集合，那么其直積UV中的模糊子集R稱為從U到V的模糊關(guān)系，表示為： (4.14)4.3 模糊計(jì)算.定義4.6 復(fù)合關(guān)系 假設(shè)R和S分別為UV和VW中的模糊關(guān)系，那么R和S的復(fù)合是一個(gè)從U到W的模糊關(guān)系，記為： (4.1

49、5)其隸屬函數(shù)為： (4.16)式(4.9)中的 * 號(hào)可為三角范式內(nèi)的恣意一種算子，包括模糊交、代數(shù)積、有界積和直積等。4.3 模糊計(jì)算.定義4.7 正態(tài)模糊集、凸模糊集和模糊數(shù) 以實(shí)數(shù)R為論域的模糊集F，假設(shè)其隸屬函數(shù)滿足 那么F為正態(tài)模糊集；假設(shè)對(duì)于恣意實(shí)數(shù)x，axb，有 那么F為凸模糊集；假設(shè)F既是正態(tài)的又是凸的，那么稱F為模糊數(shù)。定義4.8 言語(yǔ)變量 一個(gè)言語(yǔ)變量可定義為多元組 。其中，x為變量名； 為x的詞集，即言語(yǔ)值稱號(hào)的集合；U為論域；G是產(chǎn)生言語(yǔ)值稱號(hào)的語(yǔ)法規(guī)那么；M是與各言語(yǔ)值含義有關(guān)的語(yǔ)法規(guī)那么。4.3 模糊計(jì)算.4.1.2 模糊邏輯推理模糊邏輯推理是建立在模糊邏輯根底上

50、的不確定性推理方法，是在二值邏輯三段論根底上開(kāi)展起來(lái)的。這種推理方法以模糊判別為前提，動(dòng)用模糊言語(yǔ)規(guī)那么，推導(dǎo)出一個(gè)近似的模糊判別結(jié)論。曾經(jīng)提出了Zadeh法，Baldwin法、Tsukamoto法、Yager法和Mizumoto法等方法。廣義取式假言推理法(GMP)推理規(guī)那么可表示為： 前提1：x為A 前提2：假設(shè)x為A，那么y為B 結(jié) 論：y為B 4.3 模糊計(jì)算.廣義拒式假言推理法(GMT, Generalized Modus Tollens) 的推理規(guī)那么可表示為： 前提1：y為B 前提2：假設(shè)x為A，那么y為B 結(jié) 論：x為A模糊變量的隱含函數(shù)根本上可分為三類，即模糊合取、模糊析取和

51、模糊蘊(yùn)涵。4.3 模糊計(jì)算.4.1.3 模糊判決方法在推理得到的模糊集合中取一個(gè)相對(duì)最能代表這個(gè)模糊集合的單值的過(guò)程就稱作解模糊或模糊判決Defuzzification。模糊判決可以采用不同的方法：重心法、最大隸屬度方法、加權(quán)平均法、隸屬度限幅元素平均法。下面引見(jiàn)各種模糊判決方法，并以“水溫適中為例，闡明不同方法的計(jì)算過(guò)程。這里假設(shè)“水溫適中的隸屬函數(shù)為： = X: 0.0/0 + 0.0/10 + 0.33/20 + 0.67/30 + 1.0/40 + 1.0/50+ 0.75/60 + 0.5/70 + 0.25/80 + 0.0/90 + 0.0/100 4.3 模糊計(jì)算. 重心法就是

52、取模糊隸屬函數(shù)曲線與橫坐標(biāo)軸圍成面積的重心作為代表點(diǎn)。實(shí)際上應(yīng)該計(jì)算輸出范圍內(nèi)一系列延續(xù)點(diǎn)的重心，即 (4.35)但實(shí)踐上是計(jì)算輸出范圍內(nèi)整個(gè)采樣點(diǎn)的重心，用足夠小的取樣間隔來(lái)提供所需求的精度，即：=48.24.3 模糊計(jì)算1. 重心法. 這種方法最簡(jiǎn)單，只需在推理結(jié)論的模糊集合中取隸屬度最大的那個(gè)元素作為輸出量即可。要求這種情況下其隸屬函數(shù)曲線一定是正規(guī)凸模糊集合即其曲線只能是單峰曲線。 例如，對(duì)于“水溫適中，按最大隸屬度原那么，有兩個(gè)元素40和50具有最大隸屬度1.0，那就對(duì)一切取最大隸屬度的元素40和50求平均值，執(zhí)行量應(yīng)?。?.3 模糊計(jì)算2. 最大隸屬度法.3. 系數(shù)加權(quán)平均法系數(shù)加

53、權(quán)平均法的輸出執(zhí)行量由下式?jīng)Q議： (4.36) 式中，系數(shù)的選擇要根據(jù)實(shí)踐情況而定，不同的系統(tǒng)就決議系統(tǒng)有不同的呼應(yīng)特性。4.3 模糊計(jì)算. 用所確定的隸屬度值對(duì)隸屬度函數(shù)曲線進(jìn)展切割，再對(duì)切割后等于該隸屬度的一切元素進(jìn)展平均，用這個(gè)平均值作為輸出執(zhí)行量，這種方法就稱為隸屬度限幅元素平均法。 例如，當(dāng)取為最大隸屬度值時(shí)，表示“完全隸屬關(guān)系，這時(shí)1.0。在“水溫適中的情況下，40和50的隸屬度是1.0，求其平均值得到輸出代表量：4.3 模糊計(jì)算4. 隸屬度限幅元素平均法.4.4 小結(jié)計(jì)算智能神經(jīng)計(jì)算模糊計(jì)算進(jìn)化計(jì)算人工生命神經(jīng)計(jì)算：人工神經(jīng)網(wǎng)絡(luò)模糊計(jì)算：模糊邏輯.第5章 計(jì)算智能(2):進(jìn)化計(jì)算

54、人工生命.進(jìn)化計(jì)算包括：遺傳算法(genetic algorithms，GA) 進(jìn)化戰(zhàn)略(evolution strategies) 進(jìn)化編程(evolutionary rogramming) 遺傳編程(genetic programming)人類不滿足于模擬生物進(jìn)化行為，希望可以建立具有自然生命特征的人造生命和人造生命系統(tǒng)。人工生命是人工智能和計(jì)算智能的一個(gè)新的研討熱點(diǎn)。.5.1 遺傳算法 遺傳算法是模擬生物遺傳學(xué)和自然選擇機(jī)理，經(jīng)過(guò)人工方式所構(gòu)造的一類優(yōu)化搜索算法，是對(duì)生物進(jìn)化過(guò)程進(jìn)展的一種數(shù)學(xué)仿真，是進(jìn)化計(jì)算的最重要的方式。遺傳算法為那些難以找到傳統(tǒng)數(shù)學(xué)模型的難題指出了一個(gè)處理方法。進(jìn)化

55、計(jì)算和遺傳算法自創(chuàng)了生物科學(xué)中的某些知識(shí)，這也表達(dá)了人工智能這一交叉學(xué)科的特點(diǎn)。 .5.1.1 遺傳算法的根本機(jī)理 霍蘭德的遺傳算法通常稱為簡(jiǎn)單遺傳算法SGA?，F(xiàn)以此作為討論主要對(duì)象，加上順應(yīng)的改良，來(lái)分析遺傳算法的構(gòu)造和機(jī)理。 編碼與解碼順應(yīng)度函數(shù) 遺傳操作 5.1 遺傳算法.5.1.2 遺傳算法的求解步驟 1. 遺傳算法的特點(diǎn) (1) 遺傳算法是對(duì)參數(shù)集合的編碼而非針對(duì)參數(shù)本身進(jìn)展進(jìn)化；(2)遺傳算法是從問(wèn)題解的編碼組開(kāi)場(chǎng)而非從單個(gè)解開(kāi)場(chǎng)搜索；(3)遺傳算法利用目的函數(shù)的順應(yīng)度這一信息而非利用導(dǎo)數(shù)或其它輔助信息來(lái)指點(diǎn)搜索；(4)遺傳算法利用選擇、交叉、變異等算子而不是利用確定性規(guī)那么進(jìn)展隨

56、機(jī)操作。5.1 遺傳算法.2. 遺傳算法的框圖(圖5.2) (1) 初始化群體;(2) 計(jì)算群體上每個(gè)個(gè)體的順應(yīng)度值;(3) 按由個(gè)體順應(yīng)度值所決議的某個(gè)規(guī)那么選 擇將進(jìn)入下一代的個(gè)體;(4) 按概率Pc進(jìn)展交叉操作;(5) 按概率Pc進(jìn)展突變操作;(6) 假設(shè)沒(méi)有滿足某種停頓條件，那么轉(zhuǎn)第(2)步， 否那么進(jìn)入下一步。(7) 輸出群體中順應(yīng)度值最優(yōu)的染色體作為問(wèn)題的 稱心解或最優(yōu)解。 5.1 遺傳算法.初始化種群變異操作計(jì)算順應(yīng)度值選擇操作交叉操作初始化種群終止條件開(kāi)場(chǎng)圖5.2 算法框圖5.1 遺傳算法. 普通遺傳算法的主要步驟如下：(1) 隨機(jī)產(chǎn)生一個(gè)由確定長(zhǎng)度的特征字符串組成的初始群體。

57、(2)對(duì)該字符串群體迭代的執(zhí)行下面的步和 ，直到滿足停頓規(guī)范： 計(jì)算群體中每個(gè)個(gè)體字符串的順應(yīng)值； 運(yùn)用復(fù)制、交叉和變異等遺傳算子產(chǎn)生下一代群體。(3)把在后代中出現(xiàn)的最好的個(gè)體字符串指定為遺傳算法的執(zhí)行結(jié)果，這個(gè)結(jié)果可以表示問(wèn)題的一個(gè)解。 5.1 遺傳算法.產(chǎn)生初始群體能否滿足停頓準(zhǔn)那么計(jì)算每個(gè)個(gè)體的順應(yīng)值i=M?GEN:=GEN+1依概率選擇遺傳操作執(zhí)行復(fù)制選擇一個(gè)個(gè)體i:=i+1選擇兩個(gè)個(gè)體選擇一個(gè)個(gè)體執(zhí)行變異i:=0GEN:=0復(fù)制到新群體i:=i+1將兩個(gè)后代插入新群體插入到新群體執(zhí)行雜交指定結(jié)果終了是否是否變異復(fù)制交叉5.1 遺傳算法.遺傳算法的普通構(gòu)造表示 Procedure:

58、Genetic Algorithmsbegin t 0; initialize P(t);evaluate P(t); while (not termination condition ) do begin recombine P(t) to yield C(t); evaluate C(t); select P(t+1) from P(t) and C(t); t t+1; endend5.1 遺傳算法.3. 遺傳算法求解舉例5.1 遺傳算法設(shè) ，用SGA求 參數(shù)設(shè)置二進(jìn)制編碼種群大小為4染色體長(zhǎng)為4位.遺傳算法歸納為五個(gè)根本組成部份 方案表示 群體初始化 順應(yīng)度函數(shù) 遺傳操作 算法參數(shù) 5

59、.1 遺傳算法.5.2 進(jìn)化戰(zhàn)略進(jìn)化戰(zhàn)略(Evolution Strategies，ES)是一類模擬自然進(jìn)化原理以求解參數(shù)優(yōu)化問(wèn)題的算法。它是由雷切伯格Rechenberg、施韋費(fèi)爾Schwefel和彼得比納特Peter Bienert于1964年提出的，并在德國(guó)共同建立的。.5.2.1 進(jìn)化戰(zhàn)略的算法模型 尋求與函數(shù)極值關(guān)聯(lián)的實(shí)n維矢量x。隨機(jī)選擇父矢量的初始群體。父矢量xi, i=1,p產(chǎn)生子代矢量xi。對(duì)誤差 (i=1,p)排序以選擇和決議堅(jiān)持哪些矢量。繼續(xù)產(chǎn)生新的實(shí)驗(yàn)數(shù)據(jù)以及選擇最小誤差矢量。 5.2 進(jìn)化戰(zhàn)略.5.2.2 進(jìn)化戰(zhàn)略和遺傳算法的區(qū)別 進(jìn)化戰(zhàn)略和遺傳算法有著很強(qiáng)的類似性，

60、它們都是一類模擬自然進(jìn)化原理的算法。兩者也存在著區(qū)別，其中最根本的區(qū)別是它們的研討領(lǐng)域不同。進(jìn)化戰(zhàn)略是一種數(shù)值優(yōu)化的方法，它采用一個(gè)具有自順應(yīng)步長(zhǎng)和傾角的特定爬山方法。遺傳算法從廣義上說(shuō)是一種自順應(yīng)搜索技術(shù)。5.2 進(jìn)化戰(zhàn)略.5.3 進(jìn)化編程進(jìn)化編程(Evolutionary Programming，EP)，又稱為進(jìn)化規(guī)劃Evolutionary Planning，是由福格爾Fogel在1962年提出的一種模擬人類智能的方法。進(jìn)化編程根據(jù)正確預(yù)測(cè)的符號(hào)數(shù)來(lái)度量順應(yīng)值。經(jīng)過(guò)變異，為父代群體中的每個(gè)機(jī)器形狀產(chǎn)生一個(gè)子代。父代和子代中最好的部分被選擇生存下來(lái)。它的提出是受自然生物進(jìn)化機(jī)制的啟發(fā)。.5