第四章智能技術的決策支持和智能決策支持系統詳解演示文稿

第四章智能技術的決策支持和智能決策支持系統詳解演示文稿現在是1頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊優(yōu)選第四章智能技術的決策支持和智能決策支持系統現在是2頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊4.4神經網絡的決策支持神經元的結構現在是3頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊神經元由細胞體、樹突和軸突三部分組成；細胞體對接收到的信息進行處理；軸突是較長的神經纖維，是發(fā)出信息的；樹突的神經纖維較短，是接收信息的；一個神經元的軸突末端，與另一個神經元的樹突之間密切接觸，傳遞神經元沖動的地方稱為突觸。4.4神經網絡的決策支持現在是4頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊神經元具有如下性質：（1）多輸入單輸出；（2）突觸具有加權的效果；（3）信息進行傳遞；（4）信息加工是非線性。4.4神經網絡的決策支持現在是5頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊1、神經元的數學模型

其中：V1、V2、…Vn為輸入，Ｕi為該神經元的輸出，Ｔij為外面神經元與該神經元連接強度（即權值）,為閾值，f(X)為該神經元的作用函數。4.4神經網絡的決策支持現在是6頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊MP（神經元的數學模型）模型方程為：

其中Wij是神經元之間的連接強度，Wii＝0，Wij（i≠j）是可調實數，由學習過程來調整。

現在是7頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊2、神經元作用函數[0,1]階梯函數:

[-1,1]階梯函數：現在是8頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊神經元作用函數

(-1,1)S型函數：

(0,1)S型函數：現在是9頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊3、學習規(guī)則神經元的學習規(guī)則是Hebb規(guī)則。

Hebb學習規(guī)則：若i與j兩種神經元之間同時處于興奮狀態(tài)，則它們間的連接應加強，即：△Wij＝SiSj(＞0) 這一規(guī)則與“條件反射”學說一致，并得到神經細胞學說的證實。設α＝1，當Si＝Sj＝1時，△Wij＝1，在Si，Sj中有一個為0時，△Wij＝0?，F在是10頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊4.4.2反向傳播模型(BP模型)BP模型（Backpropagation），需要確定它的網絡結構、作用函數和誤差函數。1.多層網絡結構:有輸入層、輸出層，一個或多個隱含層現在是11頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊

2.作用函數為(0,1)S型函數

3.誤差函數對第p個樣本誤差計算公式為：

其中ｔpi，Opi分別是期望輸出與計算輸出。4.4.2反向傳播模型(BP模型)現在是12頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊

公式推導思想是：修正網絡權值與閾值，使誤差函數沿梯度方向下降。BP網絡表示：輸入結點xj，隱結點yi，輸出結點Ol，輸入結點與隱結點間的網絡權值為Wij，隱結點與輸出結點間的網絡權值為Tli，輸出結點的期望輸出為tl。4.4.2反向傳播模型(BP模型)現在是13頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊2.輸出結點計算輸出：其中：其中：BP模型的計算公式為：4.4.2反向傳播模型(BP模型)1.隱結點的輸出：現在是14頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊3.輸出結點的誤差公式：4.4.2反向傳播模型(BP模型)現在是15頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊1.輸出結點輸出Ol計算公式（1）輸入結點的輸入xj（2）隱結點的輸出：其中：Wij連接權值，結點閾值。

(3)輸出結點輸出：其中：Tij連接權值，結點閾值。2輸出層（隱結點到輸出結點間）的修正公式（1）輸出結點的期望輸出tl（2）誤差控制所有樣本誤差：BP模型計算公式匯總現在是16頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊其中一個樣本誤差：其中，p為樣本數，n為輸出結點數。（3）誤差公式： （4）權值修正：

其中k為迭代次數。

（5）閾值修正：

BP模型計算公式匯總現在是17頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊3、隱結點層（輸入結點到隱結點間）的修正公式（1）誤差公式：（2）權值修正：（3）閾值修正：BP模型計算公式匯總現在是18頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊

誤差反向傳播示意圖隱結點誤差的含義：現在是19頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊··

求

l(2)

i(1)Ol=f（－l）yi=f（－i）l(k+1)=l(k)+l(2)

j·

