第4章人工智能的決策支持和

智能決策支持系統第4章目錄4.1

人工智能基本原理

4.2

專家系統與智能決策支持系統4.3

神經網絡的決策支持

4.4遺傳算法的決策支持4.5機器學習的決策支持4.1人工智能基本原理1、人工智能的決策支持技術從智能決策支持系統的概念可知智能決策支持系統中包含了人工智能技術，與決策支持有關的人工智能技術主要有：專家系統、神經網絡、遺傳算法、機器學習、自然語言理解等。

專家系統是利用大量的專門知識解決特定領域中的實際問題的計算機程序系統；神經網絡是利用神經元的信息傳播模型（MP模型）進行學習和應用；遺傳算法是模擬生物遺傳過程的群體優化搜索方法；

機器學習是讓計算機模擬和實現人類的學習，獲取解決問題的知識；自然語言理解是讓計算機理解和處理人類進行交流的自然語言。4.1人工智能基本原理2．智能決策支持系統結構形式

1）基本結構智能決策支持系統（IDSS）＝決策支持系統（DSS）＋人工智能（AI）技術4.1人工智能基本原理

問題綜合與交互系統數據庫管理系統模型庫管理系統模型庫數據庫

人工智能技術專家系統神經網絡遺傳算法機器學習自然語言理解圖4.1智能決策支持系統的基本結構

圖4.2智能決策支持系統結構問題綜合與交互系統模型庫管理系統數據庫管理系統知識庫管理系統推理機用戶模型庫

