Algorithm 版 (精华区)

发信人: zjliu (秋天的萝卜), 信区: Algorithm
标  题: Genetic Algorithms-遗传算法4 算子
发信站: 哈工大紫丁香 (Tue Sep 24 10:14:25 2002) , 转信

续前(第一次翻译,请大家指点)
谢谢
QQ:16748251
http://wangzhengyao.xiloo.com
--------------
V 遗传算法中的算子
概述
在前面的遗传算法的基本结构中我们注意到交换和变异是遗传算法中最重要的部分。算
法的结果受交换和变异的影响最大。当然，在我们讨论交换和变异之前我们先要介绍一
些染色体的信息。
染色体的编码
染色体在一定能够意义上包含了它所代表的问题的解在里面。最常用的编码方式是二进
制串（Binary String）。于是染色体可以表示为：
1号染色体   1101100100110110
2号染色体   1101111000011110
每一个染色体用一个二进制串表示，这个二进制串的每一位表示解的某些特征。或者，
整个二进制串表示一个数，比如说在基本的遗传算法的Applet中就是如此。
当然，编码的方法有很多。选用什么方法编码主要取决于所要解决的问题本身。比如说
，有的问题直接用整数或者实数来编码可能更好！
交换
当我们决定了用什么方法来编码后，我们既可以考虑下一不了――交换。交换的本质就
是从母群体中选择父代以生成新的母体群。最简单的方法就是随机的选择一个交换点，
在交换点之前的部分来自父代1号染色体，交换点之后的部分来自来父代的2号染色体。

用图可以表示为上述过程如下：（｜表示交换点）
1号染色体   11011｜00100110110
2号染色体   11011｜11000011110
子代1   11011｜11000011110
子代2   11011｜00100110110
当然，交换的方式也很多。比如说一个直接的对这个方法的改变就是多选择几个交换点
。交换可能很复杂，这有可能是染色体编码方法的原因！对特定的问题我们要选择特定
的交换方法以使得遗传算法的结果比较好！
变异
一旦交换完成，变异就要开始了。变异的目的是防止母群体中的解跑到局部极值。变异
是对子代的随机的改变。对二进制串编码方式来说，我们可以随机地改变子代中的某个
位点的数字（1变为0，或者0变为1）。于是，变异可以用表表示如下：
变异前的子代1   1101111000011110
变异前的子代2   1101100100110110
变异后的子代1   1100111000011110
变异后的子代2   1101100101110110
显然，变异取决于编码方式和交换方法。比如说变异可以是交换两个基因。
续前(第一次翻译,请大家指点)
谢谢
QQ:16748251
http://wangzhengyao.xiloo.com
※ 来源:·交大兵马俑BBS站 bbs.xjtu.edu.cn·[FROM: 202.200.239.125]




--

※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 202.118.229.86]