第四章(1)_智能決策支持系統(tǒng)和智能技術(shù)的決策支持2ppt課件

1、第4章 人工智能的決策支持和 智能決策支持系統(tǒng).第4章 目錄4.1 人工智能根本原理 4.2 專家系統(tǒng)與智能決策支持系統(tǒng)4.3 神經(jīng)網(wǎng)絡(luò)的決策支持 4.4 遺傳算法的決策支持4.5 機器學習的決策支持.4.1 人工智能根本原理1、人工智能的決策支持技術(shù) 從智能決策支持系統(tǒng)的概念可知智能決策支持系統(tǒng)中包含了人工智能技術(shù)，與決策支持有關(guān)的人工智能技術(shù)主要有：專家系統(tǒng)、神經(jīng)網(wǎng)絡(luò)、遺傳算法、機器學習、自然言語了解等。 .專家系統(tǒng)是利用大量的專門知識處理特定領(lǐng)域中的實踐問題的計算機程序系統(tǒng)；神經(jīng)網(wǎng)絡(luò)是利用神經(jīng)元的信息傳播模型MP模型進展學習和運用；遺傳算法是模擬生物遺傳過程的群體優(yōu)化搜索方法； 機器學習

2、是讓計算機模擬和實現(xiàn)人類的學習，獲取處理問題的知識；自然言語了解是讓計算機了解和處置人類進展交流的自然言語。 4.1 人工智能根本原理.2智能決策支持系統(tǒng)構(gòu)造方式 1根本構(gòu)造智能決策支持系統(tǒng)IDSS決策支持系統(tǒng)DSS人工智能AI技術(shù) 4.1 人工智能根本原理. 問題綜合與交互系統(tǒng) 數(shù)據(jù)庫 管理系統(tǒng) 模型庫 管理系統(tǒng)模型庫數(shù)據(jù)庫 人工智能技術(shù)專家系統(tǒng)神經(jīng)網(wǎng)絡(luò)遺傳算法機器學習自然語言了解圖4.1 智能決策支持系統(tǒng)的根本構(gòu)造. 圖4.2 智能決策支持系統(tǒng)構(gòu)造 問題綜合與交互系統(tǒng) 模型庫管理系統(tǒng) 數(shù)據(jù)庫管理系統(tǒng) 知識庫 管理系統(tǒng) 推理機用戶 模型庫 知識庫 數(shù)據(jù)庫人工智能技術(shù)可以概括為：推理機知識庫

3、智能決策支持系統(tǒng)的構(gòu)造可以簡化為圖4.2.4.2 人工智能根本原理4.2.1 邏輯推理4.2.2 知識表示與知識推理4.2.3 搜索技術(shù).4.2.1 邏輯推理1.方式邏輯(人的思想方式、規(guī)律)1概念：反映事物的特有屬性和屬性的取值。2判別：對概念的一定或否認； 判別本身有對有錯； 判別有全稱的一定或否認判別和存在的一定或否認判別。3推理：從一個或多個判別推出一個新判別的過程。.4.2.1 邏輯推理2.推理的種類演繹推理歸納推理類比推理假言推理三段論推理數(shù)學歸納法假言易位推理枚舉歸納推理1演繹推理：從普通景象到個別特殊景象的推理。2歸納推理：從個別特殊景象到普通景象的推理。3類比推理：從個別特殊

4、景象到個別特殊景象的推理。.1演繹推理 專家系統(tǒng)的研討根本上屬于演繹推理范疇。演繹推理的中心是假言推理。 假言推理：以假言判別為前提，對該假言判別的前件或后件的推理。 1假言推理： pq，p q 2三段論推理 ： pq，qr pr 3假言易位推理拒取式：pq，q p 符號“表示推出4.2.1 邏輯推理. 2歸納推理(個別普通)1數(shù)學歸納法 這種推導是嚴厲的，結(jié)論是確實可靠的。2枚舉歸納推理 S1是P ，S2是P ， Sn是P S1Sn是S類事物中的部分分子，沒有相反事例。 所以，S類事物都是P。 枚舉歸納推理的結(jié)論是或然的(并非必然地)，它的可靠性和事例數(shù)量相關(guān) 。4.2.1 邏輯推理.枚舉歸

5、納推理實例 如察看到鐵受熱膨脹、銅受熱膨脹等現(xiàn)實而不知其所以然，由此推出“一切金屬受熱膨脹的結(jié)論就是簡單枚舉歸納推理。 . 3類比推理 它是由兩個或兩類事物在某些屬性上一樣，進而推斷它們在另一個屬性上也能夠一樣的推理。A事物有abcd屬性,B事物有abc屬性或a,b,c類似屬性所以， B事物也能夠有d屬性或d類似屬性 類比推理的結(jié)論帶有或然性，它的可靠性和相類比事物屬性之間的聯(lián)絡(luò)程度有關(guān)。4.2.1 邏輯推理.類比推理實例一 1816年的一天，法國醫(yī)生雷奈克出診為一位年輕的女性看病，一見病人，雷奈克犯起愁來：她身體非常肥胖，要診斷她的心臟和肺部能否正常，按當時醫(yī)生慣用的方法，把耳朵貼近病人的胸

6、部來聽，一定聽不清楚，更何況她是一位年輕的女性。雷奈克抬頭看了看院子里正在玩耍的小孩，腦子里忽然浮現(xiàn)出幾年前看到一個孩子們玩的游戲：一個孩子用釘子敲打木板的一頭，另外的孩子爭先恐后地抱著把耳朵貼近木板的另一頭，興致勃勃地傾聽著。. 為什么木頭可以把聲音明晰地傳過來呢？雷奈克略微想了想，只見他很很地拍了一下手說：“就是這樣！就是這樣！雷奈克要來一疊紙，緊緊地卷成一個卷，然后把紙卷的一端放在姑娘的胸部，另一端放在本人的耳朵上，側(cè)著臉聽了起來?！罢媸且粋€妙法！雷奈克高興地喊了一句。回到家里，雷奈克找到一根木棒，呵斥了歷史上第一個“聽診器。類比推理實例一.類比推理實例二 19世紀30年代，英國商人威爾

7、斯以與馮燦的茂隆皮箱商行訂購的皮箱中有不是皮的木料為由，向香港法院起訴，蓄意敲詐馮燦。針對這種情況，馮燦的律師羅文錦取出口袋的金懷表，高聲問法官：“請問這是什么表？法官答道：“這是金表，可是這與本案有什么關(guān)系？羅文錦高舉金表，面對法庭上一切的人說：“有關(guān)系。這是金表，沒有人疑心是吧？但是，請問，這塊金表除外表鍍金之外，內(nèi)部的機制都是金制嗎？旁聽者同聲議論：“當然不是。羅文錦繼續(xù)說：“那么人們?yōu)槭裁从纸兴鸨砟?？稍作停頓又高聲說：“由此可見，茂隆行的皮箱案不過是原告無理取鬧、存心敲詐而已原告理屈詞窮，法庭最后以威爾斯誣告，罰款5000元結(jié)案. 皮箱訴訟案的法庭爭辯中，賣方律師在反駁中所運用的就是

