智能決策支持系統(tǒng)和智能技術(shù)的決策支持_第1頁
智能決策支持系統(tǒng)和智能技術(shù)的決策支持_第2頁
智能決策支持系統(tǒng)和智能技術(shù)的決策支持_第3頁
智能決策支持系統(tǒng)和智能技術(shù)的決策支持_第4頁
智能決策支持系統(tǒng)和智能技術(shù)的決策支持_第5頁
已閱讀5頁,還剩92頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、第四章第四章 智能決策支持系智能決策支持系統(tǒng)和智能技術(shù)的決策支持統(tǒng)和智能技術(shù)的決策支持授課人:黃 鶯授課時(shí)間:10月10日、 10月17日、 10月24日4.1 4.1 智能決策支持系統(tǒng)概述智能決策支持系統(tǒng)概述4.1.1 4.1.1 智能決策支持系統(tǒng)概念智能決策支持系統(tǒng)概念4.1.2 4.1.2 智能決策支持系統(tǒng)結(jié)構(gòu)智能決策支持系統(tǒng)結(jié)構(gòu)4.2 4.2 人工智能基本原理人工智能基本原理4.2.1 4.2.1 邏輯推理邏輯推理4.2.2 知識(shí)表示與知識(shí)推理4.2.3 搜索技術(shù)4.3 4.3 專家系統(tǒng)與智能決策支持系統(tǒng)專家系統(tǒng)與智能決策支持系統(tǒng)4.3.1 4.3.1 專家系統(tǒng)的原理專家系統(tǒng)的原理4.

2、3.2 4.3.2 產(chǎn)生式規(guī)則專家系統(tǒng)產(chǎn)生式規(guī)則專家系統(tǒng)4.3.3 4.3.3 專家系統(tǒng)與決策支持系統(tǒng)的集成專家系統(tǒng)與決策支持系統(tǒng)的集成4.3.4 4.3.4 智能決策支持系統(tǒng)實(shí)例智能決策支持系統(tǒng)實(shí)例4.4 4.4 神經(jīng)網(wǎng)絡(luò)的決策支持系統(tǒng)神經(jīng)網(wǎng)絡(luò)的決策支持系統(tǒng)4.4.14.4.1 神經(jīng)網(wǎng)絡(luò)的原理神經(jīng)網(wǎng)絡(luò)的原理4.4.24.4.2 神經(jīng)網(wǎng)絡(luò)的傳播類型神經(jīng)網(wǎng)絡(luò)的傳播類型4.4.34.4.3 神經(jīng)網(wǎng)絡(luò)專家系統(tǒng)神經(jīng)網(wǎng)絡(luò)專家系統(tǒng)4.1.1 智能決策支持系統(tǒng)概念I(lǐng)DSS IDSS AIAIDSSDSS知識(shí)推理技術(shù)知識(shí)推理技術(shù)模型技術(shù)模型技術(shù)數(shù)據(jù)處理技術(shù)數(shù)據(jù)處理技術(shù)定性分析能力定性分析能力定量分析能力定量分

3、析能力 1981 1981年,年,BonczekBonczek提出了提出了DSSDSS三系統(tǒng)結(jié)構(gòu),該結(jié)構(gòu)三系統(tǒng)結(jié)構(gòu),該結(jié)構(gòu)中有中有“知識(shí)系統(tǒng)知識(shí)系統(tǒng)”,使得不少學(xué)者將,使得不少學(xué)者將DSSDSS劃為人工智劃為人工智能的范疇,研究知識(shí)表示與知識(shí)推理,這樣,能的范疇,研究知識(shí)表示與知識(shí)推理,這樣,DSSDSS與與人工智能的專家系統(tǒng)的界限變得模糊了。人工智能的專家系統(tǒng)的界限變得模糊了。 1980 1980年,年,Spraque提出提出DSSDSS的三部件結(jié)構(gòu),是傳統(tǒng)的三部件結(jié)構(gòu),是傳統(tǒng)DSSDSS結(jié)構(gòu)結(jié)構(gòu) 的典型代表。的典型代表。 IDSSIDSS實(shí)際上就是在實(shí)際上就是在DSSDSS基礎(chǔ)上增加了知識(shí)

4、部件?;A(chǔ)上增加了知識(shí)部件。 知識(shí)部件知識(shí)部件 知識(shí)庫知識(shí)管理系統(tǒng) 推理機(jī)4.1.2 智能決策支持系統(tǒng)結(jié)構(gòu)1.人工智能的決策支持技術(shù)(1 1)專家系統(tǒng))專家系統(tǒng)(2 2)神經(jīng)網(wǎng)絡(luò))神經(jīng)網(wǎng)絡(luò)(3 3)遺傳算法)遺傳算法(4 4)機(jī)器學(xué)習(xí))機(jī)器學(xué)習(xí)(5 5)自然語言理解)自然語言理解2.智能決策支持系統(tǒng)結(jié)構(gòu)形式(1).IDSS的基本結(jié)構(gòu)形式問題綜合與交互系統(tǒng)模型庫管理系統(tǒng)數(shù)據(jù)庫管理系統(tǒng)人工智能技術(shù)專家系統(tǒng) 神經(jīng)網(wǎng)絡(luò)遺傳算法 機(jī)器學(xué)習(xí)自然語言理解模型庫模型庫數(shù)據(jù)庫數(shù)據(jù)庫(2).IDSS的簡(jiǎn)化結(jié)構(gòu)圖問題綜合與交互系統(tǒng)模型庫管理系統(tǒng)數(shù)據(jù)庫管理系統(tǒng)知識(shí)庫管理系統(tǒng)推理機(jī)模型庫模型庫數(shù)據(jù)庫數(shù)據(jù)庫知識(shí)庫知識(shí)庫用

