人工智能和專家系統(tǒng).ppt

人工智能與專家系統(tǒng),研究生課程,第一章 緒論,1.1 人工智能的定義和發(fā)展 1.2 人類智能和人工智能 1.3 人工智能的各種認(rèn)知觀 1.4 人工智能的研究與應(yīng)用領(lǐng)域 1.5 課程概要,1.1.1 人工智能的定義,幾種定義 智能機(jī)器（intelligent machine） 人工智能（學(xué)科） 人工智能（能力） 人工智能（擬人思維、行為 ） 人工智能（理性思維、行為 ）,1.1 定義和發(fā)展,1.1.2 人工智能的起源與發(fā)展,孕育期（1956年前） 數(shù)理邏輯學(xué)科（弗雷治、維納等 ） 計(jì)算的新思想（丘奇、圖靈 等） 形成期（1956-1970年） 1956年，第一次人工智能的研討會 1969年，第一屆國際人工智能聯(lián)合會議 1970年，人工智能國際雜志創(chuàng)刊,1.1 定義和發(fā)展,1.1.2 人工智能的起源與發(fā)展,發(fā)展期（1970年） 進(jìn)一步研究AI基本原理方法和技術(shù) 進(jìn)行實(shí)用化研究 專家系統(tǒng)與知識工程 機(jī)器定理證明 智能機(jī)器人 智能控制等 從“一枝獨(dú)秀”到“百花齊放”,1.1 定義和發(fā)展,1.2 人類智能和人工智能,1.2.1 智能信息處理系統(tǒng)的假設(shè) 人是一種智能信息處理系統(tǒng) 物理符號系統(tǒng)的六種基本功能 物理符號系統(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ī) 下棋 定理證明 語言翻譯 新型智能計(jì)算機(jī) 神經(jīng)計(jì)算機(jī) 量子計(jì)算機(jī),1.2 人類智能和人工智能,1.2.3 人工智能的研究目標(biāo),近期目標(biāo) 建造智能計(jì)算機(jī)代替人類的部分智力勞動 遠(yuǎn)期目標(biāo) 用自動機(jī)模仿人類的思維過程和智能行為,1.2 人類智能和人工智能,1.3 人工智能的各種認(rèn)知觀,符號主義（Symbolicism） 基于物理符號系統(tǒng)假設(shè)和有限合理性原理 連接主義（Connectionism） 基于神經(jīng)網(wǎng)絡(luò)及其間的連接機(jī)制與學(xué)習(xí)算法 行為主義（Actionism） 基于控制論及感知動作型控制系統(tǒng),1.4 人工智能的研究及應(yīng)用領(lǐng)域,人工智能的基本技術(shù) 知識表示（Knowledge Representation） 狀態(tài)空間法、問題歸約法、謂詞邏輯法 推理搜索（Searching & Reasoning） 啟發(fā)式搜索、消解原理、不確定性推理 計(jì)算智能（Computational Intelligence） 模糊計(jì)算、神經(jīng)計(jì)算、進(jìn)化計(jì)算 構(gòu)成技術(shù)（系統(tǒng)與語言） 產(chǎn)生式系統(tǒng)、LISP語言、Prolog語言,1.4.1 問題求解,問題的表示、分解、搜索、歸約等 進(jìn)行復(fù)雜的數(shù)學(xué)公式符號運(yùn)算求解 1.4.2 邏輯推理與定理證明 通過對事實(shí)數(shù)據(jù)庫的操作來證明定理 多種證明方法 幾何定理證明的“吳氏方法”,1.4 研究及應(yīng)用,1.4.3 自然語言理解,語言 自然語言、人造語言、機(jī)器語言 “理解”的標(biāo)準(zhǔn) 1.4.4 自動程序設(shè)計(jì) 根據(jù)不同目的描述來編寫的計(jì)算機(jī)程序 促進(jìn)人工智能系統(tǒng)的發(fā)展,1.4 研究及應(yīng)用,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è)有特定目的的知識獲取過程 學(xué)習(xí)的本質(zhì)是對信息的理解與應(yīng)用 有多種學(xué)習(xí)方法,1.4 研究及應(yīng)用,1.4.7 神經(jīng)網(wǎng)絡(luò),神經(jīng)計(jì)算機(jī) 在其它領(lǐng)域中的廣泛應(yīng)用 1.4.8 機(jī)器人學(xué) 操作機(jī)器人 智能機(jī)器人 機(jī)器人的廣泛應(yīng)用 促進(jìn)人工智能的發(fā)展,1.4 研究及應(yīng)用,1.4.9 模式識別,是計(jì)算機(jī)對環(huán)境識別的需要 是對人類環(huán)境的感知模擬 1.4.10 機(jī)器視覺 人類80以上的外部信息來自視覺 低層視覺與高層視覺 前沿研究領(lǐng)域 廣泛應(yīng)用,1.4 研究及應(yīng)用,1.4.11 智能控制,驅(qū)動智能機(jī)器自主地實(shí)現(xiàn)其目標(biāo)的過程 是一個(gè)定性和定量的混合控制過程 是當(dāng)今自動控制的最高水平 1.4.12 智能檢索 是信息時(shí)代來臨的需要 智能檢索系統(tǒng)所面臨的三大問題,1.4 研究及應(yīng)用,1.4.13 智能調(diào)度與指揮,尋找最佳調(diào)度和組合 NP完全類問題的求解 軍事指揮系統(tǒng)等領(lǐng)域 1.4.14 分布式人工智能與Agent 是傳統(tǒng)人工智能的延伸和擴(kuò)展 研究目標(biāo)是創(chuàng)建一種能描述自然系統(tǒng)和社會系統(tǒng)的精確概念模型,1.4 研究及應(yīng)用,1.4.15 計(jì)算智能與進(jìn)化計(jì)算,計(jì)算智能 包括神經(jīng)計(jì)算、模糊計(jì)算、進(jìn)化計(jì)算等 進(jìn)化計(jì)算的理論基礎(chǔ)是生物進(jìn)化論 1.4.16 數(shù)據(jù)挖掘與知識發(fā)現(xiàn) 知識獲取 數(shù)據(jù)庫知識挖掘 數(shù)據(jù)庫中知識發(fā)現(xiàn)的四個(gè)特征,1.4 研究及應(yīng)用,1.4.17 人工生命,人工生命概念的提出 理論基礎(chǔ)與研究方法 研究內(nèi)容 1.4.18 系統(tǒng)與語言工具 計(jì)算機(jī)系統(tǒng)的一些概念得到發(fā)展 新的編程語言與專用開發(fā)工具,1.4 研究及應(yīng)用,1.5 課程概要,簡述人工智能的起源與發(fā)展 概括地論述知識表示的各種主要方法 討論常用的搜索原理和推理求解技術(shù) 介紹近期人工智能技術(shù)和方法的熱點(diǎn) 詳細(xì)地分析人工智能的主要應(yīng)用領(lǐng)域 敘述人工智能的爭議與展望,第二章 知識表示方法,2.1 狀態(tài)空間法 2.2 問題歸約法 2.3 謂詞邏輯法 2.4 語義網(wǎng)絡(luò)法 2.5 其他方法 2.6 小結(jié),2.1狀態(tài)空間法 （State Space Representation）,問題求解技術(shù)主要是兩個(gè)方面： 問題的表示 求解的方法 狀態(tài)空間法 狀態(tài)（state） 算符（operator） 狀態(tài)空間方法,2.1.1 問題狀態(tài)描述,定義 狀態(tài)：描述某類不同事物間的差別而引入的一組最少變量q0，q1，qn的有序集合。 算符：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。 問題的狀態(tài)空間：是一個(gè)表示該問題全部可能狀態(tài)及其關(guān)系的圖，它包含三種說明的集合，即三元狀態(tài)（S，F(xiàn)，G）。,2.1 狀態(tài)空間法,2. 狀態(tài)空間表示概念詳釋,例如下棋、迷宮及各種游戲。,Middle State,Goal State,2.1 狀態(tài)空間法,例:三數(shù)碼難題 （3 puzzle problem）,初始棋局,目標(biāo)棋局,2.1 狀態(tài)空間法,有向圖 路徑 代價(jià) 圖的顯示說明 圖的隱示說明,2.1.2 狀態(tài)圖示法,A,B,2.1 狀態(tài)空間法,2.1.3 狀態(tài)空間表示舉例,產(chǎn)生式系統(tǒng)（production system） 一個(gè)總數(shù)據(jù)庫：它含有與具體任務(wù)有關(guān)的信息隨著應(yīng)用情況的不同，這些數(shù)據(jù)庫可能簡單，或許復(fù)雜。 一套規(guī)則：它對數(shù)據(jù)庫進(jìn)行操作運(yùn)算。每條規(guī)則由左部鑒別規(guī)則的適用性或先決條件以及右部描述規(guī)則應(yīng)用時(shí)所完成的動作。 一個(gè)控制策略：它確定應(yīng)該采用哪一條適用規(guī)則，而且當(dāng)數(shù)據(jù)庫的終止條件滿足時(shí)，就停止計(jì)算。,2.1 狀態(tài)空間法,狀態(tài)空間表示舉例,例：猴子和香蕉問題,2.1 狀態(tài)空間法,解題過程,用一個(gè)四元表列（W，x，Y，z）來表示這個(gè)問題狀態(tài).,這個(gè)問題的操作（算符）如下： 2 goto（U）表示猴子走到水平位置U 或者用產(chǎn)生式規(guī)則表示為 （W，0，Y，z） goto（U） （U，0，Y，z）,2.1 狀態(tài)空間法,pushbox（V）猴子把箱子推到水平位置V，即有 （W，0，W，z） pushbox（V） （V，0，V，z）,climbbox猴子爬上箱頂，即有 （W，0，W，z） climbbox （W，1，W，z）,2.1 狀態(tài)空間法,grasp猴子摘到香蕉，即有 （c，1，c，0） grasp （c，1，c，1）,該初始狀態(tài)變換為目標(biāo)狀態(tài)的操作序列為 goto(b),pushbox(c),climbbox,grasp,2.1 狀態(tài)空間法,2.1 狀態(tài)空間法,猴子和香蕉問題自動演示：,2.1 狀態(tài)空間法,2.2 問題歸約法 （Problem Reduction Representation）,問題歸約表示的組成部分： 一個(gè)初始問題描述； 一套把問題變換為子問題的操作符； 一套本原問題描述。,問題歸約的實(shí)質(zhì)： 從目標(biāo)(要解決的問題)出發(fā)逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個(gè)平凡的本原問題集合。,2.2 問題規(guī)約法,2.2.1 問題歸約描述 （Problem Reduction Description）,梵塔難題,2.2 問題規(guī)約法,解題過程（3個(gè)圓盤問題）,2.2 問題規(guī)約法,多圓盤梵塔難題演示,2.2 問題規(guī)約法,2.2.2與或圖表示,1.與圖、或圖、與或圖,2.2 問題規(guī)約法,2.2 問題規(guī)約法,2.一些關(guān)于與或圖的術(shù)語,2.2 問題規(guī)約法,3.定義,2.2 問題規(guī)約法,不可解節(jié)點(diǎn)的一般定義 沒有后裔的非終葉節(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 問題規(guī)約法,梵塔問題歸約圖,（322） （333）,2.2 問題規(guī)約法,2.3 謂詞邏輯法,邏輯語句 形式語言,2.3.1 謂詞演算 1. 語法和語義 基本符號 謂詞符號、變量符號、函數(shù)符號、 常量符號、括號和逗號 原子公式,連詞和量詞(Connective &Quantifiers) 連詞 與及合?。╟onjunction) 或及析取（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為客體變量或變元。通常把P(x1,x2,xn)叫做謂詞演算的原子公式，或原子謂詞公式。 分子謂詞公式 可以用連詞把原子謂詞公式組成復(fù)合謂詞公式，并把它叫做分子謂詞公式。,2.3 謂詞邏輯法,合適公式（WFF，well-formed formulas） 合適公式的遞歸定義 合適公式的性質(zhì) 合適公式的真值 等價(jià)（Equivalence),2.3 謂詞邏輯法,2.3.3 置換與合一,置換 概念 假元推理 全稱化推理 綜合推理 定義 就是在該表達(dá)式中用置換項(xiàng)置換變量 性質(zhì) 可結(jié)合的 不可交換的,2.3 謂詞邏輯法,合一（Unification) 合一：尋找項(xiàng)對變量的置換，以使兩表達(dá)式一致。 可合一：如果一個(gè)置換s作用于表達(dá)式集Ei的每個(gè)元素，則我們用Ei s來表示置換例的集。我們稱表達(dá)式集Ei是可合一的。,2.3 謂詞邏輯法,2.4 語義網(wǎng)絡(luò)法 （Semantic Network Representation）,語義網(wǎng)絡(luò)的結(jié)構(gòu) 定義 組成部分 詞法 結(jié)構(gòu) 過程 語義,表示占有關(guān)系和其它情況 例： 小燕是一只燕子，燕子是鳥；巢-1是小燕的巢，巢-1是巢中的一個(gè)。,選擇語義基元 試圖用一組基元來表示知識，以便簡化表示，并可用簡單的知識來表示更復(fù)雜的知識。,2.4 語義網(wǎng)絡(luò)法,2.4. 1 二元語義網(wǎng)絡(luò)的表示,2.4.2 多元語義網(wǎng)絡(luò)的表示,謂詞邏輯與語義網(wǎng)絡(luò)等效,2.4 語義網(wǎng)絡(luò)法,多元語義網(wǎng)絡(luò)表示的實(shí)質(zhì) 把多元關(guān)系轉(zhuǎn)化為一組二元關(guān)系的組合，或二元關(guān)系的合取。,2.4 語義網(wǎng)絡(luò)法,2.4.3 連接詞和量化的表示,合取 三元變?yōu)槎M合 析取 加注析取界限，并標(biāo)記DIS，以免引起混淆。 否定 兩種表示方式：或標(biāo)注NEG界限。,2.4 語義網(wǎng)絡(luò)法,蘊(yùn)涵 在語義網(wǎng)絡(luò)中可用標(biāo)注ANTE和CONSE界限來表示蘊(yùn)涵關(guān)系。ANTE和CONSE界限分別用來把與先決條件(antecedent)及與結(jié)果(consequence)相關(guān)的鏈聯(lián)系在一起。 量化 存在量化ISA鏈 全稱量化分割法,2.4 語義網(wǎng)絡(luò)法,2.5其他方法（Others),框架（Frame）表示 框架是一種結(jié)構(gòu)化表示法，通常采用語義網(wǎng)絡(luò)中的節(jié)點(diǎn)-槽-值表示結(jié)構(gòu)。 劇本（Script）表示 劇本是框架的一種特殊形式，它用一組槽來描述某些事件的發(fā)生序列。 過程（Procedure）表示 過程式表示就是將有關(guān)某一問題領(lǐng)域的知識，連同如何使用這些知識的方法，均隱式地表達(dá)為一個(gè)求解問題的過程。,2.6 小結(jié)（Summary）,本章所討論的知識表示問題是人工智能研究的核心問題之一。知識表示方法很多，本章介紹了其中的7種，有圖示法和公式法，陳述式表示和過程式表示等。,第三章 搜索推理技術(shù),3.6 產(chǎn)生式系統(tǒng) 3.7 系統(tǒng)組織技術(shù) 3.8 不確定性推理 3.9 非單調(diào)推理 3.10 小結(jié),3.1 圖搜索策略 3.2 盲目搜索 3.3 啟發(fā)式搜索 3.4 消解原理 3.5 規(guī)則演繹系統(tǒng),3.1 圖搜索策略,圖搜索控制策略 一種在圖中尋找路徑的方法。 圖中每個(gè)節(jié)點(diǎn)對應(yīng)一個(gè)狀態(tài)，每條連線對應(yīng)一個(gè)操作符。這些節(jié)點(diǎn)和連線(即狀態(tài)與操作符)又分別由產(chǎn)生式系統(tǒng)的數(shù)據(jù)庫和規(guī)則來標(biāo)記。求得把一個(gè)數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)則序列問題就等價(jià)于求得圖中的一條路徑問題。 圖搜索過程圖,開始,把S放入OPEN表,OPEN表為空表？,把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表,n為目標(biāo)節(jié)點(diǎn)嗎？,把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供返回節(jié)點(diǎn)n的指針,修改指針方向,重排OPEN表,失敗,成功,圖3.1 圖搜索過程框圖,是,是,否,否,3.1 圖搜索策略,3.2 盲目搜索,特點(diǎn)：不需重排OPEN表 種類：寬度優(yōu)先、深度優(yōu)先、等代價(jià)搜索等。,開始,把S放入OPEN表,OPEN表為空表？,把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表,是否有后繼節(jié)點(diǎn) 為目標(biāo)節(jié)點(diǎn)？,擴(kuò)展n，把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供返回節(jié)點(diǎn)n的指針,失敗,成功,圖3.2 寬度優(yōu)先算法框圖,是,否,是,否,3.2 盲目搜索,例子 八數(shù)碼難題（8-puzzle problem）,（初始狀態(tài)）,規(guī)定：將牌移入空格的順序?yàn)椋簭目崭褡筮呴_始順時(shí)針旋轉(zhuǎn)。不許斜向移動，也不返回先輩節(jié)點(diǎn)。 從圖可見，要擴(kuò)展26個(gè)節(jié)點(diǎn)，共生成46個(gè)節(jié)點(diǎn)之后才求得解（目標(biāo)節(jié)點(diǎn)）。,3.2 盲目搜索,1,圖3.4 八數(shù)碼難題的寬度優(yōu)先搜索樹,3.2 盲目搜索,3.2.2 深度優(yōu)先搜索,定義,首先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點(diǎn)。,算法,防止搜索過程沿著無益的路徑擴(kuò)展下去，往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度深度界限。 與寬度優(yōu)先搜索算法最根本的不同在于：將擴(kuò)展的后繼節(jié)點(diǎn)放在OPEN表的前端。（算法框圖見教材）,3.2 盲目搜索,3.2.3 等代價(jià)搜索,定義,是寬度優(yōu)先搜索的一種推廣，不是沿著等長度路徑斷層進(jìn)行擴(kuò)展，而是沿著等代價(jià)路徑斷層進(jìn)行擴(kuò)展。 搜索樹中每條連接弧線上的有關(guān)代價(jià),表示時(shí)間、距離等花費(fèi)。,算法,若所有連接弧線具有相等代價(jià)，則簡化為寬度優(yōu)先搜索算法。,3.2 盲目搜索,開始,把S放入OPEN表,OPEN表為空表？,把具有最小g(i)值的節(jié)點(diǎn)i從OPEN表移至CLOSED表,是否有后繼節(jié)點(diǎn) 為目標(biāo)節(jié)點(diǎn)？,失敗,成功,圖3.2 等代價(jià)搜索算法框圖,是,否,是,否,令g(s)=0,S是否目標(biāo)節(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ā)式搜索策略和估價(jià)函數(shù),盲目搜索可能帶來組合爆炸 啟發(fā)式信息 用來加速搜索過程的有關(guān)問題領(lǐng)域的特征信息。,估價(jià)函數(shù) 為獲得某些節(jié)點(diǎn)“希望”的啟發(fā)信息，提供一個(gè)評定侯選擴(kuò)展節(jié)點(diǎn)的方法，以便確定哪個(gè)節(jié)點(diǎn)最有可能在通向目標(biāo)的最佳路徑上 。 f(n)表示節(jié)點(diǎn)n的估價(jià)函數(shù)值 應(yīng)用節(jié)點(diǎn)“希望”程度（估價(jià)函數(shù)值）重排OPEN表,3.3.2 有序搜索,實(shí)質(zhì),選擇OPEN表上具有最小f值的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。,3.3 啟發(fā)式搜索,開始,把S放入OPEN表，計(jì)算估價(jià)函數(shù) f (s),OPEN表為空表？,選取OPEN表中f值最小的節(jié)點(diǎn)i放入CLOSED表,i為目標(biāo)節(jié)點(diǎn)嗎？,擴(kuò)展i，得后繼節(jié)點(diǎn)j，計(jì)算f(j)，提供返回節(jié)點(diǎn)i的指針，利用f(j)對OPEN表重新排序，調(diào)整親子關(guān)系及指針,失敗,成功,圖3.9 有序搜索算法框圖,是,否,是,否,3.3 啟發(fā)式搜索,算法,例子,八數(shù)碼難題（8-puzzle problem）,八數(shù)碼難題的有序搜索樹見下圖：,3.3 啟發(fā)式搜索,5,7,1,4,5,6,3,2,圖3.10 八數(shù)碼難題的有序搜索樹,3.3 啟發(fā)式搜索,3.3.3 A*算法,估價(jià)函數(shù)的定義： 對節(jié)點(diǎn)n定義f*(n)=g*(n)+h*(n) ,表示從S開始約束通過節(jié)點(diǎn)n的一條最佳路徑的代價(jià)。 希望估價(jià)函數(shù)f 定義為：f(n)=g(n)+h(n) g是g*的估計(jì) ，h是h*的估計(jì) A*算法的定義： 定義1 在GRAPHSEARCH過程中，如果第8步的重排OPEN表是依據(jù)f(x)=g(x)+h(x)進(jìn)行的，則稱該過程為A算法。 定義2 在A算法中，如果對所有的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 formulas） 文字一個(gè)原子公式及其否定。 子句由文字的析取組成的合適公式。 消解對謂詞演算公式進(jìn)行分解和化簡，消去一些符號，以求得導(dǎo)出子句。,例子:,將下列謂詞演算公式化為一個(gè)子句集 (x)P(x)(y)P(y)P(f(x,y) (y)Q(x,y)P(y),開始： 消去蘊(yùn)涵符號 只應(yīng)用和符號，以AB替換AB。,(1) (x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y),3.4 消解原理,(2) 減少否定符號的轄域 每個(gè)否定符號最多只用到一個(gè)謂詞符號上，并反復(fù)應(yīng)用狄摩根定律。 (3) 對變量標(biāo)準(zhǔn)化 對啞元（虛構(gòu)變量）改名，以保證每個(gè)量詞有其自己唯一的啞元。,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è)部分。 前束形=前綴 母式 全稱量詞串 無量詞公式,(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 消解原理,把母式化為合取范式 任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否定的析取的有限集組成的合取。 (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) 消去連詞符號 用A,B代替(AB)，消去符號。最后得到一個(gè)有限集，其中每個(gè)公式是文字的析取。 (9) 更換變量名稱 可以更換變量符號的名稱，使一個(gè)變量符號不出現(xiàn)在一個(gè)以上的子句中。,3.4 消解原理,(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具有相同的謂詞符號，但一般具有不同的變量。已知兩子句L1和L2,如果L1和L2具有最一般合一，那么通過消解可以從這兩個(gè)父輩子句推導(dǎo)出一個(gè)新子句()。這個(gè)新子句叫做消解式。,消解式求法,取各子句的析取，然后消去互補(bǔ)對。,3.4 消解原理,3.4.3 含有變量的消解式,3.4 消解原理,3.4.4 消解反演求解過程,消解反演 給出S，L 否定L，得L； 把L添加到S中去； 把新產(chǎn)生的集合L，S化成子句集； 應(yīng)用消解原理，力圖推導(dǎo)出一個(gè)表示矛盾的空子句,例子儲蓄問題 前提：每個(gè)儲蓄錢的人都獲得利息。 結(jié)論：如果沒有利息，那么就沒有人去儲蓄錢,3.4 消解原理,(1）規(guī)定原子公式： S(x,y) 表示 “x儲蓄y” M(x) 表示 “x是錢” I(x) 表示 “x是利息” E(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 儲蓄問題反演樹,3.4 消解原理,反演求解過程 從反演樹求取答案步驟 把由目標(biāo)公式的否定產(chǎn)生的每個(gè)子句添加到目標(biāo)公式否定之否定的子句中去。 按照反演樹，執(zhí)行和以前相同的消解，直至在根部得到某個(gè)子句止。 用根部的子句作為一個(gè)回答語句。 實(shí)質(zhì) 把一棵根部有NIL的反演樹變換為根部帶有回 答語句的一棵證明樹。,3.4 消解原理,3.5 規(guī)則演繹系統(tǒng),定義 基于規(guī)則的問題求解系統(tǒng)運(yùn)用IfThen規(guī)則來建立，每個(gè)if可能與某斷言(assertion)集中的一個(gè)或多個(gè)斷言匹配。有時(shí)把該斷言集稱為工作內(nèi)存，then部分用于規(guī)定放入工作內(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ī)則演繹系統(tǒng)是從事實(shí)到目標(biāo)進(jìn)行操作的，即從狀況條件到動作進(jìn)行推理的，也就是從if到then的方向進(jìn)行推理的。 求解過程 事實(shí)表達(dá)式的與或形變換 在基于規(guī)則的正向演繹系統(tǒng)中，我們把事實(shí)表示為非蘊(yùn)涵形式的與或形，作為系統(tǒng)的總數(shù)據(jù)庫。,3.5 規(guī)則演繹系統(tǒng),事實(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è)事實(shí)表達(dá)式的與或樹表示,3.5 規(guī)則演繹系統(tǒng),與或圖的F規(guī)則變換 這些規(guī)則是建立在某個(gè)問題轄域中普通陳述性知識的蘊(yùn)涵公式基礎(chǔ)上的。我們把允許用作規(guī)則的公式類型限制為下列形式： L W 式中：L是單文字；W為與或形的唯一公式。,3.5 規(guī)則演繹系統(tǒng),3.5.2 規(guī)則逆向演繹系統(tǒng),定義 逆向規(guī)則演繹系統(tǒng)是從then向if進(jìn)行推理的，即從目標(biāo)或動作向事實(shí)或狀況條件進(jìn)行推理的。 求解過程 目標(biāo)表達(dá)式的與或形式 與或圖的B規(guī)則變換 作為終止條件的事實(shí)節(jié)點(diǎn)的一致解圖,3.5 規(guī)則演繹系統(tǒng),正向和逆向組合系統(tǒng)是建立在兩個(gè)系統(tǒng)相結(jié)合的基礎(chǔ)上的。此組合系統(tǒng)的總數(shù)據(jù)庫由表示目標(biāo)和表示事實(shí)的兩個(gè)與或圖結(jié)構(gòu)組成。這些與或圖結(jié)構(gòu)分別用正向系統(tǒng)的F規(guī)則和逆向系統(tǒng)的B規(guī)則來修正。,3.5.3 規(guī)則雙向演繹系統(tǒng),3.5 規(guī)則演繹系統(tǒng),3.6 產(chǎn)生式系統(tǒng),定義：用來描述若干個(gè)不同的以一個(gè)基本概念為基礎(chǔ)的系統(tǒng)。這個(gè)基本概念就是產(chǎn)生式規(guī)則或產(chǎn)生式條件和操作對的概念。 實(shí)質(zhì)：在產(chǎn)生式系統(tǒng)中，論域的知識分為兩部分：用事實(shí)表示靜態(tài)知識，如事物、事件和它們之間的關(guān)系；用產(chǎn)生式規(guī)則表示推理過程和行為。由于這類系統(tǒng)的知識庫主要用于存儲規(guī)則，因此又把此類系統(tǒng)稱為基于規(guī)則的系統(tǒng)。,3.6.1 產(chǎn)生式系統(tǒng)的組成,控制策略,圖3.22 產(chǎn)生式系統(tǒng)的主要組成,總數(shù)據(jù)庫,產(chǎn)生式規(guī)則,3.6 產(chǎn)生式系統(tǒng),選擇規(guī)則到執(zhí)行操作的步驟 1 匹配 把當(dāng)前數(shù)據(jù)庫與規(guī)則的條件部分相匹配。 2 沖突 當(dāng)有一條以上規(guī)則的條件部分和當(dāng)前數(shù)據(jù)庫相匹配時(shí)，就需要決定首先使用哪一條規(guī)則，這稱為沖突解決。 3 操作 操作就是執(zhí)行規(guī)則的操作部分。,3.6 產(chǎn)生式系統(tǒng),3.6.2 產(chǎn)生式系統(tǒng)的推理,正向推理：從一組表示事實(shí)的謂詞或命題出發(fā)，使用一組產(chǎn)生式規(guī)則，用以證明該謂詞公式或命題是否成立。 逆向推理：從表示目標(biāo)的謂詞或命題出發(fā)，使用一組產(chǎn)生式規(guī)則證明事實(shí)謂詞或命題成立，即首先提出一批假設(shè)目標(biāo)，然后逐一驗(yàn)證這些假設(shè)。 雙向推理：雙向推理的推理策略是同時(shí)從目標(biāo)向事實(shí)推理和從事實(shí)向目標(biāo)推理，并在推理過程中的某個(gè)步驟，實(shí)現(xiàn)事實(shí)與目標(biāo)的匹配。,3.6 產(chǎn)生式系統(tǒng),3.7 系統(tǒng)組織技術(shù),3.7.1 議程表,系統(tǒng)組織技術(shù)首先將一個(gè)大系統(tǒng)或復(fù)雜系統(tǒng)中的知識劃分為一組相對獨(dú)立的模塊，然后考慮各子模塊間在求解時(shí)的合作問題。,議程表是一個(gè)系統(tǒng)能夠執(zhí)行的任務(wù)表列。與每個(gè)任務(wù)有關(guān)的有兩件事，即提出該任務(wù)的理由和表示對該任務(wù)是有用的證據(jù)總權(quán)的評價(jià)。,3.7.2 黑板法,黑板法由一組稱為知識資源(KS)的獨(dú)立模塊和一塊黑板組成求解系統(tǒng)。知識資源含有系統(tǒng)中專門領(lǐng)域的知識，而黑板則是一切KS可以訪問的公用數(shù)據(jù)結(jié)構(gòu)。,3.7 系統(tǒng)組織技術(shù),3.7.3 -極小搜索法,提供了一種選擇最有希望假設(shè)的技術(shù)。,3.8 不確定性推理,以模糊集理論為基礎(chǔ)的方法 以概率為基礎(chǔ)的方法,3.8.1 關(guān)于證據(jù)的不確定性,不確定性推理是研究復(fù)雜系統(tǒng)不完全性和不確定性的有力工具。有兩種不確定性，即關(guān)于證據(jù)的不確定性和關(guān)于結(jié)論的不確定性。,3.8.2 關(guān)于結(jié)論的不確定性,關(guān)于結(jié)論的不確定性也叫做規(guī)則的不確定性，它表示當(dāng)規(guī)則的條件被完全滿足時(shí)，產(chǎn)生某種結(jié)論的不確定程度。,3.8.3 多個(gè)規(guī)則支持同一事實(shí)時(shí)的不確定性,基于模糊集理論的方法 基于概率論的方法,3.8 不確定性推理,3.9 非單調(diào)推理,定義 非單調(diào)推理用來處理那些不適合用謂詞邏輯表示的知識。 它能夠較好地處理不完全信息、不斷變化的情況以及求解復(fù)雜問題過程中生成的假設(shè)，具有較為有效的求解效率。,3.9.1 缺省推理,定義1：如果X不知道，那么得結(jié)論Y。 定義2：如果X不能被證明，那么得結(jié)論Y。 定義3：如果X不能在某個(gè)給定的時(shí)間內(nèi)被證明，那么得結(jié)論Y。,3.9 非單調(diào)推理,3.9.2 非單調(diào)推理系統(tǒng) 正確性維持系統(tǒng)用以保持其它程序所產(chǎn)生的命題 之間的相容性。一旦發(fā)現(xiàn)某個(gè)不相容，它就調(diào)出 自己的推理機(jī)制，面向從屬關(guān)系的回溯，并通過 修改最小的信念集來消除不相容。,3.10 小結(jié),經(jīng)典搜索推理技術(shù) 圖搜索技術(shù) 消解反演 高級搜索推理技術(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ù)發(fā)展的一個(gè)顯著特點(diǎn)。 計(jì)算智能涉及神經(jīng)網(wǎng)絡(luò)、模糊邏輯、進(jìn)化計(jì)算和人工生命等領(lǐng)域，它的研究和發(fā)展正反映了當(dāng)代科學(xué)技術(shù)多學(xué)科交叉與集成的重要發(fā)展趨勢。,什么是計(jì)算智能,把神經(jīng)網(wǎng)絡(luò)（NN）歸類于人工智能（AI）可能不大合適，而歸類于計(jì)算智能（CI）更能說明問題實(shí)質(zhì)。進(jìn)化計(jì)算、人工生命和模糊邏輯系統(tǒng)的某些課題，也都?xì)w類于計(jì)算智能。 計(jì)算智能取決于制造者（manufacturers）提供的數(shù)值數(shù)據(jù)，不依賴于知識；另一方面，人工智能應(yīng)用知識精品（knowledge tidbits）。人工神經(jīng)網(wǎng)絡(luò)應(yīng)當(dāng)稱為計(jì)算神經(jīng)網(wǎng)絡(luò)。,4.1 概述,計(jì)算智能與人工智能的區(qū)別和關(guān)系,輸入,人類知識 ()傳感輸入,知識 ()傳感數(shù)據(jù),計(jì)算 ()傳感器,C數(shù)值的,A符號的,B生物的,輸入,復(fù)雜性,復(fù)雜性,BNN,BPR,BI,ANN,APR,AI,CNN,CPR,CI,4.1 概述,AArtificial，表示人工的（非生物的）；BBiological，表示物理的化學(xué)的 （？）生物的； CComputational，表示數(shù)學(xué)計(jì)算機(jī) 計(jì)算智能是一種智力方式的低層認(rèn)知，它與人工智能的區(qū)別只是認(rèn)知層次從中層下降至低層而已。中層系統(tǒng)含有知識（精品），低層系統(tǒng)則沒有。,4.1 概述,當(dāng)一個(gè)系統(tǒng)只涉及數(shù)值（低層）數(shù)據(jù)，含有模式識別部分，不應(yīng)用人工智能意義上的知識，而且能夠呈現(xiàn)出： （1）計(jì)算適應(yīng)性； （2）計(jì)算容錯(cuò)性； （3）接近人的速度； （4）誤差率與人相近， 則該系統(tǒng)就是計(jì)算智能系統(tǒng)。 當(dāng)一個(gè)智能計(jì)算系統(tǒng)以非數(shù)值方式加上知識（精品）值，即成為人工智能系統(tǒng)。,4.1 概述,1960年威德羅和霍夫率先把神經(jīng)網(wǎng)絡(luò)用于自動控制研究。 60年代末期至80年代中期，神經(jīng)網(wǎng)絡(luò)控制與整個(gè)神經(jīng)網(wǎng)絡(luò)研究一樣，處于低潮。 80年代后期以來，隨著人工神經(jīng)網(wǎng)絡(luò)研究的復(fù)蘇和發(fā)展，對神經(jīng)網(wǎng)絡(luò)控制的研究也十分活躍。這方面的研究進(jìn)展主要在神經(jīng)網(wǎng)絡(luò)自適應(yīng)控制和模糊神經(jīng)網(wǎng)絡(luò)控制及其在機(jī)器人控制中的應(yīng)用上。,4.2 神經(jīng)計(jì)算 4.2.1 人工神經(jīng)網(wǎng)絡(luò)研究的進(jìn)展,人工神經(jīng)網(wǎng)絡(luò)的特性,并行分布處理 非線性映射 通過訓(xùn)練進(jìn)行學(xué)習(xí) 適應(yīng)與集成 硬件實(shí)現(xiàn),4.2 神經(jīng)計(jì)算,圖4.2 神經(jīng)元模型,4.2.2 人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu),圖4.2中的神經(jīng)元單元由多個(gè)輸入xi，i=1,2,.,n和一個(gè)輸出y組成。中間狀態(tài)由輸入信號的權(quán)和表示，而輸出為 （4.1） 式中，j為神經(jīng)元 單元的偏置，wji為 連接權(quán)系數(shù),4.2 神經(jīng)計(jì)算,圖4.3 神經(jīng)元中的某些變換（激發(fā)）函數(shù),(a) 二值函數(shù) (b) S形函數(shù) (c) 雙曲正切函數(shù),n為輸入信號數(shù)目，yj為神經(jīng)元輸出，t為時(shí)間，f(_)為輸出變換函數(shù)，如圖4.3。,4.2 神經(jīng)計(jì)算,人工神經(jīng)網(wǎng)絡(luò)的基本特性和結(jié)構(gòu),人工神經(jīng)網(wǎng)絡(luò)是具有下列特性的有向圖： 對于每個(gè)節(jié)點(diǎn) i 存在一個(gè)狀態(tài)變量xi ； 從節(jié)點(diǎn) j 至節(jié)點(diǎn) i ，存在一個(gè)連接權(quán)系統(tǒng)數(shù)wij； 對于每個(gè)節(jié)點(diǎn) i ，存在一個(gè)閾值 i； 對于每個(gè)節(jié)點(diǎn) i ，定義一個(gè)變換函數(shù)fi ；對于最一般的情況，此函數(shù)取 形式。,4.2 神經(jīng)計(jì)算,圖4.4 反饋網(wǎng)絡(luò) 圖4.5 前饋網(wǎng)絡(luò),遞歸（反饋）網(wǎng)絡(luò):在遞歸網(wǎng)絡(luò)中，多個(gè)神經(jīng)元互連以組織一個(gè)互連神經(jīng)網(wǎng)絡(luò)，如圖5.3。 前饋網(wǎng)絡(luò):前饋網(wǎng)絡(luò)具有遞階分層結(jié)構(gòu)，由同層神經(jīng)元間不存在互連的層級組成，如圖5.4。,4.2 神經(jīng)計(jì)算,人工神經(jīng)網(wǎng)絡(luò)的主要學(xué)習(xí)算法,有師學(xué)習(xí)算法：能夠根據(jù)期望的和實(shí)際的網(wǎng)絡(luò)輸出（對應(yīng)于給定輸入）間的差來調(diào)整神經(jīng)元間連接的強(qiáng)度或權(quán)。 無師學(xué)習(xí)算法：不需要知道期望輸出。 強(qiáng)化學(xué)習(xí)算法：采用一個(gè)“評論員”來評價(jià)與給定輸入相對應(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ù)前表：,4.2 神經(jīng)計(jì)算,4.2.4 基于神經(jīng)網(wǎng)絡(luò)的知識表示與推理,基于神經(jīng)網(wǎng)絡(luò)的知識表示 在這里，知識并不像在產(chǎn)生式系統(tǒng)中那樣獨(dú)立地表示為每一條規(guī)則，而是將某一問題的若干知識在同一網(wǎng)絡(luò)中表示。例如，在有些神經(jīng)網(wǎng)絡(luò)系統(tǒng)中，知識是用神經(jīng)網(wǎng)絡(luò)所對應(yīng)的有向權(quán)圖的鄰接矩陣及閾值向量表示的。,4.2 神經(jīng)計(jì)算,基于神經(jīng)網(wǎng)絡(luò)的推理,基于神經(jīng)網(wǎng)絡(luò)的推理是通過網(wǎng)絡(luò)計(jì)算實(shí)現(xiàn)的。把用戶提供的初始證據(jù)用作網(wǎng)絡(luò)的輸入，通過網(wǎng)絡(luò)計(jì)算最終得到輸出結(jié)果。 一般來說，正向網(wǎng)絡(luò)推理的步驟如下： 把已知數(shù)據(jù)輸入網(wǎng)絡(luò)輸入層的各個(gè)節(jié)點(diǎn)。 利用特性函數(shù)分別計(jì)算網(wǎng)絡(luò)中各層的輸出。 用閾值函數(shù)對輸出層的輸出進(jìn)行判定，從而得到輸出結(jié)果。,4.2 神經(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),若模糊集是論域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ù)分別為 和 ，則對于所有 ，存在下列運(yùn)算： A與B的并（邏輯或）記為 ，其隸屬函數(shù)定義為： (4.10) A與B的交（邏輯與）記為 ，其隸屬函數(shù)定義為： (4.11) A的補(bǔ)（邏輯非）記為 ，其傳遞函數(shù)定義為： (4.12),4.3 模糊計(jì)算,定義4.4 直積（笛卡兒乘積，代數(shù)積）,若 分別為論域 中的模糊集合，則這些集合的直積是乘積空間 中一個(gè)模糊集合，其隸屬函數(shù)為： (4.13),定義4.5 模糊關(guān)系,若U，V是兩個(gè)非空模糊集合，則其直積UV中的模糊子集R稱為從U到V的模糊關(guān)系，表示為： (4.14),4.3 模糊計(jì)算,定義4.6 復(fù)合關(guān)系,若R和S分別為UV和VW中的模糊關(guān)系，則R和S的復(fù)合是一個(gè)從U到W的模糊關(guān)系，記為： (4.15),其隸屬函數(shù)為： (4.16),式(4.9)中的 * 號可為三角范式內(nèi)的任意一種算子，包括模糊交、代數(shù)積、有界積和直積等。,4.3 模糊計(jì)算,定義4.7 正態(tài)模糊集、凸模糊集和模糊數(shù),以實(shí)數(shù)R為論域的模糊集F，若其隸屬函數(shù)滿足 則F為正態(tài)模糊集；若對于任意實(shí)數(shù)x，axb，有 則F為凸模糊集；若F既是正態(tài)的又是凸的，則稱F為模糊數(shù)。,定義4.8 語言變量,一個(gè)語言變量可定義為多元組 。其中，x為變量名； 為x的詞集，即語言值名稱的集合；U為論域；G是產(chǎn)生語言值名稱的語法規(guī)則；M是與各語言值含義有關(guān)的語法規(guī)則。,4.3 模糊計(jì)算,4.1.2 模糊邏輯推理,模糊邏輯推理是建立在模糊邏輯基礎(chǔ)上的不確定性推理方法，是在二值邏輯三段論基礎(chǔ)上發(fā)展起來的。這種推理方法以模糊判斷為前提，動用模糊語言規(guī)則，推導(dǎo)出一個(gè)近似的模糊判斷結(jié)論。已經(jīng)提出了Zadeh法，Baldwin法、Tsukamoto法、Yager法和Mizumoto法等方法。 廣義取式假言推理法(GMP)推理規(guī)則可表示為： 前提1：x為A 前提2：若x為A，則y為B 結(jié) 論：y為B,4.3 模糊計(jì)算,廣義拒式假言推理法(GMT, Generalized Modus Tollens) 的推理規(guī)則可表示為： 前提1：y為B 前提2：若x為A，則y為B 結(jié) 論：x為A 模糊變量的隱含函數(shù)基本上可分為三類，即模糊合取、模糊析取和模糊蘊(yùn)涵。,4.3 模糊計(jì)算,4.1.3 模糊判決方法,在推理得到的模糊集合中取一個(gè)相對最能代表這個(gè)模糊集合的單值的過程就稱作解模糊或模糊判決（Defuzzification）。模糊判決可以采用不同的方法：重心法、最大隸屬度方法、加權(quán)平均法、隸屬度限幅元素平均法。 下面介紹各種模糊判決方法，并以“水溫適中”為例，說明不同方法的計(jì)算過程。這里假設(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ì)算,重心法就是取模糊隸屬函數(shù)曲線與橫坐標(biāo)軸圍成面積的重心作為代表點(diǎn)。理論上應(yīng)該計(jì)算輸出范圍內(nèi)一系列連續(xù)點(diǎn)的重心，即 (4.35) 但實(shí)際上是計(jì)算輸出范圍內(nèi)整個(gè)采樣點(diǎn)的重心，用足夠小的取樣間隔來提供所需要的精度，即：,=48.2,4.3 模糊計(jì)算,1. 重心法,這種方法最簡單，只要在推理結(jié)論的模糊集合中取隸屬度最大的那個(gè)元素作為輸出量即可。要求這種情況下其隸屬函數(shù)曲線一定是正規(guī)凸模糊集合（即其曲線只能是單峰曲線）。,例如，對于“水溫適中”，按最大隸屬度原則，有兩個(gè)元素40和50具有最大隸屬度1.0，那就對所有取最大隸屬度的元素40和50求平均值，執(zhí)行量應(yīng)?。?4.3 模糊計(jì)算,2. 最大隸屬度法,3. 系數(shù)加權(quán)平均法,系數(shù)加權(quán)平均法的輸出執(zhí)行量由下式?jīng)Q定： (4.36) 式中，系數(shù)的選擇要根據(jù)實(shí)際情況而定，不同的系統(tǒng)就決定系統(tǒng)有不同的響應(yīng)特性。,4.3 模糊計(jì)算,用所確定的隸屬度值對隸屬度函數(shù)曲線進(jìn)行切割，再對切割后等于該隸屬度的所有元素進(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ì)算 人工生命,進(jìn)化計(jì)算包括： 遺傳算法(genetic algorithms，GA) 進(jìn)化策略(evolution strategies) 進(jìn)化編程(evolutionary rogramming) 遺傳編程(genetic programming) 人類不滿足于模仿生物進(jìn)化行為，希望能夠建立具有自然生命特征的人造生命和人造生命系統(tǒng)。 人工生命是人工智能和計(jì)算智能的一個(gè)新的研究熱點(diǎn)。,5.1 遺傳算法,遺傳算法是模仿生物遺傳學(xué)和自然選擇機(jī)理，通過人工方式所構(gòu)造的一類優(yōu)化搜索算法，是對生物進(jìn)化過程進(jìn)行的一種數(shù)學(xué)仿真，是進(jìn)化計(jì)算的最重要的形式。 遺傳算法為那些難以找到傳統(tǒng)數(shù)學(xué)模型的難題指出了一個(gè)解決方法。 進(jìn)化計(jì)算和遺傳算法借鑒了生物科學(xué)中的某些知識，這也體現(xiàn)了人工智能這一交叉學(xué)科的特點(diǎn)。,5.1.1 遺傳算法的基本機(jī)理,霍蘭德的遺傳算法通常稱為簡單遺傳算法（SGA）?，F(xiàn)以此作為討論主要對象，加上適應(yīng)的改進(jìn)，來分析遺傳算法的結(jié)構(gòu)和機(jī)理。 編碼與解碼 適應(yīng)度函數(shù) 遺傳操作,5.1 遺傳算法,5.1.2 遺傳算法的求解步驟,1. 遺傳算法的特點(diǎn) (1) 遺傳算法是對參數(shù)集合的編碼而非針對參數(shù)本身進(jìn)行進(jìn)化； (2) 遺傳算法是從問題解的編碼組開始而非從單個(gè)解開始搜索； (3) 遺傳算法利用目標(biāo)函數(shù)的適應(yīng)度這一信息而非利用導(dǎo)數(shù)或其它輔助信息來指導(dǎo)搜索； (4) 遺傳算法利用選擇、交叉、變異等算子而不是利用確定性規(guī)則進(jìn)行隨機(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) 若沒有滿足某種停止條件，則轉(zhuǎn)第(2)步， 否則進(jìn)入下一步。 (7) 輸出群體中適應(yīng)度值最優(yōu)的染色體作為問題的 滿意解或最優(yōu)解。,5.1 遺傳算法,圖5.2 算法框圖,5.1 遺傳算法,一般遺傳算法的主要步驟如下： (1) 隨機(jī)產(chǎn)生一個(gè)由確定長度的特征字符串組成的初始群體。 (2) 對該字符串群體迭代的執(zhí)行下面的步和 ，直到滿足停止標(biāo)準(zhǔn)： 計(jì)算群體中每個(gè)個(gè)體字符串的適應(yīng)值； 應(yīng)用復(fù)制、交叉和變異等遺傳算子產(chǎn)生下一代群體。 (3) 把在后代中出現(xiàn)的最好的個(gè)體字符串指定為遺傳算法的執(zhí)行結(jié)果，這個(gè)結(jié)果可以表示問題的一個(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:=0,GEN:=0,復(fù)制到新群體,i:=i+1,將兩個(gè)后代插入新群體,插入到新群體,執(zhí)行雜交,指定結(jié)果,結(jié)束,是,否,是,否,變異,復(fù)制,交叉,5.1 遺傳算法,遺傳算法的一般結(jié)構(gòu)表示,Procedure: Genetic Algorithms begin 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; end end,5.1 遺傳算法,3. 遺傳算法求解舉例,例1：用遺傳算法求解函數(shù) (5.1) 的最大值，其中 。,5.1 遺傳算法,遺傳算法歸納為五個(gè)基本組成部份,方案表示 群體初始化 適應(yīng)度函數(shù) 遺傳操作 算法參數(shù),5.1 遺傳算法,5.2 進(jìn)化策略,進(jìn)化策略(Evolution Strategies，ES)是一類模仿自然進(jìn)化原理以求解參數(shù)優(yōu)化問題的算法。 它是由雷切伯格（Rechenberg）、施韋費(fèi)爾（Schwefel）和彼得比納特（Peter Bienert）于1964年提出的，并在德國共同建立的。,5.2.1 進(jìn)化策略的算法模型,尋求與函數(shù)極值關(guān)聯(lián)的實(shí)n維矢量x。 隨機(jī)選擇父矢量的初始群體。 父矢量xi, i=1,p產(chǎn)生子代矢量xi。 對誤差 (i=1,p)排序以選擇和決定保持哪些矢量。 繼續(xù)產(chǎn)生新的試驗(yàn)數(shù)據(jù)以及選擇最小誤差矢量。,5.2 進(jìn)化策略,5.2.2 進(jìn)化策略和遺傳算法的區(qū)別,進(jìn)化策略和遺傳算法有著很強(qiáng)的相似性，它們都是一類模仿自然進(jìn)化原理的算法。 兩者也存在著區(qū)別，其中最基本的區(qū)別是它們的研究領(lǐng)域不同。 進(jìn)化策略是一種數(shù)值優(yōu)化的方法，它采用一個(gè)具有自適應(yīng)步長和傾角的特定爬山方法。 遺傳算法從廣義上說是一種自適應(yīng)搜索技術(shù)。,5.2 進(jìn)化策略,5.3 進(jìn)化編程,進(jìn)化編程(Evolutionary Programming，EP)，又稱為進(jìn)化規(guī)劃（Evolutionary Planning），是由福格爾（Fogel）在1962年提出的一種模仿人類智能的方法。 進(jìn)化編程根據(jù)正確預(yù)測的符號數(shù)來度量適應(yīng)值。通過變異，為父代群體中的每個(gè)機(jī)器狀態(tài)產(chǎn)生一個(gè)子代。父代和子代中最好的部分被選擇生存下來。 它的提出是受自然生物進(jìn)化機(jī)制的啟發(fā)。,5.3.1 進(jìn)化編程的機(jī)理與表示,進(jìn)化編程的過程，可理解為從所有可能的計(jì)算機(jī)程序形成的空間中，搜索具有高的適應(yīng)度的計(jì)算機(jī)程序個(gè)體。 進(jìn)化編程設(shè)計(jì)強(qiáng)調(diào)群體行為的變化。進(jìn)化編程系統(tǒng)的表示自然地面向任務(wù)級。一旦選定一種適應(yīng)性表示，就可以定義依賴于該