8、類比推理： 表的外表有金，內(nèi)部含有不是金的資料，但卻是金表； 箱的外表有皮，但也含有不是皮的資料；所以，箱仍是皮箱。類比推理實例二. 3. 總結(jié) 1演繹推理的結(jié)論沒有超出知的知識范圍。而歸納推理和類比推理的結(jié)論超出知的知識范圍。 演繹推理只能解釋普通規(guī)律中的個別景象 而歸納推理和類比推理發(fā)明了新的知識，使科學得到新開展，是一種發(fā)明思想方式。 2演繹推理中由于前提和結(jié)論有必然聯(lián)絡(luò)，只需前提為真，結(jié)論一定為真。 歸納推理和類比推理中前提和結(jié)論，不能保證有必然聯(lián)絡(luò)，具有或然性。這樣推理的結(jié)論未必是可靠的。需求經(jīng)過嚴厲的驗證和證明，使之構(gòu)成新的實際。4.2.1 邏輯推理.4.2.2 知識表示與知識推理

9、4.2.2.1 數(shù)理邏輯表示法(自學)4.2.2.1 產(chǎn)生式規(guī)那么4.2.2.3 語義網(wǎng)絡(luò)4.2.2.4 框架4.2.2.5 劇本(自學).4.2.2.2 產(chǎn)生式規(guī)那么if A then B1. 正向推理逐條搜索規(guī)那么庫，對每一條規(guī)那么的前提條件，檢查現(xiàn)實庫中能否存在。前提條件中各子項，假設(shè)在現(xiàn)實庫中不是全部存在，放棄該條規(guī)那么。假設(shè)在現(xiàn)實庫中全部存在，那么執(zhí)行該條規(guī)那么，把結(jié)論放入現(xiàn)實庫中。反復循環(huán)執(zhí)行上面過程，直至推出目的，并存入現(xiàn)實庫中為止。. 1. ABG 2. CDA 3. ED B,C,E4.2.2.2 產(chǎn)生式規(guī)那么現(xiàn)實庫的最后形狀為： B，C，E，D，A，G產(chǎn)生式規(guī)那么庫 現(xiàn)實庫

10、產(chǎn)生式規(guī)那么庫和現(xiàn)實庫的初始形狀為：.4.2.2.2 產(chǎn)生式規(guī)那么逆(反)向推理 逆向推理是從目的開場，尋覓以此目的為結(jié)論的規(guī)那么對該規(guī)那么的前提進展判別，假設(shè)該規(guī)那么的前提中某個子項是另一規(guī)那么的結(jié)論時，再找以此結(jié)論的規(guī)那么。反復以上過程，直到對某個規(guī)那么的前提可以進展判別。按此規(guī)那么前提判別“是或“否得出結(jié)論的判別，由此回溯到上一個 規(guī)那么的推理，不斷回溯到目的的判別。.GADEBC4.2.2.2 產(chǎn)生式規(guī)那么逆向推理中，目的改動過程： 1. ABG 2. CDA 3. ED B,C,E產(chǎn)生式規(guī)那么庫 現(xiàn)實庫.4.2.3 搜索技術(shù)搜索技術(shù)是人工智能的一個重要研討內(nèi)容。智能技術(shù)表達在減少搜索

11、樹中的盲目搜索。1.執(zhí)行時間與，等成正比的算法，稱為按多項式時間執(zhí)行。2.執(zhí)行時間與，！和等成正比的算法，稱為按指數(shù)時間執(zhí)行。按多項式時間執(zhí)行的算法，計算機是可以實現(xiàn)的。按指數(shù)時間執(zhí)行的算法，計算機是不能夠?qū)崿F(xiàn)的。.4.2.3 搜索技術(shù)人工智能中開展了一種稱為啟發(fā)式搜索方法，根本思想可用一個實例來闡明：一個外地人到某城市出差，他想到書店看看，又不知書店在何處，假設(shè)采取盲目搜索，從住地出發(fā)沿任一方向走，在分叉路口又任選一分支走，他能夠走幾天幾夜也找不到假設(shè)采用啟發(fā)式方法，他會問路上的人，到書店怎樣走。城市中的大部分人對書店不知道，問不出來。.4.2.3 搜索技術(shù)改一種問法：問該城市最繁華的地方在

12、哪兒？按照這個啟發(fā)式信息沿著指路人的道路，乘車到達最繁華的地方但書店在哪兒，依然不知道。假設(shè)盲目搜索，能夠依然找不到。假設(shè)采用啟發(fā)式方法，他會問路上的人，賣畫的地方在哪兒，他可以經(jīng)過畫店再問書店在哪兒？啟發(fā)式方法能減少大量盲目無效的搜索，能有效抑制按指數(shù)時間執(zhí)行的組合爆炸景象.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)先搜索思想 從初始形狀S開場，利用規(guī)那么，生成一切能夠的形狀。構(gòu)成樹的下一層節(jié)點，檢查能否出現(xiàn)

13、目的形狀G，假設(shè)未出現(xiàn)，就對該層一切形狀節(jié)點，分別順序利用規(guī)那么。生成再下一層的一切形狀節(jié)點，對這一層的一切形狀節(jié)點檢查能否出現(xiàn)G，假設(shè)未出現(xiàn)，繼續(xù)按上面思想生成再下一層的一切形狀節(jié)點.這樣一層一層往下展開。直到出現(xiàn)目的形狀G為止。 .圖4.7 廣度優(yōu)先搜索表示圖 .2算法1) 把初始節(jié)點S0故入OPEN表。2) 假設(shè)OPEN表為空，那么問題無解，退出 。 3) 把OPEN表的第一個節(jié)點(記為節(jié)點n)取出放入CLOSED表。4)調(diào)查節(jié)點n能否為目的節(jié)點。假設(shè)是，那么求得了問題的解，退出。 5)假設(shè)節(jié)點n不可擴展，那么轉(zhuǎn)第2)步。 6) 擴展節(jié)點n，將其子節(jié)點放入OPEN表的尾部，并為每一個子節(jié)

14、點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第2)步。.廣度優(yōu)先搜索過程開場把n的后繼節(jié)點放入OPEN表的末端，提供前往節(jié)點n的指針把S放入OPEN表OPEN表為空表？是失敗否把第一個節(jié)點n從OPEN移至CLOSED表n為目的節(jié)點？是勝利否n能否擴展能否有任何后繼節(jié)點為目的節(jié)點否是是否.例子1(八數(shù)碼難題 )重排九宮問題，在3x3的方格棋盤上放置分別標有數(shù)字1、2、3、4、5、6、7、8共8個棋子，初始形狀為S0，目的形狀為Sg，如圖1所示。可運用的算符有： 空格左移，空格上移，空格右移，空格下移。即只允許把位于空格左、上、右、下的臨近棋子移入空格。要求尋覓從初始形狀到目的形狀的途徑。?. 該途徑運用的算