修正（Tli，l），（Wij，i）修正權

l(2)=Ol(1－Ol)(dl－Ol)Til(k+1)=Til(k)＋l(2)yi

i(1)=

yi(1－yi)Wij(k+1)=Wij(k)＋i(1)xj輸出節(jié)點lTli

隱節(jié)點

i修正權Wij輸入節(jié)點xji(k+1)=i(k)+i(1)現在是20頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊按問題要求，設置輸入結點為兩個（x1,x2），輸出結點為1個（z），隱結點定為2個（y1，y2），各結點閾值和網絡權值見圖說明。異或問題求解實例現在是21頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊計算機計算結果迭代次數：16745次；總誤差：0.05隱層網絡權值和閾值：w11=5.24w12=5.231=8.01w21=6.68w22=6.642=2.98

輸出層網絡權值和閾值： T1=-10T2=10=4.79 異或問題求解實例現在是22頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊一、神經網絡專家系統特點1.神經元網絡知識庫：為神經元之間的連接強度（權值）。這種知識是分布式存儲的，適合并行處理。2.推理機：是基于神經元的信息處理過程。它是以ＭP模型為基礎的，采用數值計算方法。4.4.3神經網絡專家系統及實例現在是23頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊3.成熟的學習算法：感知機采用delta規(guī)則；BP模型采用誤差沿梯度方向下降、以及隱節(jié)點的誤差由輸出結點誤差反向傳播的思想進行的。４.容錯性好：由于信息是分布式存貯，在個別單元上即使出錯或丟失，所有單元的總體計算結果，可能并不改變。4.4.3神經網絡專家系統及實例現在是24頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊二、神經網絡專家系統結構用戶知識工程師

學習樣本

確定系統框架

神經元學習

形成學習樣本

知識庫（分布式）實際問題參數輸入模式轉換

推理機制輸出模式轉換實際問題結果開發(fā)環(huán)境運行環(huán)境現在是25頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊（一）確定系統框架1.完成對神經元網絡的拓樸結構設計：（1）神經元個數（2）神經元網絡層次（3）網絡單元的連接

2.確定神經元的作用函數和閾值作用函數用得較多的有兩種：（1）階梯函數（2）S型函數閾值的選取可為定值如i=0或i=0.5，或者進行迭代計算。現在是26頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊（二）學習樣本學習（訓練）樣本：實際問題中已有結果的實例。（三）學習算法不同的網絡模型采用不同的學習算法，但都以Hebb規(guī)則為基礎。1.Perception(感知機)模型：采用delta規(guī)則。2.Back-propagation(反向傳播)模型：采用誤差反向傳播方法?，F在是27頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊（四）推理機

推理機是基于神經元的信息處理過程。

1.神經元j的輸入：其中，Wjk為神經元j和下層神經元k之間的連接權值。Ok為k神經元的輸出。2.神經元j的輸出:Oj=f(Ij-j)

j為閾值，f為神經元作用函數。現在是28頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊

（五）知識庫知識庫主要是存放各個神經元之間連接權值。由于上下兩層間各神經元都有關系，用數組表示為(Wij)i行對應上層結點，j列對應下層結點?，F在是29頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊（六）輸入模式轉換實際問題的輸入，一般是以一種概念形式表示，而神經元的輸入，要求以(-∞,∞)間的數值形式表示，因此需要將文字概念轉換成數值。建立兩個向量集：（1）實際輸入概念集：各輸入節(jié)點的具體物理意義。（2）神經元輸入數值集：各輸入節(jié)點的數值?，F在是30頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊（七）輸出模式轉換實際問題的輸出，一般也是以一種概念形式表示。而神經元的輸出，一般是在[0,1]間的數值形式，這需要將數值向文字概念的轉換?，F在是31頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊城市醫(yī)療服務能力評價系統。5個輸入：病床數、醫(yī)生數、醫(yī)務人員數、門診數和死亡率；4個輸出：級別v、g、a和b；建立一個三層神經元網絡。訓練樣本（集）:10城市的數據,訓練后可對其它城市進行評價。輸入輸出模式轉換：文字概念的數值轉換。輸入節(jié)點數據范圍范圍(-∞,∞)，輸出數據范圍[0,1]。輸入節(jié)點：五個節(jié)點分別表示五個指標，每個指標節(jié)點都有v,g,a,b四種可能。三、神經網絡專家系統實例現在是32頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊城市醫(yī)療服務能力評價系統神經網絡結構圖現在是33頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊城市醫(yī)療服務能力訓練集現在是34頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊文字概念的數值轉換的五方案：方案1：v=3g=1 a=-1b=-3方案2：v=1.5g=0.5 a=-0.5b=-1.5方案3：v=6g=2 a=-2b=-6方案4：v=1g=0.66a=0.33b=0方案5：v=10g=7 a=4 b=1計算結果表明，方案2收斂最快Count=360，計算結果也很合理，其次是方案1，Count=451，方案3,4,5均較差。結論：盡量采用(-1,1)附近較合適?，F在是35頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊

4種動物樣本：（1）某動物是暗斑點、黃褐色、有毛發(fā)、吃肉，它就是豹。（2）某動物是黃褐色、有毛發(fā)、吃肉、黑條紋，它就是虎。（3）某動物是不飛、黑白色、會游泳、有羽毛，它就是企鵝。（4）某動物是有羽毛、善飛，它就是信天翁。4.4.4神經元網絡的容錯性現在是36頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊現在是37頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊訓練完成后，對樣本進行缺省條件輸入。（1）缺1個條件的情況（2）缺2個條件的情況（3）介于中間的情況缺省條件推理結果表現在是38頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊

從計算結果中，可以看出容錯效果很好，缺1個條件時：例如對豹缺省黃褐色條件時，輸出結果仍然是豹（0.8463）；缺2個條件時：對虎缺省黃褐色和多一個不飛的條件時，輸出結果仍然是虎（0.9286）；輸入豹和虎的共同信息（黃褐色、有毛發(fā)、吃肉）時，神經網絡的輸出是既靠近豹（0.3394）又靠近虎（0.4203），輸出結論：該動物是一個介于豹和虎的中間新品種?，F在是39頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊4.5、遺傳算法的決策支持

遺傳算法(GeneticAlgorithm，GA)是模擬生物進化的自然選擇和遺傳機制的一種尋優(yōu)算法。（1）模擬生物的繁殖和變異現象；（2）從任意一初始種群出發(fā)，產生一群新的更適應環(huán)境的后代。（3）不斷繁殖、進化，最后收斂到一個最優(yōu)個體上。

優(yōu)點：對復雜的優(yōu)化問題無需建模和復雜運算，只需利用遺傳算法的算子，即可求得問題的最優(yōu)解或滿意解?，F在是40頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊遺傳算法發(fā)展的三個階段（1）70年代的興起階段1975年美國Michigan大學J.Holland首次系統地闡述了遺傳算法的基本理論和方法。在這一時期的大部分研究都處于理論研究和建立實驗模型階段。（2）80年代的發(fā)展階段1980年Smith教授將遺傳算法應用于機器學習領域，研制出了一個著名的分類器(Classifier)系統。這期間許多學者對遺傳算法進行了大量的改進和發(fā)展，提出了許多成功的遺傳算法模型，使遺傳算法應用于更廣泛的領域。（3）90年代的高潮階段進入90年代后，遺傳算法作為一種實用、高效、魯棒性強的優(yōu)化技術，得到了極為迅速的發(fā)展。現在是41頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊一、遺傳算法的工作過程

遺傳算法是一種群體型操作，該操作以群體中的所有個體為對象。選擇（selection）、交叉（crossover）和變異（mutation）是遺傳算法的三個主要操作算子，它們構成了遺傳操作（Geneticoperation），使遺傳算法具有了其他傳統方法所沒有的特性。

遺傳算法的工作過程如圖所示：4.5遺傳算法原理現在是42頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊遺傳算法的工作過程遺傳算子編碼和初始群體形成輸出種群選擇個體適應值滿意否？交叉產生新一代群體變異NY現在是43頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊1.群體中個體的編碼如何將問題描述成位串的形式，即問題編碼。一般將問題的參數用二進制位（基因）編碼構成子串，再將子串拼接起來構成“染色體”位串。2.適應值函數的確定

