遗传算法故事1.docx

《遗传算法故事1.docx》由会员分享，可在线阅读，更多相关《遗传算法故事1.docx（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、这是个真实的故事。从前在海岸边有一群扇贝在悠哉游哉地生活繁衍着。它们自然是衣食不愁，连房子也有了着 落。它们担忧的只有一件事：每隔一段时间，总有一个人来挖走它们之中的一局部。当然啦, 挖回去干什么这大家都知道。但扇贝们不知道的是，这人的家族图腾是Firefox的图标，所 以他总是选择那些贝壳花纹长得比拟不像Firefox图标的扇贝。这种状况持续了好几十万代。大家应当也猜到扇贝们身上发生什么事情了：它们的贝壳上都 印着很像Firefox图标的图案。可能有些读者会说：你这不是糊弄我们么，Firefox才有多少年历史，你就搞了个几十万代 的扇贝？确有其事，但是这些扇贝不是真实的，它们在我电脑的内存里

2、边生活工它们是一个遗传算法 程序的一局部，这个程序的目的就是用100个半透亮 三角形把Firefox的图标尽可能 像地画出来。什么是遗传算法呢？简洁地说，遗传算法是一种解决问题的方法。它模拟大自然中种群在选择压力下的演化，从 而得到问题的一个近似解。在二十世纪五十年月，生物学家已经知道基因在自然演化过程中的作用了，而他们也盼望能 在新消失的计算机上模拟这个过程，用以尝试定量讨论基因与进化之间的关系。这就是遗传 算法的滥觞。后来，有人将其用于解决优化问题，于是就产生了遗传算法。那么，详细来说，在计算机里边是怎么模拟进化过程的呢？我们还是以开头提到的程序为例。首先，我们知道，生物个体长什么样子很大

3、程度上是由染色体上的基因打算的。同样，假如 我们把100个半透亮 三角形组成的东西看成一个生物个体的话（为了说话便利，称为 扇贝吧），我们也可以说它的样子是由这些三角形的详细位置和颜色打算的。所以，我们可 以把一个一个的半透亮 三角形看作是这些扇贝的“基因”。而组成扇贝的这100个基因 就组成了每个扇贝个体的“染色体” （chromosome）o从下面的图可以大约看出来这些基因是怎么打算扇贝的样子的（为了观看便利，我们只画出 其中五个三角形）：然后，扇贝们除了生活，当然还要繁衍后代。生物界中的繁衍无非就是父母的基因组合产生新的个体, 而在这个程序里边我们当然也这么办：选择两个原有的扇贝，然后从

4、这两个扇贝的染色体中随机选取 一共100个基因组成新个体的染色体。如下图：（仍旧是将扇贝看成是五个三角形组成的）为了产生新的基因，使基因的种类更多样化，在组合的时候，新的扇贝的基因有肯定的概率发生变异。 也就是说，其中的一个透亮 三角形的位置或者颜色会随机转变，如图（仍旧是五个三角形 我偷工减料）:其次，为了使扇贝的样子向Firefox图标靠近，我们要给它们加上一点选择压力，就是文章开头故事 中提到的那个人的行动：在每一代把最不像Firefox的扇贝淘汰出去，同时也给新的个体留下生存的空间。怎么评价这个扇贝像不像Firefox呢？最直接的方法就是一个一个像素比拟，颜色相差得越多 就越不像。这个

5、评价的函数叫做“适应函数”，它负责评价一个个体究竟有多适应我们的要求。在淘汰的过程中，为了便于编程，我们通常会在淘汰旧个体和产生新个体的数目上进行适当的调整， 使种群的大小保持不变。淘汰的作用就是使适应我们要求的个体存在的时间更长，从而到达选择的目 的。最终，在自然界中，种群的演化是一个无休止的过程，但程序总要停下来给出一个结果。那么，什么 时候终止演化输出结果呢？这就要订立一个终止条件，满意这个条件的话程序就输出当前最好的结果 并停止。最简洁的终止条件就是，假如种群经过了很多代（这里的“很多”是一个需要设定的参数）之 后仍旧没有显著转变适应性的变异的话，我们就停止并输出结果。我们就用这个终止

6、条件。好了，现在是万事俱备只欠东风了。定义好基因，写好繁衍、变异、评价适应性、淘汰和终止的代码 之后，只需要随机产生一个适当大小的种群，然后让它这样一代代的繁衍、变异和淘汰下去，到最终 终止我们就会获得一个惊喜的结果：（这回是完整的了，图片下的数字表示这个扇贝是第几代中最好 的）80008000150003000060000120000怎么样？虽说细节上很欠缺，但是也算是不错了。要不，你来试试用100个透亮 三角形画一个 更像的？就是这样的看上去很简洁的模拟演化过程也能解决一些我们这些有才智的人类也感到麻烦的问题。实际上，在生活和生产中，很多时候并不需要得到一个完善的答案；而很多问题假如要得到