15、符序列：空格上移，空格左移，空格下移，空格右移。 廣度優(yōu)先搜索的盲目性較大，當目的節(jié)點間隔初始節(jié)點較遠時將會產(chǎn)生許多無用節(jié)點，因此搜索效率低，但是，只需問題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是途徑最短的途徑。 由圖2可以看出，解的途徑是： S0381626廣度優(yōu)先法適宜于搜索樹的寬度較小的問題。.1、深度優(yōu)先搜索法思想 從初始形狀S開場，利用規(guī)那么生成搜索樹下一層任一個結(jié)點，檢查能否出現(xiàn)目的形狀G，假設(shè)未出現(xiàn)，以此形狀利用規(guī)那么生成再下一層任一個結(jié)點，再檢查能否為目的節(jié)點G。假設(shè)未出現(xiàn)，繼續(xù)以上操作過程，不斷進展到葉節(jié)點即不能再生成新形狀節(jié)點。當它仍不是目的形狀G時，回溯到上一層結(jié)果

16、，取另一能夠擴展搜索的分支。生成新形狀節(jié)點。不斷進展下去，直到找到目的形狀G為止。4.2.3.2 深度優(yōu)先搜索法.圖4.8 深度優(yōu)先搜索表示圖 .2算法1) 把初始節(jié)點S0故入OPEN表。2)假設(shè)OPEN表為空，那么問題無解，退出 。 3)把OPEN表的第一個節(jié)點(記為節(jié)點n)取出放入 CLOSED表。 4)調(diào)查節(jié)點n能否為目的節(jié)點。假設(shè)是，那么求得了問題的解，退出。 5)假設(shè)節(jié)點n不可擴展，那么轉(zhuǎn)第2)步。 6)擴展節(jié)點n，將其全部子節(jié)點放入到OPEN表的首部，并為其配置指向父節(jié)點的指針，然后轉(zhuǎn)第2)步。.開場把S放入OPEN表OPEN表為空表？是失敗否把第一個節(jié)點n從OPEN移至CLOSE

17、D表能否有任何后繼節(jié)點為目的節(jié)點是勝利否擴展n,把n的后繼節(jié)點放入OPEN表的前頭，提供前往節(jié)點n的指針s為目的節(jié)點？否是深度優(yōu)先搜索.例子2： 對圖1所示的重排九宮問題進展深度優(yōu)先搜索，可得到圖3所示的搜索樹這只是搜索樹的一部分，尚未到達目的節(jié)點，仍需繼續(xù)往下搜索。 ?. 在深度優(yōu)先搜索中，搜索一旦進入某個分支，就將沿著該分支不斷向下搜索。假設(shè)目的節(jié)點恰好在此分支上，那么可較快地得到解。但是，假設(shè)目的節(jié)點不在此分支上，而該分支又是一個無窮分支，那么就不能得到解。所以深度優(yōu)先搜索是不完備的，即使問題有解，它也不一定能求得解。顯然，用深度優(yōu)先求得的解，也不一定是途徑最短的解。 深度優(yōu)先法適宜于搜

18、索樹的深度較小的問題.4.2.3.3 生成測試法生成測試法算法是：1、生成一個能夠形狀節(jié)點。 2、測試該形狀能否為目的形狀。3、假設(shè)是目的形狀那么終了。否那么回到第1步其中：生成能夠的形狀，可以是有規(guī)律的，也可以是無規(guī)律的.4.2.3.3 生成測試法1假設(shè)搜索過程中，總是利用剛生成出的形狀來生成新形狀，這種生成測試法就是深度優(yōu)先搜索法。2假設(shè)搜索過程中，總是利用舊形狀生成一切能夠出新形狀，而且形狀節(jié)點以從舊到新的順序逐個生成的原那么。這種生成測試法就是廣度優(yōu)先搜索法。3假設(shè)搜索過程中，有時利用舊形狀生成新形狀，有時利用新形狀生成新形狀，這就是無規(guī)律的生成測試法。 .4.2.3.4 爬山法(生成

19、測試法的變種) 爬山算法：(測試函數(shù))1.開場形狀作為一個能夠形狀。2.從一個能夠形狀，運用規(guī)那么生成一切新的能夠形狀集。3.對該形狀集中每一形狀，進展如下操作： 對該形狀測試，檢查能否為目的，是那么停頓。 計算該形狀的好壞，或者比較各形狀的好壞。4.取形狀集中最好形狀，作為下一個能夠形狀。5.循環(huán)到第2步。.在爬山法中能夠出現(xiàn)以下幾種情況： 部分極大點：它比周圍鄰居形狀都好，但不是目的。 圖4.9部分極大點表示圖.在爬山法中能夠出現(xiàn)以下幾種情況： 平頂：它與全部鄰居形狀都有同一個值，構(gòu)成一個 平面。 圖4.10 平頂表示圖.在爬山法中能夠出現(xiàn)以下幾種情況： 山脊：它與線狀鄰居形狀有一樣值，比

20、其它鄰居形狀要好。圖4.11山脊表示圖.4.2.3.4 爬山法為理處理以上問題，需求采用如下戰(zhàn)略：1退回到某一更早形狀結(jié)點，沿著另一方向?qū)υ摻Y(jié)點就不一定是當時最好值的方向進展爬山。2朝一個方向前進一大步按某方向深度優(yōu)先搜索多次，走出平頂區(qū)，按別方向進展爬山。3同時朝兩個或多個方向前進，即按兩個或多個方向爬山。 .4.2.3.5 啟發(fā)式搜索 啟發(fā)式搜索是對每個在搜索過程中遇到的新形狀，用一個估計函數(shù)啟發(fā)式函數(shù)并計算其值的大小，確定下一步將從哪一個形狀開場繼續(xù)前進。普通以估計值小者為較優(yōu)的形狀，以此實行最優(yōu)搜索。估計函數(shù)值的大小與從初始形狀到達目的形狀的途徑有關(guān)。.4.2.3.5 啟發(fā)式搜索詳細需

21、求思索以下問題：1下一步選擇哪個形狀結(jié)點？2是部分展開幾個形狀結(jié)點還是全部展開一切能夠產(chǎn)生的形狀結(jié)點？3運用哪個規(guī)那么或算子來展開新形狀結(jié)點？4怎樣決議舍棄還是保管新生成的形狀結(jié)點？5如何定義啟發(fā)式函數(shù)估計值函數(shù)？6如何決議搜索方向？7怎樣決議停頓或繼續(xù)搜索？ .普通啟發(fā)式函數(shù)法用如下公式表示： fx=gx+hx fx表示由開場形狀到目的形狀的總耗費 gx表示開場形狀到當前形狀的耗費。 hx表示當前形狀到目的形狀的耗費。4.2.3.5 啟發(fā)式搜索.啟發(fā)式函數(shù)分析：1. 當hx=0，即fx=gx 取fx為最小，即取gx為最小。這要求在已擴展的結(jié)點中取最正確途徑。gx能保證找到最好解。但對搜索速度

22、沒有太多的協(xié)助。2. 當gx=0，即fx=hx hx是從當前形狀到目的形狀的耗費。取它最小，將會加快搜索速度，但它并不保證得到最優(yōu)解。4.2.3.5 啟發(fā)式搜索. gx選取的幾種特例： gx為搜索樹的深度， hx=0，那么啟發(fā)式方法為廣度優(yōu)先搜索法。 gx為搜索樹的深度的負數(shù)，hx=0，那么啟發(fā)式方法為深度優(yōu)先搜索法。由于深度愈深，負數(shù)愈大，搜索法總向深度開展。(3) gx為初始形狀到該結(jié)點的代價,那么啟發(fā)式方法為代價優(yōu)選搜索法。 f(x)普通表示估計值，愈接近準確值，啟發(fā)式效果愈好。假設(shè)是準確值,就不是啟發(fā)式函數(shù)。4.2.3.5 啟發(fā)式搜索.圖-4 啟發(fā)式搜索2831647528314765

