遗传算法导论

Introduction to Genetic Algorithms 遗传算法导论 http://cs.felk.cvut.cz/~xobitko/ga/ （其中有全部操作的小程序可视化演示） by Marek Obitko, student of Czech Technical University. 王郑耀 翻译 原文为 英语 关于好奇心的名言警句英语高中英语词汇下载高中英语词汇 下载英语衡水体下载小学英语关于形容词和副词的题 版本,你可以在这里找到.你也可以在这里下载到PDF 格式 pdf格式笔记格式下载页码格式下载公文格式下载简报格式下载 的英语版本的文件. -------------------------------------------------------------------------------- 这里我想介绍一下遗传算法的一些基础知识。我尽量写的比较通俗易懂,使得以前没有任 何相关知识的读者也能读懂。我们只假设读者对于计算机程序设计有一定的了解。这里我们 有一些Java Applet 程序用来演示遗传算法的工作情况。 遗传算法所涉及的范围是很宽的，所以我们不可能涉及到它的方方面面。但是你可以从这 里得到遗传算法的一些思想：什么是遗传算法？遗传算法可以用来做什么？这里面没有什么 很难的数学理论。 现在，你可以选择下一步去浏览下面的内容，你也可以从左边的菜单中任意选择你想要浏 览的内容。如果你不想阅读全部的内容而只关心其中的一部分，你也可以跳过去直接去首页 面。 这里还有一个日语译本。 I 简介 前言 遗传算法是进化计算技术的一部分，而进化计算技术在人工智能领域得到飞速的发展。 你或许已经在想：遗传算法是不是受到了达尔文进化论的启发？简单地说，用遗传算法求 解问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 时，问题的解是在不断进化中得到的。 历史 二十世纪六十年代，I.Rechenberg 在他的《演化战略》中第一次引入了进化算法的思想（起 初称之为 Evolutions strategies）。他的这一思想逐渐被其他一些研究者发展。遗传算法 （Genetic Algorithms） 是 John Holland 发明的，后来他和他的学生及他的同事又不断发展了 它。终于，在 1975 年 John Holland 出版了专著《自然系统和人工系统中的自适应》 （Adaption In Natural and Artificial Systems）。 1992 年，John Koza 曾经使用遗传算法编出新的程序去做一些具体的工作。他称他的这种 方法为“进化规划”（Genetic Programming，简称 GP）。其中使用了 LISP 规划方法，这是因 为这种语言中的程序被 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示为“分析树”（Parse Tree），而这种遗传算法就是以这些分析树为 对象的。 II 生物学背景 基因 所有的生物都是由细胞组成的。在每一个细胞中都有想同序列的染色体。染色体是一串 DNA 的片断，它为整个有机体提供了一种复制模式。 lenovo 铅笔 染色体是由基因组成的，或者说染色体就是一块块的基因。每一个基因为一个特定的蛋白 质编码。或者更简单的说，每一个基因为生物体的某一特定特征编码，比如说眼睛的颜色。 所有可能的某一特定特征的属性（比如，蓝色，桔黄色等）被称之为等位基因。每一个基因 在染色体上都有其特定的位置，这个位置一般被称作位点（Locus）。 全部序列的基因物质（或者全部的染色体）称之为基因组（或染色体组）（Genome）。基 因组上特定序列的基因被称作基因型（Genotype）。基因型和后天的表现型两者是有机体的 显性、生理和心理特征比如说眼睛的颜色、智力的基础。 复制（Repeoduction） 在复制中，首先发生的是交叉（Crossover）。来自于父代的基因按照一定的方式组成了新 的基因。新的子代还可能发生变异（Mutation）。变异的意思是 DNA 上的某一些成分发生了 一点点的变化。这些改变可能是由于在由父代到子代的基因复制中出现的误差。 生物体的适应度由生物体自身是否能生存来度量的。 III 搜索空间 搜索空间（Search Space） 在很多情况下,我们解决一个问题就是从一大堆的数据中寻找一个解，而通常这个解都是 混杂在数据中的。所有可行解（Feasible Solution 可行解就是满足了一定约束条件的解）组 成的空间称之为搜索空间（也可以称之为状态空间）。搜索空间中的每一个点都是一个可行 解。每一个可行解都可以被它的函数值或者它的适应度所标记。记住：问题的解就是搜索空 间中的一个点，于是我们就是要从搜索空间中找到这个点。 Example of a search space 这样，求解问题就可以转化为在搜索空间中寻找极值点（最大值或者最小值点）。搜索空 间在求解问题时可能是完全已知的，但一般来说我们只知道一些孤立的点，然后我们逐渐地 生成其它点。问题是，这个搜索过程可能很复杂，我们甚至不知道该去哪里搜索或者该从是 么地方开始搜索。事实上，有很多寻找合适解（注意：不一定是最优解）的方法，比如说爬 山法（Hill Climbing）禁止接近法(Tabu Search),模拟退火算法(Simulated Annealing)以及遗传 算法等等.用遗传算法求解出来的解一般被认为是一个比较好的解,因为我们没有办法 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 它 是最优解. NP 难题(NP-hard) 举一个比较难的 NP 问题,这个问题无法用传统的方法解决。 我们知道很多问题有快速的算法(多项式算法).但是,也有很多问题是无法用算法解决的。 lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 事实上，已经证明很多问题不可能在多项式时间内解决出来。 但是，有很多很重要的问题他们的解虽然很难求解出来，但是他们的值却是很容易求可以 算 出 来 的 。 这 种 事 实 导 致 了 NP 完 全 问 题 。 NP 表 示 非 确 定 的 多 项 式 （Nondeterministic Polynomial），意思是这个问题的解可以用非确定性的算法“猜”出来。如 果我们有一个可以猜想的机器，我们就可以在合理的时间内找到一个比较好的解。 NP-完全问题学习的简单与否，取决于问题的难易程度。因为有很多问题，它们的输出极 其复杂，比如说人们早就提出的一类被称作 NP-难题的问题。这类问题不像 NP-完全问题那 样时间有限的。 因为 NP-问题由上述那些特征，所以很容易想到一些简单的算法――把全部的可行解算一 遍。但是这种算法太慢了（通常时间复杂度为 O（2^n））在很多情况下是不可行的. 现在,没有知道有没有那种精确的算法存在。证明存在或者不存在那种精确的算法这个沉 重的担子就留给了新的研究者了，或许你就是 J。现在很多人认为那种精确的算法是不存在 的，所以他们试图寻找一种替代的算法――比如说这里的遗传算法。 这里的 NP-问题的例子，旅行商问题（Travelling Salesman Problem）或背包问题 （knapsack problem），都是满意性问题。 NP 问题的简述你可以在这里看到。 IV 遗传算法 基本思想 遗传算法受到达尔文进化论的影响很大。在遗传算法中，问题的解是逐渐进化得到的！ 遗传算法的计算从一组可能解开始，这组解被称作种群（Population），在算法中被表示成 基因。我们又把种群中的解拿出来去构成新的一个种群，这是因为我们期望新的种群要比旧 的种群要好！当然，新的种群中的解要有这样的性质，就必须按照它的适应度去选择，适应 度越高，它参与构造新的种群的机会就越大。 这个过程一次又一次的重复，一直到我们所给的约束条件满足为止，比如说种群中解得个 数或者种群的良好程度。 遗传算法的基本结构 1［开始］ 按照问题的特点随机产生一个拥有 N 个然的色体的种群； 2［适应度计算］ 用适应度函数 f(x)计算种群每一个基因的适应度； 3［产生新的种群］ 重复以下步骤，一直到新的母体群建立起来为止； 1）．［选择］按照种群中的各个基因的适应度从中选择两个父代基因（适应度越大，机会 越大）； 2）．［交叉］以一定的交叉概率交叉两个父代的基因以产生子代。交叉完成之后，子代完 完全全是父代的复制； 3）．［变异］以一定的概率对子代基因的的每一个位点（Locus）进行变异； 4）．［接受］把这个子代放到新的种群中去； 4［替换］ 对新产生的种群进行更深入的算法运算； 5［测验］ 如果终止条件满足，则停止；并且把当前母体群中最好的解输出； 6［循环］如果 5 不满足，则转到 2；继续进行 lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 lenovo 附注 对建模的够建有重要作用 lenovo 仅供参考 一些说明 你可以发现这个遗传算法的基本结构是很一般的。在具体的问题中，我们还要做很多工作 以实现算法。 首先的问题是怎样创建一个基因？怎样对它们编码？这些问题都是和对基因的操作（交 叉、变异）密切联系的。编码、交叉和变异我们将在下一章介绍。 下一个问题是怎样从父代种群中选择用来交叉的父代。方法有很多，但是最基本的思想是： 选择好的父代（因为我们认为好的父代可以产生好的子代）。你或许在想：仅仅从产生的子 代中选择基因去构造新的种群可能会丢失掉上一代种群中的很多信息。这确实是事实，我们 可以使用精英主义（Elitism）方法。也就是说，种群中最好的那个基因我们将毫无改变的复 制到新的种群中。显然，任何时刻产生的一个最优解的解都可以存活到算法结束。 还有很多问题我们都将在后面的章节中陆续讨论。 你可能在想，为什么遗传算法能够得到我们需要的结果呢？这个问题部分地可以被 Holland 的模式定理（Schema Theorem）解决。可是，这个模式定理现在被很多人批评，因 为很多人认为它是有问题的。 如果你有兴趣的话，你可以在这里找到更多的资料！ V 遗传算法中的算子 概述 在前面的遗传算法的基本结构中我们注意到交叉和变异是遗传算法中最重要的部分。算法 的结果受交叉和变异的影响最大。当然，在我们讨论交叉和变异之前我们先要介绍一些基因 的信息。 基因的编码 基因在一定能够意义上包含了它所代表的问题的解在里面。最常用的编码方式是二进制串 （Binary String）。于是基因可以表示为： Chromosome 1 1101100100110110 Chromosome 2 1101111000011110 每一个基因用一个二进制串表示，这个二进制串的每一位表示解的某些特征。或者，整个 二进制串表示一个数，比如说在基本的遗传算法的 Applet 中就是如此。 当然，编码的方法有很多。选用什么方法编码主要取决于所要解决的问题本身。比如说， 有的问题直接用整数或者实数来编码可能更好！ 交叉 当我们决定了用什么方法来编码后，我们既可以考虑下一步了――交叉。交叉的本质就 是从种群中选择父代以生成新的母体群。最简单的方法就是随机的选择一个交叉点，在交叉 点之前的部分来自父代 1 号基因，交叉点之后的部分来自来父代的 2 号基因。 用图可以表示为上述过程如下：（｜表示交叉点） lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 Chromosome 1 11011 | 00100110110 Chromosome 2 11011 | 11000011110 Offspring 1 11011 | 11000011110 Offspring 2 11011 | 00100110110 当然，交叉的方式也很多。比如说一个直接的对这个方法的改良就是多选择几个交叉点。 交叉可能很复杂，这有可能是基因编码方法的原因！对特定的问题我们要选择特定的交叉方 法以使得遗传算法的结果比较好！ 变异 一旦交叉完成，变异就要开始了。变异的目的是防止种群中的解跑到局部极值去。变异是 对子代的随机的改变。对二进制串编码方式来说，我们可以随机地改变子代中的某个位点的 数字（1 变为 0，或者 0 变为 1）。于是，变异可以用表表示如下： Original offspring 1 1101111000011110 Original offspring 2 1101100100110110 Mutated offspring 1 1100111000011110 Mutated offspring 2 1101101100110110 显然，变异取决于编码方式和交叉方法。比如说变异可以是交叉两个基因。 VI 遗传算法的一个例子 求函数最小值 问题 在搜索空间那一章中我们已经提到:我们遇到的很多问题都可以转化为求解一个函数的极 值。下面这个例子就是恰好是这种问题。 给定一些函数，然后用遗传算法求这些函数在给定空间中的最小值。对于其他一些问题， 通过定义搜索空间和适应度函数，我们通常可以转化为这种问题。 VII 遗传算法中的一些参数 交叉和变异的概率 遗传算法中有两个基本参数：交叉的概率和变异的概率。 交叉的概率是说交叉行为发生的几率大小，如果几率为 0，那么子代就完完全全和父代一 样。只要存在交叉，子代的基因是由几个父代的基因的中的片段组合而成的，所以就不完全 和父代一样。如果交叉 100％的发生，那么所有的子代都是由交叉产生的。如果交叉的概率 为 0％，那么子代就是父代的完全复制。（注意：但是，这并不意味着子代就和父代完全一 样） 交叉过程的目的就是希望新的基因是由旧的基因中好的部分组合而成的，从而新的基因比 lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 原先的基因要好。当然把旧的种群中的一部分基因完全保留到下一代中去也是很有意义的。 变异的概率说的是基因的某些部分发生变异的概率。如果没有变异的话，子代就和交叉过 的父代没有任何区别。只要存在变异，子代的基因就会发生改变。如果变异的概率为 100％， 那么所有的子代都会改变。如果交叉的概率为 0％，那么子代就不会改变。变异的目的是为 了防止遗传算法的解跑到局部极值点，所以，变异应该发生。但是变异不能发生的太频繁， 否则的话就变成了随机搜索了。 其他一些参数 遗传算法中还有一些其它参数，比如说种群的大小就是一个很重要的参数。 种群的大小是说每一代种群中所含基因的多少。如果其中的基因太少，则遗传算法中进行 交叉操作的机会就越少，所以导致我们的算法只是考察了搜索空间的一部分。另一方面，如 果基因太多，则遗传算法的速度就会变慢。进一步的研究表明，在一定的条件下（这些条件 主要由问题本身和编码方法决定）增大种群的大小是没有意义的，因为它不会加快遗传算法 的计算速度。 VIII 函数的极值点 问题 这里又是一个求函数极值的问题，但是在这个例子中我们的函数是一个二元函数。 例子(此处是 JAVA 程序,略) IX 选择算子 简介 正如我们在遗传算法基本结构中已经知道的那样,用来交叉的基因是从从父代种群中选择 出来.那么怎样选择这些基因呢?根据达尔文的进化论,适应环境的（好的）基因将生存下来并 且交叉产生新的一代。选择好的基因的方法有很多，比如轮盘赌选择方法 （Roulette Wheel Selection）、（Boltman Selection）、锦标赛选择方法（Tournament Selection）、 分级选择方法（Rank Selection）、稳定状态选择方法（Steady State Selection）等等。 在本章中我们将选择部分做深入一点的说明。 轮盘赌选择方法（Roulette Wheel Selection） 父代的选择是根据他们的适应度做出的。基因越是适应环境，那么它被选择到的机会就越 大。想像一个轮盘赌的机器上放置了种群中所有的基因。每一个基因所占的地方的大小和它 的适应度成正比。如下图所示： lenovo 铅笔 lenovo 铅笔 然后开始扔弹子，扔到那个地方就把对应的基因拿出来。显然，适应度越大的基因被选到 的机会就越大。 这个过程可以被下面的这个算法来模拟： 1．［求和］ 计算所有种群的适应度的和 S； 2．［选择］ 在区间（0，S）上随机的产生一个数 r； 3．［循环］ 从某个基因开始，逐一取出基因来，把它的适应度加到 s 上去（s 开始为 0），如 果 s 大于 r，则停止循环并返回当前基因； 当然，第一步在计算中只需要执行一次。 分级选择方法（Rank Selection） 前面这中选择方法很简单，但是当适应度变化比较大时就会有问题。比如说，当前种群中 最好的基因（适应度最大）的适应度占 S 的 90％的时候，那么其它基因就很少有机会被选 择到。 分级选择方法首先把种群分几个等级。然后，每一个基因收到各自等级中的适应度。我们 定义最差的等级的适应度为 1；次差的为 2 等等，最好的那个级适应度定义为 N（N 就是种 群中基因的个数）。 通过下面这两个图，你可以看看在分级前后有什么改变。 Situation before ranking (graph of fitnesses) Situation after ranking (graph of order numbers) 这样，所有的基因都有机会被选择到。但是这样又会导致算法的收敛速度变慢，因为最好 的基因与其它基因的差别被缩小了。 稳定状态选择方法（Steady State Selection） 其实，这并不是选择父代的特殊方法。这种方法的主要思想是有很多的基因要保留到下一 lenovo 铅笔 lenovo 附注 用得上 lenovo 铅笔 lenovo 铅笔 代中！ 于是遗传算法将按照如下的方式进行： 在每一代中选择一少部分基因（与适应度相符合）来构造子代。接着，父代中一部分基因 （与适应度不符合的）被新产生的子代所代替，父代中其它的人基因被保留到新的一代中。 精英主义 精英主义思想我们已经在前面介绍过了。这种思想是说当利用交叉和变异产生新的一代 时，我们有很大的可能把在某个中间步骤中得到的最优解丢失。 精英主义正如它的语义所蕴含的那样，在每一次产生新的一代时，我们首先把当前最优解 原封不动的复制到新的一代中。然后按照我们前面所说的那样做就行。 精英主义方法可以大幅提高运算速度，因为它可以防止丢失掉找到的最好的解！ X 编码（Encoding） 简介 当你开始用遗传算法求解问题时，基因的编码是一个很重要的问题。编码方法是依赖于问 题本身的。 在这一章中我们将介绍几种在实际中已经取得成功的方法。 二进制编码 二进制编码是最常见的一个编码方法，这主要是因为用遗传算法编的第一个程序就是用二 进制编码的。 在使用二进制编码时，每一个基因就是一个由 0 或者 1 组成的字符串。 Chromosome A 101100101100101011100101 Chromosome B 111111100000110000011111 Example of chromosomes with binary encoding 二进制编码的基因 使用二进制编码时，即使等位基因的数量不大，我们也可以得到很多种可能的基因。另一 方面，这种方法对于很多问题来都很不自然，所以有时候在交叉和变异结束后还要做一些调 整。 ――――――――――――――――― 一个问题：背包问题（Knapsack Problem） 问题：这里有一些给定价值和大小的东西。背包的容积是给定的。请你在不超过背包容积的 情况下往背包中装东西，以使得背包中东西的价值达到最大。 编码方法：二进制的每一位代表对应的东西是否在背包中。 ――――――――――――――――― 互换（排列，顺序）编码（Permutation Encoding） 互换编码可以用来解决排序问题，比如说旅行商问题（Travelling Salesman Problem）和任 务排序问题（Task Ordering Problems）。 lenovo 铅笔 Chromosome A 1 5 3 2 6 4 7 9 8 Chromosome B 8 5 6 7 2 3 1 4 9 Example of chromosomes with permutation encoding 互换编码只是对排序问题有用。即使是排序问题中的某些问题采用互换编码，在交叉和变 异后还必须作出一些调整以使得基因保持一致（比如，有可能产生实数）。 ――――――――――――――――― 一个问题：旅行商问题（Travelling Salesman Problem）――TSP 问题： 给定一些城市和这些城市间的距离。旅行商要到所有这些城市中去，但是它不能花 太多时间。寻找一个到所有这些城市的顺序以使得旅行路程最短。 编码方法：基因表示的是访问各个城市的顺序。 ――――――――――――――――― 值编码（Value Encoding） 在很多问题中我们还可以采用直接的值编码,也就是说用一些比较复杂的数来编码,比如说 实数。因为二进制编码在这类问题中不好用。 在值编码中，每个基因就是一串取值。这些取值可以是与问题有关任何值：整数，实数， 字符或者其他一些更复杂的东西。 Chromosome A 1.2324 5.3243 0.4556 2.3293 2.4545 Chromosome B ABDJEIFJDHDIERJFDLDFLFEGT Chromosome C (back), (back), (right), (forward), (left) Example of chromosomes with value encoding 值编码对于一些特殊的问题是很有效的。但是，对于这种编码方法它的交叉和变异算子就 要按照问题和编码方法具体的去设计。 ――――――――――――――――― 一个问题：为神经网络寻找权重（Finding Weights For Neural Networks） 问题：这里有一些给定了结构的神经网络算法。求要输入的神经元的权重以使得网络有我们 想要的输出。 编码方法：用一个实数表示对应的输入的权重。 ――――――――――――――――― 树形编码（Tree Encoding） 树形编码主要用于遗传规划中的演化编程或者表示。 在树形编码中，每个基因都是由数字或符号组成的树形结构。这些符号可以是函数，也可 以是规划中使用的一些命令。 数形编码的一个例子 lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 Chromosome A Chromosome B ( + x ( / 5 y ) ) ( do_until step wall ) Example of chromosomes with tree encoding 数形编码对演化规划这类问题很适合.规划语言 LISP 经常在其中使用,因为规划中使用的 很多程序可以用数形结构很容易的表示出来,从而交叉算子和变异算子相对也简单. ――――――――――――――――― 一个问题：为给定的自变量和函数值选择一个函数（Finding A Function From Given Values） 问题：给定了很多组输入和输出。请你为这些输入输出选择一个函数，使得这个函数把每个 输入尽可能近地映射为输出。 编码方法：基因就是树形结构中的一些函数。 ――――――――――――――――― XI 交叉和变异 简介 交叉和变异是遗传算法中的两个最基本的算子。遗传算法的好坏由他们决定。这两个算子 的类型和实现是由问题本身和编码方法决定的。 交叉和变异的方式有很多。这一章我们我们介绍几种例子，通过这些例子你可以去体会交 叉算子和变异算子的构造方法。 二进制编码 1． 交叉算子 ◆ 单交叉点交叉算子（Single Point Crossover）:选择一个交叉点,子代在交叉点前面的基因 从一个父代基因那里得到,后面的部分从另外一个父代基因那里得到; 11001011+11011111 = 11001111 ◆ 双交叉点交叉算子（Two Point Crossover）: 选择两个交叉点,子代基因在两个交叉点间 部分来自一个父代基因,其余部分来自于另外一个父代基因. lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 11001011 + 11011111 = 11011111 ◆ 均匀交叉算子 (Uniform Crossover):子代基因的每一个位点是随机地来自于两个父代基 因中的一个的; 11001011 + 11011101 = 11011111 ◆ 算术交叉算子（Arithmetic Crossover）:对父代基因做一个代数运算从而产生一个新的 基因。下面就是使用和运算（AND）实现的： 11001011 + 11011111 = 11001001 (AND) 2． 变异算子 ◆ 位点转换算子（Bit Inversion）：选择一些位点然后将这些地方的 0，1 互换； 11001001 => 10001001 互换编码 1． 交叉算子 ◆ 单交叉点交叉算子（Single Point Crossover）:选择一个交叉点，子代的从初始位置出发 的部分从一个基因复制，然后在另一个基因中扫描，如果某个位点在子代中没有，就把它添 加进去； 注意：这个算法交叉点后面的部分可以有很多中具体的方法； (1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7) lenovo 铅笔 lenovo 铅笔 lenovo 铅笔 2． 变异算子 ◆ 变序算子（Order Changing）：从子代基因中选择两个数，交换它们的位置； (1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7) 值编码 1． 交叉算子 上面二进制编码中所由交叉算子都适用。 2． 变异算子 ◆ 填值算子（Adding Crossover）：对于实数编码的算法，可以给选定的一些数添加一个 小的实数（扰动）： (1.29 5.68 2.86 4.11 5.55) => (1.29 5.68 2.73 4.22 5.55) 树形编码 1． 交叉算子 ◆ 树交叉算子（Tree Crossover）：在两个父代基因上选一个交叉点（位置），然后把他们 在交叉点下面的部分交换就行； 2． 变异算子 ◆ 改变交叉算子（Changing Operator）：选择一些节点，然后把他们换掉； XII 旅行商问题（TSP）（Travelling Salesman Problem） 问题背景 旅行商问题（TSP）：给定一些城市和这些城市间的距离。旅行商要到所有这些城市中去， 但是它不能花太多时间。寻找一个到所有这些城市的顺序以使得旅行路程最短。换句话的说， 就是要从有 N 个节点的完全图上寻找最短 Hamiltonian 遍历。 算法实现 我们将使用含有 16 个基因的种群，使用交换编码方式――你可以在前一章中找到有关交 换编码方式的解释，以及怎样用这种编码方法来对 TSP 问题编码。这个 TSP 是在定义了欧 氏距离的完全图上求解的，所谓完全图就是指图中的每一个节点都和其它节点直接相连。 注意，增加或者删除城市时要重新创建新的基因，然后重新开始。 你可以从下面这些交叉和变异算子中选择一个交叉算子和变异算子使用。我给它们简单的 介绍。 交叉算子 ● 一点算法：子代的基因一部分从父代一个基因上按父代的位置复制，其它部分按照父代 第二个基因上原来的顺序复制到子代上； ● 两点算法：子代的基因有两个部分从父代一个基因上按父代的位置复制，其它部分按照 父代第二个基因上原来的顺序复制到子代上； ● 不交叉：不交叉，完从父代复制过来； 变异算子 ● 普通随机算法：选择一少部分城市，把它们的顺序交换； ● 改善随机算法：选择一少部分城市，如果交换顺能改善解则交换它们的位置； ● 改善对称算法：对称地选择一些城市，如果交换顺能改善解则交换它们的位置； ● 优化随机算法：先进行“普通随机算法”，然后进行“改善随机算法”； ● 优化对称算法：先进行“普通随机算法”，然后进行“改善对称算法”； ● 不变异：不变异； 例子 下面这个例子就是一个 TSP 的演示，按“Change View”显示种群向最优解收敛的过程或者 逆序显示。你可以用鼠标在图上添加或者删除城市。添加或者删除城市后在城市中间就会产 生随机的路线，因为程序已经建立了新的种群。当然，别忘记我们是在完全图上解 TSP 问 题的。 选择不同的交叉算子和变异算子让程序去计算（并且不断增加城市的数量），看看这个遗 传算法程序会有哪些变化。 这个程序已知的 BUG：在进行操作之前，先点击一下 Change View，否则在一些浏览器上 你会发现程序运行时图形没有任何变化。我是用的是 CardLayout，我不知道怎样让这个 Applet 正常工作。如果你知道，请你给我发 Email 告诉我。 XIII 推荐 遗传算法中的参数： 这一章中我们给那些想要使用遗传算法来解决问题的人推荐一些材料。当然,这些推荐的 材料都是很一般的。所以在你的具体问题之中，你可能不得不自己实验某些参数，因为到目 前为止，还没有一个适用于遗传算法所有应用领域的关于算法参数的理论。 下面这些推荐的材料都是遗传算法研究中实验得出的结果，这些结果很多只适用于二进制 编码。 ● 交叉率 交叉率一般来说应该比较大，推荐使用 80％-95％。（还有自己得出的结果说 60％最好。） ● 变异率 变异率一般来说应该比较小，据报道使用 0.5％-1％最好。 lenovo 铅笔 lenovo 铅笔 ● 种群的规模 让人感到惊奇的是，比较大的种群的规模并不能优化遗传算法的结果。种群的大小推荐使 用 20-30，（还有自己得出的结果说 50-100 最好。）一些研究表明，种群规模的大小取决于编 码的方法，具体的说就是编码串（Encoded String）的大小。也就是说，如果说采用 32 位为 基因编码的时候种群的规模大小最好为 32 的话，那么当采用 16 位为基因编码时种群的规模 相应应变为原来的两倍。 ● 选择算法 推荐使用基本的轮盘赌选择方法，但是有时候分级选择方法可能会更好。查看 选择 那一 章，你可以看看它们的优点和缺点。当然还有一些比较复杂的方法可供使用，这些算法可以 在遗传算法程序运行过程中自动改变参数的取值，基本上算法的行为和模拟退火算法 （Simulated Annealing）差不多。如果你没有使用特别的方法来保存已经发现的最优值的话， 你 一 定 要 使 用 精 英 主 义 方 法 。 你 也 可 以 尝 试 使 用 一 下 稳 定 状 态 选 择 方 法 （Steady State Selection）。 ● 编码方法 编码方法取决于问题本身和问题中实例的个数。查看 编码 这一章你可以得到一些建议或 者这里有一些其它资源。 ● 交叉和变异的类型 这两种算子取决于问题和编码方法。查看 算子 你可以得到一些建议。你也可以查看下面 这些站点。 遗传算法的应用 遗传算法已经在很多复杂问题（比如说 NP-难题）、机器学习和简单的进化规划中得到了 使用。遗传算法在一些艺术领域也取得了很大成就，比如说进化图片和进化音乐。 遗传算法的优势在于他的并行性。遗传算法在搜索空间中非常独立地移动（按照基因型而 不是表现型），所以它几乎不可能像其它算法那样“粘”在局部极值点。 遗传算法更容易实现。一旦你有了一个遗传算法的程序，如果你想解决一个新的问题，你 只需要针对新的问题重新进行基因编码就行。如果编码方法也相同，那你只需要改变一下适 应度函数就可以了。当然，选择编码方法和适应度函数是一件非常难的问题。 遗传算法的缺点是它的计算时间太长。它们可能比其他任何算法需要的时间都长。当然， 对于今天的高速计算机来说，这已经不是个大问题了。 为了让读者更好地了解遗传算法所解决的问题,这里有一个关于遗传算法应用的小列表: ● 非线性动态系统——预测，数据分析； ● 神经网络的结构和权重设计； ● 自动控制导弹的轨道设计； ● 进化 LISP 规划（遗传规划）； ● 战略计划； ● 蛋白质分子的形状的寻找； ● 旅行商问题和时间序列排序问题； ● 构图的函数问题； lenovo 铅笔 更多的资料你可以通过附件中的 链接 找到。 ENCORE, the EvolutioNary COmputation REpository network ftp://alife.santafe.edu/pub/USER-AREA/EC/ (there are also some others nodes) FAQ - The Hitch-Hiker's Guide to Evolutionary Computation ftp://alife.santafe.edu/pub/USER-AREA/EC/FAQ/www/index.html FAQ - Genetic programming http://www-dept.cs.ucl.ac.uk/research/genprog/gp2faq/gp2faq.html The Genetic Algorithms Archive - many links, information about mailing list, some fun stuff http://www.aic.nrl.navy.mil:80/galist/ Artificial Life Online - links, if you are looking for some introductory materials, look here http://alife.santafe.edu/ Yahoo! Science:Computer Science:Algorithms:Genetic Algorithms - directory of other links http://www.yahoo.com/Science/Computer_Science/Algorithms/Genetic_Algorithms/ Usenet groups comp.ai.genetic and comp.ai.alife 关于这些页面 这些页面是 Czech Technical University 大学的学生 Marek Obitko1998 年 9 月在 Hochschule für Technik und Wirtschaft Dresden (FH) (University of Applied Sciences)期间开发 而成的。 最初几个版本的 JAVA Applets 是 1998 年夏季学期时在 Czech Technical University 在 assoc 教 授 的 指 导 下 写 成 的 。 在 Dresden 停 留 期 间 会 又 受 到 Hochschule für Technik und Wirtschaft Dresden 的 Walter P?tzold 教授的指导。 页面和 JAVA Applets 是由 Marek Obitko1998 年创作的。如果你有什么意见和建议，你可 以通过 Email 和作者联系。 答疑 1． 问题：Applets 不工作，我看到就是错误。我该怎么办？ 回答：首先，你先看一看 推荐浏览器。 你的浏览器可能不是 Java1.1 版本，甚至于有一些浏览器虽然说是支持 Java1.1 版本，其 实只支持 Java1.0 版本（其中没有新的事件驱动模式）。我推荐你升级你的浏览器。 还有时候错误发生是因为传播过程中，在这种情况下你只需要重新下载一次或者简单地过 一段时间后再试一次就可以了。如果类似于 Class Population Not Found 等的错误发生，你可 以重新下载 http://cs.felk.cvut.cz/~xobitko/ga/java/Population.class 然后连同 Applet 一起把网页 下载下来就可以运行了。 2． 问题：我有一个有关一个关于遗传算法的问题，你能帮我吗？ 回答：当然可以的。你可以给我发 Email。如果我有时间（这种情况不多）我就会帮助你的。 最好，你把问题 Post 到新闻组 comp.ai.genetic 上，在那里你的问题会有更多的机会被某些 人回答的。 3． 问题：这个网站可以作为一个文件下载吗？ 回答：可以。可以作为一个压缩的 PDF 文件下载。在这里下载 Acrobat Reader ，此软件可 以阅读.那个 PDF 文件。当然你无法看到相关的 Applet 演示。 4． 问题：你有没有一个类似的关于神经网络的主页？ 回答：我很想找时间去做一个。目前你可以浏览下面这个 页面 ，上面有一个使用后传播神 经网络方法制作的说明性的预报 Applet。 5． 问题：有没有这个网站的翻译版本？ 回答：这里本网站上网日语版本和汉语版本。 日语版本在 http://gekms3.tmit.ac.jp/mana/file/ga/index.html 由 Ishii Manabu 翻译 如果我有时间我会把他翻译成捷克语。 欢迎大家把这个站点翻译成其它语言，如果你想翻译的话，请你联系我。