遗传算法导论

《遗传算法导论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、IntroductiontoGeneticAlgorithms遗传算法导论http://cs.felk.cvut.cz/~xobitko/ga/（其中有全部操作的小程序可视化演示）byMarekObitko,studentofCzechTechnicalUniversity.王郑耀翻译原文为英语版本,你可以在这里找到.你也可以在这里下载到PDF格式的英语版本的文件.--------------------------------------------------------------------------------这里我想介绍一下遗传算法的一些基础知识。

2、我尽量写的比较通俗易懂,使得以前没有任何相关知识的读者也能读懂。我们只假设读者对于计算机程序设计有一定的了解。这里我们有一些JavaApplet程序用来演示遗传算法的工作情况。遗传算法所涉及的范围是很宽的，所以我们不可能涉及到它的方方面面。但是你可以从这里得到遗传算法的一些思想：什么是遗传算法？遗传算法可以用来做什么？这里面没有什么很难的数学理论。现在，你可以选择下一步去浏览下面的内容，你也可以从左边的菜单中任意选择你想要浏览的内容。如果你不想阅读全部的内容而只关心其中的一部分，你也可以跳过去直接去首页面。这里还有一个日语译本。I简介前言遗传算法是进化计算技术的

3、一部分，而进化计算技术在人工智能领域得到飞速的发展。你或许已经在想：遗传算法是不是受到了达尔文进化论的启发？简单地说，用遗传算法求解问题时，问题的解是在不断进化中得到的。历史二十世纪六十年代，I.Rechenberg在他的《演化战略》中第一次引入了进化算法的思想（起初称之为Evolutionsstrategies）。他的这一思想逐渐被其他一些研究者发展。遗传算法（GeneticAlgorithms）是JohnHolland发明的，后来他和他的学生及他的同事又不断发展了它。终于，在1975年JohnHolland出版了专著《自然系统和人工系统中的自适应》（Adap

4、tionInNaturalandArtificialSystems）。1992年，JohnKoza曾经使用遗传算法编出新的程序去做一些具体的工作。他称他的这种方法为“进化规划”（GeneticProgramming，简称GP）。其中使用了LISP规划方法，这是因为这种语言中的程序被表示为“分析树”（ParseTree），而这种遗传算法就是以这些分析树为对象的。II生物学背景基因所有的生物都是由细胞组成的。在每一个细胞中都有想同序列的染色体。染色体是一串DNA的片断，它为整个有机体提供了一种复制模式。染色体是由基因组成的，或者说染色体就是一块块的基因。每一个基因为

5、一个特定的蛋白质编码。或者更简单的说，每一个基因为生物体的某一特定特征编码，比如说眼睛的颜色。所有可能的某一特定特征的属性（比如，蓝色，桔黄色等）被称之为等位基因。每一个基因在染色体上都有其特定的位置，这个位置一般被称作位点（Locus）。全部序列的基因物质（或者全部的染色体）称之为基因组（或染色体组）（Genome）。基因组上特定序列的基因被称作基因型（Genotype）。基因型和后天的表现型两者是有机体的显性、生理和心理特征比如说眼睛的颜色、智力的基础。复制（Repeoduction）在复制中，首先发生的是交叉（Crossover）。来自于父代的基因按照一定

6、的方式组成了新的基因。新的子代还可能发生变异（Mutation）。变异的意思是DNA上的某一些成分发生了一点点的变化。这些改变可能是由于在由父代到子代的基因复制中出现的误差。生物体的适应度由生物体自身是否能生存来度量的。III搜索空间搜索空间（SearchSpace）在很多情况下,我们解决一个问题就是从一大堆的数据中寻找一个解，而通常这个解都是混杂在数据中的。所有可行解（FeasibleSolution可行解就是满足了一定约束条件的解）组成的空间称之为搜索空间（也可以称之为状态空间）。搜索空间中的每一个点都是一个可行解。每一个可行解都可以被它的函数值或者它的适应

7、度所标记。记住：问题的解就是搜索空间中的一个点，于是我们就是要从搜索空间中找到这个点。Exampleofasearchspace这样，求解问题就可以转化为在搜索空间中寻找极值点（最大值或者最小值点）。搜索空间在求解问题时可能是完全已知的，但一般来说我们只知道一些孤立的点，然后我们逐渐地生成其它点。问题是，这个搜索过程可能很复杂，我们甚至不知道该去哪里搜索或者该从是么地方开始搜索。事实上，有很多寻找合适解（注意：不一定是最优解）的方法，比如说爬山法（HillClimbing）禁止接近法(TabuSearch),模拟退火算法(SimulatedAnnealing)以

8、及遗传算法等等.用遗传算