《智能決策支持系統(tǒng)和智能技術(shù)的決策支持.ppt》由會員分享，可在線閱讀，更多相關(guān)《智能決策支持系統(tǒng)和智能技術(shù)的決策支持.ppt（216頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

人工智能的決策支持和智能決策支持系統(tǒng),第4章目錄,4.1人工智能基本原理4.2專家系統(tǒng)與智能決策支持系統(tǒng)4.3神經(jīng)網(wǎng)絡(luò)的決策支持4.4遺傳算法的決策支持4.5機(jī)器學(xué)習(xí)的決策支持,4.1人工智能基本原理,1、人工智能的決策支持技術(shù)從智能決策支持系統(tǒng)的概念可知智能決策支持系統(tǒng)中包含了人工智能技術(shù)，與決策支持有關(guān)的人工智能技術(shù)主要有：專家系統(tǒng)、神經(jīng)網(wǎng)絡(luò)、遺傳算法、機(jī)器學(xué)習(xí)、自然語言理解等。,專家系統(tǒng)是利用大量的專門知識解決特定領(lǐng)域中的實(shí)際問題的計(jì)算機(jī)程序系統(tǒng)；神經(jīng)網(wǎng)絡(luò)是利用神經(jīng)元的信息傳播模型（MP模型）進(jìn)行學(xué)習(xí)和應(yīng)用；遺傳算法是模擬生物遺傳過程的群體優(yōu)化搜索方法；機(jī)器學(xué)習(xí)是讓計(jì)算機(jī)模擬和實(shí)現(xiàn)人類的學(xué)習(xí)，獲取解決問題的知識；自然語言理解是讓計(jì)算機(jī)理解和處理人類進(jìn)行交流的自然語言。,4.1人工智能基本原理,2．智能決策支持系統(tǒng)結(jié)構(gòu)形式1）基本結(jié)構(gòu)智能決策支持系統(tǒng)（IDSS）＝?jīng)Q策支持系統(tǒng)（DSS）＋人工智能（AI）技術(shù),4.1人工智能基本原理,,,,,,人工智能技術(shù)可以概括為：推理機(jī)＋知識庫智能決策支持系統(tǒng)的結(jié)構(gòu)可以簡化為圖4.2,4.2人工智能基本原理,4.2.1邏輯推理4.2.2知識表示與知識推理4.2.3搜索技術(shù),4.2.1邏輯推理,1.形式邏輯(人的思維形式、規(guī)律),（1）概念：反映事物的特有屬性和屬性的取值。（2）判斷：對概念的肯定或否定；判斷本身有對有錯(cuò)；判斷有全稱的肯定（或否定）判斷和存在的肯定（或否定）判斷。（3）推理：從一個(gè)或多個(gè)判斷推出一個(gè)新判斷的過程。,4.2.1邏輯推理,2.推理的種類,,演繹推理,歸納推理,類比推理,,假言推理,三段論推理,數(shù)學(xué)歸納法,假言易位推理,枚舉歸納推理,,1）演繹推理：從一般現(xiàn)象到個(gè)別（特殊）現(xiàn)象的推理。,2）歸納推理：從個(gè)別（特殊）現(xiàn)象到一般現(xiàn)象的推理。,3）類比推理：從個(gè)別（特殊）現(xiàn)象到個(gè)別（特殊）現(xiàn)象的推理。,1）演繹推理專家系統(tǒng)的研究基本上屬于演繹推理范疇。演繹推理的核心是假言推理。假言推理：以假言判斷為前提，對該假言判斷的前件或后件的推理。1）假言推理：p?q，p┝q2）三段論推理：p?q，q?r┝p?r3）假言易位推理（拒取式）：p?q，?q┝?p符號“┝”表示推出,4.2.1邏輯推理,2）歸納推理(個(gè)別→一般)（1）數(shù)學(xué)歸納法這種推導(dǎo)是嚴(yán)格的，結(jié)論是確實(shí)可靠的。（2）枚舉歸納推理S1是P，S2是P，……Sn是PS1……Sn是S類事物中的部分分子，沒有相反事例。所以，S類事物都是P。枚舉歸納推理的結(jié)論是或然的(并非必然地)，它的可靠性和事例數(shù)量相關(guān)。,4.2.1邏輯推理,枚舉歸納推理實(shí)例,如觀察到鐵受熱膨脹、銅受熱膨脹等事實(shí)而不知其所以然，由此推出“所有金屬受熱膨脹”的結(jié)論就是簡單枚舉歸納推理。,3）類比推理它是由兩個(gè)（或兩類）事物在某些屬性上相同，進(jìn)而推斷它們在另一個(gè)屬性上也可能相同的推理。A事物有abcd屬性,B事物有abc屬性（或a,b,c相似屬性）所以，B事物也可能有d屬性（或d相似屬性）類比推理的結(jié)論帶有或然性，它的可靠性和相類比事物屬性之間的聯(lián)系程度有關(guān)。,4.2.1邏輯推理,類比推理實(shí)例一,1816年的一天，法國醫(yī)生雷奈克出診為一位年輕的女性看病，一見病人，雷奈克犯起愁來：她身體非常肥胖，要診斷她的心臟和肺部是否正常，按當(dāng)時(shí)醫(yī)生慣用的方法，把耳朵貼近病人的胸部來聽，肯定聽不清楚，更何況她是一位年輕的女性。雷奈克抬頭看了看院子里正在玩耍的小孩，腦子里突然浮現(xiàn)出幾年前看到一個(gè)孩子們玩的游戲：一個(gè)孩子用釘子敲打木板的一頭，另外的孩子爭先恐后地抱著把耳朵貼近木板的另一頭，興致勃勃地傾聽著。,,為什么木頭能夠把聲音清晰地傳過來呢？雷奈克稍微想了想，只見他很很地拍了一下手說：“就是這樣！就是這樣！”雷奈克要來一疊紙，緊緊地卷成一個(gè)卷，然后把紙卷的一端放在姑娘的胸部，另一端放在自己的耳朵上，側(cè)著臉聽了起來?！罢媸且粋€(gè)妙法！”雷奈克高興地喊了一句?；氐郊依铮啄慰苏业揭桓景?，造成了歷史上第一個(gè)“聽診器”。,類比推理實(shí)例一,類比推理實(shí)例二,19世紀(jì)30年代，英國商人威爾斯以與馮燦的茂隆皮箱商行訂購的皮箱中有不是皮的木料為由，向香港法院起訴，蓄意敲詐馮燦。針對這種情況，馮燦的律師羅文錦取出口袋的金懷表，高聲問法官：“請問這是什么表？”法官答道：“這是金表，可是這與本案有什么關(guān)系？”羅文錦高舉金表，面對法庭上所有的人說：“有關(guān)系。這是金表，沒有人懷疑是吧？但是，請問，這塊金表除表面鍍金之外，內(nèi)部的機(jī)制都是金制嗎？”旁聽者同聲議論：“當(dāng)然不是?！绷_文錦繼續(xù)說：“那么人們?yōu)槭裁从纸兴鸨砟兀俊鄙宰魍ｎD又高聲說：“由此可見，茂隆行的皮箱案不過是原告無理取鬧、存心敲詐而已”原告理屈詞窮，法庭最后以威爾斯誣告，罰款5000元結(jié)案,,皮箱訴訟案的法庭辯論中，賣方律師在反駁中所使用的就是類比推理：表的外表有金，內(nèi)部含有不是金的材料，但卻是金表；箱的外表有皮，但也含有不是皮的材料；所以，箱仍是皮箱。,類比推理實(shí)例二,,,3.總結(jié)1）演繹推理的結(jié)論沒有超出已知的知識范圍。而歸納推理和類比推理的結(jié)論超出已知的知識范圍。演繹推理只能解釋一般規(guī)律中的個(gè)別現(xiàn)象而歸納推理和類比推理創(chuàng)造了新的知識，使科學(xué)得到新發(fā)展，是一種創(chuàng)造思維方式。2）演繹推理中由于前提和結(jié)論有必然聯(lián)系，只要前提為真，結(jié)論一定為真。歸納推理和類比推理中前提和結(jié)論，不能保證有必然聯(lián)系，具有或然性。這樣推理的結(jié)論未必是可靠的。需要經(jīng)過嚴(yán)格的驗(yàn)證和證明，使之形成新的理論。,4.2.1邏輯推理,4.2.2知識表示與知識推理,4.2.2.1數(shù)理邏輯表示法(自學(xué))4.2.2.1產(chǎn)生式規(guī)則4.2.2.3語義網(wǎng)絡(luò)4.2.2.4框架4.2.2.5劇本(自學(xué)),4.2.2.2產(chǎn)生式規(guī)則（ifAthenB）,1.正向推理逐條搜索規(guī)則庫，對每一條規(guī)則的前提條件，檢查事實(shí)庫中是否存在。前提條件中各子項(xiàng)，若在事實(shí)庫中不是全部存在，放棄該條規(guī)則。若在事實(shí)庫中全部存在，則執(zhí)行該條規(guī)則，把結(jié)論放入事實(shí)庫中。反復(fù)循環(huán)執(zhí)行上面過程，直至推出目標(biāo)，并存入事實(shí)庫中為止。,1.A∧B→G2.C∧D→A3.E→D,B,C,E,4.2.2.2產(chǎn)生式規(guī)則,事實(shí)庫的最后狀態(tài)為：,B，C，E，D，A，G,產(chǎn)生式規(guī)則庫事實(shí)庫,產(chǎn)生式規(guī)則庫和事實(shí)庫的初始狀態(tài)為：,4.2.2.2產(chǎn)生式規(guī)則,逆(反)向推理逆向推理是從目標(biāo)開始，尋找以此目標(biāo)為結(jié)論的規(guī)則對該規(guī)則的前提進(jìn)行判斷，若該規(guī)則的前提中某個(gè)子項(xiàng)是另一規(guī)則的結(jié)論時(shí)，再找以此結(jié)論的規(guī)則。重復(fù)以上過程，直到對某個(gè)規(guī)則的前提能夠進(jìn)行判斷。按此規(guī)則前提判斷（“是”或“否”）得出結(jié)論的判斷，由此回溯到上一個(gè)規(guī)則的推理，一直回溯到目標(biāo)的判斷。,G,A,D,E,B,C,,,,,,,,4.2.2.2產(chǎn)生式規(guī)則,逆向推理中，目標(biāo)改變過程：,1.A∧B→G2.C∧D→A3.E→D,B,C,E,產(chǎn)生式規(guī)則庫事實(shí)庫,4.2.3搜索技術(shù),搜索技術(shù)是人工智能的一個(gè)重要研究內(nèi)容。智能技術(shù)體現(xiàn)在減少搜索樹中的盲目搜索。1.執(zhí)行時(shí)間與ｎ，ｎ２，ｎ３等成正比的算法，稱為按多項(xiàng)式時(shí)間執(zhí)行。2.執(zhí)行時(shí)間與２ｎ，ｎ！和ｎｎ等成正比的算法，稱為按指數(shù)時(shí)間執(zhí)行。,按多項(xiàng)式時(shí)間執(zhí)行的算法，計(jì)算機(jī)是可以實(shí)現(xiàn)的。按指數(shù)時(shí)間執(zhí)行的算法，計(jì)算機(jī)是不可能實(shí)現(xiàn)的。,4.2.3搜索技術(shù),人工智能中發(fā)展了一種稱為啟發(fā)式搜索方法，基本思想可用一個(gè)實(shí)例來說明：一個(gè)外地人到某城市出差，他想到書店看看，又不知書店在何處，如果采取盲目搜索，從住地出發(fā)沿任一方向走，在分叉路口又任選一分支走，他可能走幾天幾夜也找不到如果采用啟發(fā)式方法，他會問路上的人，到書店怎樣走。城市中的大部分人對書店不知道，問不出來。,4.2.3搜索技術(shù),改一種問法：問該城市最熱鬧的地方在哪兒？按照這個(gè)啟發(fā)式信息沿著指路人的路線，乘車到達(dá)最熱鬧的地方但書店在哪兒，仍然不知道。如果盲目搜索，可能仍然找不到。如果采用啟發(fā)式方法，他會問路上的人，賣畫的地方在哪兒，他可以通過畫店再問書店在哪兒？啟發(fā)式方法能減少大量盲目無效的搜索，能有效克服按指數(shù)時(shí)間執(zhí)行的組合爆炸現(xiàn)象,4.2.3搜索技術(shù),搜索方法分類：1、基本搜索法（1）廣度優(yōu)先搜索法。（2）深度優(yōu)先搜索法。2、生成測試法。3、爬山法。4、啟發(fā)式搜索。5、博弈算法。（1）極小極大搜索法。（2）???剪枝算法。,4.2.3.1廣度優(yōu)先搜索（寬度優(yōu)先搜索）,1、廣度優(yōu)先搜索思想從初始狀態(tài)S開始，利用規(guī)則，生成所有可能的狀態(tài)。構(gòu)成樹的下一層節(jié)點(diǎn)，檢查是否出現(xiàn)目標(biāo)狀態(tài)G，若未出現(xiàn)，就對該層所有狀態(tài)節(jié)點(diǎn)，分別順序利用規(guī)則。生成再下一層的所有狀態(tài)節(jié)點(diǎn)，對這一層的所有狀態(tài)節(jié)點(diǎn)檢查是否出現(xiàn)G，若未出現(xiàn)，繼續(xù)按上面思想生成再下一層的所有狀態(tài)節(jié)點(diǎn).這樣一層一層往下展開。直到出現(xiàn)目標(biāo)狀態(tài)G為止。,圖4.7廣度優(yōu)先搜索示意圖,,（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ò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表的尾部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2)步。,廣度優(yōu)先搜索過程,例子1(八數(shù)碼難題)重排九宮問題，在3x3的方格棋盤上放置分別標(biāo)有數(shù)字1、2、3、4、5、6、7、8共8個(gè)棋子，初始狀態(tài)為S0，目標(biāo)狀態(tài)為Sg，如圖1所示?？墒褂玫乃惴校嚎崭褡笠?，空格上移，空格右移，空格下移。即只允許把位于空格左、上、右、下的鄰近棋子移入空格。要求尋找從初始狀態(tài)到目標(biāo)狀態(tài)的路徑。,,,?,,,該路徑使用的算符序列：空格上移，空格左移，空格下移，空格右移。廣度優(yōu)先搜索的盲目性較大，當(dāng)目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)將會產(chǎn)生許多無用節(jié)點(diǎn)，因此搜索效率低，但是，只要問題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的路徑。,由圖2可以看出，解的路徑是：S0——3——8——16——26,廣度優(yōu)先法適合于搜索樹的寬度較小的問題。,1、深度優(yōu)先搜索法思想從初始狀態(tài)S開始，利用規(guī)則生成搜索樹下一層任一個(gè)結(jié)點(diǎn)，檢查是否出現(xiàn)目標(biāo)狀態(tài)G，若未出現(xiàn)，以此狀態(tài)利用規(guī)則生成再下一層任一個(gè)結(jié)點(diǎn)，再檢查是否為目標(biāo)節(jié)點(diǎn)G。若未出現(xiàn)，繼續(xù)以上操作過程，一直進(jìn)行到葉節(jié)點(diǎn)（即不能再生成新狀態(tài)節(jié)點(diǎn)）。當(dāng)它仍不是目標(biāo)狀態(tài)G時(shí)，回溯到上一層結(jié)果，取另一可能擴(kuò)展搜索的分支。生成新狀態(tài)節(jié)點(diǎn)。一直進(jìn)行下去，直到找到目標(biāo)狀態(tài)G為止。,4.2.3.2深度優(yōu)先搜索法,圖4.8深度優(yōu)先搜索示意圖,,（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ò)展節(jié)點(diǎn)n，將其全部子節(jié)點(diǎn)放入到OPEN表的首部，并為其配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2)步。,深度優(yōu)先搜索,例子2：對圖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)先求得的解，也不一定是路徑最短的解。,深度優(yōu)先法適合于搜索樹的深度較小的問題,4.2.3.3生成測試法,生成測試法算法是：1、生成一個(gè)可能狀態(tài)節(jié)點(diǎn)。2、測試該狀態(tài)是否為目標(biāo)狀態(tài)。3、若是目標(biāo)狀態(tài)則結(jié)束。否則回到第1步其中：生成可能的狀態(tài)，可以是有規(guī)律的，也可以是無規(guī)律的,4.2.3.3生成測試法,（1）如果搜索過程中，總是利用剛生成出的狀態(tài)來生成新狀態(tài)，這種生成測試法就是深度優(yōu)先搜索法。（2）如果搜索過程中，總是利用舊狀態(tài)生成所有可能出新狀態(tài)，而且狀態(tài)節(jié)點(diǎn)以從舊到新的順序逐個(gè)生成的原則。這種生成測試法就是廣度優(yōu)先搜索法。（3）如果搜索過程中，有時(shí)利用舊狀態(tài)生成新狀態(tài)，有時(shí)利用新狀態(tài)生成新狀態(tài)，這就是無規(guī)律的生成測試法。,4.2.3.4爬山法(生成測試法的變種),爬山算法：(測試函數(shù))1.開始狀態(tài)作為一個(gè)可能狀態(tài)。2.從一個(gè)可能狀態(tài)，應(yīng)用規(guī)則生成所有新的可能狀態(tài)集。3.對該狀態(tài)集中每一狀態(tài)，進(jìn)行如下操作：⑴對該狀態(tài)測試，檢查是否為目標(biāo)，是則停止。⑵計(jì)算該狀態(tài)的好壞，或者比較各狀態(tài)的好壞。4.取狀態(tài)集中最好狀態(tài)，作為下一個(gè)可能狀態(tài)。5.循環(huán)到第2步。,在爬山法中可能出現(xiàn)以下幾種情況：,⑴局部極大點(diǎn)：它比周圍鄰居狀態(tài)都好，但不是目標(biāo)。,圖4.9局部極大點(diǎn)示意圖,在爬山法中可能出現(xiàn)以下幾種情況：,⑵平頂：它與全部鄰居狀態(tài)都有同一個(gè)值，構(gòu)成一個(gè)平面。,圖4.10平頂示意圖,在爬山法中可能出現(xiàn)以下幾種情況：,⑶山脊：它與線狀鄰居狀態(tài)有相同值，比其它鄰居狀態(tài)要好。,圖4.11山脊示意圖,4.2.3.4爬山法,為了解決以上問題，需要采用如下策略：（1）退回到某一更早狀態(tài)結(jié)點(diǎn)，沿著另一方向（對該結(jié)點(diǎn)就不一定是當(dāng)時(shí)最好值的方向）進(jìn)行爬山。（2）朝一個(gè)方向前進(jìn)一大步（按某方向深度優(yōu)先搜索多次），走出平頂區(qū)，按別方向進(jìn)行爬山。（3）同時(shí)朝兩個(gè)或多個(gè)方向前進(jìn)，即按兩個(gè)或多個(gè)方向爬山。,4.2.3.5啟發(fā)式搜索,啟發(fā)式搜索是對每個(gè)在搜索過程中遇到的新狀態(tài)，用一個(gè)估計(jì)函數(shù)（啟發(fā)式函數(shù)）并計(jì)算其值的大小，確定下一步將從哪一個(gè)狀態(tài)開始繼續(xù)前進(jìn)。一般以估計(jì)值小者為較優(yōu)的狀態(tài)，以此實(shí)行最優(yōu)搜索。估計(jì)函數(shù)值的大小與從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)的路徑有關(guān)。,4.2.3.5啟發(fā)式搜索,具體需要考慮以下問題：（1）下一步選擇哪個(gè)狀態(tài)結(jié)點(diǎn)？（2）是部分展開幾個(gè)狀態(tài)結(jié)點(diǎn)還是全部展開所有可能產(chǎn)生的狀態(tài)結(jié)點(diǎn)？（3）使用哪個(gè)規(guī)則（或算子）來展開新狀態(tài)結(jié)點(diǎn)？（4）怎樣決定舍棄還是保留新生成的狀態(tài)結(jié)點(diǎn)？（5）如何定義啟發(fā)式函數(shù)（估計(jì)值函數(shù)）？（6）如何決定搜索方向？（7）怎樣決定停止或繼續(xù)搜索？,一般啟發(fā)式函數(shù)法用如下公式表示：f（x）=g（x）+h（x）f（x）表示由開始狀態(tài)到目標(biāo)狀態(tài)的總耗費(fèi)g（x）表示開始狀態(tài)到當(dāng)前狀態(tài)的耗費(fèi)。h（x）表示當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的耗費(fèi)。,4.2.3.5啟發(fā)式搜索,啟發(fā)式函數(shù)分析：1.當(dāng)h（x）=0，即f（x）=g（x）取f（x）為最小，即取g（x）為最小。這要求在已擴(kuò)展的結(jié)點(diǎn)中取最佳路徑。g（x）能保證找到最好解。但對搜索速度沒有太多的幫助。2.當(dāng)g（x）=0，即f（x）=h（x）h（x）是從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的耗費(fèi)。取它最小，將會加快搜索速度，但它并不保證得到最優(yōu)解。,4.2.3.5啟發(fā)式搜索,g（x）選取的幾種特例：⑴g（x）為搜索樹的深度，h（x）=0，則啟發(fā)式方法為廣度優(yōu)先搜索法。⑵g（x）為搜索樹的深度的負(fù)數(shù)，h（x）=0，則啟發(fā)式方法為深度優(yōu)先搜索法。因?yàn)樯疃扔睿?fù)數(shù)愈大，搜索法總向深度發(fā)展。(3)g（x）為初始狀態(tài)到該結(jié)點(diǎn)的代價(jià),則啟發(fā)式方法為代價(jià)優(yōu)選搜索法。f(x)一般表示估計(jì)值，愈接近精確值，啟發(fā)式效果愈好。如果是精確值,就不是啟發(fā)式函數(shù)。,4.2.3.5啟發(fā)式搜索,圖-4啟發(fā)式搜索,,,*,,,,,,,,,,,,,,,,,,,,,*,4,4,5,5,4,5,3,5,4,2,3,0,5,4,5,5,4,5,3,2,0,4,h（x）可以定義為節(jié)點(diǎn)x中數(shù)碼位置與目標(biāo)節(jié)點(diǎn)相比不同的個(gè)數(shù),4.3專家系統(tǒng)與智能決策支持系統(tǒng)4.3.1專家系統(tǒng)原理4.3.2產(chǎn)生式規(guī)則專家系統(tǒng)4.3.3專家系統(tǒng)與DSS的集成4.3.4建模專家系統(tǒng)4.3.4智能決策支持系統(tǒng),4.3.1專家系統(tǒng)原理,1.專家系統(tǒng)概念1）專家系統(tǒng)定義專家系統(tǒng)是具有大量專門知識，并能運(yùn)用這些知識解決特定領(lǐng)域中實(shí)際問題的計(jì)算機(jī)程序系統(tǒng)。專家系統(tǒng)是利用大量的專家知識，運(yùn)用知識推理的方法來解決各特定領(lǐng)域中的實(shí)際問題。計(jì)算機(jī)專家系統(tǒng)這樣的軟件能夠達(dá)到人類專家解決問題的水平。,4.3.1專家系統(tǒng)原理,2）專家系統(tǒng)的特點(diǎn)專家系統(tǒng)需要大量的知識，這些知識是屬于規(guī)律性知識，它可以用來解決千變?nèi)f化的實(shí)際問題。,4.3.1專家系統(tǒng)原理,例如：求解微積分問題，是利用30～40條微分、積分公式來求解千變?nèi)f化的微分、積分問題，得出各自的結(jié)果。其中微積分公式就是規(guī)律性知識，求解微積分問題就是對某函數(shù)反復(fù)利用微積分公式進(jìn)行推導(dǎo)，最后得出該問題的結(jié)果。這個(gè)推理過程是一個(gè)不固定形式的推理，即前后用哪個(gè)公式，調(diào)用多少次這些公式都隨問題變化而變化。,1）專家系統(tǒng)對比數(shù)據(jù)庫檢索數(shù)據(jù)庫中存放的記錄可以看成是事實(shí)性知識。如果把檢索數(shù)據(jù)庫記錄看成是推理的話，它也是一種知識推理。它與專家系統(tǒng)的不同在于：（A）知識只含事實(shí)性知識，不包含規(guī)律性知識。（B）推理是對已有記錄的檢索，記錄不存在，則檢索不到。不能適應(yīng)變化的事實(shí)，推理不出新事實(shí)。,4.3.1專家系統(tǒng)原理,4.3.1專家系統(tǒng)原理,2）專家系統(tǒng)對比數(shù)值計(jì)算數(shù)值計(jì)算是用算法解決實(shí)際問題，對不同的數(shù)據(jù)可以算出不同的結(jié)果。如果把數(shù)據(jù)看成是知識，算法看成推理的話，它也是一種知識推理。它與專家系統(tǒng)的不同在于：（A）算法（推理過程）是固定形式的。算法一經(jīng)確定，推理過程就固定了。而專家系統(tǒng)的推理是不固定形式的，隨著問題不同，推理過程也不一樣。（B）數(shù)值計(jì)算只能處理數(shù)值，不能處理符號。,知識處理的特點(diǎn),從上面分析可見，數(shù)值計(jì)算、數(shù)據(jù)處理是知識處理的特定情況，知識處理則是它們的發(fā)展!（A）知識包括事實(shí)和規(guī)則（狀態(tài)轉(zhuǎn)變過程）。（B）適合于符號處理（如微積分求解）。（C）推理過程是不固定形式的（推導(dǎo)過程中每次選用的規(guī)則知識是變化的）。（D）能得出未知的事實(shí)（如推導(dǎo)出新的微分公式）。,2.專家系統(tǒng)結(jié)構(gòu)專家系統(tǒng)的核心是知識庫和推理機(jī)。專家系統(tǒng)可以概括為：專家系統(tǒng)＝知識庫+推理機(jī),4.3.1專家系統(tǒng)原理,知識獲取,人機(jī)接口,知識庫,推理機(jī),,,,,,,專家,用戶,咨詢建議,,專家系統(tǒng)核心,專家系統(tǒng)結(jié)構(gòu),3.產(chǎn)生式規(guī)則知識的推理機(jī)產(chǎn)生式規(guī)則的推理機(jī)＝搜索+匹配（假言推理）在推理過程中，是一邊搜索一邊匹配。匹配需要找事實(shí),這個(gè)事實(shí)一是來自于規(guī)則庫中別的規(guī)則，一是來自向用戶提問。在匹配時(shí)會出現(xiàn)成功或不成功，對于不成功的將引起搜索中的回溯和由一個(gè)分枝向另一個(gè)分枝的轉(zhuǎn)移，可見在搜索過程中包含了回溯。,4.3.1專家系統(tǒng)原理,4.3.1專家系統(tǒng)原理,4.產(chǎn)生式規(guī)則推理的解釋推理中的搜索和匹配過程，如果進(jìn)行跟蹤和顯示就形成了向用戶說明的解釋機(jī)制。好的解釋機(jī)制不顯示那些對于失敗路徑的跟蹤。,4.3.2產(chǎn)生式規(guī)則專家系統(tǒng),4.3.2.1產(chǎn)生式規(guī)則4.3.2.2推理樹(知識樹)4.3.2.3逆向推理過程4.3.2.4事實(shí)數(shù)據(jù)和解釋機(jī)制,4.3.2產(chǎn)生式規(guī)則專家系統(tǒng),產(chǎn)生式規(guī)則的優(yōu)點(diǎn)產(chǎn)生式規(guī)則知識表示形式容易被人理解它是基于演繹推理的,保證了推理結(jié)果的正確性大量產(chǎn)生式規(guī)則所連成的推理樹(知識樹),可以是多棵樹.樹的寬度—反映問題的范圍樹的深度—反映問題的難度,4.3.2.1產(chǎn)生式規(guī)則ES,產(chǎn)生式規(guī)則知識一般表示為:ifAthenB，或：如果A成立則B成立，或：A→B,4.3.2.1產(chǎn)生式規(guī)則,產(chǎn)生式規(guī)則知識表示允許有如下的特點(diǎn)：⒈相同的條件可以得出不同的結(jié)論。如：A─→BA─→C⒉相同的結(jié)論可以有不同的條件來得到。如A─→GB─→G⒊條件之間可以是“與”（AND）連接和“或”（OR）連接如A∧B─→GA∨B→G（相當(dāng)于A→G，B→G）⒋一條規(guī)則中的結(jié)論，可以是另一條規(guī)則中的條件。如F∧B→Ｚ，C∧Ｄ→F其中F在前一條規(guī)則中是條件，在后一條規(guī)則中是結(jié)論。,4.3.2.1產(chǎn)生式規(guī)則ES,由于以上特點(diǎn)，規(guī)則知識集能做到：能描述和解決各種不同的靈活的實(shí)際問題。（由前三點(diǎn)特點(diǎn)形成）能把規(guī)則知識集中的所有規(guī)則連成一棵“與、或”推理樹（知識樹）。即這些規(guī)則知識集之間是有關(guān)聯(lián)的（由后二個(gè)特點(diǎn)形成）。,4.3.2.2推理樹（知識樹）,規(guī)則庫中的各條規(guī)則之間一般來說都是有聯(lián)系的某條規(guī)則中的前提是另外一條規(guī)則中的結(jié)論。按逆向推理思想把知識庫所含的總目標(biāo)（它是某些規(guī)則的結(jié)論）作為根結(jié)點(diǎn)，按規(guī)則的前提和結(jié)論展開成一棵樹的形式。這棵樹一般稱為推理樹或知識樹，它把知識庫中的所有規(guī)則都連結(jié)起來由于連結(jié)時(shí)有“與”關(guān)系和“或”關(guān)系，從而構(gòu)成了“與或”推理樹。,,XF,G,LME,C,,,,,,,,,,,,4.3.2.2推理樹（知識樹）,（注：兩斜線中間的弧線表示“與”關(guān)系，無弧線表示“或”關(guān)系）,規(guī)則知識庫的逆向推理樹,例：若有知識庫為：A∨（B∧C）→G（I∧J）∨K→AX∧F→JL→BM∨E→CW∧Z→MP∧Q→E畫出“與或”推理樹,A,B,IJK,WZ,PQ,用規(guī)則的前提和結(jié)論形式畫出逆向推理樹形式為：,4.3.2.2推理樹（知識樹）,該“與或”推理樹的特點(diǎn)是：⒈每條規(guī)則對應(yīng)的節(jié)點(diǎn)分枝有與（AND）關(guān)系，或（OR）關(guān)系⒉樹的根結(jié)點(diǎn)是推理樹的總目標(biāo)⒊相鄰兩層之間是一條或多條規(guī)則連接⒋每個(gè)結(jié)點(diǎn)可以是單值，也可以是多值。若結(jié)點(diǎn)是多值時(shí)，各值對應(yīng)的規(guī)則將不同。⒌所有的葉結(jié)點(diǎn)，都安排向用戶提問，或者把它的值直接放在事實(shí)數(shù)據(jù)庫中。,4.3.2.2推理樹（知識樹）,4.3.2.3逆向推理過程,⒈推理樹的深度優(yōu)先搜索,逆向推理過程在推理樹中的反映為推理樹的深度優(yōu)先搜索過程。,4.3.2.3逆向推理過程,在計(jì)算機(jī)中實(shí)現(xiàn)時(shí)，并不把規(guī)則連成推理樹，而是利用規(guī)則棧來完成。當(dāng)調(diào)用此規(guī)則時(shí)，把它壓入棧內(nèi)（相當(dāng)于對樹的搜索），當(dāng)此規(guī)則的結(jié)論已求出（yes或no）時(shí)，需要將此規(guī)則退棧（相當(dāng)于對樹的回溯）。利用規(guī)則棧的壓入和退出的過程，相當(dāng)于完成了推理樹的深度優(yōu)先搜索和回溯過程。,4.3.2.3逆向推理過程,⒉結(jié)點(diǎn)的否定每個(gè)結(jié)點(diǎn)有兩種可能，即YES和NO。葉結(jié)點(diǎn)為NO是由用戶回答形成的。中間結(jié)點(diǎn)為NO是由葉結(jié)點(diǎn)為NO，回溯時(shí)引起該結(jié)點(diǎn)為NO。若當(dāng)該結(jié)點(diǎn)還有其它“或條件”分枝時(shí)，不能立即確定該結(jié)點(diǎn)為NO，必須再搜索另一分枝，當(dāng)另一分枝回溯為YES時(shí)，該結(jié)點(diǎn)仍為YES。中間結(jié)點(diǎn)只有所有“或”分枝的回溯值均為NO時(shí)，才能最后確定該中間結(jié)點(diǎn)為NO。,4.3.2.4事實(shí)數(shù)據(jù)庫和解釋機(jī)制,1.事實(shí)數(shù)據(jù)庫(動態(tài)數(shù)據(jù)庫),事實(shí)欄放入命題,規(guī)則號：事實(shí)取Y或N的理由,可信度：事實(shí)的可信度,2.解釋機(jī)制解釋機(jī)制是專家系統(tǒng)中重要內(nèi)容。它把推理過程顯示給用戶，讓用戶知道目標(biāo)是如何推導(dǎo)出來的。消除用戶對目標(biāo)結(jié)論的疑慮。兩種實(shí)現(xiàn)方法一種是推理過程的全部解釋；一種是推理過程中正確路徑的解釋。,4.3.2.4事實(shí)數(shù)據(jù)庫和解釋機(jī)制,4.3.3專家系統(tǒng)與決策支持系統(tǒng)集成,IDSS充分發(fā)揮了專家系統(tǒng)以知識推理形式解決定性分析問題的特點(diǎn).發(fā)揮了決策支持系統(tǒng)以模型計(jì)算為核心的解決定量分析問題的特點(diǎn).充分做到定性分析和定量分析的有機(jī)結(jié)合.,圖4.16智能決策支持系統(tǒng)集成結(jié)構(gòu)圖,綜合系統(tǒng),DSS和ES的總體結(jié)合。由集成系統(tǒng)把DSS和ES有機(jī)結(jié)合起來2.KB和MB的結(jié)合。模型庫中的數(shù)學(xué)模型和數(shù)據(jù)處理模型作為知識的一種形式，即過程性知識，加入到知識推理過程中去。3.DB和動態(tài)DB的結(jié)合。DSS中的DB可以看成是相對靜態(tài)的數(shù)據(jù)庫，它為ES中的動態(tài)數(shù)據(jù)庫提供初始數(shù)據(jù)，ES推理結(jié)束后，動態(tài)DB中的結(jié)果再送回到DSS中的DB中去。,DSS與ES集成形式一：DSS和ES并重的IDSS結(jié)構(gòu),4.3.3專家系統(tǒng)與決策支持系統(tǒng)集成,集成特點(diǎn)1.具有綜合系統(tǒng)，具有調(diào)用和集成DSS和ES的能力。2.擴(kuò)充DSS的問題與人機(jī)交互系統(tǒng)功能，增加對ES的調(diào)用組合能力DSS與ES的關(guān)系：DSS中DB與ES中的動態(tài)DB進(jìn)行數(shù)據(jù)交換解決問題的特點(diǎn)體現(xiàn)定性分析和定量分析并重解決問題的特點(diǎn)。,DSS與ES集成形式二：DSS為主體的IDSS結(jié)構(gòu),4.3.3專家系統(tǒng)與決策支持系統(tǒng)集成,集成特點(diǎn)集成系統(tǒng)和DSS控制系統(tǒng)合為一體DSS與ES的關(guān)系：ES被DSS控制系統(tǒng)調(diào)用解決問題的特點(diǎn)體現(xiàn)以定量分析為主，結(jié)果定性分析解決問題的特點(diǎn)。,圖4.19DSS作為推理形式的IDSS,圖4.20模型作為知識的IDSS,DSS與ES集成形式三：ES為主體的IDSS結(jié)構(gòu),4.3.3專家系統(tǒng)與決策支持系統(tǒng)集成,集成特點(diǎn)人機(jī)交互系統(tǒng)和ES合為一體,DSS與ES的關(guān)系：圖4.19DSS作為推理機(jī)，受ES的推理機(jī)控制；圖4.20數(shù)據(jù)模型作為知識出現(xiàn),解決問題的特點(diǎn)體現(xiàn)以定量分析為主，結(jié)果定性分析解決問題的特點(diǎn)。,4.3.4建模專家系統(tǒng),專家系統(tǒng)實(shí)現(xiàn)模型選擇的實(shí)例進(jìn)行說明。例如，彈簧振動建模專家系統(tǒng)。該專家系統(tǒng)是解決彈簧在不同受力情況下（包括沖力、摩擦力等）應(yīng)該滿足那種類型的微分方程模型。彈簧振動建模專家系統(tǒng)進(jìn)行簡化說明如下：,1、規(guī)則20條：R1：A∧B∧C∧Ｄ→M1R2：A1→AR3：A11→A1R4：A12→A1R5：A∧B∧E∧F∧Ｄ→M2R6：C1→CR7：E1→ER8：A∧B∧E∧F∧G→M3R9：A∧B∧C∧G→M4R10：B1→B,R11：H1→HR12：A2→AR13：H∧B∧C∧Ｄ→M5R14：H∧B∧C∧G→M6R15：H∧B∧E∧F∧Ｄ→M7R16：H∧B∧E∧F∧G→M8R17：A∧B∧E∧I∧Ｄ→M9R18：A∧B∧I∧G→M10R19：H∧B∧E∧I∧Ｄ→M11R20：H∧B∧E∧I∧G→M12,4.3.4建模專家系統(tǒng),A：彈簧滿足胡克定律B：彈簧質(zhì)量可以忽略C：可以忽略摩擦力D：沒有沖力A1：彈簧有線性恢復(fù)力A11：彈力與位移成正比A12：位移量很小E：要考慮摩擦力F：摩擦力與速度之間為線性關(guān)系C1：若振動為自發(fā)時(shí)振幅為常數(shù),E1：若振動為自發(fā)時(shí)振幅是遞減的G：有沖力F（T）B1：彈簧具有質(zhì)量N并且N/M遠(yuǎn)遠(yuǎn)小于1H1：彈簧勢能不是關(guān)于平衡位置對稱H：彈簧不潢足胡克定律A2：彈簧勢能與函數(shù)X（T）成正比I：摩擦力與速度之間為非線性關(guān)系,各項(xiàng)英文字母含義為：,M1：X″+（C2/M）X＝0M2：X″+（C1/M）X′+（C2/M）X＝0M3：X″+（C1/M）X′+（C2/M）X＝F（T）/MM4：X″+（C2/M）X＝F（T）/MM5：X″+F（X）/M＝0M6：X″+F（X）/M＝F（T）/MM7：X″+（C1/M）X′+F（X）/M＝0,M8：X″+（C1/M）X′+F（X）/M＝F（T）/MM9：X″+（G/M）X′+（C2/M）X＝0M10：X″+（G/M）X′+（C2/M）X＝F（T）/MM11：X″+（G/M）X′+F（X）/M＝0M12：X″+（G/M）X′+F（X）/M＝F（T）/M其中X″表示X對ｔ的二階導(dǎo)數(shù)，X′表示一階導(dǎo)數(shù)。,各模型微分方程為：,3.規(guī)則庫的推理樹將20條規(guī)則連成的推理樹見下圖所示。每個(gè)葉節(jié)點(diǎn)提問的回答為：Y－yes，N－no專家系統(tǒng)將解釋為證實(shí)某條規(guī)則而安排的提問。用戶不明白專家系統(tǒng)為什么要提該問題，可以回答Ｗ－why,4.3.4建模專家系統(tǒng),圖4.21彈簧振動推理樹的標(biāo)準(zhǔn)形式,專家系統(tǒng)應(yīng)用,現(xiàn)有一個(gè)彈簧，滿足如下特性：H1（彈簧勢能不是關(guān)于平衡位置對稱）B1（彈簧具有質(zhì)量N并且N/M遠(yuǎn)遠(yuǎn)小于1）C1（若振動為自發(fā)時(shí)振幅為常數(shù)）G（有沖力F（T））通過專家系統(tǒng)推理將得出：該彈簧滿足模型6（M6）的微分方程。,4.5遺傳算法的決策支持,4.5.1遺傳算法原理4.5.2優(yōu)化模型的遺傳算法求解4.5.3獲取知識的遺傳算法4.5.4遺傳規(guī)劃建立模型,4.5.1遺傳算法原理,遺傳算法(GeneticAlgorithm，GA)是模擬生物進(jìn)化的自然選擇和遺傳機(jī)制的一種尋優(yōu)算法。適用于復(fù)雜的非線性問題,主要應(yīng)用在組合優(yōu)化和機(jī)器學(xué)習(xí)兩個(gè)方面。應(yīng)用領(lǐng)域：圖像識別、圖像恢復(fù)、自適應(yīng)控制、優(yōu)化調(diào)度等領(lǐng)域。,遺傳算法的發(fā)展過程大體上可分為以下三個(gè)階段：（1）70年代的興起階段。1975年美國Michigan大學(xué)J.Holland首次系統(tǒng)地闡述了遺傳算法的基本理論和方法。在這一時(shí)期的大部分研究都處于理論研究和建立實(shí)驗(yàn)?zāi)Ｐ碗A段（2）80年代的發(fā)展階段。1980年Smith教授將遺傳算法應(yīng)用于機(jī)器學(xué)習(xí)領(lǐng)域，研制出了一個(gè)著名的分類器(Classifier)系統(tǒng)。這期間許多學(xué)者對遺傳算法進(jìn)行了大量的改進(jìn)和發(fā)展，提出了許多成功的遺傳算法模型，使遺傳算法應(yīng)用于更廣泛的領(lǐng)域。（3）90年代的高潮階段。進(jìn)入90年代后，遺傳算法作為一種實(shí)用、高效的優(yōu)化技術(shù)，得到了極為迅速的發(fā)展。,4.5.1遺傳算法原理,4.5.1遺傳算法原理,4.5.1.1遺傳算法工作過程4.5.1.2遺傳算法的理論基礎(chǔ)4.5.1.3遺傳算法的基本特征,4.5.1.1遺傳算法的工作過程,遺傳算法是一種群體型操作，該操作以群體中的所有個(gè)體為對象。個(gè)體就是模擬生物個(gè)體而對問題中的對象（一般就是問題的解）的一種稱呼，一個(gè)個(gè)體也就是搜索空間中的一個(gè)點(diǎn)。種群(population)就是模擬生物種群而由若干個(gè)體組成的群體,它一般是整個(gè)搜索空間的一個(gè)很小的子集。遺傳算法的三個(gè)主要操作算子：選擇（selecation）、交叉（crossover）和變異（mutation）構(gòu)成了遺傳操作（Geneticoperation），使遺傳算法具有了其他傳統(tǒng)方法所沒有的特性。,產(chǎn)生新一代群體,編碼和初始群體形成,,,,個(gè)體適應(yīng)值滿意否？,,,,,4.5.1.1遺傳算法的工作過程,首先將問題的每個(gè)可能的解按某種形式編碼，編碼后的解稱作染色體（個(gè)體）。隨機(jī)選取N個(gè)染色體構(gòu)成初始種群，再根據(jù)預(yù)定的評價(jià)函數(shù)對每個(gè)染色體計(jì)算適應(yīng)值，使得性能較好的染色體具有較高的適應(yīng)值。選擇適應(yīng)值高的染色體進(jìn)行復(fù)制，通過遺傳算子來產(chǎn)生一群新的更適應(yīng)環(huán)境的染色體，形成新的種群。這樣一代一代不斷繁殖，最后收斂到一個(gè)最適應(yīng)環(huán)境的個(gè)體上，求得問題的最優(yōu)解。,,1.群體中個(gè)體的編碼如何將問題描述成位串的形式，即問題編碼。一般將問題的參數(shù)用二進(jìn)制位（基因）編碼構(gòu)成子串，再將子串拼接起來構(gòu)成“染色體”位串。,4.5.1.1遺傳算法的工作過程,例如：個(gè)體染色體9----1001（2，5，6）----010101110,2.適應(yīng)值函數(shù)的確定遺傳算法的執(zhí)行過程中，每一代有許多不同的染色體（個(gè)體）同時(shí)存在，這些染色體中哪個(gè)保留(生存)、哪個(gè)淘汰(死亡)是根據(jù)它們對環(huán)境的適應(yīng)能力決定的，適應(yīng)性強(qiáng)的有更多的機(jī)會保留下來。適應(yīng)性強(qiáng)弱是計(jì)算個(gè)體適應(yīng)值函數(shù)f(x)的值來判別的，這個(gè)值稱為適應(yīng)值(fitness)。適應(yīng)值函數(shù)(即評價(jià)函數(shù))是根據(jù)目標(biāo)函數(shù)確定的。適應(yīng)值總是非負(fù)的，任何情況下總是希望越大越好。如果目標(biāo)函數(shù)不是取最大值時(shí)，需要將它映射成適應(yīng)值函數(shù)。適應(yīng)值函數(shù)f(x)的構(gòu)成與目標(biāo)函數(shù)有密切關(guān)系，往往是目標(biāo)函數(shù)的變種。一般是一個(gè)實(shí)值函數(shù)。該函數(shù)就是遺傳算法中指導(dǎo)搜索的評價(jià)函數(shù)。,4.5.1.1遺傳算法的工作過程,3.遺傳算法的三個(gè)算子（一）選擇(Selection)算子（二）交叉(Crossover)算子（三）變異(Mutation)算子,4.5.1.1遺傳算法的工作過程,它又稱復(fù)制(reproduction)、繁殖算子。選擇是從種群中選擇生命力強(qiáng)的染色體產(chǎn)生新種群的過程。依據(jù)每個(gè)染色體的適應(yīng)值大小，適應(yīng)值越大，被選中的概率就越大，其子孫在下一代產(chǎn)生的個(gè)數(shù)就越多。選擇操作是建立在群體中個(gè)體的適應(yīng)值估評基礎(chǔ)上的。,4.5.1.1遺傳算法的工作過程,（一）選擇(Selection)算子,通常做法是：對于一個(gè)規(guī)模為N的種群S,按每個(gè)染色體xi∈S的選擇概率P(xi)所決定的選中機(jī)會,分N次從S中隨機(jī)選定N個(gè)染色體,并進(jìn)行復(fù)制。,4.5.1.1遺傳算法的工作過程,（一）選擇(Selection)算子,（二）交叉(crossover)算子,它又稱重組(recombination)、配對(breeding)算子，在遺傳算法中起著核心作用。染色體重組是分兩步驟進(jìn)行的:首先在新復(fù)制的群體中隨機(jī)選取兩個(gè)個(gè)體然后，沿著這兩個(gè)個(gè)體(字符串)隨機(jī)地取一個(gè)位置，二者互換從該位置起的末尾部分。交叉率(crossoverrate)就是參加交叉運(yùn)算的染色體個(gè)數(shù)占全體染色體總數(shù)的比例，記為Pc,取值范圍一般為0.4～0.99。,4.5.1.1遺傳算法的工作過程,4.5.1.1遺傳算法的工作過程,例1:有兩個(gè)用二進(jìn)制編碼的個(gè)體A和B。長度L=5，A=a1a2a3a4a5，B=b1b2b3b4b5隨機(jī)選擇一整數(shù)k∈[1，L-1]，設(shè)k=4，經(jīng)交叉后變?yōu)椋篈=a1a2a3|a4a5B=b1b2b3|b4b5A’=a1a2a3b4b5B’=b1b2b3a4a5,s1′=01000101,s2′=10011011可以看做是原染色體s1和s2的子代染色體。,例2,設(shè)染色體s1=01001011,s2=10010101,交換其后4位基因,即,（二）交叉(crossover)算子,變異就是以很小的概率，隨機(jī)地改變字符串某個(gè)位置上的值。變異操作是按位（bit）進(jìn)行的，即把某一位的內(nèi)容進(jìn)行變異。在二進(jìn)制編碼中，就是將某位0變成1，1變成0。選擇和交叉算子基本上完成了遺傳算法的大部分搜索功能，而變異則增加了遺傳算法找到接近最優(yōu)解的能力。變異率(mutationrate)是指發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，記為Pm，取值范圍一般為0.0001～0.02。它保證了遺傳算法的有效性。,4.5.1.1遺傳算法的工作過程,（三）變異(Mutation)算子,4.5.1.1遺傳算法的工作過程,例如:設(shè)染色體s=11001101將其第三位上的0變?yōu)?,即s=11001101→11101101=s′。s′也可以看做是原染色體s的子代染色體。,（三）變異(Mutation)算子,4.控制參數(shù)設(shè)定遺傳算法中的參數(shù)包括群體中個(gè)體的數(shù)目、交叉概率、變異概率等這些參數(shù)的設(shè)定隨具體問題的不同將有所差別，帶有經(jīng)驗(yàn)性，它會影響遺傳算法的迭代收斂過程。,4.5.1.1遺傳算法的工作過程,1.模式定理遺傳算法的理論基礎(chǔ)是Holland提出的模式定理。一個(gè)模式(Schema)就是一個(gè)描述種群中在位串的某些確定位置上具有相似性的位串子集的相似性模板(SimilarityTemplate)。二進(jìn)制串中的模式是如下的形式：（a1，a2，…，ai，…，an），ai∈{0，1，*}，其中“*”是任意符，或0，或1，模式是串的集合.模式H中確定位的個(gè)數(shù),稱為H的階,記為O(H)。模式H中第一個(gè)確定位與最后一個(gè)確定位之間的距離稱為的定義距,記為δ(H)。,4.5.1.2遺傳算法的理論基礎(chǔ),例:以長度L=5的串為例,模式*101*描述了在位置2、3、4具有形式“010”的所有字符串,：*101*={(11010)，(01010)，(01011)，(11011)}。其階為3,定義距為2。,1.模式定理模式定理是遺傳算法的理論基礎(chǔ)它說明高適應(yīng)值、長度短、階數(shù)低的模式在后代中至少以指數(shù)增長包含該模式H的位串的數(shù)目。遺傳使高適應(yīng)值的模式復(fù)制更多的后代！,4.5.1.2遺傳算法的理論基礎(chǔ),2．基因塊假設(shè)高適應(yīng)值、長度短、低階的模式叫基因塊?；驂K假說基因塊通過遺傳操作繁殖、交換、變異，再繁殖、再交換、再變異的逐漸進(jìn)化，形成潛在的適應(yīng)性較高的位串。該假設(shè)指出，通過遺傳算法能尋找到接近全局最優(yōu)解的能力。,4.5.1.2遺傳算法的理論基礎(chǔ),1.遺傳算法的處理對象是問題參數(shù)的編碼個(gè)體（位串）遺傳算法要求將問題的參數(shù)編碼成長度有限的位串。遺傳算法是在求解問題的編碼串上進(jìn)行操作，從中找出高適應(yīng)值的位串，而不是對問題目標(biāo)函數(shù)和它們的參數(shù)直接操作。遺傳算法不受函數(shù)限制條件(如導(dǎo)數(shù)存在、連續(xù)性、單極值等)的約束。,4.5.1.3遺傳算法的基本特征,2.遺傳算法的搜索是從問題解位串集開始搜索，而不是從單個(gè)解開始在最優(yōu)化問題中，傳統(tǒng)的方法是從一個(gè)點(diǎn)開始搜索，如爬山法。一般復(fù)雜問題會在“地形”中出現(xiàn)若干“山峰”，傳統(tǒng)的方法很容易走入假“山峰”。遺傳算法同時(shí)從種群的每個(gè)個(gè)體開始搜索，象一張網(wǎng)罩在“地形”上，數(shù)量極大的個(gè)體同時(shí)在很多區(qū)域中進(jìn)行搜索，這樣就減少了陷入局部解的可能性。,4.5.1.3遺傳算法的基本特征,3.遺傳算法只使用目標(biāo)函數(shù)(即適應(yīng)值)來搜索，而不需要導(dǎo)數(shù)等其他輔助信息傳統(tǒng)搜索算法需要一些輔助信息，如梯度算法需要導(dǎo)數(shù)，當(dāng)這些信息不存在時(shí)，這些算法就失效了。而遺傳算法只需目標(biāo)函數(shù)和編碼串，因此，遺傳算法幾乎可以處理任何問題。4.遺傳算法使用的三種遺傳算子是一種隨機(jī)操作，而不是確定性規(guī)則遺傳算法使用隨機(jī)操作，但并不意味著遺傳算法是簡單的隨機(jī)搜索。遺傳算法是使用隨機(jī)工具來指導(dǎo)搜索向著一個(gè)最優(yōu)解前進(jìn)。5.隱含的并行性6.易介入到已有的模型中，并具有擴(kuò)展性；易于同別的技術(shù)結(jié)合使用,4.5.1.3遺傳算法的基本特征,4.5.2優(yōu)化模型的遺傳算法求解,優(yōu)化模型的計(jì)算是遺傳算法最基本的也是最重要的研究和應(yīng)用領(lǐng)域之一。一般說來，優(yōu)化計(jì)算問題通常帶有大量的局部極值點(diǎn)，往往是不可微的、不連續(xù)的、多維的、有約束條件的、高度非線性的NP完全問題。精確地求解優(yōu)化問題的全局最優(yōu)解一般是不可能的。,4.5.2優(yōu)化模型的遺傳算法求解,4.5.2.1優(yōu)化模型的遺傳算法處理4.5.2.2實(shí)例,1、適應(yīng)值函數(shù)優(yōu)化遺傳算法在進(jìn)化搜索中用目標(biāo)函數(shù)即適應(yīng)值函數(shù)為依據(jù)。遺傳算法的目標(biāo)原函數(shù)不受連續(xù)可微的約束且定義域可以為任意集合對目標(biāo)函數(shù)的唯一要求是，對輸入個(gè)體可計(jì)算出能進(jìn)行比較的非負(fù)適應(yīng)值。這一特點(diǎn)使得遺傳算法應(yīng)用范圍很廣。遺傳算法中，適應(yīng)值函數(shù)要比較排序，并在此基礎(chǔ)上計(jì)算選擇概率，所以適應(yīng)值函數(shù)的值要取正值。適應(yīng)值函數(shù)評估是選擇操作的依據(jù)，適應(yīng)值函數(shù)設(shè)計(jì)直接影響到遺傳算法的性能。在不少場合，將目標(biāo)函數(shù)映射成求最大值形式且函數(shù)值非負(fù)的適應(yīng)值函數(shù)是必要的。,4.5.2.1優(yōu)化模型的遺傳算法處理,2、約束條件的處理遺傳算法是由適應(yīng)值來評估和引導(dǎo)搜索，而對求解問題的約束條件不能明確地表示出來。用遺傳算法求解這些帶約束的問題，需要進(jìn)行一些處理。在等式約束方程中，對P個(gè)等式方程中抽出P個(gè)變量，經(jīng)過線性組合變換后，用其余變量表示為該P(yáng)個(gè)變量的等式，并將它代入目標(biāo)函數(shù)中，消去該P(yáng)個(gè)變量。這樣，在目標(biāo)函數(shù)中，就包含了這些等式約束條件。,4.5.2.1優(yōu)化模型的遺傳算法處理,4.5.2.1優(yōu)化模型的遺傳算法處理,3、遺傳算法的迭代終止條件當(dāng)適應(yīng)值函數(shù)的最大值已知時(shí)，一般以發(fā)現(xiàn)滿足最大值或準(zhǔn)最優(yōu)解作為遺傳算法迭代終止條件。但是，在許多優(yōu)化計(jì)算問題中，適應(yīng)值函數(shù)的最大值并不清楚，迭代終止條件一般定為：群體中個(gè)體的進(jìn)化已趨于穩(wěn)定狀態(tài)，即發(fā)現(xiàn)占群體中一定比例的個(gè)體已完全是同一個(gè)體。,步1在搜索空間U上定義一個(gè)適應(yīng)度函數(shù)f(x)，給定種群規(guī)模N，交叉率Pc和變異率Pm，代數(shù)T；步2隨機(jī)產(chǎn)生U中的N個(gè)個(gè)體s1,s2,…,sN，組成初始種群S={s1,s2,…,sN}，置代數(shù)計(jì)數(shù)器t=1；步3計(jì)算S中每個(gè)個(gè)體的適應(yīng)度f()；步4若終止條件滿足，則取S中適應(yīng)度最大的個(gè)體作為所求結(jié)果，算法結(jié)束。步5按選擇概率P(xi)所決定的選中機(jī)會，每次從S中隨機(jī)選定1個(gè)個(gè)體并將其染色體復(fù)制，共做N次，然后將復(fù)制所得的N個(gè)染色體組成群體S1；步6按交叉率Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機(jī)確定c個(gè)染色體，配對進(jìn)行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體S2；步7按變異率Pm所決定的變異次數(shù)m，從S2中隨機(jī)確定m個(gè)染色體，分別進(jìn)行變異操作，并用產(chǎn)生的新染色體代替原染色體，得群體S3；步8將群體S3作為新一代種群，即用S3代替S，t=t+1，轉(zhuǎn)步3；,基本遺傳算法步聚,例4.1利用遺傳算法求解區(qū)間［0,31］上的二次函數(shù)y=x2的最大值。,分析原問題可轉(zhuǎn)化為在區(qū)間［0,31］中搜索能使y取最大值的點(diǎn)a的問題。那么，［0,31］中的點(diǎn)x就是個(gè)體,函數(shù)值f(x)恰好就可以作為x的適應(yīng)度，區(qū)間［0,31］就是一個(gè)(解)空間。這樣,只要能給出個(gè)體x的適當(dāng)染色體編碼,該問題就可以用遺傳算法來解決。,解(1)設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。將種群規(guī)模設(shè)定為4；用5位二進(jìn)制數(shù)編碼染色體；取下列個(gè)體組成初始種群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)(2)定義適應(yīng)度函數(shù),取適應(yīng)度函數(shù)：f(x)=x2(3)計(jì)算各代種群中的各個(gè)體的適應(yīng)度,并對其染色體進(jìn)行遺傳操作,直到適應(yīng)度最高的個(gè)體(即31（11111）)出現(xiàn)為止。,,首先計(jì)算種群S1中各個(gè)體s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)的適應(yīng)度f(si)。容易求得f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361,再計(jì)算種群S1中各個(gè)體的選擇概率。,選擇概率的計(jì)算公式為,由此可求得P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31,賭輪選擇示意,●賭輪選擇法,在算法中賭輪選擇法可用下面的子過程來模擬:①在［0,1］區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)r。②若r≤q1,則染色體x1被選中。③若qk-10有：,由上式易知，公式發(fā)現(xiàn)問題可以看成如下優(yōu)化問題：,1、遺傳規(guī)劃個(gè)體編碼設(shè)計(jì)對于遺傳規(guī)劃問題，搜索優(yōu)化公式是在函數(shù)空間上進(jìn)行的，采用二叉樹描述遺傳規(guī)劃個(gè)體。在把樹轉(zhuǎn)化為二叉樹中，樹的第一棵子樹變?yōu)槎鏄涞淖笞訕?，子樹的兄弟變?yōu)槎鏄渲性撟笞訕涞挠易訕?，如此遞歸，形成樹和二叉樹的一一對應(yīng)關(guān)系。,4.5.4.1遺傳規(guī)劃建立模型的設(shè)計(jì)與實(shí)現(xiàn),,例如表達(dá)式f(x)=f1(x1,x2,x3)+f2(x1,C1)+C2用樹及二叉樹分別表示如下圖所示。,初始化群體隨機(jī)生成具有μ個(gè)公式模型的初始群體。根據(jù)公式的編碼表示，這里每個(gè)公式對應(yīng)一個(gè)二叉樹，公式的復(fù)雜度可以由樹的深度來控制。樹的中間結(jié)點(diǎn)和葉結(jié)點(diǎn)元素分別從函數(shù)空間中按均勻分布選取。公式個(gè)體適應(yīng)度評估計(jì)算群體內(nèi)每個(gè)公式的適應(yīng)值。適應(yīng)度函數(shù)的確立應(yīng)反映公式發(fā)現(xiàn)的目標(biāo)，通常不僅希望誤差小而且希望公式的形式比較簡單。,4.5.4.1遺傳規(guī)劃建立模型的設(shè)計(jì)與實(shí)現(xiàn),2、遺傳算子（1）選擇算子根據(jù)一定的選擇策略對每個(gè)個(gè)體分配選擇概率，再根據(jù)選擇概率并使用輪盤式選擇來選擇個(gè)體進(jìn)行繁殖，采用擇優(yōu)策略，將上代最好的個(gè)體保留在當(dāng)前新的種群中，保證了算法的收斂性。（2）交換算子由于遺傳規(guī)劃中的函數(shù)的不同，定義域和值域的差異，遺傳規(guī)劃的搜索空間過大，趨向于隨機(jī)搜索。所以，不能仿照遺傳算法進(jìn)行設(shè)計(jì)遺傳規(guī)劃的遺傳算子。（具體見書）,4.5.4.1遺傳規(guī)劃建立模型的設(shè)計(jì)與實(shí)現(xiàn),（3）變異算子變異算子首先在父體中隨機(jī)選擇一個(gè)結(jié)點(diǎn)（稱為變異點(diǎn)），若變異點(diǎn)是內(nèi)部結(jié)點(diǎn)（即非葉結(jié)點(diǎn)），則執(zhí)行下述三種操作之一：刪除以變異點(diǎn)為根結(jié)點(diǎn)的子樹（稱為變異子樹），并在變異點(diǎn)插入一個(gè)隨機(jī)生成的子樹；交換變異子樹的左右子樹；化簡變異子樹，用計(jì)算獲得的值替代某些部分,4.5.4.1遺傳規(guī)劃建立模型的設(shè)計(jì)與實(shí)現(xiàn),step1.根據(jù)給定參數(shù)，隨機(jī)產(chǎn)生初始群體F(0)，計(jì)算F(0)中個(gè)體的適應(yīng)度。適應(yīng)度由誤差公式得出；step2.根據(jù)個(gè)體適應(yīng)度及選擇策略確定F(T)內(nèi)每個(gè)個(gè)體的選擇概率Pi；step3.根據(jù)給定參數(shù)，確定交換操作的個(gè)體數(shù)量為2M(交換操作的個(gè)體數(shù)量應(yīng)為偶數(shù))、變異個(gè)體數(shù)量為N；,基于遺傳規(guī)劃的公式發(fā)現(xiàn)算法流程設(shè)計(jì),step4.依據(jù)概率Pi，在F(T)中選擇2M個(gè)個(gè)體執(zhí)行交換操作step5.執(zhí)行變異操作，利用變異算子，產(chǎn)生N個(gè)個(gè)體，插入到F(T)中；step6.執(zhí)行選擇操作，在F(T)中依據(jù)個(gè)體適應(yīng)度，選擇給定數(shù)量的新個(gè)體組成新的群體F(T+1)；step7.計(jì)算F(T+1)中個(gè)體的適應(yīng)值，迭代次數(shù)+1；step8.終止條件判定：發(fā)現(xiàn)公式的誤差小于預(yù)定誤差或者遺傳規(guī)劃的遺傳代數(shù)超過預(yù)先定義的值則終止。滿足終止條件，輸出結(jié)果；不滿足終止條件，則返回Step2繼續(xù)迭代,基于遺傳規(guī)劃的公式發(fā)現(xiàn)算法流程設(shè)計(jì),有如下已知數(shù)據(jù)：遺傳建模主要參數(shù)設(shè)置：種群規(guī)模500，最大進(jìn)化代數(shù)50，個(gè)體創(chuàng)建時(shí)最大樹深10，交換操作時(shí)樹深限制20，算子空間F={+，-，*，/，log，sin，cos，abs，sqrt，x，x2，x3，x-1，x-2}。遺傳規(guī)劃發(fā)現(xiàn)公式為：(x)=x2+log(x+1)+log7,3、遺傳規(guī)劃建立模型應(yīng)用實(shí)例,,計(jì)算結(jié)果發(fā)現(xiàn)公式的誤差：0.032345公式發(fā)現(xiàn)結(jié)果顯示：,,“蟲與草游戲”,草地上有著一群吃草的蟲子。(這些蟲子不能看見遠(yuǎn)處什么地方有草)每個(gè)蟲子都按自己的“遺傳策略”爬行，碰到草就將草吃掉，沒有碰到就繼續(xù)爬行……而草被吃掉后，過一段時(shí)間又會(隨機(jī)的)長出來?，F(xiàn)在的問題是：怎樣的“爬行策略”才是“智慧”的——能夠讓蟲子吃到最多的草？,要回答這個(gè)問題，就可以使用“常階遺傳算法”：將蟲子使用的“爬行策略”編碼成“基因串”；讓那些吃到足夠多的草的蟲子繁殖后代——“遺傳基因串”，反之沒到草的蟲子就讓它“餓死”。經(jīng)過很多代的“基因遺傳”后，我們會看到“爬行策略”開始向“問題的解”“收斂”。,遺傳收斂可以看到隨著算法的運(yùn)行，蟲“直走的概率”會慢慢變大——“長途遷徙”的蟲子會越來越多，“原地打圈”的蟲子則會被淘汰，這就是“遺傳算法的收斂”。要想“遺傳收斂”得“快”，“寬與高”就應(yīng)該足夠大，“生長草”的概率可以相應(yīng)降低些。比如，寬=60,高=60，草能量=6，草概率=0.002，繁殖能量=120，初始蟲數(shù)量=18,4.5機(jī)器學(xué)習(xí)的決策支持,4.5.1機(jī)器學(xué)習(xí)概述4.5.2機(jī)器學(xué)習(xí)分類4.5.3建立模型的發(fā)現(xiàn)學(xué)習(xí),4.5.1機(jī)器學(xué)習(xí)綜述,1.基本概念學(xué)習(xí)和解決問題是人類最重要的兩個(gè)智能行為機(jī)器學(xué)習(xí)是讓計(jì)算機(jī)模擬和實(shí)現(xiàn)人類的學(xué)習(xí)，獲取知識。機(jī)器學(xué)習(xí)也是計(jì)算機(jī)具有智能的重要標(biāo)志。,4.5.1機(jī)器學(xué)習(xí)綜述,(1)人類學(xué)習(xí)概念的學(xué)習(xí)、領(lǐng)域知識的學(xué)習(xí)、技能（元知識即解決問題）的學(xué)習(xí)特點(diǎn)：過程緩慢、會忘記、知識傳授困難、能不斷修改知識，使人類逐漸變得聰明。,4.5.1機(jī)器學(xué)習(xí)綜述,(2)機(jī)器學(xué)習(xí)（1）R.S.Michalski認(rèn)為：學(xué)習(xí)是構(gòu)造或修改所經(jīng)歷的事物的表示。該觀點(diǎn)強(qiáng)調(diào)知識的表示。（2）學(xué)習(xí)是知識的獲取。該觀點(diǎn)強(qiáng)調(diào)知識獲取。（3）H.A.Simon認(rèn)為：學(xué)習(xí)是系統(tǒng)在相似的任務(wù)中，做一些適應(yīng)性變化，使得在下一次類似的任務(wù)中，做得更好。該觀點(diǎn)強(qiáng)調(diào)學(xué)習(xí)的效果。,4.5.1機(jī)器學(xué)習(xí)綜述,2.機(jī)器學(xué)習(xí)與專家系統(tǒng)專家系統(tǒng)知識獲取的“瓶頸”現(xiàn)象知識的脆弱性缺乏直覺判斷能力機(jī)器學(xué)習(xí)提供知識獲取提供有效途徑,4.5.1機(jī)器學(xué)習(xí)綜述,3.機(jī)器學(xué)習(xí)實(shí)例1.Michalski和R.L.Chilausky的PLANT/SS系統(tǒng)它是一個(gè)大豆病害診斷防治專家系統(tǒng)。該系統(tǒng)用示例學(xué)習(xí)AQ11算法自動產(chǎn)生規(guī)則進(jìn)行診斷。把631種有病害的大豆的性狀描述（表示為包含35種特性的向量）和每種植物的病名一起輸入到計(jì)算機(jī)中選用290種做為訓(xùn)練例子（例子間相差很遠(yuǎn)），利用AQ11算法獲得規(guī)則知識。再用340個(gè)樣本作為測試?yán)?，并將專家和?jì)算機(jī)的診斷結(jié)果進(jìn)行對比。,4.5.1機(jī)器學(xué)習(xí)綜述,計(jì)算機(jī)產(chǎn)生的規(guī)則優(yōu)于專家歸納的規(guī)則專家的正確判斷率為71.8％。計(jì)算機(jī)的正確判斷率高達(dá)97.6％。,4.5.1機(jī)器學(xué)習(xí)綜述,鐘鳴和陳文偉的IBLE算法利用信息論的信道容量思想，研制了IBLE算法。對已有結(jié)論的化學(xué)物質(zhì)的質(zhì)譜進(jìn)行學(xué)習(xí)，得出了質(zhì)譜規(guī)則。然后利用這些規(guī)則再去測試未知化學(xué)物質(zhì)的質(zhì)譜，得出它的種類。,鐘鳴和陳文偉的IBLE算法,一般專家的正確識別率70%,4.5.2機(jī)器學(xué)習(xí)分類,學(xué)習(xí)過程的本質(zhì)是學(xué)生(學(xué)習(xí)系統(tǒng))把教師或環(huán)境(如書本)提供的信息轉(zhuǎn)換成能夠理解的形式記憶下來，以便將來使用.當(dāng)前,國際上流行的機(jī)器學(xué)習(xí)分類方法主要有四種:按應(yīng)用領(lǐng)域分類(專家系統(tǒng)、問題求解、認(rèn)知模擬）按獲取知識的表示分類(邏輯表達(dá)式、產(chǎn)生式規(guī)則、決策樹、框架、神經(jīng)網(wǎng)絡(luò))按推理策略分類(演繹推理和歸納推理)機(jī)械學(xué)習(xí)、示教學(xué)習(xí)、通過例子學(xué)習(xí)、解釋學(xué)習(xí)、類比學(xué)習(xí)、發(fā)現(xiàn)學(xué)習(xí)按系統(tǒng)性分類(歷史淵源、知識表示、推理策略、應(yīng)用領(lǐng)域).,4.5.2機(jī)器學(xué)習(xí)系統(tǒng)基本結(jié)構(gòu),環(huán)境,學(xué)習(xí),知識庫,執(zhí)行,(1)機(jī)械學(xué)習(xí)（ROTELEARNING),1.思想:記憶=檢索+計(jì)算2.示意圖,例子：汽車保險(xiǎn)程序,該程序能對被損壞的汽車的修理費(fèi)用進(jìn)行計(jì)算.它的輸入是汽車損壞情況,即生