知識庫數據庫人工智能技術可以概括為：推理機＋知識庫智能決策支持系統的結構可以簡化為圖4.24.2人工智能基本原理4.2.1邏輯推理4.2.2知識表示與知識推理4.2.3搜索技術4.2.1邏輯推理1.形式邏輯(人的思維形式、規律)（1）概念：反映事物的特有屬性和屬性的取值。（2）判斷：對概念的肯定或否定；判斷本身有對有錯；判斷有全稱的肯定（或否定）判斷和存在的肯定（或否定）判斷。（3）推理：從一個或多個判斷推出一個新判斷的過程。邏邏輯推推理2.推推理的的種類類演繹推推理歸納推推理類比推推理假言推推理三段論論推理理數學歸歸納法法假言易易位推推理枚舉歸歸納推推理1）演繹推推理：從一一般現現象到到個別別（特特殊））現象象的推推理。。2）歸納推推理：從個個別（（特殊殊）現現象到到一般般現象象的推推理。。3）類比推推理：從個個別（（特殊殊）現現象到到個別別（特特殊））現象象的推推理。。1）演繹推推理專家系系統的的研究究基本本上屬屬于演演繹推推理范范疇。。演繹繹推理理的核核心是是假言言推理理。假言推推理：以假假言判判斷為為前提提，對對該假假言判判斷的的前件件或后后件的的推理理。1）假假言推推理：：pq，p┝q2）三三段論論推理理：：pq，qr┝pr3）假假言易易位推推理（（拒取取式））：pq，q┝p符號““┝”表示示推出出邏邏輯推推理2）歸歸納推推理(個別別→一一般)（1））數學學歸納納法這種推推導是是嚴格格的，，結論論是確確實可可靠的的。（2））枚舉舉歸納納推理理S1是P，，S2是P，，…………Sn是PS1……Sn是S類類事物物中的的部分分分子子，沒沒有相相反事事例。。所以，，S類類事物物都是是P。。枚舉歸歸納推推理的的結論論是或或然的的(并非非必然然地)，它的可可靠性性和事事例數數量相相關。邏邏輯推推理枚舉歸歸納推推理實實例如觀察察到鐵受熱熱膨脹脹、銅受熱熱膨脹脹等事實實而不知其其所以以然，，由此此推出出“所有金金屬受受熱膨膨脹”的結論論就是是簡單單枚舉舉歸納納推理理。3）類類比推推理它是由兩兩個（或或兩類））事物在在某些屬性性上相同，進而推推斷它們們在另一個屬屬性上也可能能相同的推理。。A事物有有abcd屬性性,B事事物有abc屬屬性（或或a,b,c相相似屬性性）所以，，B事物也可可能有d屬性（或或d相似似屬性））類比推理理的結論論帶有或或然性，，它的可可靠性和和相類比比事物屬屬性之間間的聯系系程度有有關。邏邏輯推理理類比推理理實例一一1816年的一一天，法法國醫生生雷奈克克出診為為一位年年輕的女女性看病病，一見見病人，，雷奈克克犯起愁愁來：她她身體非非常肥胖胖，要診診斷她的的心臟和和肺部是是否正常常，按當時醫醫生慣用用的方法法，把耳耳朵貼近近病人的的胸部來來聽，肯肯定聽不不清楚，，更何況況她是一一位年輕輕的女性性。雷奈克抬抬頭看了了看院子子里正在在玩耍的的小孩，，腦子里里突然浮浮現出幾幾年前看看到一個個孩子們們玩的游游戲：一一個孩子子用釘子敲敲打木板板的一頭頭，另外外的孩子子爭先恐恐后地抱抱著把耳耳朵貼近近木板的的另一頭頭，興致勃勃勃地傾傾聽著。。為什么木木頭能夠夠把聲音音清晰地地傳過來來呢？雷奈克稍稍微想了了想，只只見他很很很地拍拍了一下下手說：：“就是是這樣！！就是這這樣！””雷奈克克要來一一疊紙，，緊緊地地卷成一一個卷，，然后把把紙卷的的一端放放在姑娘娘的胸部部，另一一端放在在自己的的耳朵上上，側著著臉聽了了起來。。“真是是一個妙妙法！””雷奈克克高興地地喊了一一句。回回到家里里，雷奈克找找到一根根木棒，，造成了了歷史上上第一個個“聽診診器”。。類比推理理實例一一類比推理理實例二二19世紀紀30年年代，英英國商人人威爾斯斯以與馮馮燦的茂茂隆皮箱箱商行訂訂購的皮箱中有有不是皮皮的木料料為由，向向香港法法院起訴訴，蓄意意敲詐馮馮燦。針針對這種種情況，，馮燦的的律師羅羅文錦取取出口袋袋的金懷懷表，高高聲問法法官：““請問這這是什么么表？””法官答答道：““這是金金表，可可是這與與本案有有什么關關系？””羅文錦錦高舉金金表，面面對法庭庭上所有有的人說說：“有有關系。。這是金金表，沒沒有人懷懷疑是吧？但是是，請問問，這塊塊金表除表表面鍍金金之外，，內部的的機制都都是金制制嗎？”旁聽聽者同聲聲議論：：“當然然不是。。”羅文文錦繼續續說：““那么人人們為什什么又叫叫它金表表呢？””稍作停停頓又高高聲說：：“由此此可見，，茂隆行行的皮箱箱案不過過是原告告無理取取鬧、存存心敲詐詐而已””原告理理屈詞窮窮，法庭庭最后以以威爾斯斯誣告，，罰款5000元結案案皮箱訴訟訟案的法法庭辯論論中，賣賣方律師師在反駁駁中所使使用的就就是類比比推理：：表的外表表有金，，內部含含有不是是金的材材料，但但卻是金金表；箱的外表表有皮，，但也含含有不是是皮的材材料；所以，箱箱仍是皮皮箱。類比推理理實例二二3.總總結1）演繹推理理的結論論沒有超出出已知的知知識范圍圍。而歸歸納推理理和類比比推理的的結論超出已知的知知識范圍圍。演繹推理理只能解解釋一般般規律中中的個別別現象而歸納推推理和類類比推理理創造了了新的知識，，使科學學得到新新發展，，是一種種創造思思維方式式。2）演繹推理理中由于于前提和和結論有有必然聯聯系，只只要前提提為真，，結論一一定為真真。歸納推理理和類比比推理中中前提和和結論，，不能保保證有必必然聯系系，具有有或然性性。這樣樣推理的的結論未未必是可可靠的。。需要經經過嚴格格的驗證證和證明明，使之之形成新新的理論論。邏邏輯推理理知知識表示示與知識識推理4.2.2.1數理理邏輯表表示法(自學)4.2.2.1產生生式規則則4.2.2.3語義義網絡4.2.2.4框架架4.2.2.5劇本本(自學學)產生式規規則（ifAthenB）1.正正向推理理逐條搜索索規則庫庫，對每每一條規規則的前前提條件件，檢查查事實庫中是否存存在。前提條件件中各子子項，若若在事實實庫中不是全部部存在，放棄該該條規則則。若在在事實庫庫中全部存在在，則執行行該條規規則，把把結論放入事實庫中。反復循環環執行上上面過程程，直至至推出目目標，并并存入事實庫中為止。。1.A∧B→→G2.C∧D→→A3.E→DB,C,E產產生式規規則事實庫的的最后狀狀態為：：B，C，，E，D，A，，G產生式規規則庫事實庫產生式規規則庫和和事實庫庫的初始始狀態為為：產生式規規則逆(反)向推理逆向推理理是從目目標開始始，尋找找以此目標為為結論的規則對該規則則的前提提進行判判斷，若該規規則的前前提中某某個子項項是另一一規則的的結論時時，再找找以此結結論的規規則。重復以上上過程，，直到對對某個規規則的前前提能夠夠進行判判斷。按按此規則則前提判判斷（““是”或或“否””）得出出結論的的判斷，，由此回回溯到上上一個規規則的的推理，，一直回回溯到目目標的判判斷。GADEBC產產生式規規則逆向推理中中，目標改改變過程：：1.A∧B→G2.C∧∧D→A3.E→DB,C,E產生式規則則庫事實庫4.2.3搜索技技術搜索技術是是人工智能能的一個重重要研究內內容。智能能技術體現在減少搜索樹樹中的盲目目搜索。1.執行時間與與ｎ，ｎ２，ｎ３等成正比的的算法，稱稱為按多項式時時間執行。2.執行時間與與２ｎ，ｎ！和ｎｎｎ等成正比的的算法，稱稱為按指數時間間執行。按多項式時時間執行的的算法，計計算機是可可以實現的的。按指數數時間執行行的算法，，計算機是是不可能實實現的。4.2.3搜索技技術人工智能中中發展了一一種稱為啟啟發式搜索索方法，基基本思想可可用一個實實例來說明明：一個外地人人到某城市市出差，他他想到書店店看看，又又不知書店店在何處，，如果采取取盲目搜索索，從住地地出發沿任任一方向走走，在分叉叉路口又任任選一分支支走，他可可能走幾天天幾夜也找找不到如果采用啟啟發式方法法，他會問問路上的人人，到書店店怎樣走。。城市中的的大部分人人對書店不不知道，問問不出來。。4.2.3搜索技技術改一種問法法：問該城市最最熱鬧的地地方在哪兒兒？按照這個個啟發式信信息沿著指指路人的路路線，乘車車到達最熱熱鬧的地方方但書店在哪哪兒，仍然然不知道。。如果盲目目搜索，可可能仍然找找不到。如如果采用啟啟發式方法法，他會問問路上的人人，賣畫的的地方在哪哪兒，他可可以通過畫畫店再問書書店在哪兒兒？啟發式方法法能減少大大量盲目無無效的搜索索，能有效效克服按指指數時間執執行的組合合爆炸現象象4.2.3搜索技技術搜索方法分分類：1、基本搜索索法（1）廣度優先先搜索法。。（2）深度優先先搜索法。。2、生成測試試法。3、爬山法。。4、啟發式搜搜索。5、博弈算法法。（1）極小極大大搜索法。。（2）剪枝算法。。4.2.3.1廣度優先搜搜索（寬度度優先搜索索）1、廣度優優先搜索思思想從初始狀態態S開始，，利用規則，生成所有可可能的狀態態。構成樹的的下一層節節點，檢查查是否出現現目標狀態態G，若未未出現，就就對該層所所有狀態節節點，分別別順序利用用規則。生成再下一一層的所有有狀態節點點，對這一一層的所有有狀態節點點檢查是否否出現G，，若未出現現，繼續按按上面思想想生成再下下一層的所所有狀態節節點.這樣一層一一層往下展展開。直到到出現目標狀狀態G為止。圖4.7廣度優先搜搜索示意圖圖（2）算法法1)把初初始節點S0故入OPEN表。2)如果果OPEN表為空，，則問題無無解，退出出。3)把OPEN表表的第一個個節點(記記為節點n)取出放放入CLOSED表表。4)考察節節點n是否否為目標節節點。若是是，則求得得了問題的的解，退出出。5)若節點點n不可擴擴展，則轉轉第2)步步。6)擴展展節點n，，將其子節節點放入OPEN表表的尾部，，并為每一一個子節點點都配置指指向父節點點的指針，，然后轉第第2)步。。廣度優先搜索過程開始把n的后繼節點放入OPEN表的末端，提供返回節點n的指針把S放入OPEN表OPEN表為空表？是失敗否把第一個節點（n）從OPEN移至CLOSED表n為目標節點？是成功否n能否擴展是否有任何后繼節點為目標節點否是是否例子1(八數碼難題題)重排九宮問問題，在3x3的方方格棋盤上上放置分別別標有數字字1、2、、3、4、、5、6、、7、8共共8個棋子子，初始狀狀態為S0，目標狀態態為Sg，如圖1所所示。可使用的算算符有：空格左移，，空格上移移，空格右右移，空格格下移。即即只允許把把位于空格格左、上、、右、下的的鄰近棋子子移入空格格。要求尋尋找從初始始狀態到目目標狀態的的路徑。?該路徑使用用的算符序序列：空格格上移，空空格左移，，空格下移移，空格右右移。廣度優先搜搜索的盲目目性較大，，當目標節節點距離初初始節點較較遠時將會會產生許多多無用節點點，因此搜搜索效率低低，但是，，只要問題題有解，用用廣度優先先搜索總可可以得到解解，而且得得到的是路路徑最短的的路徑。由圖2可以以看出，解解的路徑是是：S0——3——8———16———26廣度優先法法適合于搜搜索樹的寬寬度較小的的問題。1、深度優優先搜索法法思想從初始狀態態S開始，，利用規則則生成搜索索樹下一層層任一個結點點，檢查是否否出現目標標狀態G，，若未出現現，以此狀狀態利用規規則生成再再下一層任一個結點，再檢檢查是否為為目標節點點G。若未未出現，繼繼續以上操操作過程，，一直進行行到葉節點點（即不能能再生成新新狀態節點點）。當它仍不是是目標狀態態G時，回回溯到上一一層結果，，取另一可可能擴展搜搜索的分支支。生成新新狀態節點點。一直進行下下去，直到到找到目標標狀態G為為止。深深度優先搜搜索法圖4.8深度優先搜搜索示意圖圖（2）算法法1)把初初始節點S0故入OPEN表。2)如果OPEN表表為空，則則問題無解解，退出。3)把OPEN表的的第一個節節點(記為為節點n)取出放入入CLOSED表。4)考察節節點n是否否為目標節節點。若是是，則求得得了問題的的解，退出出。5)若節點點n不可擴擴展，則轉轉第2)步步。6)擴展節節點n，將將其全部子子節點放入入到OPEN表的首首部，并為為其配置指指向父節點點的指針，，然后轉第第2)步。。開始把S放入OPEN表OPEN表為空表？是失敗否把第一個節點（n）從OPEN移至CLOSED表是否有任何后繼節點為目標節點是成功否擴展n,把n的后繼節點放入OPEN表的前頭，提供返回節點n的指針s為目標節點？否是深度優先搜索例子2：對圖1所示示的重排九九宮問題進進行深度優優先搜索，，可得到圖圖3所示的的搜索樹這這只是搜索索樹的一部部分，尚未未到達目標標節點，仍仍需繼續往往下搜索。。?在深度優先先搜索中，，搜索一旦旦進入某個個分支，就就將沿著該該分支一直直向下搜索索。如果目目標節點恰恰好在此分分支上，則則可較快地地得到解。。但是，如果目標節點點不在此分支支上，而該分分支又是一個個無窮分支，，則就不能得得到解。所以深度優先先搜索是不完完備的，即使使問題有解，，它也不一定定能求得解。。顯然，用深度優先求求得的解，也也不一定是路路徑最短的解解。深度優先法適適合于搜索樹樹的深度較小小的問題4.2.3.3生成測試法生成測試法算算法是：1、生成一個可可能狀態節點點。2、測試該狀態態是否為目標標狀態。3、若是目標狀狀態則結束。。否則回到第第1步其中：生成可可能的狀態，，可以是有規規律的，也可可以是無規律的4.2.3.3生成測試法（1）如果搜索過過程中，總是利用剛生生成出的狀態態來生成新狀狀態，這種生成測測試法就是深度優先搜索法。（2）如果搜索過過程中，總是利用舊狀狀態生成所有有可能出新狀狀態，而且狀態節節點以從舊到到新的順序逐逐個生成的原原則。這種生生成測試法就就是廣度優先搜索法。（3）如果搜索過過程中，有時利用舊狀狀態生成新狀狀態，有時利利用新狀態生生成新狀態，，這就是無規律的生成測試法法。4.2.3.4爬山法(生成成測試法的變變種)爬山算法：(測試函數)1.開始狀態態作為一個可可能狀態。2.從一個可可能狀態，應應用規則生成所有新的的可能狀態集集。3.對該狀態態集中每一狀狀態，進行如如下操作：⑴對該狀態態測試，檢查查是否為目標標，是則停止止。⑵計算該狀狀態的好壞，，或者比較各各狀態的好壞壞。4.取狀態集集中最好狀態態，作為下一一個可能狀態態。5.循環到第第2步。在爬山法中可可能出現以下下幾種情況：：⑴局部極大大點：它比周圍鄰居狀態都好，但但不是目標。。圖4.9局部部極大點示意意圖在爬山法中可可能出現以下下幾種情況：：⑵平頂：它它與全部鄰居狀態都有同一個值，構成成一個平平面。圖4.10平平頂示意圖圖在爬山法中可可能出現以下下幾種情況：：⑶山脊：它它與線狀鄰居狀態有相同值值，比其它鄰鄰居狀態要好好。圖4.11山山脊示意圖4.2.3.4爬山法為了解決以上上問題，需要要采用如下策策略：（1）退回到某一更早狀態結點，沿沿著另一方向（對該該結點就不一一定是當時最最好值的方向向）進行爬山山。（2）朝一個方向向前進一大步（按某方向深深度優先搜索索多次），走走出平頂區，，按別方向進進行爬山。（3）同時朝兩個或多個方方向前進，即按兩兩個或多個方方向爬山。4.2.3.5啟發式搜索啟發式搜索是是對每個在搜搜索過程中遇遇到的新狀態，用一個估計函數（啟發式函數數）并計算其其值的大小，，確定下一步步將從哪一個個狀態開始繼繼續前進。一般以估計值小者為為較優的狀態，以此此實行最優搜搜索。估計函數值的的大小與從初始狀態到達達目標狀態的路徑有關。。4.2.3.5啟發式搜索具體需要考慮慮以下問題：（1）下一步步選擇哪個狀狀態結點？（2）是部分分展開幾個狀狀態結點還是是全部展開所所有可能產生生的狀態結點點？（3）使用哪哪個規則（或或算子）來展展開新狀態結結點？（4）怎樣決決定舍棄還是是保留新生成成的狀態結點點？（5）如何定定義啟發式函函數（估計值值函數）？（6）如何決決定搜索方向向？（7）怎樣決決定停止或繼繼續搜索？一般啟發式函函數法用如下下公式表示：：f（x）=g（x）+h（x）f（x）表示由開始狀狀態到目標狀狀態的總耗費費g（x）表示開始狀態態到當前狀態態的耗費。h（x）表示當前狀態態到目標狀態態的耗費。4.2.3.5啟發式式搜索啟發式函數分分析：1.當h（x）=0，即f（x）=g（x）取f（x）為最小，即即取g（x）為最小。這這要求在已擴展的結點中取最最佳路徑。g（x）能保證找到到最好解。但對搜索速速度沒有太多多的幫助。2.當g（x）=0，即f（x）=h（x）h（x）是從當前狀狀態到目標狀狀態的耗費。。取它最小，，將會加快搜索速度，但但它并不保證得到最優優解。4.2.3.5啟發式式搜索g（x）選取的幾種種特例：⑴g（x）為搜索樹的的深度，h（x）=0，則啟發式方方法為廣度優優先搜索法。。⑵g（x）為搜搜索樹樹的深深度的的負數數，h（x）=0，則啟啟發式式方法法為深深度優優先搜搜索法法。因因為深深度愈愈深，，負數數愈大大，搜搜索法法總向向深度度發展展。(3)g（x）為初初始狀狀態到到該結結點的的代價價,則則啟發發式方方法為為代價價優選選搜索索法。。f(x)一般表表示估估計值值，愈愈接近近精確確值，，啟發發式效效果愈愈好。。如果果是精精確值值,就就不是是啟發發式函函數。。啟啟發式式搜索索圖-4啟啟發發式搜搜索28316475283147651382476528314765231847652831476583214765283714652318476523184765832147651382476512384765813264758132476512378465832147658132476581324765123847651382476512384765*81372465*4455453542305455453204h（x）可可以定義為為節點點x中數數碼位位置與目標標節點點相比不不同的的個數4.3專專家系系統與與智能能決策策支持持系統統專專家系系統原原理產產生式式規則則專家家系統統專專家系系統與與DSS的的集成成建建模專專家系系統智智能決決策支支持系系統4.3.1專家家系統統原理理1.專專家家系統統概念念1）專專家系系統定定義專家系系統是是具有有大量專專門知知識，并能能運用用這些些知識識解決決特定定領域域中實實際問問題的的計算算機專家系統是利用大量的專家知識，運用知識推理的方法來解決各特定領域中的實際問題。計算機專家系統這樣的軟件能夠達到人類專家解決問題的水平。4.3.1專家家系統統原理理2）專家系系統的的特點點專家系系統需需要大大量的的知識識，這這些知知識是是屬于于規律性性知識識，它可可以用用來解解決千千變萬萬化的的實際際問題題。4.3.1專家家系統統原理理例如：：求解微微積分分問題題，是利利用30～～40條微微分、、積分分公式式來求求解千千變萬萬化的的微分分、積積分問問題，，得出出各自自的結結果。。其中微微積分分公式式就是是規律律性知知識，，求解解微積積分問問題就就是對對某函函數反反復利利用微微積分分公式式進行行推導導，最最后得得出該該問題題的結結果。。這個推推理過過程是是一個個不固固定形形式的的推理理，即即前后后用哪哪個公公式，，調用用多少少次這這些公公式都都隨問問題變變化而而變化化。1）專專家家系統統對比比數據據庫檢檢索數據庫庫中存存放的的記錄錄可以以看成成是事實性性知識識。如果果把檢檢索數數據庫庫記錄錄看成成是推推理的的話，，它也也是一一種知知識推推理。。它與與專家家系統統的不不同在在于：：（A））知識識只含含事實實性知知識，，不包包含規規律性性知識識。（B））推理理是對對已有有記錄錄的檢檢索，，記錄錄不存存在，，則檢檢索不不到。。不能能適應應變化化的事事實，，推理理不出出新事事實。。4.3.1專家家系統統原理理4.3.1專家家系統統原理理2）專專家系系統對對比數數值計計算數值計計算是是用算算法解解決實實際問問題，，對不不同的的數據據可以以算出出不同同的結結果。。如果把把數據據看成成是知知識，，算法法看成成推理理的話話，它它也是是一種種知識識推理理。它它與專專家系系統的的不同同在于于：（A））算法法（推推理過過程））是固固定形形式的的。算算法一一經確確定，，推理理過程程就固固定了了。而而專家家系統統的推推理是是不固固定形形式的的，隨隨著問問題不不同，，推理理過程程也不不一樣樣。（B））數值值計算算只能能處理理數值值，不不能處處理符符號。。知識處處理的的特點點從上面面分析析可見見，數數值計計算、、數據據處理理是知知識處處理的的特定定情況況，知知識處處理則則是它它們的的發展展!（A）知知識包包括事事實和和規則則（狀狀態轉轉變過過程））。（B））適合合于符符號處處理（（如微微積分分求解解）。。（C））推理理過程程是不不固定定形式式的（（推導導過程程中每每次選選用的的規則則知識識是變變化的的）。。（D））能得得出未知的事實實（如如推導導出新新的微微分公公式））。2.專專家系系統結結構專家系系統的的核心心是知知識庫庫和推推理機機。專家系統可可以概括為為：專家系統＝＝知識庫+推理機4.3.1專家系統統原理知識獲取人機接口知識庫推理機專家用戶咨詢建建議專家系統核核心專家系統結結構3.產生式式規則知識識的推理機機產生式規則則的推理機機＝搜索+匹配（假假言推理））在推理過程程中，是一邊搜索一一邊匹配。匹配需要要找事實,這個事實實一是來自自于規則庫庫中別的規規則，一是是來自向用用戶提問。。在匹配時會會出現成功功或不成功功，對于不不成功的將將引起搜索索中的回溯溯和由一個個分枝向另另一個分枝枝的轉移，，可見在搜搜索過程中中包含了回回溯。4.3.1專家系系統原理4.3.1專家系系統原理4.產生生式規則推推理的解釋釋推理中的搜搜索和匹配配過程，如如果進行跟蹤和顯示就形成了向向用戶說明明的解釋機機制。好的解釋機機制不顯示那些對于失敗路徑的跟蹤。4.3.2產生式式規則專家家系統產產生式規則則推推理樹(知知識樹)逆逆向推理過過程事事實數據和和解釋機制制4.3.2產生式式規則專家家系統產生式規則則的優點產生式規則則知識表示示形式容易易被人理解解它是基于演演繹推理的的,保證了了推理結果果的正確性性大量產生式式規則所連連成的推理理樹(知識識樹),可可以是多棵棵樹.樹的寬度——反映問題題的范圍樹的深度——反映問題題的難度產產生式規則則ES產生式規則則知識一般般表示為:ifAthenB，或：如果A成立則B成立，或：A→B產產生式規則則產生式規則則知識表示示允許有如如下的特點點：⒈相同的的條件可以以得出不同同的結論。。如：A─→→BA─→C⒉相同的的結論可以以有不同的的條件來得得到。如A─→→GB─→G⒊條件之之間可以是是“與”（（AND））連接和““或”（OR）連接接如A∧B─→GA∨B→G（相當于于A→G，，B→G））⒋一條規規則中的結結論，可以以是另一條條規則中的的條件。如F∧B→Ｚ，C∧ＤＤ→F其中F在前前一條規則則中是條件件，在后一一條規則中中是結論。。產產生式規則則ES由于以上特特點，規則則知識集能能做到：能描述和解解決各種不同的靈活的實實際問題。。（由前三三點特點形形成）能把規則知知識集中的的所有規則則連成一棵棵“與、或””推理樹（知識樹））。即這些些規則知識識集之間是是有關聯的的（由后二二個特點形形成）。4.3.2.2推理理樹（知識識樹）規則庫中的的各條規則則之間一般般來說都是是有聯系的某條規則中中的前提是另外一條條規則中的的結論。按逆向推理思想把知識識庫所含的的總目標（它是某些些規則的結結論）作為為根結點，，按規則的的前提和結結論展開成成一棵樹的的形式。這這棵樹一般般稱為推理理樹或知識識樹，它把把知識庫中中的所有規規則都連結結起來由于連結時時有“與””關系和““或”關系系，從而構構成了“與或”推推理樹。XFGLMEC4.3.2.2推理理樹（知識識樹）（注：兩斜斜線中間的的弧線表示“與”關系，無無弧線表示示“或”關關系）規則知識庫庫的逆向推推理樹例：若有知知識庫為：：A∨（B∧∧C）→G（I∧J））∨K→AX∧F→JL→BM∨E→CW∧Z→MP∧Q→E畫出“與或或”推理樹樹ABIJKWZPQ用規則的前前提和結論論形式畫出出逆向推理理樹形式為為：4.3.2.2推理理樹（知識識樹）前提I前提J前提L前提M前提E(結論)(結論)(結論)

