Algorithm 版 (精华区)

发信人: zjliu (秋天的萝卜), 信区: Algorithm
标  题: Genetic Algorithms--遗传算法(3):基本结构!
发信站: 哈工大紫丁香 (Mon Sep 23 17:38:46 2002) , 转信



续前(第一次翻译,请大家指点)
谢谢
QQ:16748251
http://wangzhengyao.xiloo.com
--------------
IV 遗传算法
基本思想
遗传算法受到达尔文进化论的影响很大。在遗传算法中，问题的解是逐渐进化得到的！

遗传算法的计算从一组可能解开始，这组解被称作母群体（Population），在算法中被
表示成 染色体。我们又把母群体中的解拿出来去构成新的一个母群体，这是因为我们期
望新的母群体要比旧的母群体要好！当然，新的母群体中的解要有这样的性质，就必须
按照它的适应度去选择，适应度越高，它在新的母群体中的机会就越大。
这个过程一次又一次的重复，我直到我们所给的约束条件满足为止，比如说母群体中解
得个数或者母群体的良好程度。
例：
--
5［测验］ 如果终止条件满足，则停止；并且把当前母体群中最好的解输出；
6［循环］如果5不满足，则转到2；继续进行
一些说明
你可以发现这个遗传算法的基本结构是很一般的。在具体的问题中，我们还要做很多工
作以实现算法。
首先的问题是怎样创建一个染色体？怎样对它们编码？这些问题都是和对染色体的操作
（交换、变异）密切联系的。编码，交换，变异我们将在下一章介绍。
下一个问题是怎样从父代母群体中选择用来交换的父代。方法有很多，但是最基本的思
想是：选择好的父代（因为我们认为好的父代可以产生好的子代）。你或许在想：仅仅
从产生的子代中选择染色体去构造新的母群体可能会丢失掉上一代母群体中的很多信息
。这确实是事实，我们可以使用精英主义（Elitism）方法。也就是说，母群体中最好的
那个染色体我们将毫无改变的复制到新的母群体中。显然，任何时刻产生的一个最优解
的解都可以存活到算法结束。
还有很多问题我们都将在后面的章节中陆续讨论。
你可能在想，为什么遗传算法能够得到我们需要的结果呢？这个问题部分地可以被Holl
and的模式定理（Schema Theorem）解决。可是，这个模式定理现在被很多人批评，认为
它是有问题的。
如果你有兴趣的话，你可以在这里找到更多的资料！
QQ:16748251
http://wangzhengyao.xiloo.com
--------------
--
          http://wangzhengyao.xiloo.com;
※ 转载:·交大兵马俑BBS站 bbs.xjtu.edu.cn·[FROM: 202.200.239.125]




--

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