5、戶4.2.1 邏輯推理1.形式邏輯(1)概念:概念反映事物的特有屬性和屬性的取值。(2)判斷:對(duì)概念的肯定或否定; 判斷本身有對(duì)有錯(cuò); 判斷有全稱的肯定(或否定)判斷和存在的肯定(或否定)判斷。(3)推理:從一個(gè)或多個(gè)判斷推出一個(gè)新判斷的過程。2.推理的 種類演繹推理歸納推理類比推理假言推理三段論推理數(shù)學(xué)歸納法假言易位推理枚舉歸納推理(1)假言推理:“如果p,那么q”為真,同時(shí)“p”為真,則推出“q”為真。 pq,p q (2)三段論推理:“如果p,那么q”為真,同時(shí)“如果q,那么r”為真,則推出“如果p,那么r”為真。 pq,q r p r(3)假言易位推理:“如果p,那么q”為真,同時(shí)“非

6、q”為真,則推出“非p”為真。 pq,q p(1)數(shù)學(xué)歸納法: A包含B1、B2, A真(2)枚舉歸納推理:由所見的某一類事物的部分分子具有某種屬性,而且沒有遇到相反的情況,于是得出這一類事物都具有這種屬性的一般性結(jié)論。 S1是P,S2 是P Sn是P, S1Sn是S類中的部分分子,而且沒有遇到相反的事例 所以,S類事物都是PB1真,Bn Bn1類比推理: 由兩個(gè)(或兩類)事物在某些屬性上相同,進(jìn)而推斷它們?cè)诹硪粋€(gè)屬性也可能相同的推理。A事物有a、b、c、d屬性,B事物有a、b、c屬性( a,、b,、c,相似屬性)所以,B事物也可能有d 屬性(或d,相似屬性)3.總結(jié)(1)演繹推理的結(jié)論沒有超

7、出已知的知識(shí)范圍,而歸納推理和類比推理的結(jié)論超出了已知的知識(shí)范圍;(2)演繹推理中由于前提和結(jié)論有必然聯(lián)系,只要前提為真,結(jié)論一定為真。歸納推理和類比推理中前提和結(jié)論,不能保證有必然聯(lián)系,具有或然性。這樣的結(jié)論未必是可靠的。4.2.2 知識(shí)表示與知識(shí)推理1. 1.數(shù)理邏輯表示法數(shù)理邏輯表示法2.2.產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則3.3.語義網(wǎng)絡(luò)語義網(wǎng)絡(luò)4.4.框架框架5.5.劇本劇本產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則v 產(chǎn)生式規(guī)則知識(shí)一般表示為:if A then B,即如果A成立則B成立, AB。v 產(chǎn)生式規(guī)則知識(shí)有正向和逆向兩種推理方式。(1)正向推理v 逐條搜索規(guī)則庫,對(duì)每一條規(guī)則的前提條件都檢查事實(shí)庫中是否存

8、在;v 對(duì)前提條件中各子項(xiàng),若事實(shí)庫中不是全部都存在,放棄該條規(guī)則;v 若在事實(shí)庫中全部存在,則執(zhí)行該條規(guī)則,并結(jié)論放入到事實(shí)庫中;v 反復(fù)執(zhí)行上述過程,直至推出目標(biāo),并存放入事實(shí)庫中。(2)逆向推理v從目標(biāo)開始,尋找以此目標(biāo)為結(jié)論的規(guī)則,并對(duì)該規(guī)則的前提進(jìn)行判斷;v若該規(guī)則的前提中某個(gè)子項(xiàng)是另以規(guī)則的結(jié)論,再找此結(jié)論的規(guī)則;v重復(fù)上述過程,直到對(duì)某個(gè)規(guī)則的前提能夠進(jìn)行判斷;v按此規(guī)則前提的判斷得出結(jié)論的判斷,由此回溯到上一個(gè)規(guī)則的推理,一直回溯到目標(biāo)的判斷。語義網(wǎng)絡(luò)語義網(wǎng)絡(luò)v 用結(jié)點(diǎn)表示概念,用弧線表示概念之間的關(guān)系,將領(lǐng)域知識(shí)表示成一種結(jié)構(gòu)圖形式;v 在語義網(wǎng)絡(luò)中,尋找概念之間的內(nèi)在聯(lián)系,

