【正文】 ,ki1)，則表示屬性 ci的所有分割點的串長為 l(i)(ki1)，分割點 cij與長度為 l(i)的二進制編碼之間的值對應(yīng)關(guān)系可由下式確定： 式中 m(s)是長度為 l(i)的二進制編碼中第 s位的編碼值。 si為連續(xù)屬性 ci的起點值， ei為其終點值 )(122)()()(11iiililssiji sesmsc ???????2022年 5月 27日 9時 39分 決策理論與方法 智能決策理論與方法 機器學習 — 遺傳算法 對 C’中的所有屬性進行編碼形成的二進制串長度為： 因此，連續(xù)屬性集離散化問題的搜索空間規(guī)模為 2l。 l(i)的選擇與樣本的規(guī)模有關(guān)。 例如，若樣本規(guī)模為 200，連續(xù)屬性集 C’={c1,c2,c3}，k1=k2=4， k3=3。選擇 l(1)=l(2)=l(3)=5，則l=5 3+5 3+5 2=40，問題的搜索空間規(guī)模為 240≈1012 00110 10010 11011 01100 10101 11101 00111 10011表示了分割點集的一條染色體。 ????miikill1)1)((2022年 5月 27日 9時 39分 決策理論與方法 智能決策理論與方法 機器學習 — 遺傳算法 ? 適應(yīng)度函數(shù) ： 體現(xiàn)決策目標的優(yōu)化方向 。從粗糙集理論的角度，離散化往往會破壞信息系統(tǒng)中原來的不可分辨關(guān)系，即原來兩個可分辨的對象可能變?yōu)椴豢煞直妫@樣等價類包含的對象數(shù)量增加，而等價類數(shù)量減少，分類能力可能減弱。因此使離散化后系統(tǒng)的分類能力最大是我們的優(yōu)化目標，因此可用決策屬性 d對 C’的依賴度作為適應(yīng)度函數(shù)： )())((),( / UC a rdXCC a rddCk dUX???? ???2022年 5月 27日 9時 39分 決策理論與方法 智能決策理論與方法 機器學習 — 遺傳算法 ? 復制算子 。把當前群體中的個體按與適應(yīng)值成比例的概率復制到新的群體中，復制過程應(yīng)用賭盤技術(shù)選擇要被復制的串。 復制算子的作用效果將提高群體的平均適應(yīng)值 。 ? 設(shè)種群數(shù)為 N，則將賭盤分成 N份，第 i份的比例按如下值確定： ????? NiiiidCdCN1),(),(??2022年 5月 27日 9時 39分 決策理論與方法 智能決策理論與方法 機器學習 — 遺傳算法 s4 s2 s1 2022年 5月 27日 9時 39分 決策理論與方法 智能決策理論與方法 機器學習 — 遺傳算法 ? 交叉算子 ：按一定的概率從交配池中任選 2條染色體進行多點雜交 (隨機互換兩個染色體某些位上的基因 )。方法如下：挑選 2個染色體串，按概率確定它們是否發(fā)生雜交，若未發(fā)生雜交，另取 2個染色體串，否則，先產(chǎn)生 m個隨機數(shù) r(i)(ci?C’)，隨機數(shù)的范圍為 1到 l(i)(ki1)1，然后配對的 2個串相互對應(yīng)地交換從 到 的位段。 1)()1)((11??????irkjlijj)1)(()1)((11??????iijj kilkjl2022年 5月 27日 9時 39分 決策理論與方法 智能決策理論與方法 機器學習 — 遺傳算法 例： 設(shè)染色體 s1= 00110 10010 11011 01100 10101 11101 00111 10011 s2= 10110 10100 01011 01101 00101 10101 10001 10101 按箭頭所指進行交叉，得到兩條新的染色體。 s1’= 00110 01011 11011 01100 01101 11101 10101 10011 s2’= 10110 10100 10010 10101 00101 10101 10001 00111 2022年 5月 27日 9時 39分 決策理論與方法 智能決策理論與方法 機器學習 — 遺傳算法 ? 變異算子 ：以一個很小的概率隨機改變某條染色體中的某些基因位，形成新的種群，改變種群結(jié)構(gòu)。方法如下：挑選 1條染色體串，按概率確定它們是否發(fā)生變異，若未發(fā)生變異，另取 1條染色體串，否則，先產(chǎn)生 m個隨機數(shù)r(i)(ci?C’)，隨機數(shù)的范圍為 1到 l(i)(ki1)，然后對該串的第 位進行改變。 )()1)((11irkjlijj ?????2022年 5月 27日 9時 39分 決策理論與方法 智能決策理論與方法 機器學習 — 遺傳算法 例： 設(shè)染色體 s1= 00110 10010 11011 01100 10101 11101 00111 10011 按下劃線所指進行變異操作，得到一條新的染色體。 s1’= 00110 10110 11011 01000 10101 11101 00110 10011 ? 基于 GA算法的離散化算例 ： ? 問題與參數(shù) ：一個含有連續(xù)屬性集 C’={c1,c2,c3}和一個決策屬性 d的決策表，各項參數(shù)確定為： k1=k2=3， k3=4，l(3)=5 ， l(1)=l(2)=4， N=40， Pc=， Pm=；停機條件是 M=50或分類能力 ?(C’,d)?。 2022年 5月 27日 9時 39分 決策理論與方法 智能決策理論與方法 機器學習 — 遺傳算法 ? 原始數(shù)據(jù) ? 分割點 c1 c2 c3 d c1 c2 c3 d 19 119 1 270 2 26 120 1 202 1 93 15 1 199 2 186 1 11 120 2 101 2 121 1 150 1 266 1 58 1 141 1 65 1 214 1 172 1 1c231c屬性 (區(qū)間 ) c1() c2(58270) c3() 分割點 c11 c12 c21 c22 c31 c32 c33 分割點基因 0010 0100 0011 1101 00011 00110 01110 分割點坐標 2022年 5月 27日 9時 39分 決策理論與方法 智能決策理論與方法 機器學習 — 遺傳算法 ? 離散化結(jié)果 c1 c2 c3 d c1 c2 c3 d 2 1 1 1 2 2 3 2 2 1 2 1 2 1 3 1 2 0 0 1 0 1 0 2 2 1 3 1 1 1 0 2 2 1 1 2 2 1 1 1 1 1 1 1 2 2 3 1 1 0 0 1 1 1 1 1 2 0 0 1 2 1 3 1 2 1 3 1 2022年 5月 27日 9時 39分 決策理論與方法 智能決策理論與方法 機器學習 — 遺傳算法 ? Matlab(Geic Algrithm amp。 Direct Search Toolbox)提供了一個函數(shù) ga()，可直接求解某個函數(shù)的極小值；另外還提供了一個遺傳算法工具gatool。