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

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

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

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

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

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

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

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

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

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