適應值函數(即評價函數)是根據目標函數確定的。適應值總是非負的，任何情況下總是希望越大越好。如果目標函數不是取最大值時，需要將它映射成適應值函數。現在是44頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊

遺傳算法的執(zhí)行過程中，每一代有許多不同的染色體（個體）同時存在，這些染色體中哪個保留(生存)、哪個淘汰(死亡)是根據它們對環(huán)境的適應能力決定的，適應性強的有更多的機會保留下來。適應性強弱是計算個體適應值函數f(x)的值來判別的，這個值稱為適應值(fitness)。適應值函數f(x)的構成與目標函數有密切關系，往往是目標函數的變種。3遺傳算法的三個算子現在是45頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊（一）選擇(Selection)算子

它又稱復制(reproduction)、繁殖算子。

選擇是從種群中選擇生命力強的染色體產生新種群的過程。依據每個染色體的適應值大小，適應值越大，被選中的概率就越大，其子孫在下一代產生的個數就越多。

選擇操作是建立在群體中個體的適應值估評基礎上的，目前常用的選擇算子有以下幾種：

重組(recombination)、配對(breeding)算子?，F在是46頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊

染色體重組分兩步（1）首先在新復制的群體中隨機選取兩個個體；（2）沿著這兩個個體(字符串)隨機取一個位置，二者互換從該位置起的末尾部分。如有兩個用二進制編碼的個體A和B。長度L=5，A=a1a2a3a4a5，B=b1b2b3b4b5隨機選擇一整數k∈[1，L-1]，設k=4，經交叉后變?yōu)椋?/p>

A=a1a2a3|a4a5A’=a1a2a3b4b5 B=b1b2b3|b4b5B’=b1b2b3a4a5交叉算子在遺傳算法中起著核心作用。

現在是47頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊

選擇和交叉算子基本上完成了遺傳算法的大部分搜索功能，而變異則增加了遺傳算法找到接近最優(yōu)解的能力。變異就是以很小的概率，隨機地改變字符串某個位置上的值。變異操作是按位（bit）進行的，即把某一位的內容進行變異。在二進制編碼中，就是將某位0變成1，1變成0。變異發(fā)生的概率即變異概率Pm都取得很小(一般在0.001～0.02之間)，它保證了遺傳算法的有效性。

現在是48頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊控制參數的設定遺傳算法中的參數包括：群體中個體的數目、交叉概率、變異概率等。這些參數的設定隨具體問題的不同將有所差別，帶有經驗性，它會影響遺傳算法的迭代收斂過程?，F在是49頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊遺傳算法的理論基礎1.模式定理遺傳算法的理論基礎是Holland提出的模式定理。一個模式(Schema)就是一個描述種群中在位串的某些確定位置上具有相似性的位串子集的相似性模板(SimilarityTemplate)。模式定理是遺傳算法的理論基礎，它說明高適應值、長度短、階數低的模式在后代中至少以指數增長包含該模式H的位串的數目。原因在于遺傳使高適應值的模式復制更多的后代?，F在是50頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊遺傳算法的理論基礎2．基因塊假設

高適應值、長度短、低階的模式叫基因塊。長度短的、低階的、高適應值的模式(基因塊)通過遺傳操作繁殖、交換、變異，再繁殖、再交換、再變異的逐漸進化，形成潛在的適應性較高的位串，這就是基因塊假說。

該假設指出，通過遺傳算法能尋找到接近全局最優(yōu)解的能力?，F在是51頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊1.遺傳算法的處理對象是問題參數的編碼個體（位串）遺傳算法要求將問題的參數編碼成長度有限的位串。遺傳算法是在求解問題的編碼串上進行操作，從中找出高適應值的位串，而不是對問題目標函數和它們的參數直接操作。遺傳算法不受函數限制條件(如導數存在、連續(xù)性、單極值等)的約束。遺傳算法的基本特征