9、主要通過語義網(wǎng)絡(luò)的形式推理來回答兩類問題: 從概念結(jié)點(diǎn)間問它們之間的關(guān)系 通過概念和關(guān)系問其他結(jié)點(diǎn)框架框架v 框架由一組描述事物的各個(gè)方面的槽(屬性)組成。v每個(gè)槽又可包含若干側(cè)面,每個(gè)側(cè)面都有自己的名字和填入的值。一般框架的結(jié)構(gòu):frame slotslot 值21 值22 值11 值12v 槽值的幾種類型:v填充槽值的兩種主要方法: 具體值value 默認(rèn)值default 過程值procedure 另一框架名 空 匹配 繼承4.2.3 搜索技術(shù)1. 1.問題求解過程的形式表示問題求解過程的形式表示2. 2.盲目搜索方法盲目搜索方法3.3.啟發(fā)式搜索啟發(fā)式搜索v 狀態(tài)空間表示法狀態(tài)空間表示法

10、 v 與或樹表示法與或樹表示法 v 廣度優(yōu)先搜索法廣度優(yōu)先搜索法v 生成測(cè)試法生成測(cè)試法v 深度優(yōu)先搜索法深度優(yōu)先搜索法 v 爬山法爬山法狀態(tài)空間表示法狀態(tài)空間表示法 狀態(tài)空間表示法是表示問題及其搜索過程的一種形式表示方法。狀態(tài)空間表示法用“狀態(tài)”和“算符”來表示問題,其中,“狀態(tài)”用以描述問題求解過程不同時(shí)刻的狀態(tài);“算符”表示對(duì)狀態(tài)的操作,算符的每一次使用就使問題由一種狀態(tài)變換為另一種狀態(tài)。當(dāng)?shù)竭_(dá)目標(biāo)狀態(tài)時(shí),出初始狀態(tài)到目標(biāo)狀態(tài)所用算符的序列就是問題的一個(gè)解。狀態(tài):狀態(tài): 狀態(tài)是描述問題求解過程中任時(shí)刻狀況的數(shù)據(jù)結(jié)構(gòu),可用一組變量的有序集表示: Sk(Sk1,Sk2,Skn)當(dāng)給每一個(gè)分量

11、以確定的值時(shí),就得到了一個(gè)具體的狀態(tài)。算符:算符: 引起狀態(tài)中某些分量發(fā)生變化,從而使問題由一個(gè)狀態(tài)變?yōu)榱硪粋€(gè)狀態(tài)的操作稱為算符。在產(chǎn)生式系統(tǒng)中,每條產(chǎn)生式規(guī)則就是一個(gè)算符。狀態(tài)空間: 由問題的全部狀態(tài)及一切可用算符所構(gòu)成的集合稱為問題的狀態(tài)空間,一般用一個(gè)三元組表示: (S,F(xiàn),G) 其中S是問題的所有初始狀態(tài)構(gòu)成的集合,F(xiàn)是算符的集合;G是目標(biāo)狀態(tài)的集合。 狀態(tài)空間的圖示形式稱為狀態(tài)空間圖。其中,節(jié)點(diǎn)表示狀態(tài),有向邊(弧)表示算符。1) 用狀態(tài)空間方法表示問題時(shí),首先必須定義狀態(tài)的描述形式,通過使用這種描述形式可把問題的一切狀態(tài)都表示出來。其次,還要定義一組算符,通過使用算符可把問題由一種

12、狀態(tài)轉(zhuǎn)變?yōu)榱矸N狀態(tài)。2) 問題的求解過程是個(gè)不斷把算符作用于狀態(tài)的過程。如果在使用某個(gè)算符后得到的新狀態(tài)是目標(biāo)狀態(tài),就得到了問題的一個(gè)解。這個(gè)解是從初始狀態(tài)到目標(biāo)狀態(tài)所用算符構(gòu)成的序列。 3) 算符的一次使用,就使問題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)??赡苡卸鄠€(gè)算符序列都可使問題從初始狀態(tài)變到目標(biāo)狀態(tài),這就得到了多個(gè)解。其中有的使用算符較少,有的較多,我們把使用算符最少的解稱為最優(yōu)解。 4) 對(duì)任何一個(gè)狀態(tài),可使用的算符可能不止一個(gè),因而由一個(gè)狀態(tài)所生成的后繼狀態(tài)就可能有多個(gè)。當(dāng)對(duì)這些后繼狀態(tài)使用算符時(shí),首先應(yīng)對(duì)哪個(gè)后繼狀態(tài)進(jìn)行操作,取決于問題求解采用的搜索策略搜索策略。搜索策略將影響搜索策略將影響