23、1382476528314765231847652831476583214765283714652318476523184765832147651382476512384765813264758132476512378465832147658132476581324765123847651382476512384765*81372465*4455453542305455453204hx可以定義為節(jié)點x中數(shù)碼位置與目的節(jié)點相比不同的個數(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

24、智能決策支持系統(tǒng).4.3.1專家系統(tǒng)原理1. 專家系統(tǒng)概念1專家系統(tǒng)定義專家系統(tǒng)是具有大量專門知識，并能運用這些知識處理特定領(lǐng)域中實踐問題的計算機程序系統(tǒng)。專家系統(tǒng)是利用大量的專家知識，運用知識推理的方法來處理各特定領(lǐng)域中的實踐問題。計算機專家系統(tǒng)這樣的軟件可以到達人類專家處理問題的程度。.4.3.1專家系統(tǒng)原理2專家系統(tǒng)的特點專家系統(tǒng)需求大量的知識，這些知識是屬于規(guī)律性知識，它可以用來處理千變?nèi)f化的實踐問題。.4.3.1專家系統(tǒng)原理 例如： 求解微積分問題，是利用3040條微分、積分公式來求解千變?nèi)f化的微分、積分問題，得出各自的結(jié)果。其中微積分公式就是規(guī)律性知識，求解微積分問題就是對某函數(shù)反

25、復利用微積分公式進展推導，最后得出該問題的結(jié)果。這個推理過程是一個不固定方式的推理，即前后用哪個公式，調(diào)用多少次這些公式都隨問題變化而變化。.1 專家系統(tǒng)對比數(shù)據(jù)庫檢索數(shù)據(jù)庫中存放的記錄可以看成是現(xiàn)實性知識。假設(shè)把檢索數(shù)據(jù)庫記錄看成是推理的話，它也是一種知識推理。它與專家系統(tǒng)的不同在于：A知識只含現(xiàn)實性知識，不包含規(guī)律性知識。B推理是對已有記錄的檢索，記錄不存在，那么檢索不到。不能順應(yīng)變化的現(xiàn)實，推理不出新現(xiàn)實。4.3.1專家系統(tǒng)原理.4.3.1專家系統(tǒng)原理 2專家系統(tǒng)對比數(shù)值計算數(shù)值計算是用算法處理實踐問題，對不同的數(shù)據(jù)可以算出不同的結(jié)果。假設(shè)把數(shù)據(jù)看成是知識，算法看成推理的話，它也是一種知

26、識推理。它與專家系統(tǒng)的不同在于：A算法推理過程是固定方式的。算法一經(jīng)確定，推理過程就固定了。而專家系統(tǒng)的推理是不固定方式的，隨著問題不同，推理過程也不一樣。B數(shù)值計算只能處置數(shù)值，不能處置符號。.知識處置的特點從上面分析可見，數(shù)值計算、數(shù)據(jù)處置是知識處置的特定情況，知識處置那么是它們的開展! A知識包括現(xiàn)實和規(guī)那么形狀轉(zhuǎn)變過程。B適宜于符號處置如微積分求解。C推理過程是不固定方式的推導過程中每次選用的規(guī)那么知識是變化的。D能得出未知的現(xiàn)實如推導出新的微分公式。. 2.專家系統(tǒng)構(gòu)造 專家系統(tǒng)的中心是知識庫和推理機。 專家系統(tǒng)可以概括為： 專家系統(tǒng)知識庫+推理機4.3.1專家系統(tǒng)原理.知識獲取人機

27、接口知識庫推理機 專家用戶咨詢 建議專家系統(tǒng)中心 專家系統(tǒng)構(gòu)造 . 3.產(chǎn)生式規(guī)那么知識的推理機 產(chǎn)生式規(guī)那么的推理機搜索+匹配假言推理在推理過程中，是一邊搜索一邊匹配。匹配需求找現(xiàn)實,這個現(xiàn)實一是來自于規(guī)那么庫中別的規(guī)那么，一是來自向用戶提問。在匹配時會出現(xiàn)勝利或不勝利，對于不勝利的將引起搜索中的回溯和由一個分枝向另一個分枝的轉(zhuǎn)移，可見在搜索過程中包含了回溯。4.3.1 專家系統(tǒng)原理.4.3.1 專家系統(tǒng)原理4. 產(chǎn)生式規(guī)那么推理的解釋推理中的搜索和匹配過程，假設(shè)進展跟蹤和顯示就構(gòu)成了向用戶闡明的解釋機制。好的解釋機制不顯示那些對于失敗途徑的跟蹤。 .4.3.2 產(chǎn)生式規(guī)那么專家系統(tǒng)4.3.

28、2.1 產(chǎn)生式規(guī)那么4.3.2.2 推理樹(知識樹)4.3.2.3 逆向推理過程4.3.2.4 現(xiàn)實數(shù)據(jù)和解釋機制.4.3.2 產(chǎn)生式規(guī)那么專家系統(tǒng)產(chǎn)生式規(guī)那么的優(yōu)點產(chǎn)生式規(guī)那么知識表示方式容易被人了解它是基于演繹推理的,保證了推理結(jié)果的正確性大量產(chǎn)生式規(guī)那么所連成的推理樹(知識樹),可以是多棵樹.樹的寬度反映問題的范圍樹的深度反映問題的難度 .4.3.2.1 產(chǎn)生式規(guī)那么ES 產(chǎn)生式規(guī)那么知識普通表示為:if A then B， 或 ：假設(shè)A成立那么B成立， 或 ： AB.4.3.2.1 產(chǎn)生式規(guī)那么產(chǎn)生式規(guī)那么知識表示允許有如下的特點： 一樣的條件可以得出不同的結(jié)論。如：ABAC 一樣的結(jié)

29、論可以有不同的條件來得到。如AGBG 條件之間可以是“與AND銜接和“或OR銜接如ABGABG相當于AG，BG 一條規(guī)那么中的結(jié)論，可以是另一條規(guī)那么中的條件。如FB，CF其中F在前一條規(guī)那么中是條件，在后一條規(guī)那么中是結(jié)論。.4.3.2.1 產(chǎn)生式規(guī)那么ES由于以上特點，規(guī)那么知識集能做到：能描畫和處理各種不同的靈敏的實踐問題。由前三點特點構(gòu)成 能把規(guī)那么知識集中的一切規(guī)那么連成一棵“與、或推理樹知識樹。即這些規(guī)那么知識集之間是有關(guān)聯(lián)的由后二個特點構(gòu)成。 .4.3.2.2推理樹知識樹規(guī)那么庫中的各條規(guī)那么之間普通來說都是有聯(lián)絡(luò)的某條規(guī)那么中的前提是另外一條規(guī)那么中的結(jié)論。按逆向推理思想把知識

