【文章內(nèi)容簡介】 前代或最近幾代群體中的最大目標(biāo)函數(shù)值。 2021/6/15 50 比例選擇算子 選擇算子或復(fù)制算子的作用是從當(dāng)前代群體中選擇出一些比較優(yōu)良的個體 ， 并將其復(fù)制到下一代群體中 。 最常用和最基本的選擇算子是比例選擇算子 。 比例選擇實際上是一種有退還隨機選擇 ， 也叫做賭盤 (Roulette wheel)選擇 ， 因為這種選擇方式與賭博中的賭盤操作原理頗為相似 。 所謂比例選擇算了，是指個體被選中并遺傳到下一代群體中的概率與該個體的適應(yīng)度大小成正比。 2021/6/15 51 如圖所示為一賭盤示意圖。 整個賭盤被分為大小不同的一些扇面，分別對應(yīng)著價值各不相同的一些賭博物品。當(dāng)旋轉(zhuǎn)著的賭盤自然停下來時，其指針?biāo)干让嫔系奈锲肪蜌w賭博者所有。 雖然賭盤的指針具體停止在哪一個扇面是無法預(yù)測的 ， 但指針指向各個扇面的概率卻是可以估計的 ， 它與各個扇面的圓心角大小成正比：圓心角越大 ， 停在該扇面的可能性也越大；圓心角越小 ，停在該扇面的可能性也越小 。 與此類似 ， 在遺傳算法中 ， 整個群體被各個個體所分割 ， 各個個體的適應(yīng)度在全部個體的適應(yīng)度之和中所占比例也大小不一 ，這個比例值瓜分了整個賭盤盤面 ， 它們也決定了各個個體被遺傳到下一代群體中的概率 。 2021/6/15 52 金 銀 銅 鐵 10％ 20％ 30％ 40％ 2021/6/15 53 比例選擇算子的具體執(zhí)行過程是： (1)先計算出群體中所有個體的適應(yīng)度的總和 。 (2)其次計算出每個個體的相對適應(yīng)度的大小 ， 它即為各個個體被遺傳到下一代群體中的概率 。 (3)最后再使用模擬賭盤操作 (即 0到 1之間的隨機數(shù) )來確定各個個體被選中的次數(shù) 。 2021/6/15 54 單點交叉算子 單點交叉算子是最常用和最基本的交叉操作算子。 算子的具體執(zhí)行過程如下 ： (1)對群體中的個體進行兩兩隨機配對。 若群體的大小為 M，則共有 [M/2]對相互配對的個體組。其中 [x]表示不大于 x的最大整數(shù)。 (2)對每一對相互配對的個體，隨機設(shè)置某一基因座之后的位置為交叉點。若染色體的長度為 n，則共有 (n1)個可能的交叉點位置。 (3)對每一對相互配對的個體，依設(shè)定的交叉概率 pc在其交叉點處相互交換兩個個體的部分染色體，從而產(chǎn)生出兩個新的個體。 2021/6/15 55 單點交叉示意如下所示： A： 1 0 1 1 0 1 1 1 0 0 A’： 1 0 1 1 0 1 1 1 1 1 B： 0 0 0 1 1 1 0 0 1 1 B’； 0 0 0 1 1 1 0 0 0 0 單點交叉 交叉點 2021/6/15 56 基本位變異算子 對于基本遺傳算法中用二進制編碼符號串所表示的個體 ， 若需要進行變異操作的某一基因座上的原有基因值為 0， 則變異操作將該基因值變?yōu)?1；反之 ， 若原有基因值為 l， 則變異操作將其變?yōu)?0。 A： 1 0 l 0 1 0 1 0 1 0 A’： 1 0 l 0 0 0 1 0 1 0 基本位變異 變異點 (1)對個體的每一個基因座，依變異概率 pm指定其為變異點。 (2)對每一個指定的變異點 ， 對其基因值做取反運算或用其它等位基因值來代替 ， 從而產(chǎn)生出一個新的個體 。 2021/6/15 57 四、基本遺傳算法應(yīng)用舉例 遺傳算法的應(yīng)用步驟 第一步：確定決策變量及其各種約束條件，即確定出個體的表現(xiàn)型 X和問題的解空間。 第二步：建立優(yōu)化模型，即確定出目標(biāo)函數(shù)的類型 (是求目標(biāo)函數(shù)的最大值還是求目標(biāo)函數(shù)的最小值 )及其數(shù)學(xué)描述形式或量化方法。 第三步：確定表示可行解的染色體編碼方法，也即確定出個體的基因型 X及遺傳算法的搜索空間。 第四步：確定解碼方法，即確定出由個體基因型 X到個體表現(xiàn)型 X的對應(yīng)關(guān)系或轉(zhuǎn)換方法。 2021/6/15 58 )(12 m i nm a xm i naabaa m ????若參數(shù) a的變化范圍為 [amin， amax]， 用 m位二進制數(shù) b來表示 ，則二者之間滿足： 第五步：確定個體適應(yīng)度的量化評價方法，即確定出由目標(biāo)函數(shù)值 f (X)到個體適應(yīng)度 F(X)的轉(zhuǎn)換規(guī)則。 第六步：設(shè)計遺傳算子，即確定出選擇運算、交叉運算、變異運算等遺傳算子的具體操作方法。 第七步：確定遺傳算法的有關(guān)運行參數(shù)，即確定出遺傳算法的 M、T、 pc、 pm等參數(shù)。 2021/6/15 59 遺傳算法的手工模擬計算示例 ???????????}7,1,0{}7,1,0{..),(m a x21222121??xxtsxxxxf例：求下述二元函數(shù)的最大值： 2021/6/15 60 (1)個體編碼 遺傳算法的運算對象是表示個體的符號串 ， 所以必須把變量 xl、x2編碼為一種符號串 。 該例題中 ， xl和 x2取 0— 7之間的整數(shù) ， 可分別用 3位無符號二進制整數(shù)來表示 ， 將它們連接在一起所組成的 6位無符號二進制整數(shù)就形成了個體的基因型 ， 表示一個可行解 。 例如 ， 基因型 X=10l110所對應(yīng)的表現(xiàn)型是： X＝ [5， 6]T。 個體的表現(xiàn)型和基因型之間可通過編碼和解碼程序相互轉(zhuǎn)換 。 2021/6/15 61 (2)初始群體的產(chǎn)生 遺傳算法是對群體進行的進化操作 ， 需要給其準(zhǔn)備一些表示起始搜索點的初姑群體數(shù)據(jù) 。 本例中 ， 群體規(guī)模的大小取為 4， 即群體由 4個個體組成 ， 每個個體可通過隨機方法產(chǎn)生 。 一個隨機產(chǎn)生的初始群體如表中第 1欄所示 。 2021/6/15 62 (3)適應(yīng)度計算 遺傳算法中以個體適應(yīng)度的大小來評定各個個體的優(yōu)劣程度 ，從而決定其遺傳機會的大小 。 本例中 ， 目標(biāo)函數(shù)總?cè)》秦撝?， 并且是以求函數(shù)最大值為優(yōu)化目標(biāo) ， 故可直接利用目標(biāo)函數(shù)值作為個體的適應(yīng)度 。 為計算函數(shù)的目標(biāo)值 ， 需先對個體基因型 X進行解碼 。 表中第 3欄所示為初始群體中各個個體的解碼結(jié)果 ， 第 4欄所示為各個個體所對應(yīng)的目標(biāo)函數(shù)值 ， 它也是個體的適應(yīng)度 ，第 4欄中還給出了群體中適應(yīng)度的最大值和平均值 。 2021/6/15 63 個體 1 P(0) 2 x1 3 x2 4 fi(x1,x2) 1 011101 3 5 34 2 101011 5 3 34 3 011100 3 4 25 4 111001 7 1 50 50143ma x????fff i2021/6/15 64 (4)選擇運算 選擇運算 (或稱為復(fù)制運算 )把當(dāng)前群體中適應(yīng)度較高的個體按某種規(guī)則或模型遺傳到下 — 代群體中 。 一般要求適應(yīng)度較高的個體將有更多的機會遺傳到下一代群體中 。 本例中 ， 采用與適應(yīng)度成正比的概率來確定各個個體復(fù)制到下一代群體中的數(shù)量 。 其具體操作過程是： 先計算出群體中所有個體的適應(yīng)度的總和； 其次計算出每個個體的相對適應(yīng)度的大小 ， 如表中第 5欄所示 ，它即為每個個體被遺傳到下一代群體中的概率 ， 每個概率值組成一個區(qū)域 ， 全部概率值之代為 l。 最后產(chǎn)生一個 0到 1之間的隨機數(shù) ， 依據(jù)該隨機數(shù)出現(xiàn)在上述哪一個概率區(qū)域內(nèi)來確定各個個體被選中的次數(shù) 。 如表中第 7欄所示為一隨機產(chǎn)生的選樣結(jié)果 。 2021/6/15 65 個體 5 6 選擇次數(shù) 7 選擇結(jié)果 1 1 011101 2 1 111001 3 0 101011 4 2 111001 ? ii ff /2021/6/15 66 (5)交叉運算 交叉運算是遺傳算法中產(chǎn)生新個體的主要操作過程 ， 它以某一概率相互交換某兩個個體之間的部分染色體 。 本例采用單點交叉的方法 ， 其具體操作過程是： 先對群體進行隨機配對 ， 表中第 8欄所示為一種隨機配對情況； 其次隨機設(shè)置交叉點位置 ， 如表第 9欄所示為一隨機產(chǎn)生的交叉點位置 ， 其中的數(shù)字表示交叉點設(shè)置在該基因座之后； 最后再相互交換配對染色體之間的部分基因 。 表中第 10欄所示為交叉運算的結(jié)果 。 2021/6/15 67 個體 8 配對情況 9 交叉點 10 交叉結(jié)果 11 變異點 12 變異結(jié)果 1 1－ 2 3－ 4 2 4 011001 4 011101 2 111101 5 111111 3 101001 2 111001 4 111011 6 111010 2021/6/15 68 例如，若第 3號和第 4號個體在第 4個基因座之后進行交叉運算，則可得到兩個新的個體： 第 3號個體： 1 0 1 0 1 1 第 4號個體： 1 1 1 0 0 1 1 0 1 0 0 1 1 1 1 0 1 1 交叉操作 可以看出，其中新產(chǎn)生的個體 “ 111011”的適應(yīng)度較原來兩個個體的適應(yīng)度都要高。 2021/6/15 69 (6)變異運算 變異運算是對個體的某一個或某一些基因座上的基因值按某一較小的概率進行改變 ， 它也是產(chǎn)生新個體的一種操作方法 。 本例中 ， 我們采用基本位變異的方法來進行變異運算 ， 其具體操作過程是： 首先確定出各個個體的基因變異位置 ， 如表中第 11欄所示為隨機產(chǎn)生的變異點位置 ， 其中的數(shù)字表示變異點設(shè)置在該基因座處； 然后依照某 — 概率將變異點的原有基因值取反 。 表中第 12欄所示為變異運算結(jié)果 。 2021/6/15 70 例如，若第 3號個體的第 2個基因座需要進行變異運算，則可產(chǎn)生出 — 個新的個體： 第 3號個體： 1 0 1 0 0 1 1 1 1 0 0 1 第二位變異 對群體 P(t)進行 — 輪選擇、交叉、變異運算之后可得到新一代的群體 P(t+1)。如表第 13欄所示。 表中第 1 1 1 17欄還分別表示出了新群體的解碼值、適應(yīng)度和相對適應(yīng)度，并給出了適應(yīng)度的最大值和平均值等。 從表中可以看出，群體經(jīng)過一代進化之后，其適應(yīng)度的最大值、平均值都得到了明顯的改進。事實上，這里已經(jīng)找到了最佳個體“ 111111”。 2021/6/15 71 個體 13 P(1) 14 x1 15 x2 16 fi(x1,x2) 17 1 011101 3 5 34 2 111111 7 7 98 3 111001 7 1 50 4 111010 7 2 53 ? ii ff /98235ma x????fff i需要說明的是，表中第 11欄的數(shù)據(jù)是隨機產(chǎn)生的。這里為了更好地說明問題，特意選擇了一些較好的數(shù)值以便能夠得到較好的結(jié)果。 在實際運算過程中有可能需要一定的循環(huán)次數(shù)才能達到這個最優(yōu)結(jié)果。 2021/6/15 72 基本遺傳算法在函數(shù)優(yōu)化中的應(yīng)用 )2,1(..)1()(100),(m ax 21222121????????ixtsxxxxxfi該函數(shù)有兩個局部極大值，分別是 f(,)= f(,)=，其中后者為全局最大值。 下面介紹求解該問題的遺傳算法的構(gòu)造過程。 第一步：確定決策變量和約束條件。 第二步：建立優(yōu)化模型。 例： Rosenbrock函數(shù)的全局最大值計算。 2021/6/15 73 用長度為 l0位的二進制編碼串來分別表示二個決策變量 x1， x2。 10位二進制編碼串可以表示從 0到 1023之間的 1024個不同的數(shù)，故將 x1， x2的定義域離散化為 1023個均等的區(qū)域，包括兩個端點在內(nèi)共有 1024個不同的離散點。 第三步：確定編碼方法。 從離散點－ ，依次讓它們分別對應(yīng)于從0000000000(0)到 1111111111(1023)之間的二進制編碼。 再將分別表示 x1， x2的二個 10位長的二進制編碼串連接在一起，組成一個 20位長的二進制編碼串，它就構(gòu)成了這個函數(shù)優(yōu)化問題的染色體編碼方法。 使用這種編碼方法．解空間和遺傳算法的搜索空間具有一一對應(yīng)的關(guān)系。 例如 X： 000011011l 1101110001就表示一個個體的基因型，其中前 l0位表示 x1，后 10為表示 x2。 2021/6/15 74 第四步：確定解碼方法。 解碼時需先將 20位長的二進制編碼串切斷為二個 10位長的二進制編碼串，然后分別將它們轉(zhuǎn)換為對應(yīng)的十進制整數(shù)代碼，分別記為 y1和 y2。 )2,1( 0 ???? iyx ii例如，對于前述個體 X： 000011011l 1101110001 它由這樣的兩個代碼所組成： y1＝ 55 y2＝ 881 經(jīng)解碼處理后，可得到： x1=－ x2= 依據(jù)前述個體編碼方法和對定義域的離散化方法可知，將代碼 yi轉(zhuǎn)換為變量 xi的解