7、完善的答 案的话，需要很大量的计算。所以，由于遗传算法能在相对较短的时间内给出一个足够好能凑合的答 案，它从问世伊始就越来越受到大家的重视，对它的讨论也是方兴未艾。当然，它也有缺点，比方说 早期的优势基因可能会很快通过交换基因的途径散播到整个种群中，这样有可能导致早熟 (premature),也就是说整个种群的基因过早同一化，得不到足够好的结果。这个问题是难以完全避开的。其实，通过微调参数和繁衍、变异、淘汰、终止的代码，我们有可能得到更有效的算法。遗传算法只 是一个框架，里边详细内容可以依据实际问题进行调整，这也是它能在很多问题上派上用场的一个缘 由。像这样可以适应很多问题的算法还有模拟退火算

8、法、粒子群算法、蚁群算法、禁忌搜寻等等，统 称为元启发式算法(Meta-heuristic algorithms)。此外，基于自然演化过程的算法除了在这里说到的遗传算法以外，还有更广泛的群体遗传算法和遗传 编程等，它们能解决很多麻烦的问题。这也从一个侧面说明，我们不肯定需要一个智能才能得到一个 构造精致的系统。无论如何，假如我们要将遗传算法的创造归功于一个人的话，我会将它归功于达尔文，进化论的奠基 人。假如我们不知道自然演化的过程，我们也不行能在电脑中模拟它，更不用说将它应用于实际了。向达尔文致敬！Bonus：假如你看明白了这篇文章，而且你懂英语的话，你自然明白下面这个冷笑话：(来自 . co

9、m/534/)Just to make sure you dont have it maximize instead of minimize.v/pDvp这是个真实的故事。v/pDvp从前在 海岸边有一群扇贝在悠哉游哉地生活繁衍着。它们自然是衣食不愁，连房子也有了着落。它们担忧的 只有一件事：每隔一段时间，总有一个人来挖走它们之中的一局部。当然啦，挖回去干什么这大家都 知道。但扇贝们不知道的是，这人的家族图腾是Firefox的图标，所以他总是选择那些贝壳花纹长得 比拟不像Firefox图标的扇贝。口vp这种状况持续了好几十万代。大家应当也猜到扇贝们身 上发生什么事情了：它们的贝壳上都印着很像F

10、irefox图标的图案。vspan id = more-10462” v/span v/pD vp可能有些读者会说：你这不是糊弄我们么，Firefox才 有多少年历史，你就搞了个几十万代的扇贝？ v/pDvp确有其事，但是这些扇贝不是真实的，它 们在我电脑的内存里边生活。它们是一个遗传算法程序的一局部，这个程序的目的就是用100个半 透亮 三角形把Firefox的图标尽可能像地画出来。v/pDvp什么是遗传算法呢？ v/pDvp简洁地说，遗传算法是一种解决问题的方法。它模拟大自然中种群在选择压力下的演化, 从而得到问题的一个近似解。v/pDvp在二十世纪五十年月，生物学家已经知道基因在自然演化

11、 过程中的作用了，而他们也盼望能在新消失的计算机上模拟这个过程，用以尝试定量讨论基因与进化 之间的关系。这就是遗传算法的滥觞。后来，有人将其用于解决优化问题，于是就产生了遗传算法。 v/pDvp那么，详细来说，在计算机里边是怎么模拟进化过程的呢？ v/pDvp我们还是以开 头提到的程序为例。v/pDvp首先，我们知道，生物个体长什么样子很大程度上是由染色体上的 基因打算的。同样，假如我们把100个半透亮三角形组成的东西看成一个生物个体的话（为了说话便利，称为扇贝吧），我们也可以说它的样子是由这些三角形的详细位置和颜色打算的。所以， 我们可以把一个一个的半透亮三角形看作是这些扇贝的“基因工而组成

12、扇贝的这100个基因就组成了每个扇贝个体的“染色体”（chromosome）。v/pDvp从下面的图可以大约看出来这些基 因是怎么打算扇贝的样子的（为了观看便利，我们只画出其中五个三角形）：Dnn口 vp然后，扇贝们除了生活，当然 还要繁衍后代。生物界中的繁衍无非就是父母的基因组合产生新的个体，而在这个程序里边我们当然 也这么办：选择两个原有的扇贝，然后从这两个扇贝的染色体中随机选取一共100个基因组成新个 体的染色体。如下图：（仍旧是将扇贝看成是五个三角形组成的）v/pDvpva href= bpOqGKEAqnlxhTMc4a-ulsXskzup7EHOpC7g3QLITXTRMkfK6m