13、問題求解過程的效率。問題求解過程的效率。與或樹表示法與或樹表示法v 與或樹表示法也稱為問題歸約方法。它把初始問題通過一系列變換最終變?yōu)橐粋€(gè)子問題集合,而這些子問題的解可以直接得到,從而解答了初始問題。(1 1)分解分解 把一個(gè)復(fù)雜問題分解為若干個(gè)較為簡(jiǎn)單的子問題,每個(gè)子問題又可繼續(xù)分解為若干個(gè)更為簡(jiǎn)單的子問題。重復(fù)此過程,直到不需要再分解或者不能再分解為止。然后對(duì)每個(gè)子問題分別進(jìn)行求解,最后把各子問題的解復(fù)合起來就得到了原問題的解。 例如,把問題P分解為三個(gè)子問題P1,P2,P3,可用圖表示。 P1,P2,P3是問題P的三個(gè)子問題,只有當(dāng)這三個(gè)子問題都可解時(shí),問題P才可解,稱P1,P2,P3之

14、間存在“與”關(guān)系;稱節(jié)點(diǎn)P為“與”節(jié)點(diǎn);由P、 P1,P2,P3所構(gòu)成的圖稱為“與”樹。在圖中,為了標(biāo)明某個(gè)節(jié)點(diǎn)是“與”節(jié)點(diǎn),通常用一條弧把各條邊連接起來。(2 2)等價(jià)變換等價(jià)變換 對(duì)于一個(gè)復(fù)雜問題,除了可用“分解”方法進(jìn)行求解外,還可利用同構(gòu)或同態(tài)的等價(jià)變換,把它變換成若干個(gè)較容易求解的新問題。若新問題中有一個(gè)可求解,則就得到了原問題的解。 問題的等價(jià)變換過程也可用一個(gè)圖表示出來,稱為“或”樹。例如,問題P被等價(jià)變換為新問題P1,P2,P3 ,可用圖表示。其中,新問題P1,P2,P3中只要有一個(gè)可解,則原問題就可解。我們稱P1,P2,P3之間存在“或”關(guān)系:節(jié)點(diǎn)P稱為“或”節(jié)點(diǎn);由P、 P

15、1,P2,P3所構(gòu)成的圖是一個(gè)“或”樹。分解和等價(jià)變換也可結(jié)合起來使用,此時(shí)的圖稱為“與/或”樹。其中既有“或”節(jié)點(diǎn),也有“與”節(jié)點(diǎn),如右圖所示。(3)本原問題(4)端節(jié)點(diǎn)與終止節(jié)點(diǎn) 不能再分解或變換,而且直接可解的子問題稱為本原問題。在與或樹中,沒有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為端節(jié)點(diǎn);本原問題所對(duì)應(yīng)的節(jié)點(diǎn)稱為終止節(jié)點(diǎn)。終止節(jié)點(diǎn)一定是端節(jié)點(diǎn),但端節(jié)點(diǎn)不一定是終止節(jié)點(diǎn)。 5 5可解節(jié)點(diǎn)可解節(jié)點(diǎn)6.6.不可解節(jié)點(diǎn)不可解節(jié)點(diǎn)在與或樹中,滿足下列條件之一者,稱為可解節(jié)點(diǎn):1)它是一個(gè)終止節(jié)點(diǎn)。2)它是一個(gè)“或”節(jié)點(diǎn),且其子節(jié)點(diǎn)至少有一個(gè)是可解節(jié)點(diǎn)。3)它是一個(gè)“與”節(jié)點(diǎn),且其子節(jié)點(diǎn)全部是可解節(jié)點(diǎn)??山夤?jié)點(diǎn)的三個(gè)條

16、件全部不滿足的節(jié)點(diǎn)稱為不可解節(jié)點(diǎn)。 7 7解樹解樹 由可解節(jié)點(diǎn)所構(gòu)成的,并且由這些可解節(jié)點(diǎn)可推出初始節(jié)點(diǎn)(它對(duì)應(yīng)于原始問題)為可解節(jié)點(diǎn)的子樹稱為解樹。在解樹中一定包含初始節(jié)點(diǎn)。 廣度優(yōu)先搜索法廣度優(yōu)先搜索法(1 1). .基本思想基本思想從初始狀態(tài)S0開始,利用算符,生成所有可能的后繼狀態(tài),構(gòu)成下一層節(jié)點(diǎn),檢查目標(biāo)節(jié)點(diǎn)G是否出現(xiàn),若未出現(xiàn),就對(duì)該層所有的狀態(tài)節(jié)點(diǎn),分別順序利用算符,成生該層所有節(jié)點(diǎn)的后繼節(jié)點(diǎn),再再檢查是否出現(xiàn)G,若未出現(xiàn),繼續(xù)生成再下層的所有狀態(tài)節(jié)點(diǎn),這樣一層一層展開,直到目標(biāo)出現(xiàn)。S0S1S2S3S11S12S21S22S31S111S121S122S221S311G(2 2

17、)算法)算法1) 把初始節(jié)點(diǎn)S0故入OPEN表。2)如果OPEN表為空,則問題無解,退出 。 3) 把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出放入CLOSED表。4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是,則求得了問題的解,退出。 5)若節(jié)點(diǎn)n不可擴(kuò)展,則轉(zhuǎn)第2)步。 6) 擴(kuò)展節(jié)點(diǎn)n,將其子節(jié)點(diǎn)放入OPEN表的尾部,并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針,然后轉(zhuǎn)第2)步。例子例子1 1:重排九宮問題,在3x3的方格棋盤上放置分別標(biāo)有數(shù)字1、2、3、4、5、6、7、8共8個(gè)棋子,初始狀態(tài)為S0,目標(biāo)狀態(tài)為Sg,如圖1所示。可使用的算符有: 空格左移,空格上移,空格右移,空格下移。即只允許把位于空格左、

