【文章內容簡介】 ? ? ? ?n 該 “ 與或 ” 推理樹的特點是：n ⒈ 每條規(guī)則對應的節(jié)點分枝有與（ AND）關系，或（ OR）關系n ⒉ 樹的 根結點 是推理樹的 總目標n ⒊ 相鄰兩層之間是 一條 或 多條 規(guī)則連接n ⒋ 每個結點可以是單值，也可以是多值。若結點是多值時，各值對應的規(guī)則將不同。n ⒌ 所有的葉結點，都安排向用戶提問，或者把它的值直接放在 事實數(shù)據(jù)庫 中。（知識樹） 逆向推理過程 ⒈ 推理樹的深度優(yōu)先搜索 N1 7 982GA B CJI K L M E4 5Y X F Z P Q1011 123Y WY Y YN6逆向推理過逆向推理過程在推理樹程在推理樹中的反映為中的反映為推理樹的深推理樹的深度優(yōu)先搜索度優(yōu)先搜索過程。過程。 逆向推理過程在計算機中實現(xiàn)時，并不把規(guī)則連成推理樹，而是利用規(guī)則棧來完成。當調用此規(guī)則時，把它壓入棧內（相當于對樹的搜索），當此規(guī)則的結論已求出（ yes或 no）時，需要將此規(guī)則退棧（相當于對樹的回溯）。 利用規(guī)則棧的壓入和退出的過程，相當于完成了推理樹的深度優(yōu)先搜索和回溯過程 。 逆向推理過程⒉ 結點的否定n 每個結點有兩種可能，即 YES和 NO。n 葉結點為 NOn 是由用戶回答形成的。n 中間結點為 NOn 是由葉結點為 NO，回溯時引起該結點為 NO。n 若當該結點還有其它 “ 或條件 ” 分枝時，不能立即確定該結點為 NO，必須再搜索另一分枝，當另一分枝回溯為 YES時，該結點仍為 YES。n 中間結點只有所有 “ 或 ” 分枝的回溯值均為 NO時，才能最后確定該中間結點為 NO。 事實數(shù)據(jù)庫和解釋機制 1. 事實數(shù)據(jù)庫 (動態(tài)數(shù)據(jù)庫 ) 事實 Y,N值 規(guī)則號 可信度A11 N 0(提問 ) 0A12 Y 0 A1 Y 4 事實欄放入命題規(guī)則號：事實取 Y或N的理由可信度：事實的可信度2. 解釋機制n 解釋機制是專家系統(tǒng)中重要內容。它把推理過程顯示給用戶，讓用戶知道目標是如何推導出來的。消除用戶對目標結論的疑慮。n 兩種實現(xiàn)方法n 一種是推理過程的全部解釋；n 一種是推理過程中正確路徑的解釋。事實數(shù)據(jù)庫和解釋機制 專家系統(tǒng)與決策支持系統(tǒng)集成 n IDSS充分發(fā)揮了專家系統(tǒng)以 知識推理 形式解決 定性 分析問題的特點 .n 發(fā)揮了決策支持系統(tǒng)以 模型計算 為核心的解決 定量 分析問題的特點 .n 充分做到 定性分析 和 定量分析 的有機結合 . 數(shù)據(jù)庫DBDSS控制系統(tǒng)模型庫MB問題綜合與交互系統(tǒng)動態(tài)DB推理機和解釋器知識庫KB集成系統(tǒng)DSS ES 圖 綜合系統(tǒng)1. DSS和和 ES的總體結的總體結合。合。2. 由集成系統(tǒng)把由集成系統(tǒng)把 DSS和和 ES有機結合起來有機結合起來3. 2.KB和和 MB的結合。的結合。4. 模型庫中的數(shù)學模模型庫中的數(shù)學模型和數(shù)據(jù)處理模型作型和數(shù)據(jù)處理模型作為知識的一種形式，為知識的一種形式，即即 過程性知識過程性知識 ，加入，加入到知識推理過程中到知識推理過程中去。去。5. 3.DB和動態(tài)和動態(tài) DB的結的結合。合。6. DSS中的中的 DB可以可以看成是相對靜態(tài)的數(shù)看成是相對靜態(tài)的數(shù)據(jù)庫，它為據(jù)庫，它為 ES中的動中的動態(tài)數(shù)據(jù)庫提供初始數(shù)態(tài)數(shù)據(jù)庫提供初始數(shù)據(jù)，據(jù)， ES推理結束后，推理結束后，動態(tài)動態(tài) DB中的結果再送中的結果再送回到回到 DSS中的中的 DB中中去。去。 DSS與 ES集成形式一： DSS和 ES并重的 IDSS結 構 集成系統(tǒng)DSS ES 專家系統(tǒng)與決策支持系統(tǒng)集成 集成特點，具有調用和集成 DSS和 ES的能力。 DSS的問題與人機交互系統(tǒng)功能，增加對 ES的調用組合能力DSS與 ES的關系 ：DSS中 DB與 ES中的動態(tài) DB進行數(shù)據(jù)交換解決問題的特點體現(xiàn)定性分析和定量分析并重解決問題的特點。DSS控制系統(tǒng)MBDBESDSS與 ES集成形式二： DSS為主體的 IDSS結構 專家系統(tǒng)與決策支持系統(tǒng)集成 集成特點集成系統(tǒng)和 DSS控制系統(tǒng)合為一體DSS與 ES的關系 ：ES被 DSS控制系統(tǒng)調用解決問題的特點體現(xiàn)以定量分析為主，結果定性分析解決問題的特點。推理機（廣義）DSS動態(tài)DBKB 推理機 MB動態(tài)DBKB圖 DSS作為推理形式的 IDSS 圖 IDSSDSS與 ES集成形式三： ES為主體的 IDSS結構 專家系統(tǒng)與決策支持系統(tǒng)集成 集成特點人機交互系統(tǒng)和 ES合為一體DSS與 ES的關系 ：圖 DSS作為推理機，受 ES的推理機控制；圖 解決問題的特點 體現(xiàn)以定量分析為主，結果定性分析解決問題的特點。 建模專家系統(tǒng) 專家系統(tǒng)實現(xiàn) 模型選擇 的實例進行說明。 例如，彈簧振動建模專家系統(tǒng)。 該專家系統(tǒng)是解決彈簧在不同受力情況下（包括沖力、摩擦力等）應該滿足那種類型的微分方程模型。 彈簧振動建模專家系統(tǒng)進行簡化說明如下： 規(guī)則　、規(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→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 建模專家系統(tǒng) A：彈簧滿足胡克定律B：彈簧質量可以忽略C：可以忽略摩擦力D：沒有沖力A1：彈簧有線性恢復力A11：彈力與位移成正比A12：位移量很小E：要考慮摩擦力F：摩擦力與速度之間為線性關系C1：若振動為自發(fā)時振幅為常數(shù)　E1：若振動為自發(fā)時振幅是遞減的G：有沖力 F（ T）B1：彈簧具有質量 N并且 N/M遠遠小于 1H1：彈簧勢能不是關于平衡位置對稱H：彈簧不潢足胡克定律A2：彈簧勢能與函數(shù) 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對 ｔ 的二階導數(shù)，X′表示一階導數(shù)。各模型微分方程為：各模型微分方程為：3. 規(guī)則庫的推理樹 將 20條規(guī)則連成的推理樹見下圖所示。 每個葉節(jié)點提問的回答為： Y－ yes　， N－ no 專家系統(tǒng)將解釋為證實某條規(guī)則而安排的提問。用戶不明白專家系統(tǒng)為什么要提該問題，可以回答Ｗ－ why建模專家系統(tǒng) A2A1B1C1？ E1？ ？ B1？A11A12？ ？ ？ ？DEFGHIA B C？ ？M（ M1， M2， ， M12）圖 專家系統(tǒng)應用現(xiàn)有一個彈簧，滿足如下特性：H1（彈簧勢能不是關于平衡位置對稱）B1（彈簧具有質量 N并且 N/M遠遠小于 1）C1（若振動為自發(fā)時振幅為常數(shù)）G（有沖力 F（ T））通過專家系統(tǒng)推理將得出： 該彈簧滿足模型 6（ M6）的微分方程。 遺傳算法的決策支持 遺傳算法原理遺傳算法原理 優(yōu)化模型的遺傳算法求解優(yōu)化模型的遺傳算法求解 獲取知識的遺傳算法獲取知識的遺傳算法 遺傳規(guī)劃建立模型遺傳規(guī)劃建立模型遺傳算法原理n 遺傳算法 (GeicAlgorithm， GA)n 是模擬 生物進化 的自然選擇和遺傳機制的一種 尋優(yōu)算法。n 適用于 復雜的非線性 問題 ,主要應用在組合優(yōu)化和機器學習兩個方面。n 應用領域：n 圖像識別、圖像恢復、自適應控制、優(yōu)化調度等領域。n 遺傳算法的發(fā)展過程大體上可分為以下三個階段： n （ 1） 70年代的興起階段。n 1975年美國 Michigan 大學 法的基本理論和方法。 n 在這一時期的大部分研究都處于理論研究和建立實驗模型階段n （ 2） 80年代的發(fā)展階段。n 1980年 Smith教授將遺傳算法應用于機器學習領域，研制出了一個著名的分類器 (Classifier)系統(tǒng)。n 這期間許多學者對遺傳算法進行了大量的改進和發(fā)展，提出了許多成功的遺傳算法模型，使遺傳算法應用于更廣泛的領域。 n （ 3） 90年代的高潮階段。n 進入 90年代后，遺傳算法作為一種實用、高效的優(yōu)化技術，得到了極為迅速的發(fā)展。 遺傳算法原理遺傳算法原理 遺傳算法工作過程 遺傳算法的理論基礎 遺傳算法的基本特征遺傳算法的工作過程n 遺傳算法是一種群體型操作，該操作以群體中的所有個體為對象。n 個體就是模擬生物個體而對問題中的對象（一般就是問題的解）的一種稱呼，一個個體也就是搜索空間中的一個點。n 種群 (population)就是模擬生物種群而由若干個體組成的群體 , 它一般是整個搜索空間的一個很小的子集。n 遺傳算法的三個主要操作算子 ： 選擇 （ selecation）、交叉 （ crossover）和 變異 （ mutation） 構成了遺傳操作（ Geicoperation），使遺傳算法具有了其他傳統(tǒng)方法所沒有的特性。產(chǎn)生新一代群體編碼和初始群體形成輸出種群 個體適應值滿意否？遺傳算法的工作過程n首先將問題的每個可能的解按某種形式編碼，編碼后的解稱作染色體（個體）。n隨機選取 N個染色體構成 初始 種群，再根據(jù) 預定 的 評價函數(shù) 對每個染色體計算適應值，使得性能較好的染色體具有 較高 的適應值。n選擇 適應值高 的染色體進行復制，通過遺傳算子來產(chǎn)生一群新的更適應環(huán)境的染色體，形成新的種群。n這樣一代一代不斷繁殖，最后收斂到一個最適應環(huán)境的個體上，求得問題的最優(yōu)解。遺傳算子選擇交叉變異1.群體中個體的編碼n 如何將問題描述成位串的形式，即問題編碼。一般將問題的參數(shù)用 二進制位 （基因）編碼構成子串，再將 子串 拼接起來構成 “染色體 ”位串。遺傳算法的工作過程例如：例如： 個體個體 染色體染色體 9 1001（（ 2， 5， 6）） 010 101 1102.適應值函數(shù)的確定n 遺傳算法的執(zhí)行過程中，每一代有許多不同的染色體（個體）同時存在，這些染色體中哪個保留 (生存 )、哪個淘汰 (死亡 )是根據(jù)它們對環(huán)境的適應能力決定的，適應性強的有更多的機會保留下來。n 適應性強弱 是計算個體適應值函數(shù) f(x)的值來判別的，這個值稱為適應值 (fitness)。n 適應值函數(shù) (即評價函數(shù) )是根據(jù) 目標函數(shù) 確定的。適應值總是 非 負的，任何情況下總是希望越大越好。如果目標函數(shù)不是取最大值時，需要將它映射成適應值函數(shù)。適應值函數(shù) f(x)的構成與目標函數(shù)有密切關系，往往是目標函數(shù)的變種。n 一般是一個實值函數(shù)。該函數(shù)就是遺傳算法中指導搜索的評價函數(shù)。遺傳算法的工作過程n （一）選擇 (Selection)算子n （二）交叉 (Crossover)算子n （三）變異 (Mutation)算子遺傳算法的工作過程n 它又稱 復制 (reproduction)、繁殖算子。n 選擇是從種群中選擇生命力強的染色體產(chǎn)生 新種群的過程 。依據(jù)每個染色體的適應值大小，適應值越大，被選中的概率就越大，其子孫在下一代產(chǎn)生的個數(shù)就越多。n 選擇操作是建立在群體中個體的 適應值估評基礎 上的。遺傳算法的工作過程（一）選擇（一）選擇 (Selection)算子算子通常做法是：對于一個規(guī)模為 N的種群 S,按每個染色體 xi∈ S的選擇概率 P(xi)所決定的選中機會 ,分 N次從 S中隨機選定 N個染色體 ,并進行復制。遺傳算法的工作過程這里的選擇概率 P(xi)的計算公式為（一）選擇（一）選擇 (Selection)算子算子（二）交叉（二）交叉 (crossover)算子算子n 它又稱 重組 (rebination)、配對 (breeding)算子， 在遺傳算法中起著核心作用。n 染色體重組是分兩步驟進行的 :n 首先在新復制的群體中隨機選取 兩個 個體n 然后，沿著這兩個個體 (字符串 )隨機地取一個位置，二者互換從該位置起的末尾部分。n 交叉率 (crossover rate)就是 參加 交叉運算的染色體個數(shù)占 全體 染色體總數(shù)的比例，記為 Pc,取值范圍一般為 ～ 。遺傳算法的工作過程遺傳算法的工作過程例 1:有兩個用二