前提A前提B前提C（結論)（結論）(結論)總目標G（結論)前提X前提F前提W前提Z前提P前提Q???

?????該“與或””推理樹的的特點是：：⒈每條規規則對應的的節點分枝枝有與（AND）關關系，或（（OR）關關系⒉樹的根結點是推理樹的的總目標⒊相鄰兩兩層之間是是一條或多條規則連接⒋每個結結點可以是是單值，也也可以是多多值。若結結點是多值值時，各值值對應的規規則將不同同。⒌所有的的葉結點，，都安排向向用戶提問問，或者把把它的值直直接放在事實數據庫庫中。4.3.2.2推理理樹（知識識樹）逆逆向推理過過程⒈推理樹的深深度優先搜搜索N17982GABCJIKLME45YXFZPQ1011123YWYYYN6逆向推理過過程在推理理樹中的反反映為推理理樹的深度度優先搜索索過程。逆逆向推理過過程在計算機中中實現時，，并不把規規則連成推推理樹，而而是利用規規則棧來完完成。當調調用此規則則時，把它它壓入棧內內（相當于于對樹的搜搜索），當當此規則的的結論已求求出（yes或no）時，需需要將此規規則退棧（（相當于對對樹的回溯溯）。利用規則棧的的壓入和退出出的過程，相相當于完成了了推理樹的深深度優先搜索索和回溯過程程。4.3.2.3逆向推推理過程⒉結點的否定每個結點有兩兩種可能，即即YES和NO。葉結點為NO是由用戶回答答形成的。中間結點為NO是由葉結點為為NO，回溯時引起起該結點為NO。若當該結點還還有其它“或或條件”分枝枝時，不能立立即確定該結結點為NO，必須再搜索索另一分枝，，當另一分枝枝回溯為YES時，該結點仍仍為YES。中間結點只有有所有“或””分枝的回溯溯值均為NO時，才能最后后確定該中間間結點為NO。4.3.2.4事實數數據庫和解釋釋機制1.事實數數據庫(動態態數據庫)事實Y,N值規則號可信度A11N0(提問)0A12Y00.9