18、上、右、下的鄰近棋子移入空格。要求尋找從初始狀態(tài)到目標(biāo)狀態(tài)的路徑。由圖2可以看出,解的路徑是: S0381626該路徑使用的算符序列:空格上移,空格左移,空格下移,空格右移。 寬度優(yōu)先搜索的盲目性較大,當(dāng)目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)將會(huì)產(chǎn)生許多無用節(jié)點(diǎn),因此搜索效率低,但是,只要問題有解,用寬度優(yōu)先搜索總可以得到解,而且得到的是路徑最短的路徑。 深度優(yōu)先搜索法深度優(yōu)先搜索法 (1 1)基本思想)基本思想從初始狀態(tài)S0開始,利用算符,生成搜索樹下一層的任意一個(gè)節(jié)點(diǎn),檢查目標(biāo)節(jié)點(diǎn)是否出現(xiàn),若未出現(xiàn),以此節(jié)點(diǎn)利用一個(gè)算符生成再下一層的任一節(jié)點(diǎn),然后再檢查目標(biāo)節(jié)點(diǎn)是否出現(xiàn),若未出現(xiàn),繼續(xù)以上操作過程,一

19、直進(jìn)行到葉節(jié)點(diǎn)(即不能再生成新的狀態(tài)節(jié)點(diǎn)),當(dāng)它仍不是目標(biāo)節(jié)點(diǎn)時(shí),回溯到上一層,取另一可能擴(kuò)展搜索的分支。生成新的狀態(tài)節(jié)點(diǎn)。仍不是目標(biāo),采用相同的回溯辦法回退到上層節(jié)點(diǎn),擴(kuò)展可能的分支生成新狀態(tài)節(jié)點(diǎn)。如此一直下去,直到目標(biāo)節(jié)點(diǎn)出現(xiàn)。S0S1S2S3S11S12S21S22S31S111S121S122S221S311G(2 2)算法)算法1) 把初始節(jié)點(diǎn)S0故入OPEN表。2)如果OPEN表為空,則問題無解,退出 。 3)把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出放入CLOSED表。 4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是,則求得了問題的解,退出。 5)若節(jié)點(diǎn)n不可擴(kuò)展,則轉(zhuǎn)第2)步。 6)擴(kuò)展展

20、節(jié)點(diǎn)n,將其全部子節(jié)點(diǎn)放入到OPEN表的首部,并為其配置指向父節(jié)點(diǎn)的指針,然后轉(zhuǎn)第2)步。例子例子2 2: 對(duì)圖1所示的重排九宮問題進(jìn)行深度優(yōu)先搜索,可得到圖3所示的搜索樹這只是搜索樹的一部分,尚未到達(dá)目標(biāo)節(jié)點(diǎn),仍需繼續(xù)往下搜索。 在深度優(yōu)先搜索中,搜索一旦進(jìn)入某個(gè)分支,就將沿著該分支一直向下搜索。如果目標(biāo)節(jié)點(diǎn)恰好在此分支上,則可較快地得到解。但是,如果目標(biāo)節(jié)點(diǎn)不在此分支上,而該分支又是一個(gè)無窮分支,則就不能得到解。所以深度優(yōu)先搜索是不完備的,即使問題有解,它也不一定能求得解。顯然,用深度優(yōu)先求得的解,也不一定是路徑最短的解。 生成測(cè)試法生成測(cè)試法1)生成一個(gè)可能的狀態(tài)節(jié)點(diǎn);2) 檢查該狀態(tài)節(jié)

21、點(diǎn)是否是目標(biāo)節(jié)點(diǎn)。3)若是目標(biāo)節(jié)點(diǎn)則結(jié)束,若不是,回到1)步。爬山法爬山法1)開始狀態(tài)作為一個(gè)可能狀態(tài)。2)從一個(gè)可能狀態(tài),應(yīng)用算符生成所有新的可能狀態(tài)集。3)對(duì)該狀態(tài)集中的每一狀態(tài),進(jìn)行以下操作: 對(duì)該狀態(tài)進(jìn)行測(cè)試,檢索是否是目標(biāo)狀態(tài),是則結(jié)束, 計(jì)算該狀態(tài)的好壞,或者比較各狀態(tài)的好壞。4)取該狀態(tài)集中的最好狀態(tài),作為下一個(gè)可能狀態(tài)5)返回到第2)步。爬山法得不到目標(biāo)狀態(tài)的三種情況:1)局部極大點(diǎn):它比周圍鄰居狀態(tài)都好,但不是目標(biāo)。2)平頂:它與全部鄰居狀態(tài)都有同一值,構(gòu)成一個(gè)平面。3)山脊:它與線性鄰居狀態(tài)有相同值,比其他鄰居狀態(tài)要好。得不到目標(biāo)狀態(tài)時(shí)的處理辦法:1)退回到某一更早狀態(tài)節(jié)點(diǎn)

