《遗传算法讲义》由会员分享，可在线阅读，更多相关《遗传算法讲义（61页珍藏版）》请在金锄头文库上搜索。
1、遗传算法简介20世纪40年代以来，科学家不断努力从生物学中寻求用 于计算科学和人工系统的新思想、新方法，很多学者对 关于从生物进化和遗传的机理中发展出适合于现实世界 复杂适应系统研究的计算技术自然进化系统的模型 和模拟进化算法等 ，进行了开拓性的长期探索和研究， Holland及其学生首先提出的遗传算法（GA）就是一个重 要的发展方向。自然界的进化是一上不断循环的过程，在这一过程中， 生物群体也就不断地完善和发展，可见，生物进化过程 本质上是一种优化过程，在计算科学上具有直接的借鉴 意义。在计算机技术迅猛发展的时代，生物进化过程不 仅可以在计算机上模拟实现 ，而且还可以模拟进化过程 ，创立新的
2、优化计算方法，并应用到复杂工程领域中， 这就是GA等 一类模拟自然进化的计算方法的思想源泉。*遗传算法的发展1962年,John Holland在Outline for a Logic Theory of Adaptive Systems 一文中,提出了所谓监 控程序 的概念,即利用群体进化模拟适应性系统的思想,他 注意到在建立智能机器的研究中,不仅可以完成单 个生物体的适应性改进,而且通过一个种群许多代 的进货 也可以产生非常好的适应性效果。为了获 得一个好的学习方法，仅靠单个策略的改进是不 够的，采用多策略的群体系列往往能产生显著的学 习效果。在这里他提出了群体、适应值 、选择 、 变异、
3、交叉等基本概念。1967年John Holland的学生J.D.Bagley通过对 跳棋 游戏参数的研究，在博士论文中首次提出了“遗传 算法”一词。*1975年，Holland出版了专著自然一人工系统中的适应 性行为（Adaptation in Natural and Artificial System） ，该书系统地阐述了遗传算法的基本理论和方法，提出 了对遗传 算法的理论发展极为重要的模式和理论，其中 首次确认也选择、交叉、变异等遗传算子，以及遗传算 法的隐并行性，并将遗传算法应用于适应性系统模拟、 函数优化、机器学习、自动控制等领域。*1975年之后，遗传算法作为函数优化器不但在各 个领
4、域得到广泛应用，而且还丰富和发展了若干 遗传算法的基本理论。1980年，Bethke对函数 优化GA进行了研究，包括应用研究和数学分析 。Smith在1980年首次提出使用变长位串的概念 ，这在某种程度上为以后的遗传规 划奠定了基础 Goldberg,Davis,Grefenstette,Bauer,Srinivas和 Parnaik等大批研究人员对遗传 算法理论的基本 框架和遗传算子进行了构建和改进，并将遗传算 法分别应用于工程设计、自动控制、经济金融 、博弈问题、机器学习等诸多领域中。*1989年，David Goldberg 出版了Genetic Algorithms in Search
5、 Optimization and Machine Learning一书，这是第一本遗传算法教科书， 它是对当前算法领域研究工作的全面而系统的总 结，因而也成为引用最多的参考书之一。1992年，Koza教授出版了第一本遗传规 划专著 Genetic Programming ,两年之后又出版了第二本 关于遗传规 划的专者，他通过大量的实验说 明 了遗传规 划能够成功地解决一类复杂问题 ，为 基于符号表示的函数学习问题 增添了一个强有力 的工具。*1985年在美国召开了第一届遗传算法国际会议， 即ICGA。这次会议是遗传算法发展的重要里程 碑，此会以后每隔一年举行一次。从1999年起， ICGA和
6、GP的系列会议合并为每年一次的遗传和 进化国际会议。*遗传算法的生物学基础生物在自然界中的生存繁衍，显示出了其对自然 环境的自适应能力。受其启发， 人们致力于对 生物各种生存特性的机理研究和行为模拟，为人 工自适应系统的设计和开发提供了广阔的前景。遗传算法(Genetic Algorithms，简称GAs)就是 这种生物行为的计算机模拟中令人瞩目的重要成 果。基于对生物遗传和进化过程的计算机模拟， 遗传算法使得各种人工系统具有优良的自适应能 力和优化能力。*遗传算法概述*1. 1. 复制复制生物的主耍遗传方式是复制。遗传过程中，父代的遗传物质DNA被复制 到子代。即细胞在分裂时，遗传物质DNA
7、通过复制(Reproduction)而转移到 新生的细胞中，新细胞就继承了旧细胞的基因。2. 2. 交叉交叉有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉 (Crossover)而重组，亦即在两个染色体的某一相同位置处DNA被切断，其 前后两串分别交义组合而形成两个新的染色体。3. 3. 变异变异在进行细胞复制时，虽然概率很小，仅仅有可能产生某些复制差错， 从而使DNA发生某种变异(Mutation)，产生出新的染色体。这些新的染 色体表现出新的性状。我们可以得出：*(1) 生物的繁殖过程是由其基因的复制过程来完成的。（继承）(2) 通过同源染色体之间的交叉或染色体的变异会产生新的物种
8、，使生物呈现新的性状。（更新）(3) 对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。（优化）遗传算法经过几十年的发展已不单单是一个 模式固定的算法，而已经成为一个算法簇。我 们主要就基本遗传算法进行讲解。遗传算法内涵1.2. 1.2. 基本遗传算法的运算过程基本遗传算法的运算过程编码编码 将实际问题转化为计算机能够“看懂”的代码。（比如二进制码）选择选择( (复制复制) )： 根据各个个体的适应度，按照一定的规则或方法，从第t代群体P(t) 中选择出一些优良的个体遗传到下一代群体P(t+1)中；交叉：交叉： 将群体P(t)内的各个个体随机搭配成对，对每一对个
9、体，以某个概 率(称为交叉概率）交换它们之间的部分染色体；变异：变异： 对群体P(t)中的每一个个体，以某一概率(称为变异概率)改变某一 个或某一些基因座上的基因值为其他基因值。检验检验： 是否已达到要求或达到遗传代数。结束结束： 达到目标要求或达到遗传代数。*实际问题参数集编码群体t计算适值运算：复制交叉变异群体t+1满足要求？解码改善或解决实际问题群体t+1群体tYN*编码的重要性编码的重要性编码是应用遗传算法时要解决的首要问题，也 是设计遗传算法的一个关键步骤。编码方法除了决 定个体的染色体排列形式之外，它还决定了个体从 搜索空间的基因型变换到解空间的表现型时的解码 方法;编码方法也影响
10、到交叉算子、变异算子等遗 传算子的运算方法。由此可见，编码方法在很大程度上决定了如何 进行群体的遗传进化运算以及遗传进化运算的效率 。*1.编码*编码原则编码原则 针对一个具体应用问题，如何设计一种完美的编码方案一直是遗传算法的应 用难点之一，也是遗传算法的一个重要研究方向。目前还没有一套既严密又完整 的指导理论及评价准则能够帮助我们设计编码方案。有两条操作性较强的实用编码 原则(又称为编码规则)：编码原则一(有意义积木块编码原则)：应使用能易于产生与所求问题相关的且具有 低阶、短定义长度模式的编码方案。 编码原则二(最小字符集编码原则)：应使用能使问题得到自然表示或描述的具有最 小编码字符集
11、的编码方案。 由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的编码方法。 总的来说，这些编码方法可以分为三大类：二进制编码方法 浮点数编码方法 符号编码方法二进制编码*二进制编码方法是遗传算法中最常用的一 种编码方法，它使用的编码符号集是由二进 制符号0和1所组成的二值符号集0，1，它 所构成的个体基因型是一个二进制编码符号 串。*(1)(1)编码编码假设某一参数的取值范围是umax, umin，我们用长度为l的二进制编码符串来号表示该参数，则它总共能够产生 2l种不同的编码，参数编码时的对应关系如下：umin 00000000000000000umin + 00000000000
12、000011umax 1111111111111111=2l1二进制编码的编码精度为： = Umax umin2l 1 *(2) (2) 解码解码假设某一个体的编码是：x： bl bl-1 bl-2b2b1则对应的解码公式为：x = umin + ( bi 2i-1) i=1Umax umin2l 1 例如，对于 x 0, 1023 ，若用 10 位长的二进制编码表示 该参数的话，则下述符号串：x：0010101111 就可表示一个个体，它所对应的参数值是 x175。编码精度为 = 1。l *(3) (3) 二进制编码方法的优点：二进制编码方法的优点：. 编码、解码操作简单易行；. 交叉、变异
13、等遗传操作便于实现；. 符合最小字符集编码原则；. 便于利用模式定理对算法进行理论分析。*浮点数编码个体的每个基因值用某一范围内的一个浮 点数来表示；个体的编码长度等于其决策变量 的个数。因为这种编码方法使用的是决策变量 的真实值，所以浮点数编码方法也叫做真值编 码方法。*在研究自然界生物的遗传和进化现象时，生物学家使 用适应度这个术语来度量某个物种对于其生存环境的适 应程度。与此相类似，遗传算法中也使用适应度这个概 念来度量群体中各个个体在优化计算中有可能达到或接 近于或有助于找到最优解的优良程度。定义：度量个体适应度的函数称为适应度函数。 2、适应度函数目标函数与适应度函数遗传算法的一个特
14、点是它仅使用所求问题的目标函数值就可以得到下一步的 有关搜索信息。最优化问题可分为两大类，一类为求目标函数的全局最大值，另一类为求目标函数的全局最小值。由目标函数值 f(x) 到搜索空间中对应个体的适应度函数值F(x)的转换，对于求最大值的问题，作下述转换： *F(X) =f(X)+Cmin f(X)+Cmin 00 f(X)+Cmin 0对于求最小值问题，变换如下：F(X) =Cmax - f(X) Cmax-f(X) 00 f(X) Cmax *3、选择遗传算法中的选择操作用来确定如何从父代群体中 按某种方法选取哪些个体遗传到下一代群体中的一 种遗传运算。选择操作建立在对个体的适应度进行
15、评 价的基础上。常用的选择算子有以下几种：1.1.比例选择比例选择各个个体被选中的概率与其适应度大小成正比。 设群体大小为M，个体i的适应度为Fi，则个体i被选中的概率pis为：Mpis= Fi / Fii=1i=1,2,M* 特点特点 适应度越高的个体被选中的概率也越大， 适应度越低的个体被选中的概 率也越小。 缺点缺点 由于是随机操作的原因，这种选择方法的 选择误差比较大，有时甚至连 适应度较高的个 体也选择不上。2 2、分级选择、分级选择 遗传算法中个体适应度数值上的差别有时会很大， 尤其是在算法的早期这种差别更是悬殊。因此，个别 特优个体会多次被选中进行复制，经过几代后它们在 群体中数目愈来愈多，冲淡了群体的多样性。因此， 人们提出分级的概念，用连续渐变的分级代替数值悬 殊的适应度。*【方法方法】设群体中有m个个体，将它们按降序方法依次排序，规 定个体优劣的等级依次为：1，2，3，i，M。采用线性分级， 使各个个体被选中的可能性有如下线性 关系：p(i) = q - ( i -1 )d 其中， q 最优个体被选中的概率；d 相邻个体被选中概率之差。上述线性关系使p(i)构成等差级数，即：q， q - d， q 2d，