A1Y40.8事實欄放入命命題規則號：事實實取Y或N的的理由可信度：事實實的可信度2.解釋機機制解釋機制是專專家系統中重重要內容。它它把推理過程程顯示給用戶戶，讓用戶知知道目標是如如何推導出來來的。消除用用戶對目標結結論的疑慮。。兩種實現方法法一種是推理過過程的全部解解釋；一種是推理過過程中正確路路徑的解釋。。4.3.2.4事實數數據庫和解釋釋機制專專家系統與與決策支持系系統集成IDSS充分分發揮了專家家系統以知識推理形式解決定性分析問題的特特點.發揮了決策支支持系統以模型計算為核心的解決決定量分析問題的特特點.充分做到定性分析和定量分析的有機結合.數據庫DBDSS控制系統模型庫MB問題綜合與交互系統動態DB推理機和解釋器知識庫KB集成系統DSSES圖4.16智智能決策支持持系統集成結結構圖綜合系統DSS和ES的總體結合合。由集成系統把把DSS和ES有機結合合起來2.KB和和MB的結合合。模型庫中的數數學模型和數數據處理模型型作為知識的的一種形式，，即過程性知識，加入到知識識推理過程中中去。3.DB和和動態DB的的結合。DSS中的DB可以看成成是相對靜態態的數據庫，，它為ES中中的動態數據據庫提供初始始數據，ES推理結束后后，動態DB中的結果再再送回到DSS中的DB中去。DSS與ES集成形式一一：DSS和和ES并重的的IDSS結結構集成系統DSSES專專家系統與與決策支持系系統集成集成特點1.具有綜合合系統，具有有調用和集成成DSS和ES的能力。。2.擴充DSS的問題與與人機交互系系統功能，增增加對ES的的調用組合能能力DSS與ES的關系：DSS中DB與ES中的的動態DB進進行數據交換換解決問題的特特點體現定性分析析和定量分析析并重解決問問題的特點。。DSS控制系統MBDBESDSS與ES集成形式二二：DSS為主體的IDSS結構構專專家系統與與決策支持系系統集成集成特點集成系統和DSS控制系系統合為一體體DSS與ES的關系：ES被被DSS控控制系系統調調用解決問問題的的特點點體現以以定量量分析析為主主，結結果定定性分分析解解決問問題的的特點點。推理機（廣義）