30、庫所含的總目的它是某些規(guī)那么的結(jié)論作為根結(jié)點，按規(guī)那么的前提和結(jié)論展開成一棵樹的方式。這棵樹普通稱為推理樹或知識樹，它把知識庫中的一切規(guī)那么都連結(jié)起來由于連結(jié)時有“與關(guān)系和“或關(guān)系，從而構(gòu)成了“與或推理樹。. X F GL M EC4.3.2.2推理樹知識樹注：兩斜線中間的弧線表示“與關(guān)系，無弧線表示“或關(guān)系規(guī)那么知識庫的逆向推理樹例：假設(shè)有知識庫為：ABCGIJKAXFJLBMECWZMPQE 畫出“與或推理樹ABI J KW ZP Q. 用規(guī)那么的前提和結(jié)論方式畫出逆向推理樹方式為： 4.3.2.2推理樹知識樹前提I 前提J 前提L 前提M 前提E (結(jié)論) (結(jié)論) (結(jié)論) 前提A 前

31、提B 前提C結(jié)論) 結(jié)論 (結(jié)論)總目的G結(jié)論)前提X 前提F 前提W 前提Z 前提P 前提Q ? ? ? ? ? ? ? ?.該“與或推理樹的特點是： 每條規(guī)那么對應(yīng)的節(jié)點分枝有與AND關(guān)系，或OR關(guān)系 樹的根結(jié)點是推理樹的總目的 相鄰兩層之間是一條或多條規(guī)那么銜接 每個結(jié)點可以是單值，也可以是多值。假設(shè)結(jié)點是多值時，各值對應(yīng)的規(guī)那么將不同。 一切的葉結(jié)點，都安排向用戶提問，或者把它的值直接放在現(xiàn)實數(shù)據(jù)庫中。4.3.2.2推理樹知識樹.4.3.2.3 逆向推理過程 推理樹的深度優(yōu)先搜索 N17982GABCJIKLME45YXFZPQ1011123YWYYYN6逆向推理過程在推理樹中的反映為

32、推理樹的深度優(yōu)先搜索過程。 .4.3.2.3 逆向推理過程 在計算機中實現(xiàn)時，并不把規(guī)那么連成推理樹，而是利用規(guī)那么棧來完成。當調(diào)用此規(guī)那么時，把它壓入棧內(nèi)相當于對樹的搜索，當此規(guī)那么的結(jié)論已求出yes或no時，需求將此規(guī)那么退棧相當于對樹的回溯。 利用規(guī)那么棧的壓入和退出的過程，相當于完成了推理樹的深度優(yōu)先搜索和回溯過程。.4.3.2.3 逆向推理過程 結(jié)點的否認每個結(jié)點有兩種能夠，即YES和NO。葉結(jié)點為NO是由用戶回答構(gòu)成的。中間結(jié)點為NO是由葉結(jié)點為NO，回溯時引起該結(jié)點為NO。假設(shè)當該結(jié)點還有其它“或條件分枝時，不能立刻確定該結(jié)點為NO，必需再搜索另一分枝，當另一分枝回溯為YES時，

33、該結(jié)點仍為YES。中間結(jié)點只需一切“或分枝的回溯值均為NO時，才干最后確定該中間結(jié)點為NO。 .4.3.2.4 現(xiàn)實數(shù)據(jù)庫和解釋機制 1. 現(xiàn)實數(shù)據(jù)庫(動態(tài)數(shù)據(jù)庫) 現(xiàn)實Y,N值規(guī)那么號可信度A11N0(提問)0A12Y00.9A1Y40.8現(xiàn)實欄放入命題規(guī)那么號：現(xiàn)實取Y或N的理由可信度：現(xiàn)實的可信度.2. 解釋機制解釋機制是專家系統(tǒng)中重要內(nèi)容。它把推理過程顯示給用戶，讓用戶知道目的是如何推導出來的。消除用戶對目的結(jié)論的疑慮。兩種實現(xiàn)方法一種是推理過程的全部解釋；一種是推理過程中正確途徑的解釋。4.3.2.4 現(xiàn)實數(shù)據(jù)庫和解釋機制 .4.3.3 專家系統(tǒng)與決策支持系統(tǒng)集成 IDSS充分發(fā)揚了

34、專家系統(tǒng)以知識推理方式處理定性分析問題的特點.發(fā)揚了決策支持系統(tǒng)以模型計算為中心的處理定量分析問題的特點.充分做到定性分析和定量分析的有機結(jié)合. .數(shù)據(jù)庫DBDSS控制系統(tǒng)模型庫MB問題綜合與交互系統(tǒng)動態(tài)DB推理機和解釋器知識庫KB集成系統(tǒng)DSSES 圖4.16智能決策支持系統(tǒng)集成構(gòu)造圖綜合系統(tǒng)DSS和ES的總體結(jié)合。 由集成系統(tǒng)把DSS和ES有機結(jié)合起來2. KB和MB的結(jié)合。 模型庫中的數(shù)學模型和數(shù)據(jù)處置模型作為知識的一種方式，即過程性知識，參與到知識推理過程中去。3. DB和動態(tài)DB的結(jié)合。 DSS中的DB可以看成是相對靜態(tài)的數(shù)據(jù)庫，它為ES中的動態(tài)數(shù)據(jù)庫提供初始數(shù)據(jù)，ES推理終了后，動

35、態(tài)DB中的結(jié)果再送回到DSS中的DB中去。 .DSS與ES集成方式一：DSS和ES并重的IDSS構(gòu)造 集成系統(tǒng)DSSES4.3.3 專家系統(tǒng)與決策支持系統(tǒng)集成 集成特點1.具有綜合系統(tǒng)，具有調(diào)用和集成DSS和ES的才干。2.擴展DSS的問題與人機交互系統(tǒng)功能，添加對ES的調(diào)用組合才干DSS與ES的關(guān)系：DSS中DB與ES中的動態(tài)DB進展數(shù)據(jù)交換處理問題的特點表達定性分析和定量分析并重處理問題的特點。.DSS控制系統(tǒng)MBDBESDSS與ES集成方式二： DSS為主體的IDSS構(gòu)造 4.3.3 專家系統(tǒng)與決策支持系統(tǒng)集成 集成特點集成系統(tǒng)和DSS控制系統(tǒng)合為一體DSS與ES的關(guān)系：ES被DSS控制

36、系統(tǒng)調(diào)用處理問題的特點表達以定量分析為主，結(jié)果定性分析處理問題的特點。.推理機廣義DSS動態(tài)DBKB推理機MB動態(tài)DBKB圖4.19 DSS作為推理方式的IDSS圖4.20模型作為知識的IDSSDSS與ES集成方式三： ES為主體的IDSS構(gòu)造4.3.3 專家系統(tǒng)與決策支持系統(tǒng)集成 集成特點人機交互系統(tǒng)和ES合為一體DSS與ES的關(guān)系：圖4.19 DSS作為推理機，受ES的推理機控制；圖4.20數(shù)據(jù)模型作為知識出現(xiàn)處理問題的特點表達以定量分析為主，結(jié)果定性分析處理問題的特點。.4.3.4 建模專家系統(tǒng) 專家系統(tǒng)實現(xiàn)模型選擇的實例進展闡明。 例如，彈簧振動建模專家系統(tǒng)。 該專家系統(tǒng)是處理彈簧在不