13、VA?PARTNER=WRITER ximgclass=alignnonesrc= bpOqGKEAqnlxhTMc4a-ulsXskzup7EHOpC7g3QLITXTRMkfK6mVA?PARTNER=WRITER alt=n, width = 510, height=387“/ v/a v/pD vp为了产生新的基因，使基因的种类更多 样化，在组合的时候，新的扇贝的基因有肯定的概率发生变异。也就是说，其中的一个透亮三角形的位置或者颜色会随机转变，如图（仍旧是五个三角形我偷工减料）：nv/pDvp其次，为了使扇贝的样子向 Firefox图标靠近，我们要给它们加上一点选择压力，就是文章开头故

14、事中提到的那个人的行动：在 每一代把最不像Firefox的扇贝淘汰出去，同时也给新的个体留下生存的空间。怎么评价这个扇贝像 不像Firefox呢？最直接的方法就是一个一个像素比拟，颜色相差得越多就越不像。这个评价的函数 叫做“适应函数”，它负责评价一个个体究竟有多适应我们的要求。v/pDvp在淘汰的过程中，为 了便于编程，我们通常会在淘汰旧个体和产生新个体的数目上进行适当的调整，使种群的大小保持不 变。淘汰的作用就是使适应我们要求的个体存在的时间更长，从而到达选择的目的。v/pDvp最 终，在自然界中，种群的演化是一个无休止的过程，但程序总要停下来给出一个结果。那么，什么时 候终止演化输出结果

15、呢？这就要订立一个终止条件，满意这个条件的话程序就输出当前最好的结果并 停止。最简洁的终止条件就是，假如种群经过了很多代(这里的“很多”是一个需要设定的参数)之后 仍旧没有显著转变适应性的变异的话，我们就停止并输出结果。我们就用这个终止条件。v/pDvp 好了，现在是万事俱备只欠东风了。定义好基因，写好繁衍、变异、评价适应性、淘汰和终止的代码 之后，只需要随机产生一个适当大小的种群，然后让它这样一代代的繁衍、变异和淘汰下去，到最终 终止我们就会获得一个惊喜的结果：(这回是完整的了，图片下的数字表示这个扇贝是第几代中最好 的)Dv/av/pDvp怎么样？虽说细节上很欠缺，但是也算是不错了。要不，

16、你来试试用100个 透亮三角形画一个更像的？就是这样的看上去很简洁的模拟演化过程也能解决一些我们这些有才智的人类也感到麻烦的问题。v/pDvp实际上，在生活和生产中，很多时候并不需要得到一个 完善的答案；而很多问题假如要得到完善的答案的话，需要很大量的计算所以，由于遗传算法能在 相对较短的时间内给出一个足够好能凑合的答案，它从问世伊始就越来越受到大家的重视，对它的讨 论也是方兴未艾。当然，它也有缺点，比方说早期的优势基因可能会很快通过交换基因的途径散播到 整个种群中，这样有可能导致早熟(premature),也就是说整个种群的基因过早同一化，得不到足 够好的结果。这个问题是难以完全避开的。v/

17、pDvp其实，通过微调参数和繁衍、变异、淘汰、 终止的代码，我们有可能得到更有效的算法。遗传算法只是一个框架，里边详细内容可以依据实际问 题进行调整，这也是它能在很多问题上派上用场的一个缘由。像这样可以适应很多问题的算法还有模 拟退火算法、粒子群算法、蚁群算法、禁忌搜寻等等，统称为元启发式算法(Meta-heuristic algorithms)0 v/pDvp止匕外，基于自然演化过程的算法除了在这里说到的遗传算法以外，还有 更广泛的群体遗传算法和遗传编程等，它们能解决很多麻烦的问题。这也从一个侧面说明，我们不肯 定需要一个智能才能得到一个构造精致的系统。v/pDvp无论如何，假如我们要将遗传算法的创 造归功于一个人的话，我会将它归功于达尔文，进化论的奠基人。假如我们不知道自然演化的过程， 我们也不行能在电脑中模拟它，更不用说将它应用于实际了。v/pDvp向达尔文致敬！ Dv/pDvpBonus：假如你看明白了这篇文章，而且你懂英语的话，你自然明白下面这个冷笑 话： (来 自 va title=n :/xkcd /534/ href= :/xkcd /534/ :/xkcd /534/) DnJust to make sure you dont have it maximize instead of minimize. nnnD