22、,沿另一方向進(jìn)行爬山。2)朝一個(gè)方向前進(jìn)一大步,走出平頂區(qū),按別的方向進(jìn)行爬山。3)同時(shí)朝兩個(gè)方向或多個(gè)方向前進(jìn)。啟發(fā)式搜索啟發(fā)式搜索v 啟發(fā)式搜索要用到問題自身的某些特性信息,以指導(dǎo)搜索朝著最有希望的方向前進(jìn)。v 用于估價(jià)節(jié)點(diǎn)重要性的函數(shù)稱為估價(jià)函數(shù)。其一般形式為; f(x)g(x)h(x)。 其中g(shù)(x)為從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x已經(jīng)實(shí)際付出的代價(jià);h(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的估計(jì)代價(jià),它體現(xiàn)了問題的啟發(fā)性信息,其形式要根據(jù)問題的特性確定。對(duì)啟發(fā)函數(shù)的分析:v 當(dāng)h(x)0,即f(x) g(x),取f(x)最小,即g(x)取最小,在已擴(kuò)展的節(jié)點(diǎn)中取最佳路徑, g(x)保證得到

23、最好的解,但對(duì)搜索速度沒幫助。v當(dāng)g(x)0,即f(x) h(x),h(x)是從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的耗費(fèi),取它最小,將加快搜索速度,當(dāng)不能保證得到最優(yōu)解。v g(x)為搜索樹的深度,h(x)0,則啟發(fā)方法為廣度優(yōu)先搜索法;v g(x)為搜索樹的深度的負(fù)樹,h(x)0,則啟發(fā)方法為深度優(yōu)先搜索法;v g(x)為初始狀態(tài)到該狀態(tài)節(jié)點(diǎn)的代價(jià),啟發(fā)方法為代價(jià)優(yōu)先搜索方法。(1)局部擇優(yōu)搜索 局部擇優(yōu)搜索是對(duì)深度優(yōu)先搜索方法的一種改進(jìn)。其基本思想是:當(dāng)一個(gè)節(jié)點(diǎn)被擴(kuò)展以后,按f(x)對(duì)每一個(gè)子節(jié)點(diǎn)計(jì)算估價(jià)值,并選擇最小者作為下一個(gè)要考察的節(jié)點(diǎn)。由于它每次都只是在子節(jié)點(diǎn)的范圍內(nèi)選擇下一個(gè)要考察的節(jié)點(diǎn),范圍比

24、較狹窄,所以稱為局部擇優(yōu)搜索。局部擇優(yōu)搜索的搜索過程:1)初始節(jié)點(diǎn)S0放入OPEN表,計(jì)算f(S0)。2)如果OPEN表為空,則問題無解,退出。3)把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出放入CLOSED表。4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是,則求得了問題的解,推出。5)若節(jié)點(diǎn)n不可擴(kuò)展,則轉(zhuǎn)第2)步。 6)擴(kuò)展節(jié)點(diǎn)n,用估價(jià)函數(shù)f(x)計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值,并按估價(jià)值從小到大的順序依次放到OPEN表的首都,為每個(gè)子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)的指針。然后轉(zhuǎn)第2)步。 (2)全局擇優(yōu)搜索 1)把初始節(jié)點(diǎn)S0放入OPEN表,計(jì)算f(S0)。 2)如果OPEN表為空,則搜索失敗,退出。 3)把OPEN表

25、中的第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)n)從表中移出放入CLOSED表。 4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是,則求得了問題的解,退出。 5)若節(jié)點(diǎn)n不可擴(kuò)展,則轉(zhuǎn)第2)步。 6)擴(kuò)展節(jié)點(diǎn)n,用估價(jià)函數(shù)f(x)計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值,并為每個(gè)子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)的指針,把這些子節(jié)點(diǎn)都送入OPEN表中,然后對(duì)0PEN表中的全部節(jié)點(diǎn)按估價(jià)值從小至大的順序進(jìn)行排序。然后轉(zhuǎn)第2)步。 4.3.1 專家系統(tǒng)的原理一.專家系統(tǒng)概念 專家系統(tǒng)是一種模擬人類專家解決領(lǐng)域問題的計(jì)算機(jī)程序系統(tǒng)。 解釋型、診斷型、調(diào)試型、預(yù)測(cè)型、維修型、教育型、規(guī)劃型、設(shè)計(jì)型、監(jiān)測(cè)型、控制型。 專家系統(tǒng)求解的問題可分為分類問題和構(gòu)造問題兩類。求解分類