37、同受力情況下包括沖力、摩擦力等應(yīng)該滿足那種類型的微分方程模型。 彈簧振動建模專家系統(tǒng)進展簡化闡明如下： .1、規(guī)那么20條：R1：ABCM1R2：A1AR3：A11A1R4：A12A1R5：ABEFM2R6：C1CR7：E1ER8：ABEFGM3R9：ABCGM4R10：B1BR11：H1HR12：A2AR13：HBCM5R14：HBCGM6R15：HBEFM7R16：HBEFGM8R17：ABEIM9R18：ABIGM10R19：HBEIM11R20：HBEIGM124.3.4 建模專家系統(tǒng) .A：彈簧滿足胡克定律B：彈簧質(zhì)量可以忽略C：可以忽略摩擦力D：沒有沖力A1：彈簧有線性恢復力A11

38、：彈力與位移成正比A12：位移量很小E：要思索摩擦力F：摩擦力與速度之間為線性關(guān)系C1：假設(shè)振動為自發(fā)時振幅為常數(shù)E1：假設(shè)振動為自發(fā)時振幅是遞減的G：有沖力FTB1：彈簧具有質(zhì)量N并且N/M遠遠小于1H1：彈簧勢能不是關(guān)于平衡位置對稱H：彈簧不潢足胡克定律A2：彈簧勢能與函數(shù)XT成正比I：摩擦力與速度之間為非線性關(guān)系各項英文字母含義為：.M1：X+C2/MX0M2：X+C1/MX+C2/MX0M3：X+C1/MX+C2/MXFT/MM4：X+C2/MXFT/MM5：X+ FX/M0M6：X+ FX/MFT/MM7：X+C1/MX+ FX/M0M8：X+C1/MX+ FX/MFT/MM9：X+

39、G/MX+C2/MX0M10：X+G/MX+C2/MXFT/MM11：X+G/MX+ FX/M0M12：X+G/MX+ FX/MFT/M其中X表示X對的二階導數(shù)，X表示一階導數(shù)。各模型微分方程為：.3. 規(guī)那么庫的推理樹 將20條規(guī)那么連成的推理樹見以下圖所示。 每個葉節(jié)點提問的回答為： Yyes，Nno 專家系統(tǒng)將解釋為證明某條規(guī)那么而安排的提問。用戶不明白專家系統(tǒng)為什么要提該問題，可以回答why4.3.4 建模專家系統(tǒng) . A2 A1 B1 C1 ？ E1 ？ ？ B1 ？ A11 A12 ？ ？ ？ ？ D E F G H IA B C ？ ？MM1，M2，M12圖4.21彈簧振動推理樹

40、的規(guī)范方式.專家系統(tǒng)運用現(xiàn)有一個彈簧，滿足如下特性： H1彈簧勢能不是關(guān)于平衡位置對稱 B1彈簧具有質(zhì)量N并且N/M遠遠小于1 C1假設(shè)振動為自發(fā)時振幅為常數(shù) G有沖力FT經(jīng)過專家系統(tǒng)推理將得出： 該彈簧滿足模型6M6的微分方程。 .4.5 遺傳算法的決策支持4.5.1 遺傳算法原理4.5.2 優(yōu)化模型的遺傳算法求解4.5.3 獲取知識的遺傳算法4.5.4 遺傳規(guī)劃建立模型.4.5.1 遺傳算法原理遺傳算法(Genetic Algorithm，GA)是模擬生物進化的自然選擇和遺傳機制的一種尋優(yōu)算法。適用于復雜的非線性問題,主要運用在組合優(yōu)化和機器學習兩個方面。運用領(lǐng)域：圖像識別、圖像恢復、自順

41、應(yīng)控制、優(yōu)化調(diào)度等領(lǐng)域。.遺傳算法的開展過程大體上可分為以下三個階段： 170年代的興起階段。1975年美國Michigan 大學J.Holland初次系統(tǒng)地論述了遺傳算法的根本實際和方法。 在這一時期的大部分研討都處于實際研討和建立實驗?zāi)Ｐ碗A段280年代的開展階段。1980年Smith教授將遺傳算法運用于機器學習領(lǐng)域，研制出了一個著名的分類器(Classifier)系統(tǒng)。這期間許多學者對遺傳算法進展了大量的改良和開展，提出了許多勝利的遺傳算法模型，使遺傳算法運用于更廣泛的領(lǐng)域。 390年代的高潮階段。進入90年代后，遺傳算法作為一種適用、高效的優(yōu)化技術(shù)，得到了極為迅速的開展。 4.5.1 遺

42、傳算法原理.4.5.1 遺傳算法原理4.5.1.1 遺傳算法任務(wù)過程4.5.1.2 遺傳算法的實際根底4.5.1.3 遺傳算法的根本特征.4.5.1.1 遺傳算法的任務(wù)過程遺傳算法是一種群體型操作，該操作以群體中的一切個體為對象。個體就是模擬生物個體而對問題中的對象普通就是問題的解的一種稱謂，一個個體也就是搜索空間中的一個點。種群(population)就是模擬生物種群而由假設(shè)干個體組成的群體, 它普通是整個搜索空間的一個很小的子集。遺傳算法的三個主要操作算子：選擇selecation、交叉crossover和變異mutation 構(gòu)成了遺傳操作Genetic operation，使遺傳算法具

43、有了其他傳統(tǒng)方法所沒有的特性。.產(chǎn)生新一代群體編碼和初始群體構(gòu)成輸出種群 個體順應(yīng)值稱心否？4.5.1.1 遺傳算法的任務(wù)過程 首先將問題的每個能夠的解按某種方式編碼，編碼后的解稱作染色體個體。 隨機選取N個染色體構(gòu)成初始種群，再根據(jù)預定的評價函數(shù)對每個染色體計算順應(yīng)值，使得性能較好的染色體具有較高的順應(yīng)值。 選擇順應(yīng)值高的染色體進展復制，經(jīng)過遺傳算子來產(chǎn)生一群新的更順應(yīng)環(huán)境的染色體，構(gòu)成新的種群。 這樣一代一代不斷繁衍，最后收斂到一個最順應(yīng)環(huán)境的個體上，求得問題的最優(yōu)解。遺傳算子選擇交叉變異.1. 群體中個體的編碼如何將問題描畫成位串的方式，即問題編碼。普通將問題的參數(shù)用二進制位基因編碼構(gòu)成

44、子串，再將子串拼接起來構(gòu)成“染色體位串。4.5.1.1 遺傳算法的任務(wù)過程例如： 個體 染色體 9 - 10012，5，6- 010 101 110.2. 順應(yīng)值函數(shù)確實定遺傳算法的執(zhí)行過程中，每一代有許多不同的染色體個體同時存在，這些染色體中哪個保管(生存)、哪個淘汰(死亡)是根據(jù)它們對環(huán)境的順應(yīng)才干決議的，順應(yīng)性強的有更多的時機保管下來。順應(yīng)性強弱是計算個體順應(yīng)值函數(shù)f(x)的值來判別的，這個值稱為順應(yīng)值(fitness)。順應(yīng)值函數(shù)(即評價函數(shù))是根據(jù)目的函數(shù)確定的。順應(yīng)值總是非負的，任何情況下總是希望越大越好。假設(shè)目的函數(shù)不是取最大值時，需求將它映射成順應(yīng)值函數(shù)。順應(yīng)值函數(shù)f(x)的構(gòu)

