遗传算法-蔡自兴,徐光佑.doc

遗传算法 生物种群的生存过程普遍遵循达尔文的物竞天择、适者生存的进化准则。种群中的个体根据对环境的适应能力而被大自然所选择或淘汰。进化过程的结果反映在个体结构上，其染色体包含若干基因，相应的表现型和基因型的联系体现了个体的外部特性与内部机理间的逻辑关系。生物通过个体间的选择、交叉、变异来适应大自然环境。生物染色体用数学方式或计算机方式来体现就是一串数码，仍叫染色体，有时也叫个体；适应能力用对应一个染色体的数值来衡量；染色体的选择或淘汰的问题是按求最大还是最小问题来进行的。 20世纪60年代以来，如何模仿生物来建立功能强大的算法，进而将它们运用于复杂的优化问题，越来越成为一个研究热点。进化计算（evolutionary computation）正是在这一背景下孕育而生的。进化计算包括遗传算法（genetic algorithm, GA）、进化策略（evolution strategy）、进化编程（evolutionary programming）和遗传编程（genetic programming）,从本节起将逐一对它们进行讨论。 遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化有哪些信誉好的足球投注网站算法，是对生物进化过程进行的一种数学仿真，是进化计算的一种最重要的形式。遗传算法用与传统的数学模型截然不同，它为那些难以找到传统数学模型的难题找出了一个解决方法。同时，进化计算和遗传算法借鉴了生物科学中的某些知识，从而体现了人工智能这一交叉学科的特点。自从霍兰德（Holland）于1975年在它的著作“Adaptation in Natural and Articial Systems” 中首次提出遗传算法以来，经过近30年的研究，现在已发展到一个比较成熟的阶段，并且在实际中得到很好的应用。本节将介绍遗传算法的基本机理和求解步骤，使读者了解什么是遗传算法，它是如何工作的，并评价遗传算法研究的进展和应用情况。 4．5．1遗传算法的基本机理 霍兰德的遗传算法通常称为简单遗传算法（SGA）。现以此作为讨论的主要对象，加上适当的改进，来分析遗传算法的结构和机理。 首先介绍主要概念。在讨论中会结合推销员旅行问题（TSP）加以说明：设有n个城市，城市i和城市j之间的距离为d（i, j）(i, j=1,……n)。TSP问题是要寻找遍访每个城市恰好一次的一条回路，且其路径总长度最短。 编码与解码 许多应用问题的结构很复杂，但可以化为简单的位串形式编码表示。将问题结构变换位串形式编码表示的过程叫做编码；相反的，将位串形式编码表示变换位原问题结构的过程叫做解码或译码。把位串形式编码表示叫做染色体，有时也叫做个体。 GA的算法过程简述如下。首先，在解空间中取一群点，作为遗传开始的第一代。每个点（基因）用一个二进制数字串表示，其优劣程度用一个目标函数——适应度函数（fitness function）来衡量。 遗传算法最常用的编码方法是二进制编码，其编码方法如下。 假设某一参数的取值范围是[A,B], AB。用长度为的二进制编码串来表示该参数，将[A, B]等分成个子部分，记每一个等分的长度为，则它能够产生种不同的编码，参数的对应关系如下： 0 ―― A 1 ――A+ 2l－1 ――B 其中 假如某一个体的编码是： 则上述二进制编码所对应的解码公式为 二进制编码的最大缺点是长度较大，对很多问题用其他编码方法可能更有利。其他编码方法主要有：浮点数编码方法、格雷码、符号编码方法、多参数编码方法等。 浮点数编码方法是指个体的每个染色体用某一范围内的一个浮点数来表示，个体的编码长度等于其问题变量的个数。因为这种编码方法使用的是变量的真实值，所以浮点数编码方法也叫做真值编码方法。对于一些多维、高精度要求的连续函数优化问题，用浮点数编码来表示个体时将会有一些益处。 格雷码是其连续的两个整数所对应的编码值之间只有一个码位是不相同的，其余码位都完全相同。例如十进制数7和8的格雷码分别为0100和1100，而二进制编码分别为0111和1000。 符号编码方法是指个体染色体编码串的基因值取自一个无数值含义而只有代码含义的符号集。这个符号集可以是一个字母表，如{A,B,C,D,……}；也可以是一个数字序号表，如{1,2,3,4,5,……}；还可以是一个代码表，如{x1, x2, x3, x4, ……}，等等。 对应推销员旅行问题，就采用符号编码方法，按一条回路中城市的次序进行编码。例如，码串134567829表示从城市1开始，依次是城市3，4，5，6，7，8，2，9，最后回到城市1。 一般情况是从城市开始，依次经