26、問題的專家系統(tǒng)稱為分析型專家系統(tǒng),求解構(gòu)造問題的專家系統(tǒng)稱為設(shè)計(jì)型專家系統(tǒng)。二.專家系統(tǒng)的特點(diǎn) (1)知識(shí)的匯集 (2)啟發(fā)性推理 (3)推理和解釋的透明性 (4)知識(shí)更新三.專家系統(tǒng)的結(jié)構(gòu)專家知識(shí)獲取知識(shí)表示用戶人機(jī)接口知識(shí)庫推理機(jī)咨詢建議全局?jǐn)?shù)據(jù)庫 1.知識(shí)獲取與知識(shí)表示 知識(shí)獲取是指知識(shí)工程師如何從領(lǐng)域?qū)<夷抢铽@得將要納入知識(shí)庫的知識(shí), 知識(shí)表示要解決的問題是如何使用計(jì)算機(jī)能夠理解的形式來表示和存儲(chǔ)知識(shí)的問題。2. 知識(shí)庫(Knowledge Base) 以某種存儲(chǔ)結(jié)構(gòu)存儲(chǔ)領(lǐng)域?qū)<业闹R(shí),包括事實(shí)和可行的操作與規(guī)則等。 3.全局?jǐn)?shù)據(jù)庫 全局?jǐn)?shù)據(jù)庫(Global Database)也稱為總

27、數(shù)據(jù)庫,它用于存儲(chǔ)求解問題的初始數(shù)據(jù)和推理過程中得到的中間數(shù)據(jù)。 4.推理機(jī) 根據(jù)全局?jǐn)?shù)據(jù)庫的當(dāng)前內(nèi)容,從知識(shí)庫中選擇可匹配的規(guī)則,并通過執(zhí)行規(guī)則來修改數(shù)據(jù)庫中的內(nèi)容,再通過不斷地推理導(dǎo)出問題的結(jié)論。推理機(jī)中包含如何從知識(shí)庫中選擇規(guī)則的策略和當(dāng)有多個(gè)可用規(guī)則時(shí)如何消解規(guī)則沖突的策略。 5.人機(jī)接口 人機(jī)接口是系統(tǒng)與用戶進(jìn)行對(duì)話的界面。用戶通過人機(jī)接口輸入必要的數(shù)據(jù)、提出問題和獲得推理結(jié)果及系統(tǒng)作出的解釋;系統(tǒng)通過人機(jī)接口要求用戶回答系統(tǒng)的詢問,回答用戶的問題和解釋。 4.3.2 產(chǎn)生式規(guī)則專家系統(tǒng)一.產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則知識(shí)一般表示為: if A then B或表示為“如果A成立則B成立,簡(jiǎn)化

28、為A B。產(chǎn)生式規(guī)則知識(shí)的特點(diǎn):(1)相同的條件可以得出不同的結(jié)論;(2)相同的結(jié)論可以由不同的條件得到;(3)條件之間可以是“與(and)”連接和“或(or)”連接;(4)一條規(guī)則中的結(jié)論,可以是另一條規(guī)則中的條件。所以,規(guī)則知識(shí)集能 描述和解決各種不同的靈活的實(shí)際問題; 把規(guī)則知識(shí)集中的所有規(guī)則連成一棵“與或與或”樹(知樹(知識(shí)樹)識(shí)樹),也就是這些規(guī)則知識(shí)之間是有關(guān)聯(lián)的。二.推理樹(與或樹 ) 規(guī)則庫中的各條規(guī)則之間一般來說都是有聯(lián)系的,即某條規(guī)則的前提是另一條規(guī)則的結(jié)論。 按逆向推理的思想,把知識(shí)庫所含的總目標(biāo)(它是某些規(guī)則的結(jié)論)作為根節(jié)點(diǎn),按規(guī)則的前提和結(jié)論展開成一棵樹的形式,這棵

29、樹就是推理樹(與或樹、知識(shí)樹)。推理樹的特點(diǎn):(1)每條規(guī)則對(duì)應(yīng)的節(jié)點(diǎn)分支有與關(guān)系、或關(guān)系(2)樹的根節(jié)點(diǎn)是推理樹的總目標(biāo)(3)相鄰兩層是一條或多條規(guī)則連接(4)每個(gè)節(jié)點(diǎn)可以是單值,也可以是多值,若節(jié)點(diǎn)是多值,各值對(duì)應(yīng)的規(guī)則將不同(5)所有的葉節(jié)點(diǎn),都安排向用戶提問,或者把它的值直接存放在全局?jǐn)?shù)據(jù)庫中。推理樹的深度優(yōu)先搜索過程:1) 把根節(jié)點(diǎn)G放入OPEN表。2) 把OPEN表中的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出放入CLOSED表。3) 如果節(jié)點(diǎn)n可擴(kuò)展,則: 擴(kuò)展節(jié)點(diǎn)n,將其子節(jié)點(diǎn)放入OPEN表的首部,并為每個(gè)子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)的指針。 考察這些子節(jié)點(diǎn)中是否是終止節(jié)點(diǎn)。若有,則標(biāo)示這些終止節(jié)點(diǎn)