45、成與目的函數(shù)有親密關(guān)系，往往是目的函數(shù)的變種。普通是一個實值函數(shù)。該函數(shù)就是遺傳算法中指點搜索的評價函數(shù)。4.5.1.1 遺傳算法的任務(wù)過程.3.遺傳算法的三個算子一選擇(Selection)算子二交叉(Crossover)算子三變異(Mutation)算子4.5.1.1 遺傳算法的任務(wù)過程.它又稱復制(reproduction) 、繁衍算子。選擇是從種群中選擇生命力強的染色體產(chǎn)生新種群的過程。根據(jù)每個染色體的順應(yīng)值大小，順應(yīng)值越大，被選中的概率就越大，其子孫在下一代產(chǎn)生的個數(shù)就越多。選擇操作是建立在群體中個體的順應(yīng)值估評根底上的。4.5.1.1 遺傳算法的任務(wù)過程一選擇(Selection)

46、算子. 通常做法是：對于一個規(guī)模為N的種群S,按每個染色體xiS的選擇概率P(xi)所決議的選中時機, 分N次從S中隨機選定N個染色體, 并進展復制。4.5.1.1 遺傳算法的任務(wù)過程 這里的選擇概率P(xi)的計算公式為一選擇(Selection)算子.二交叉(crossover)算子它又稱重組(recombination) 、配對(breeding)算子，在遺傳算法中起著中心作用。染色體重組是分兩步驟進展的:首先在新復制的群體中隨機選取兩個個體然后，沿著這兩個個體(字符串)隨機地取一個位置，二者互換從該位置起的末尾部分。交叉率(crossover rate)就是參與交叉運算的染色體個數(shù)占全

47、體染色體總數(shù)的比例，記為Pc,取值范圍普通為0.40.99。4.5.1.1 遺傳算法的任務(wù)過程.4.5.1.1 遺傳算法的任務(wù)過程例1:有兩個用二進制編碼的個體A和B。長度L=5，A=a1a2a3a4a5 ，B=b1b2b3b4b5隨機選擇一整數(shù)k1，L-1 ，設(shè)k=4，經(jīng)交叉后變?yōu)椋篈 = a1a2a3|a4a5 B = b1b2b3|b4b5 A= a1a2a3 b4b5 B = b1b2b3 a4a5 s1=01000101, s2=10011011可以看做是原染色體s1和s2的子代染色體。例2, 設(shè)染色體 s1=01001011, s2=10010101, 交換其后4位基因, 即二交叉

48、(crossover)算子.變異就是以很小的概率，隨機地改動字符串某個位置上的值。變異操作是按位bit進展的，即把某一位的內(nèi)容進展變異。在二進制編碼中，就是將某位0變成1，1變成0。選擇和交叉算子根本上完成了遺傳算法的大部分搜索功能，而變異那么添加了遺傳算法找到接近最優(yōu)解的才干。變異率(mutation rate)是指發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，記為Pm，取值范圍普通為0.00010.02。它保證了遺傳算法的有效性。4.5.1.1 遺傳算法的任務(wù)過程三變異(Mutation)算子.4.5.1.1 遺傳算法的任務(wù)過程例如: 設(shè)染色體 s=11001101將其第三位上的0變

49、為1, 即 s=11001101 11101101= s。 s也可以看做是原染色體s的子代染色體。三變異(Mutation)算子.4.控制參數(shù)設(shè)定遺傳算法中的參數(shù)包括群體中個體的數(shù)目、交叉概率、變異概率等這些參數(shù)的設(shè)定隨詳細問題的不同將有所差別，帶有閱歷性，它會影響遺傳算法的迭代收斂過程。4.5.1.1 遺傳算法的任務(wù)過程.1.方式定理遺傳算法的實際根底是Holland提出的方式定理。一個方式(Schema)就是一個描畫種群中在位串的某些確定位置上具有類似性的位串子集的類似性模板(Similarity Template)。二進制串中的方式是如下的方式：a1，a2，ai，an，ai0，1，*，其

50、中“*是恣意符，或0，或1，方式是串的集合.方式H中確定位的個數(shù),稱為H的階,記為O(H)。方式H中第一個確定位與最后一個確定位之間的間隔稱為的定義距,記為(H)。4.5.1.2 遺傳算法的實際根底例:以長度L= 5的串為例,方式*101*描畫了在位置2、3、4具有方式“010的一切字符串, ：*101*=(11010)，(01010)，(01011)，(11011)。其階為3,定義距為2。.1.方式定理方式定理是遺傳算法的實際根底它闡明高順應(yīng)值、長度短、階數(shù)低的方式在后代中至少以指數(shù)增長包含該方式H的位串的數(shù)目。遺傳使高順應(yīng)值的方式復制更多的后代！4.5.1.2 遺傳算法的實際根底.2基因塊

51、假設(shè)高順應(yīng)值、長度短、低階的方式叫基因塊?；驂K假說基因塊經(jīng)過遺傳操作繁衍、交換、變異，再繁衍、再交換、再變異的逐漸進化，構(gòu)成潛在的順應(yīng)性較高的位串。該假設(shè)指出，經(jīng)過遺傳算法能尋覓到接近全局最優(yōu)解的才干。4.5.1.2 遺傳算法的實際根底.1. 遺傳算法的處置對象是問題參數(shù)的編碼個體位串遺傳算法要求將問題的參數(shù)編碼生長度有限的位串。遺傳算法是在求解問題的編碼串上進展操作，從中找出高順應(yīng)值的位串，而不是對問標題的函數(shù)和它們的參數(shù)直接操作。遺傳算法不受函數(shù)限制條件(如導數(shù)存在、延續(xù)性、單極值等)的約束。 4.5.1.3 遺傳算法的根本特征 .2. 遺傳算法的搜索是從問題解位串集開場搜索，而不是從單

52、個解開場在最優(yōu)化問題中，傳統(tǒng)的方法是從一個點開場搜索，如爬山法。普通復雜問題會在“地形中出現(xiàn)假設(shè)干“山峰，傳統(tǒng)的方法很容易走入假“山峰。遺傳算法同時從種群的每個個體開場搜索，象一張網(wǎng)罩在“地形上，數(shù)量極大的個體同時在很多區(qū)域中進展搜索，這樣就減少了墮入部分解的能夠性。4.5.1.3 遺傳算法的根本特征 .3. 遺傳算法只運用目的函數(shù)(即順應(yīng)值)來搜索，而不需求導數(shù)等其他輔助信息傳統(tǒng)搜索算法需求一些輔助信息，如梯度算法需求導數(shù)，當這些信息不存在時，這些算法就失效了。而遺傳算法只需目的函數(shù)和編碼串，因此，遺傳算法幾乎可以處置任何問題。4. 遺傳算法運用的三種遺傳算子是一種隨機操作，而不是確定性規(guī)那

