一個實例的遺傳操作步驟分析

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

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

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

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

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

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

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

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

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