現在是52頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊2.遺傳算法的搜索是從問題解位串集開始搜索，而不是從單個解開始在最優(yōu)化問題中，傳統的方法是從一個點開始搜索，如爬山法。一般復雜問題會在“地形”中出現若干“山峰”，傳統的方法很容易走入假“山峰”。而遺傳算法同時從種群的每個個體開始搜索，象一張網罩在“地形”上，數量極大的個體同時在很多區(qū)域中進行搜索，這樣就減少了陷入局部解的可能性?，F在是53頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊3.遺傳算法只使用目標函數(即適應值)來搜索，而不需要導數等其他輔助信息。傳統搜索算法需要一些輔助信息，如梯度算法需要導數，當這些信息不存在時，這些算法就失效了。而遺傳算法只需目標函數和編碼串，因此，遺傳算法幾乎可以處理任何問題?，F在是54頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊4.遺傳算法使用的三種遺傳算子是一種隨機操作，而不是確定性規(guī)則遺傳算法使用隨機操作，但并不意味著遺傳算法是簡單的隨機搜索。遺傳算法是使用隨機工具來指導搜索向著一個最優(yōu)解前進?，F在是55頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊4.5.2優(yōu)化模型的遺傳算法求解

優(yōu)化模型的計算是遺傳算法最基本的也是最重要的研究和應用領域之一。一般說來，優(yōu)化計算問題通常帶有大量的局部極值點，往往是不可微的、不連續(xù)的、多維的、有約束條件的、高度非線性的問題。

精確地求解優(yōu)化問題的全局最優(yōu)解一般是不可能的?，F在是56頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊1、適應值函數

遺傳算法在進化搜索中用目標函數即適應值函數為依據。遺傳算法的目標原函數不受連續(xù)可微的約束,且定義域可以為任意集合。對目標函數的唯一要求是，對輸入個體可計算出能進行比較的非負適應值。這一特點使得遺傳算法應用范圍很廣。適應值函數評估是選擇操作的依據，適應值函數設計直接影響到遺傳算法的性能。

現在是57頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊遺傳算法中，適應值函數要比較排序并在此基礎上計算選擇概率，所以適應值函數的值要取正值。將目標函數映射成求最大值形式且函數值非負的適應值函數是必要的?，F在是58頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊2、約束條件的處理

遺傳算法是由適應值來評估和引導搜索，而對求解問題的約束條件不能明確地表示出來。用遺傳算法求解這些帶約束的問題，需要進行一些處理。在等式約束方程中，對P個等式方程中抽出P個變量，經過線性組合變換后，用其余變量表示為該P個變量的等式，并將它代入目標函數中，消去該P個變量。這樣，在目標函數中，就包含了這些等式約束條件?，F在是59頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊3、遺傳算法的迭代終止條件當適應值函數的最大值已知時，一般以發(fā)現滿足最大值或準最優(yōu)解作為遺傳算法迭代終止條件。但是，在許多優(yōu)化計算問題中，適應值函數的最大值并不清楚，迭代終止條件一般定為：群體中個體的進化已趨于穩(wěn)定狀態(tài)，即發(fā)現占群體中一定比例的個體已完全是同一個體?，F在是60頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊旅行商問題（TSP）的遺傳算法求解實例

已知n個城市的地理位置（x,y），求經過所有城市，并回到出發(fā)城市且每個城市僅經過一次的最短距離。其計算量為城市個數的指數量級?，F用遺傳算法來解決這個問題。

現在是61頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊1、編碼

每條路徑對應一個個體，個體形式地表示為R={City_No|City_No互不重復}n，n為城市數。例如對于n=10的TSP問題，對其中一個個體

它表示一條城市路徑：3 1 5 7 8 910 4 2 631578910426現在是62頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊2、適應值函數

每個個體代表一條可能的路徑。個體n的適應值為：其中N為種群數，Dn為

沿個體標示的城市序列的所經過的距離：其中ni表示個體中第i位的城市編號，n11=n1。適應值為非負，且取值越大越好。表示所有個體的路徑長度的總和現在是63頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊3、交叉

隨機地從種群中選出要交叉的兩個不同個體，隨機地選取一個交叉段。交叉段中兩個個體的對應部分通過匹配換位實現交叉操作。對個體A和B：

A＝984

|567|

13210

B＝871

|4103|

2965交叉段

對個體A，對交叉段中由B換位來的數，如4、10、3，在A中其它位相同的數進行反交換，即4換為5，10換為6，3換為7；對個體B，相似處理，最后得到：

A，＝98

5

|4103|

1

7

2

6

B，＝8

3