DSS動態DBKB推理機MB動態DBKB圖4.19DSS作為為推理理形式式的IDSS圖4.20模型作作為知知識的的IDSSDSS與ES集集成形形式三三：ES為主體體的IDSS結構專專家系系統與與決策策支持持系統統集成成集成特特點人機交交互系系統和和ES合為為一體體DSS與ES的的關系系：圖4.19DSS作為為推理理機，，受ES的的推理理機控控制；；圖4.20數據據模型型作為為知識識出現現解決問問題的的特點點體現以以定量量分析析為主主，結結果定定性分分析解解決問問題的的特點點。建建模專專家系系統專家系系統實實現模型選選擇的實例例進行行說明明。例如，，彈簧簧振動動建模模專家家系統統。該專家家系統統是解解決彈彈簧在在不同同受力力情況況下（（包括括沖力力、摩摩擦力力等））應該該滿足足那種種類型型的微微分方方程模模型。。彈簧振振動建建模專專家系系統進進行簡簡化說說明如如下：：1、規規則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→BR11：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建建模專專家系系統A：彈簧滿足足胡克定律律B：彈簧質量量可以忽略略C：可以忽略略摩擦力D：沒有沖力力A1：彈簧有線線性恢復力力A11：彈力與位位移成正比比A12：位移量很很小E：要考慮摩摩擦力F：摩擦力與與速度之間間為線性關關系C1：若振動為為自發時振振幅為常數數E1：若振動為為自發時振振幅是遞減減的G：有沖力F（T）B1：彈簧具有有質量N并并且N/M遠遠小于于1H1：彈簧勢能能不是關于于平衡位置置對稱H：彈簧不潢潢足胡克定定律A2：彈簧勢能能與函數X（T）成成正比I：摩擦力與與速度之間間為非線性性關系各項英文字字母含義為為：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＝0M8： 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對ｔ的二階導導數，X′表示一階階導數。。各模型微微分方程程為：3.規規則庫的的推理樹樹將20條條規則連連成的推推理樹見見下圖所所示。每個葉節節點提問問的回答答為：Y－yes，，N－no專家系統統將解釋釋為證實實某條規規則而安安排的提提問。用用戶不明明白專家家系統為為什么要要提該問問題，可可以回答答Ｗ－why建建模專家家系統A2A1B1C1？E1？？B1？A11A12？？？？DEFGHIABC？？M（M1，M2，···，M12）圖4.21彈簧振振動推理理樹的標標準形式式專家系統統應用現有一個個彈簧，，滿足如如下特性性：H1（彈簧勢勢能不是是關于平平衡位置置對稱））B1（彈簧具具有質量量N并且N/M遠遠小于于1）C1（若振動動為自發發時振幅幅為常數數）G（有沖力力F（T））通過專家家系統推推理將得得出：該彈簧滿滿足模型型6（M6）的微分分方程。。4.5遺遺傳算算法的決決策支持持遺遺傳算法法原理優優化模型型的遺傳傳算法求求解獲獲取知識識的遺傳傳算法遺遺傳規劃劃建立模模型遺遺傳算法法原理遺傳算法法(GeneticAlgorithm，GA)是模擬生物進化化的自然選選擇和遺遺傳機制制的一種種尋優算法。適用于復雜的非非線性問題,主主要應用用在組合合優化和和機器學學習兩個個方面。。應用領域域：圖像識別別、圖像像恢復、、自適應應控制、、優化調調度等領領域。遺傳算法法的發展展過程大大體上可可分為以以下三個個階段：：（1）70年代代的興起起階段。。1975年美國國Michigan大大學J.Holland首首次系統統地闡述述了遺傳傳算法的的基本理理論和方方法。在這一時時期的大大部分研研究都處處于理論論研究和和建立實實驗模型型階段（2）80年代代的發展展階段。。1980年Smith教授將將遺傳算算法應用用于機器器學習領領域，研研制出了了一個著著名的分分類器(Classifier)系系統。這期間許許多學者者對遺傳傳算法進進行了大大量的改改進和發發展，提提出了許許多成功功的遺傳傳算法模模型，使使遺傳算算法應用用于更廣廣泛的領領域。（3）90年代代的高潮潮階段。。進入90年代后后，遺傳傳算法作作為一種種實用、、高效的的優化技技術，得得到了極極為迅速速的發展展。遺遺傳算法法原理遺遺傳算法法原理4.5.1.1遺傳傳算法工工作過程程4.5.1.2遺傳傳算法的的理論基基礎遺遺傳算法法的基本本特征4.5.1.1遺傳傳算法的的工作過過程遺傳算法法是一種種群體型型操作，，該操作作以群體體中的所所有個體體為對象象。個體就是是模擬生生物個體體而對問問題中的的對象（（一般就就是問題題的解））的一種種稱呼，，一個個個體也就就是搜索索空間中中的一個個點。種群(population)就是是模擬生生物種群群而由若若干個體體組成的的群體,它一一般是整整個搜索索空間的的一個很很小的子子集。遺傳算法法的三個個主要操操作算子子：選擇（selecation）、、交叉（crossover）和變異（mutation）構成了遺傳傳操作（Geneticoperation），使遺傳傳算法具有有了其他傳傳統方法所所沒有的特特性。產生新一代代群體編碼和初始始群體形成成輸出種群個體適應值值滿意否？？遺遺傳算法的的工作過程程首先將問題題的每個可可能的解按按某種形式式編碼，編編碼后的解解稱作染色色體（個體體）。隨機選取N個染色體構構成初始種群，再根根據預定的評價函數對每個染色色體計算適適應值，使使得性能較較好的染色色體具有較高的適應值。。選擇適應值高的染色體進進行復制，，通過遺傳傳算子來產產生一群新新的更適應應環境的染染色體，形形成新的種種群。這樣一代一一代不斷繁繁殖，最后后收斂到一一個最適應應環境的個個體上，求求得問題的的最優解。。遺傳算子選擇交叉變異1.群體體中個體的的編碼如何將問題題描述成位位串的形式式，即問題題編碼。一一般將問題題的參數用用二進制位（基因）編編碼構成子子串，再將將子串拼接起來構構成“染色體”位串。遺遺傳算法的的工作過程程例如：個體染染色色體9----1001（2，5，，6）----0101011102.適應應值函數的的確定遺傳算法的的執行過程程中，每一一代有許多多不同的染染色體（個個體）同時時存在，這這些染色體體中哪個保保留(生存存)、哪個個淘汰(死死亡)是根根據它們對對環境的適適應能力決決定的，適適應性強的的有更多的的機會保留留下來。適應性強弱弱是計算個體體適應值函函數f(x)的值來來判別的，，這個值稱稱為適應值值(fitness)。適應值函數數(即評價價函數)是是根據目標函數確定的。適適應值總是是非負的，任何何情況下總總是希望越越大越好。。如果目標標函數不是是取最大值值時，需要要將它映射射成適應值值函數。適適應值函數數f(x)的構成與與目標函數數有密切關關系，往往往是目標函函數的變種種。一般是一個個實值函數數。該函數數就是遺傳傳算法中指指導搜索的的評價函數數。遺遺傳算法的的工作過程程3.遺傳算算法的三個個算子（一）選擇擇(Selection)算算子（二）交叉叉(Crossover)算算子（三）變異異(Mutation)算子子遺遺傳算法的的工作過程程它又稱復制(reproduction)、、繁殖算算子。選擇是從種種群中選擇擇生命力強強的染色體體產生新種群的過過程。依據每個個染色體的的適應值大大小，適應應值越大，，被選中的的概率就越越大，其子子孫在下一一代產生的的個數就越越多。選擇操作是是建立在群群體中個體體的適應值估評評基礎上的。遺遺傳算法的的工作過程程（一）選擇擇(Selection)算算子通常做法是是：對于一一個規模為為N的種群S,按每個染染色體xi∈S的選擇概率率P(xi)所決定的的選中機會會,分N次從S中隨機選定定N個染色體,并進行行復制。遺遺傳算法的的工作過程程

