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

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