53、么遺傳算法運用隨機操作，但并不意味著遺傳算法是簡單的隨機搜索。遺傳算法是運用隨機工具來指點搜索向著一個最優(yōu)解前進。5.隱含的并行性6.易介入到已有的模型中，并具有擴展性；易于同別的技術(shù)結(jié)合運用4.5.1.3 遺傳算法的根本特征 .4.5.2 優(yōu)化模型的遺傳算法求解 優(yōu)化模型的計算是遺傳算法最根本的也是最重要的研討和運用領(lǐng)域之一。 普通說來，優(yōu)化計算問題通常帶有大量的部分極值點，往往是不可微的、不延續(xù)的、多維的、有約束條件的、高度非線性的NP完全問題。 準確地求解優(yōu)化問題的全局最優(yōu)解普通是不能夠的。 .4.5.2 優(yōu)化模型的遺傳算法求解4.5.2.1 優(yōu)化模型的遺傳算法處置4.5.2.2 實例.

54、1、順應(yīng)值函數(shù)優(yōu)化遺傳算法在進化搜索中用目的函數(shù)即順應(yīng)值函數(shù)為根據(jù)。遺傳算法的目的原函數(shù)不受延續(xù)可微的約束且定義域可以為恣意集合對目的函數(shù)的獨一要求是，對輸入個體可計算出能進展比較的非負順應(yīng)值。這一特點使得遺傳算法運用范圍很廣。遺傳算法中，順應(yīng)值函數(shù)要比較排序，并在此根底上計算選擇概率，所以順應(yīng)值函數(shù)的值要取正值。順應(yīng)值函數(shù)評價是選擇操作的根據(jù)，順應(yīng)值函數(shù)設(shè)計直接影響到遺傳算法的性能。在不少場所，將目的函數(shù)映射成求最大值方式且函數(shù)值非負的順應(yīng)值函數(shù)是必要的。4.5.2.1 優(yōu)化模型的遺傳算法處置.2、約束條件的處置遺傳算法是由順應(yīng)值來評價和引導搜索，而對求解問題的約束條件不能明確地表示出來。用

55、遺傳算法求解這些帶約束的問題，需求進展一些處置。在等式約束方程中，對P個等式方程中抽出P個變量，經(jīng)過線性組合變換后，用其他變量表示為該P個變量的等式，并將它代入目的函數(shù)中，消去該P個變量。這樣，在目的函數(shù)中，就包含了這些等式約束條件。4.5.2.1 優(yōu)化模型的遺傳算法處置.4.5.2.1 優(yōu)化模型的遺傳算法處置 3、遺傳算法的迭代終止條件當順應(yīng)值函數(shù)的最大值知時，普通以發(fā)現(xiàn)滿足最大值或準最優(yōu)解作為遺傳算法迭代終止條件。但是，在許多優(yōu)化計算問題中，順應(yīng)值函數(shù)的最大值并不清楚，迭代終止條件普通定為：群體中個體的進化已趨于穩(wěn)定形狀，即發(fā)現(xiàn)占群體中一定比例的個體已完全是同一個體。.步1 在搜索空間U上

56、定義一個順應(yīng)度函數(shù)f(x)，給定種群規(guī)模N，交叉率Pc和變異率Pm，代數(shù)T；步2 隨機產(chǎn)生U中的N個個體s1, s2, , sN，組成初始種群S=s1, s2, , sN，置代數(shù)計數(shù)器t=1；步3 計算S中每個個體的順應(yīng)度f() ；步4 假設(shè)終止條件滿足，那么取S中順應(yīng)度最大的個體作為所求結(jié)果，算法終了。 步5 按選擇概率P(xi)所決議的選中時機，每次從S中隨機選定1個個體并將其染色體復制，共做N次，然后將復制所得的N個染色體組成群體S1； 步6 按交叉率Pc所決議的參與交叉的染色體數(shù)c，從S1中隨機確定c個染色體，配對進展交叉操作，并用產(chǎn)生的新染色體替代原染色體，得群體S2； 步7 按變異

57、率Pm所決議的變異次數(shù)m，從S2中隨機確定m個染色體，分別進展變異操作，并用產(chǎn)生的新染色體替代原染色體，得群體S3；步8 將群體S3作為新一代種群，即用S3替代S，t = t+1，轉(zhuǎn)步3； 根本遺傳算法步聚.例4.1 利用遺傳算法求解區(qū)間0,31上的二次函數(shù)y=x2的最大值。y=x2 31 XY. 分析 原問題可轉(zhuǎn)化為在區(qū)間0, 31中搜索能使y取最大值的點a的問題。那么，0, 31 中的點 x就是個體, 函數(shù)值f(x)恰好就可以作為x的順應(yīng)度，區(qū)間0, 31就是一個(解)空間 。這樣, 只需能給出個體x的適當染色體編碼, 該問題就可以用遺傳算法來處理。.解(1) 設(shè)定種群規(guī)模,編碼染色體，產(chǎn)

58、生初始種群。 將種群規(guī)模設(shè)定為4；用5位二進制數(shù)編碼染色體；取以下個體組成初始種群S1: s1= 13 (01101), s2= 24 (11000) s3= 8 (01000), s4= 19 (10011) (2) 定義順應(yīng)度函數(shù), 取順應(yīng)度函數(shù)：f (x)=x2 (3) 計算各代種群中的各個體的順應(yīng)度, 并對其染色體進展遺傳操作,直到順應(yīng)度最高的個體(即3111111)出現(xiàn)為止。 . 首先計算種群S1中各個體 s1= 13(01101), s2= 24(11000) s3= 8(01000), s4= 19(10011)的順應(yīng)度f (si) 。 容易求得 f (s1) = f(13) =

59、 132 = 169 f (s2) = f(24) = 242 = 576 f (s3) = f(8) = 82 = 64 f (s4) = f(19) = 192 = 361.再計算種群S1中各個體的選擇概率。選擇概率的計算公式為 由此可求得 P(s1) = P(13) = 0.14 P(s2) = P(24) = 0.49 P(s3) = P(8) = 0.06 P(s4) = P(19) = 0.31. 賭輪選擇表示s40.31s20.49s10.14s30.06 賭輪選擇法在算法中賭輪選擇法可用下面的子過程來模擬: 在0, 1區(qū)間內(nèi)產(chǎn)生一個均勻分布的隨機數(shù)r。 假設(shè)rq1,那么染色體x

60、1被選中。 假設(shè)qk-1rqk(2kN), 那么染色體xk被選中。 其中的qi稱為染色體xi (i=1, 2, , n)的積累概率, 其計算公式為 .選擇-復制 設(shè)從區(qū)間0, 1中產(chǎn)生4個隨機數(shù)如下: r1 = 0.450126, r2 = 0.110347 r3 = 0.572496, r4 = 0.98503 染色體 適應(yīng)度選擇概率積累概率選中次數(shù)s1=01101 169 0.14 0.14 1s2=11000 576 0.49 0.63 2s3=01000 64 0.06 0.69 0s4=10011 361 0.31 1.00 1.于是，經(jīng)復制得群體：s1 =1100024, s2 =