1

|567|

29

104現在是64頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊4、變異

根據變異概率Pe，隨機地從種群中選出要變異的個體，隨機地在該個體上選出變異兩個位置，然后兩個位置上的城市序號進行交換。如：

A=9

8

456

7

13210下劃線部分為要變異的兩個位置。變異為：

A`=9

7

456

8

13210計算結果表明：n個城市的最佳路徑接近一個外圈無交叉的環(huán)路?，F在是65頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊4.5.3獲取知識的遺傳算法1980年，Smith采用遺傳算法研制了一種分類器系統，這是遺傳算法在機器學習中的重要應用系統。他使用單個字符串來表示一條規(guī)則。分類器系統的規(guī)則形式如下：IF<condition>THEN<action>意思是當條件（condition）滿足時，就可能采取行動（action）。分類器系統的規(guī)則采用固定長度表示。這便于遺傳算子的處理。現在是66頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊一、分類學習系統的結構檢測器消息表遺傳算法分類器信任分配算法測試表作用器客觀環(huán)境現在是67頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊客觀環(huán)境信息通過分類器系統的檢測器（Detector）被編碼成有限長的消息（Messages）然后發(fā)往消息表；消息表中的消息觸發(fā)位串規(guī)則（稱為分類器），被觸發(fā)的分類器又向消息表發(fā)消息，這些消息又有可能觸發(fā)其它的分類器或引發(fā)一個行動。通過執(zhí)行機構（作用器Effector）作用于客觀環(huán)境。現在是68頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊1.檢測器（Detector）一條消息Mi是一個二元組，其形式如下：Mi=[xi,yi]其中：i為消息號；x為條件部分，即訓練例子的各特征編碼，y為結論部分，即訓練例子的類別。例如：[(10001011),(1011)]是一條由一個8位條件和4位結論組成的消息。2.消息表（MessageList）包含當前所有的消息（訓練例子集）。現在是69頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊3.分類器（Classifier）所獲得的規(guī)則中包含通配符#，如：1##0，1110是一致的。規(guī)則集越小，系統的時間性能當然越好。一個規(guī)則Ci是一個三元組，形式如下：Ci=[Ui,Vi,fitnessi]其中，Ui是條件部分，，#表示通配符；Vi是結論部分。fitnessi是規(guī)則i的適應值，它又是一個二元組，其形式如下：fitnessi=[fit1,fit2]分別表示在該規(guī)則覆蓋的范圍內，與規(guī)則結論一致和不一致的消息個數。現在是70頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊4.測試表（TestList）一個測試例子Ti也是一個同消息形式一樣的二元組，只是它的結論部分，yi表示未確定。當執(zhí)行完精練分類器規(guī)則后，其結論部分yi就被賦值成與消息Mi完全一樣形式，即，變成一條新的消息。5.作用器（Effector）將測試的判別結果轉換成具體問題的真實的輸出值，并作用于環(huán)境?，F在是71頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊二、分類學習系統的主要算法1.信任分配算法：將規(guī)則與消息表中的消息逐個匹配，根據匹配結果修改規(guī)則的適應值。步驟如下：（1）初始化規(guī)則的適應值，即：fit10，fit20。（2）從消息表[M]中取出一條消息，與工作分類器[WC]中的規(guī)則逐個進行比較。（3）IF 條件和結論均匹配，THEN fit1fit1+1；（4）IF 條件匹配，結論不匹配，THENfit2fit2+1；（5）IF 條件不匹配，THENfitnessfitness。返回步驟（2），直到[M]中的消息全部取完?，F在是72頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊2.遺傳算法（GeneticAlgorithms）對同一結論的規(guī)則，只允許其條件部分進化。如規(guī)則的條件和結論同時進化，則可能引起種群不收斂。遺傳算法的主要步驟如下：（1）根據分類器（規(guī)則）的適應值的大小，從中選出幾對分類器。分類器實力越大，被選中的概率越大。（2）對選出的分類器利用GA中的遺傳算子，產生其“后代”。（3）用產生的“后代”取代分類器中適應值小者?，F在是73頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊三、遺傳分類器學習系統GCLS及其應用應用實例：學習識別腦出血和腦血栓兩種疾病的診斷規(guī)則，此問題實際上是從大量已知患者病例（訓練例子集）中找到這兩類病的識別規(guī)則。實際上只有兩種類別：A.腦出血；B.腦血栓為了作出判斷，應當考慮如下幾個方面的特征（屬性）；（1）病人的既往史，包括a.高血壓（有01，無00）；b.動脈硬化（有01，無00）；（2）起病方式（快01，慢00）；現在是74頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊（3）局部癥狀，包括：a.偏癱（是01，否00）；b.瞳孔不等大（是01，否00）；c.兩便失禁（是01，否00）；d.語言障礙（是01，否00）；f.意識障礙（無00，深度01，輕度10）；（4）病理反射（陽01，陰00）；（5）膝腱反射（無00，活躍01，不活躍10）；（6）病情發(fā)展（快01，慢00）；上面是從六個方面12個特征來識別診斷患者到底得的是腦出血還是腦血栓?，F在是75頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊獲取知識從二百多個腦出血和腦血栓病人的病例中，選出30個病例作為訓練樣本，100個作為測試樣本。本實例采用二進制編碼方式。每個訓練例子是由12個特征和1個類別組成，每個特征和類別都由2位二進制字符表示。那么，將例子編碼成二進制字符串的消息訓練集是由15個腦出血和15個腦血栓患者組成30個訓練樣本。本實驗在對30個訓練樣本進行學習后，得到12個規(guī)則，學習終止于第170代?，F在是76頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊獲取的主要規(guī)則如下：（1）高血壓=有瞳孔不等大=是膝腱反射=不活躍 腦出血（11）（2）瞳孔不等大=是語言障礙=是 腦出血（12）（3）高血壓=有起病方式=快意識障礙=深度 腦出血（13）（4）高血壓=有病情發(fā)展=快 腦出血（15）（5）高血壓=有動脈硬化=有起病方式=慢 腦血栓（13）（6）動脈硬化=有病情發(fā)展=慢 腦血栓（15）（7）動脈硬化=有意識障礙=無 腦血栓（12）以上括號內的數值表示該規(guī)則的適應值。現在是77頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊經驗總結在GCLS系統中，幾個主要的控制參數有：（1）環(huán)境消息(訓練例子)的長度：length（2）初始化工作分類器時，隨機產生的規(guī)則數目：n（3）遺傳算法中的交叉概率：Pc（4）遺傳算法中的變異概率：Pm（5）判斷工作種群收斂與否的參數：M現在是78頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊GCLS的幾個控制參數現在是79頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊在我們所做的腦出血與腦血栓疾病的識別診斷實例中，根據兩位腦血管專家的提議，認為：訓練集的正確率TR%達到95%以上，測試集的正確率TE%達到70%以上，則可表明GCLS系統對于輔助醫(yī)生臨床診斷是成功的。我們選取了不同的模型，即上表所示?，F在是80頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊樣本集的大小(samplesize)。樣本集包括訓練集和測試集，當樣本選取50和25個時系統性能不太好。我們選取樣本數為100時，全部模型均能達到要求?，F在是81頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊（2）消息長度(即規(guī)則的長度)(length)。消息的長度是由每個特征的取值范圍來確定的。計算表明，消息長度越長，其系統性能越好。但隨著消息長度的增加，系統的執(zhí)行時間也隨之增加。我們也發(fā)現，消息長度等于39bits的系統性能比消息長度等于26bits的僅稍好一些，我們認為消息長度選取26bits就足以保證系統性能達到一個較好的水準?，F在是82頁\一共有93頁\編輯于星期四4/18/2023信息分析與決策支持唐晶磊（3）初始化工作分類器時隨機產生的種群數目(n)。初始工作分類器中種群的數目影響著遺傳算法的有效性。n太小，遺傳算法會很差或根本找不出問題的解，因為太小的種群數目不能提高足夠的采樣點；n太大，會增加計算量，使收斂時間增長。一般種群數目在50到300之間比較合適。通過各種方案計算表明，訓練集和測試集的識別正確率，都隨著分類器數目的增加而有所提高。如：對于Pc=0.8，n=200比n=150的測試識別率提高了20%；當Pc、Pm取不同的值時，也會得到相似的結論。