這里的選擇概率P(xi)的計算公式為（一）選擇擇(Selection)算算子（二）交叉叉(crossover)算算子它又稱重組(recombination)、配對對(breeding)算子子，在遺傳算法法中起著核核心作用。。染色體重組組是分兩步步驟進行的的:首先在新復復制的群體體中隨機選選取兩個個體然后，沿著著這兩個個個體(字符符串)隨機機地取一個個位置，二二者互換從從該位置起起的末尾部部分。交叉率(crossoverrate)就是參加交叉運算的的染色體個個數占全體染色體體總數數的比比例，，記為為Pc,取取值范范圍一一般為為0.4～～0.99。遺遺傳算算法的的工作作過程程遺遺傳算算法的的工作作過程程例1:有兩兩個用用二進進制編編碼的的個體體A和和B。。長度度L=5，，A=a1a2a3a4a5，B=b1b2b3b4b5隨機選選擇一一整數數k∈∈[1，L-1]，，設設k=4，，經交交叉后后變為為：A=a1a2a3|a4a5B=b1b2b3|b4b5A’=a1a2a3b4b5B’=b1b2b3a4a5s1′=01000101,s2′=10011011可以看看做是是原染染色體體s1和s2的子代代染色色體。。例2,設設染染色體體s1=01001011,s2=10010101,交換其其后4位基基因,即即（二））交叉叉(crossover)算算子變異就就是以以很小的的概率率，隨機機地改改變字字符串串某個位位置上的值值。變變異操操作是是按位位（bit）進進行的的，即即把某某一位位的內內容進進行變變異。。在二二進制制編碼碼中，，就是是將某某位0變成成1，，1變變成0。選擇和和交叉叉算子子基本本上完完成了了遺傳傳算法法的大大部分分搜索索功能能，而而變異異則增增加了了遺傳傳算法法找到到接近最最優解解的能力力。變異率率(mutationrate)是是指發發生變異的基因因位數數所占占全體染色體體的基基因總總位數數的比比例，，記為為Pm，取值值范圍圍一般般為0.0001～～0.02。它保證證了遺遺傳算算法的的有效效性。。遺遺傳算算法的的工作作過程程（三））變異異(Mutation)算子子遺遺傳算算法的的工作作過程程例如:設設染色色體s=11001101將其其第三三位上上的0變為為1,即即s=11001101→11101101=s′。s′也可可以看看做是是原染染色體體s的子代代染色色體。。（三））變異異(Mutation)算子子4.控控制參參數設設定遺傳算算法中中的參參數包括群群體中中個體體的數數目、、交叉叉概率率、變變異概概率等等這些參參數的的設定定隨具具體問問題的的不同同將有有所差差別，，帶有有經驗驗性，，它會會影響響遺傳傳算法法的迭迭代收收斂過過程。。遺遺傳算算法的的工作作過程程1.模模式定定理遺傳算法的理理論基礎是Holland提出的模模式定理。一個模式(Schema)就是一個個描述種群中中在位串的某某些確定位置置上具有相似性的位串子集的的相似性模板(SimilarityTemplate)。二進制串中的的模式是如下下的形式：（（a1，a2，…，ai，…，an），ai∈∈{0，1，，*}，其中中“*”是任任意符，或0，或1，模模式是串的集集合.模式H中確定定位的個數,稱為H的階階,記為O(H)。模式H中第一一個確定位與與最后一個確確定位之間的的距離稱為的的定義距,記記為δ(H)。4.5.1.2遺傳算算法的理論基基礎例:以長度L=5的串串為例,模式式*101*描述了在位位置2、3、、4具有形式式“010””的所有字符符串,：*101*={(11010)，(01010)，(01011)，(11011)}。其階階為3,定義義距為2。1.模式定理理模式定理是遺遺傳算法的理理論基礎它說明高適應值、長長度短、階數數低的模式在后代代中至少以指指數增長包含含該模式H的的位串的數目目。遺傳使高適應應值的模式復復制更多的后后代！4.5.1.2遺傳算算法的理論基基礎2．基因塊假假設高適應值、長長度短、低階階的模式叫基基因塊。基因塊假說基因塊通過遺遺傳操作繁殖殖、交換、變變異，再繁殖殖、再交換、、再變異的逐逐漸進化，形形成潛在的適適應性較高的的位串。該假設指出，，通過遺傳算算法能尋找到到接近全局最優優解的能力。4.5.1.2遺傳算算法的理論基基礎1.遺傳算算法的處理對對象是問題參參數的編碼個個體（位串））遺傳算法要求求將問題的參參數編碼成長度有限的位位串。遺傳算法是在在求解問題的編編碼串上進行操作，，從中找出高高適應值的位位串，而不是是對問題目標標函數和它們們的參數直接接操作。遺傳算法不受函數限制條件件(如導數存存在、連續性性、單極值等等)的約束。。4.5.1.3遺傳算算法的基本特特征2.遺遺傳算法法的搜索索是從問問題解位串集開始搜索索，而不不是從單單個解開開始在最優化化問題中中，傳統統的方法法是從一個點開始搜索索，如爬爬山法。。一般復復雜問題題會在““地形””中出現現若干““山峰””，傳統統的方法法很容易易走入假假“山峰峰”。遺傳算法法同時從種群的的每個個個體開始始搜索，，象一張張網罩在在“地形形”上，，數量極極大的個個體同時時在很多多區域中中進行搜搜索，這這樣就減少了陷陷入局部部解的可能性性。4.5.1.3遺傳傳算法的的基本特特征3.遺遺傳算法法只使用用目標函函數(即即適應值值)來搜搜索，而而不需要要導數等等其他輔輔助信息息傳統搜索索算法需需要一些些輔助信息息，如梯度度算法需需要導數數，當這這些信息息不存在在時，這這些算法法就失效效了。而而遺傳算算法只需目標函函數和編編碼串，，因此，，遺傳算算法幾乎乎可以處處理任何何問題。。4.遺遺傳算法法使用的的三種遺遺傳算子子是一種種隨機操操作，而而不是確確定性規規則遺傳算法法使用隨隨機操作作，但并并不意味味著遺傳傳算法是是簡單的的隨機搜搜索。遺遺傳算法法是使用用隨機工工具來指指導搜索索向著一一個最優優解前進進。5.隱含含的并行行性6.易介介入到已已有的模模型中，，并具有有擴展性性；易于于同別的的技術結結合使用用4.5.1.3遺傳傳算法的的基本特特征優優化模型型的遺傳傳算法求求解優化模型型的計算算是遺傳傳算法最最基本的的也是最最重要的的研究和和應用領領域之一一。一般說來來，優化化計算問問題通常常帶有大大量的局局部極值值點，往往往是不