【正文】 適應(yīng)度是 費用、贏利、方差 等目標(biāo)的表達(dá)式。在運用過程中可以借鑒以下經(jīng)驗。 （ 2） 適應(yīng)度 42 1統(tǒng)一表達(dá)形式 在實際問題中，有時希望適應(yīng)度越大越好（如贏利、勞動生產(chǎn)率），有時要求適應(yīng)度越小越好（費用、方差）。為了使遺傳算法有通用性，這種最大、最小值問題宜統(tǒng)一表達(dá)。通常都統(tǒng)一按最大值問題處理，而且不允許適應(yīng)度小于 0。 對于最小值問題，其適應(yīng)度按下式轉(zhuǎn)換： f (x) = Cmax g (x) 當(dāng) g(x) Cmax 0 其他情況 f(x)：轉(zhuǎn)換后的適應(yīng)度。 g(x)：最小值問題下的適應(yīng)度。 Cmax ：足夠大的常數(shù)，可取 g(x)的最大值。 （ 2） 適應(yīng)度 43 1統(tǒng)一表達(dá)形式 為了保證適應(yīng)度不出現(xiàn)負(fù)值，對于有可能產(chǎn)生負(fù)值的最大值問題，可以采用下式進(jìn)行變換： f (x) = U(x) + Cmin 當(dāng) U(x) + Cmin 0 0 其他情況 f(x)： 變換后的適應(yīng)度。 U(x)：最大值問題下的適應(yīng)度。 Cmin ：足夠大的常數(shù)。 （ 2） 適應(yīng)度 44 2適應(yīng)度縮放 在執(zhí)行遺傳算法的初始階段，各個個體的適應(yīng)度比較離散，某些個體的適應(yīng)度會很高或很低。對于個別適應(yīng)度很高的個體，會連續(xù)多次被復(fù)制；對于適應(yīng)度很低的個體，會過早被舍棄。這種不正常的取舍，對于個體數(shù)目不多的群體尤為嚴(yán)重，會把遺傳算法的搜索引向誤區(qū) ，過早地收斂于 局部最優(yōu)解 。為了克服這種缺陷，需要采用適應(yīng)度縮放技術(shù)，將適應(yīng)度按下式變換： f 39。 ： 縮放后的適應(yīng)度。 f：原來的適應(yīng)度。 a、 b ：系數(shù)。 f 39。= a*f + b 利用這種縮放技術(shù)，縮小（放大）原來最大（最?。┑倪m應(yīng)度，從而可以減弱離散現(xiàn)象。 （ 2） 適應(yīng)度 45 復(fù)制是遺傳算法的基本算子，它將優(yōu)良個體在下一代新群體中繁殖，體現(xiàn)了“適者生存”的自然選擇原則。 個體是否被復(fù)制的依據(jù)是其適應(yīng)度的大小，適應(yīng)度大者被復(fù)制，小者被淘汰，使新群體中的個體總數(shù)與原來群體相同。 在遺傳算法中，常常采用 輪盤賭方式 選擇復(fù)制對象。 （ 3） 復(fù)制 46 表中第一行說明有 10個個體參與選擇，第二行表示各個體的適應(yīng)度，第三行標(biāo)記適應(yīng)度的累計值，總值為 76。然后，在 [ 0，76 ]區(qū)間內(nèi)產(chǎn)生均勻分布的隨機(jī)數(shù)，如第四行所示。依次序?qū)⒌谌械睦塾嬤m應(yīng)度與隨機(jī)數(shù)相比較，其值大于或等于隨機(jī)數(shù)的第一個個體列為入選的復(fù)制對象。例如，第一個隨機(jī)數(shù)是 23，除了 1號、 2號個體外，其余個體的累計適應(yīng)度均大于 23，然而 3號個體累計值為 27，是第一個大于 23的個體，所以它入選。 個體序號 1 2 3 4 5 6 7 8 9 10 適應(yīng)度 8 2 17 7 2 12 11 7 3 7 適應(yīng)度累計值 8 10 27 34 36 48 59 66 69 76 隨機(jī)數(shù) 23 49 76 13 1 27 57 被選中的個體 3 7 10 3 1 3 7 輪盤選擇示例： （ 3） 復(fù)制 47 （ 1）依次累計群體內(nèi)各個體的適應(yīng)度，得相應(yīng)的累計值 Si，最后一個累計值為 Sn； （ 2）在 [ 0， Sn ]區(qū)間內(nèi)產(chǎn)生均勻分布的隨機(jī)數(shù) R； （ 3）依次用 Si與 R相比較，第一個出現(xiàn) Si大于或等于 R的個體 i被選為復(fù)制對象； （ 4）重復(fù)（ 2）、（ 3），直至滿足所需要的個體數(shù)目。 上述選擇過程，可描述如下： （ 3） 復(fù)制 48 因此，適應(yīng)度 fi越大， △ Si的距離越大，隨機(jī)數(shù)落在這個區(qū)間的可能性越大，第 i個個體被選中的機(jī)會也越多。如下圖所示。 表面上看，復(fù)制個體的選擇是隨機(jī)的。但是，選擇時是依據(jù)相鄰兩個適應(yīng)度累計值的差值△ Si ： △ Si = Si – Si1 = fi fi表示第 i個個體的適應(yīng)度 （ 3） 復(fù)制 49 輪盤（賭）選擇原理 S2 S1 S3 S4 Si Sn1 Sn … 圖中的指針固定不動，外圈的圓環(huán)可以任意轉(zhuǎn)動，圓環(huán)中每段對應(yīng)于適應(yīng)度的大小。從統(tǒng)計意義上講，適應(yīng)度大的個體被復(fù)制的機(jī)會越大。當(dāng)然，適應(yīng)度小的個體盡管被復(fù)制的概率小，但仍有可能被“破格”復(fù)制，這樣就增加個體的多樣性，便于執(zhí)行交換及突變。所以，輪盤選擇方法既體現(xiàn)“適者生存”原則，又保持個體性態(tài)多種多樣。 （ 3） 復(fù)制 50 選擇復(fù)制個體的隨機(jī)方法還有別的形式，不過輪盤選擇法是最常用的方法。 每代群體中，被復(fù)制的個體數(shù)目由復(fù)制概率 Pt控制， Pt常取 ～ ，也就是說，群體中有 10%個體被復(fù)制，相應(yīng)地有 10%個體被淘汰，以保持群體大小。 （ 3） 復(fù)制 51 下表是個體兩兩交換的示例，字符串內(nèi)的下橫線代表交換點的位置，交換點及其后面的字符串兩兩互換。 在遺傳算法中，交換是產(chǎn)生新個體的主要手段。它仿照生物學(xué)中雜交的原理，將兩個個體（染色體）的部分字符（基因）互相交換。 序號 交換前 交換后 1 2 親代 1： 1 1 1 1 1 1 親代 2： 0 0 0 0 0 0 子代 1： 1 1 1 1 0 0 子代 2： 0 0 0 0 1 1 3 4 親代 1： 1 0 1 1 0 1 親代 2： 0 0 1 1 0 0 子代 1： 1 0 1 1 0 0 子代 2： 0 0 1 1 0 1 （ 4） 交換 52 執(zhí)行交換的個體是隨機(jī)選擇的。首先，要確定交換的概率 Pc，大致為 ～ 。這就是說，約 50%～ 80%的個體要執(zhí)行交換。然后，采用上述輪盤選擇的方法，按適應(yīng)度大小選擇被交換的個體，依次兩兩進(jìn)行交換。 交換點的選擇也是隨機(jī)的。假設(shè)字符串長度為 L，則在 [ 0， L ]區(qū)間內(nèi)產(chǎn)生隨機(jī)整數(shù)，該整數(shù)便是交換點的位置。需要注意的是，交換點不能選在第一個字符上。因此，長度為 L的字符串，可供選擇的交換點為（ L1）個。 根據(jù)交換點數(shù)目的不同，可分為 一點交換 和多 點交換 ，前者只選取一個交換點，該點之后的字符全部參加交換。后者選擇兩個或多個交換點，只有兩點間的字符才參加交換。當(dāng)字符串長度大時，常采用兩點交換。此外還有 多點交換 ，即對長字符串實行多段交換。 （ 4） 交換 53 通過交換，子代的字符串不同于親代。有時，這種差別很明顯，如表中的第一組個體，被交換部分完全不一樣。有時，這種差別卻不大，如表中的第二組個體，被交換的三個字符中只有最后一個字符發(fā)生變化。后一種情況說明交換后產(chǎn)生的個體，其性態(tài)變化不大。盡管如此，交換仍然是遺傳算法產(chǎn)生新個體的主要手段。正是有了交換操作，群體的性態(tài)才多種多樣。 序號 交換前 交換后 1 2 親代 1： 1 1 1 1 1 1 親代 2： 0 0 0 0 0 0 子代 1： 1 1 1 1 0 0 子代 2： 0 0 0 0 1 1 3 4 親代 1： 1 0 1 1 0 1 親代 2： 0 0 1 1 0 0 子代 1： 1 0 1 1 0 0 子代 2： 0 0 1 1 0 1 傳統(tǒng)的優(yōu)化算法，例如動態(tài)規(guī)劃法、個體性態(tài)不能增添，只能在原有的個體群體中擇優(yōu)，從而限制了搜索尋優(yōu)的范圍。因此，可以說，如果沒有交換，遺傳算法就失去了其優(yōu)越性。 （ 4） 交換 54 突變是遺傳算法中產(chǎn)生新個體的另一種方法，它是將某一個體的某一位字符進(jìn)行補運算，使 0變?yōu)?1，或使1變?yōu)?0。 突變個體的選擇以及突變位置的確定，都是采用隨機(jī)的方法產(chǎn)生。首先，確定突變概