30、為可解節(jié)點(diǎn),并應(yīng)用可解標(biāo)示過程對(duì)其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)行標(biāo)示。如果初始節(jié)點(diǎn)G也被標(biāo)示為可解節(jié)點(diǎn),就得到可解樹,搜索成功,退出搜索過程;如果不能確定G為可解節(jié)點(diǎn),則從OPEN表中刪去具有可解先輩的節(jié)點(diǎn)。 轉(zhuǎn)第 2)步。4) 如果節(jié)點(diǎn)n不可擴(kuò)展,則: 標(biāo)示節(jié)點(diǎn)n為不可解節(jié)點(diǎn)。 應(yīng)用不可解標(biāo)示過程對(duì)節(jié)點(diǎn)n的先輩節(jié)點(diǎn)中不可解的節(jié)點(diǎn)進(jìn)行標(biāo)示。如果初始節(jié)點(diǎn)G也被標(biāo)示為不可解節(jié)點(diǎn),則搜索失敗,表明原始問題無解,退出搜索過程;如果不能確定G為不可解節(jié)點(diǎn),則從OPEN表中刪去具有不可解先輩的節(jié)點(diǎn)。 轉(zhuǎn)第 2)步 三.產(chǎn)生式規(guī)則專家系統(tǒng)的推理過程1.正向推理過程 正向推理是:根據(jù)在綜合數(shù)據(jù)庫中

31、給出的己知事實(shí),正向使用規(guī)則,即把規(guī)則的前件同當(dāng)前數(shù)據(jù)庫的內(nèi)容進(jìn)行匹配來選取可用規(guī)則,若有多條規(guī)則可用,則按沖突消解策略從中選擇一條規(guī)則執(zhí)行,將執(zhí)行規(guī)則的結(jié)論添加到綜合數(shù)據(jù)庫中,直至問題求解或沒有可用規(guī)則。正向推理過程可描述如下: procedure respond ( 將規(guī)則庫中規(guī)則的前提同當(dāng)前數(shù)據(jù)庫內(nèi)容匹配,若匹配成功,則找到一條可用規(guī)則送入到可用規(guī)則集S,否則,用下一條規(guī)則進(jìn)行匹配。) While S非空且問題未求解非空且問題未求解 do 調(diào)用調(diào)用selectrule(S) , 調(diào)用調(diào)用respond end2.逆向推理過程 根據(jù)在綜合數(shù)據(jù)庫中給出的假設(shè),反向使用規(guī)則,即把規(guī)則的后件同當(dāng)

32、前數(shù)據(jù)庫的內(nèi)容進(jìn)行匹配來選取可用規(guī)則,若有多條規(guī)則可用,則按沖突消解策略從中選擇一條規(guī)則,將該規(guī)則的前件添加到綜合數(shù)據(jù)庫中,直至問題求解(假設(shè)成立所需要的全部證據(jù)和事實(shí)在數(shù)據(jù)庫中)或沒有可用規(guī)則。反向推理過程可描述如下:precedure achieve(G) If S為空 then 向用戶直接詢問假設(shè)G的真假性,若用戶確認(rèn)G為真或假,則問題已求解;否則,把用戶回答的有關(guān)G的證據(jù)添加到數(shù)據(jù)庫中。else while G未求解 do begin 調(diào)用chooserule(S),從S中選擇一條規(guī)則R; G R的前件; if G未求解 then 調(diào)用achieve(G) if G為真 then 把規(guī)

33、則R的后件添加到數(shù)據(jù)庫中end4.3.3 專家系統(tǒng)與決策支持系統(tǒng)的集成一.IDSS中DSS與ES的結(jié)合體現(xiàn): 1.DSS與ES的總體結(jié)合 2.知識(shí)庫與模型庫的結(jié)合 3.數(shù)據(jù)庫和動(dòng)態(tài)數(shù)據(jù)庫的結(jié)合數(shù)據(jù)庫DSS控制系統(tǒng)模型庫動(dòng)態(tài)數(shù)據(jù)庫推理機(jī)和解釋器知識(shí)庫問題綜合與交互系統(tǒng)二.IDSS中DSS與ES的結(jié)合形式 1.DSS和ES并重的結(jié)構(gòu) 由集成系統(tǒng)完成對(duì)DSS和ES的控制和調(diào)度,根據(jù)實(shí)際問題的需要協(xié)調(diào)DSS和ES的運(yùn)行,DSS和ES并重。 (1)DSS與ES之外有綜合系統(tǒng),它具有調(diào)用和集成DSS和ES的能力; (2)將DSS的“問題綜合與人機(jī)交互系統(tǒng)”的功能擴(kuò)展,增加對(duì)ES的控制功能。 2.以DSS為主體的IDSS結(jié)構(gòu) 體現(xiàn)以定量分析為主,結(jié)合定性分析解決問題。該結(jié)構(gòu)中集成系統(tǒng)和DSS控制系統(tǒng)

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論