一個(gè)實(shí)例的遺傳操作步驟分析

1、一個(gè)實(shí)例的遺傳操作步驟分析,為了說(shuō)明遺傳算法的實(shí)質(zhì)，本節(jié)以簡(jiǎn)單函數(shù)極值的求解過(guò)程為例。設(shè)自變量介于0-31，求其二次函數(shù)的最大值，即 （1-1） 當(dāng)然，利用簡(jiǎn)單的代數(shù)運(yùn)算，我們可以求出該問(wèn)題的解為x=31?，F(xiàn)在改用遺傳算法求解。遺傳算法通常包括下述工作：,(1) 遺傳算法首先要用字符串表達(dá)所研究的問(wèn)題

2、，這稱作編碼。表達(dá)問(wèn)題的字符串相當(dāng)于遺傳學(xué)中的染色體。每個(gè)字符串稱作個(gè)體。每一遺傳代次中個(gè)體的組合稱為群體。為了便于計(jì)算機(jī)操作，通常字符串長(zhǎng)度固定，字符用二進(jìn)制碼或?yàn)?，或?yàn)?。 本例中，用二進(jìn)制數(shù)表示x值。由于x的最大值（31）只需5位二進(jìn)制數(shù)，以利用5位二進(jìn)制數(shù)組成個(gè)體。,（2）形成初始群體。遺傳算法中，常用隨機(jī)的方法產(chǎn)生初始群體，即隨機(jī)生成一組任意排列的字符串。群體中個(gè)體的數(shù)目通常也是固定的。 本例中，采用隨機(jī)產(chǎn)生

3、的方法，假設(shè)得出擁有4個(gè)個(gè)體的初始群體，即：01101、11000、01100、10011。它們的x值相應(yīng)為：13、24、8、19（見表2-1）。,表2-1 遺傳算法的第0代,（3）計(jì)算適應(yīng)度。衡量字符串（染色體）好壞的指標(biāo)是適應(yīng)度（Fitness），它通常也就是遺傳算法中的目標(biāo)函數(shù)。適應(yīng)度是今后優(yōu)勝劣汰的主要判據(jù)。 在本例中，適應(yīng)度比較簡(jiǎn)單，用 計(jì)算。當(dāng)x值為13、24、6、19時(shí)的適應(yīng)度分別為：169、576、64、3

4、61（表2-1的第4列）。表1-1中還列舉當(dāng)前適應(yīng)度的總和 及平均值 ，即,,表1-1中第6列的 表示每個(gè)個(gè)體的相對(duì)適應(yīng)度，它反映個(gè)體之間的相對(duì)優(yōu)劣性。例如，2號(hào)個(gè)體的 值最高（1.97）,為優(yōu)良個(gè)體；而3號(hào)個(gè)體最低（0.22），為不良個(gè)體。,（4）復(fù)制（Reproduction）。為了將已有的群體變?yōu)橄乱淮后w，遺傳算法仿效進(jìn)化論中“自然選擇，適者生存”的原則，從舊群體中選擇優(yōu)良個(gè)體予以復(fù)制

5、，直接進(jìn)入下一代群體。選擇的依據(jù)是個(gè)體適應(yīng)度的大小，適應(yīng)度大的個(gè)體接受復(fù)制，使之繁殖；適應(yīng)度小的個(gè)體則予刪除，使之死亡。 本例中，根據(jù)相對(duì)適應(yīng)度 的大小對(duì)個(gè)體進(jìn)行取舍。2號(hào)個(gè)體性能最優(yōu)（ ），予以復(fù)制繁殖。3號(hào)個(gè)體性能最差（ ），將它刪除，使之消亡。表2-1第7列表示傳遞給下一代的個(gè)體數(shù)目，其中2號(hào)個(gè)體占2個(gè)，3號(hào)個(gè)體為0個(gè)，1號(hào)及4號(hào)個(gè)體仍保持為1個(gè)。,這樣，就產(chǎn)生下一代新群體，如表

6、1-2所示。新群體的4個(gè)個(gè)體分別是01101、11000、11000、10011。從表2-2第4列可以看出，復(fù)制后產(chǎn)生的新一代群體，其平均適應(yīng)度明顯增加，由原來(lái)的293（表2-1）增至421（表2-2）。造成平均適應(yīng)度增加的原因有二：一是淘汰原來(lái)最差的個(gè)體，使最小的適應(yīng)度由原來(lái)的64（表2-1）增至169（表2-2）；另一個(gè)原因是增加優(yōu)良個(gè)體（2號(hào)）的個(gè)數(shù)，使適應(yīng)度累計(jì)值增加。因此，復(fù)制體現(xiàn)優(yōu)勝劣汰原則，使群體素質(zhì)不斷得到改善。,表2-

7、2 遺傳算法的復(fù)制與交叉（第1代）,（5）交叉（Crossover）。通過(guò)復(fù)制產(chǎn)生新群體，其總體性能得到改善，然而卻不能產(chǎn)生新的個(gè)體。為了產(chǎn)生新的個(gè)體，遺傳算法仿照生物學(xué)中交叉的方法，對(duì)染色體（字符串）的某些部分進(jìn)行交叉換位。被交換的母體都選自經(jīng)過(guò)復(fù)制產(chǎn)生的新一代個(gè)體（優(yōu)勝者）。 本例中，利用隨機(jī)配對(duì)的方法，決定1號(hào)和2號(hào)個(gè)體、3號(hào)和4號(hào)個(gè)體分別交叉，如表1-2第5列所示。再利用隨機(jī)定位的方法，確定這兩對(duì)母體交叉換位的位置分別

8、從字符串左數(shù)第三位字符及第二位字符之后。例如，3號(hào)及4號(hào)如下式左側(cè)所示，交換始于字符串左數(shù)第2位之后，交叉開始的位置稱為交叉點(diǎn)，用“ ”標(biāo)記，所得的新個(gè)體如下表所示：,至于1號(hào)、2 號(hào)個(gè)體交換結(jié)果如表2-2第7列所示。表2-2中最后一列表示交換后群體的適應(yīng)度。從表中可以看出，交換后出現(xiàn)優(yōu)異個(gè)體3號(hào)，其適應(yīng)度高達(dá)729，大大高于交換前的最大值（576）。與此同時(shí)，平均適應(yīng)度也從原來(lái)的421提高到439，說(shuō)明變換后的群體正朝優(yōu)良方向發(fā)展。

9、,（6）變異（Mutation）。遺傳算法模仿生物學(xué)中基因變異的方法，將個(gè)體字符串某位符號(hào)進(jìn)行逆變，即由1變?yōu)?或由0變?yōu)?。例如，下式左側(cè)的個(gè)體于第3位變異，得到新個(gè)體如右側(cè)所示： 遺傳算法中，個(gè)體是否進(jìn)行變異以及在哪個(gè)字符變異，都由事先給定的概率決定。通常，變異概率很小，約為0.01，本例的第一代中就沒有發(fā)生變異。（7）終止。反復(fù)執(zhí)行上述（3）-（6）項(xiàng)工作，直至得出滿意的最優(yōu)解。 通過(guò)上述函數(shù)極值求解的例子可以看