遗传算法及其育种.doc

PAGE PAGE 7 遗传算法及其育种 1 前言 遗传算法（GA，Genetic Algorithm）是一种逐次迭代方法，但是，遗传算法是模拟生物的遗传和进化过程而发展起来的一种搜索和优化方法，其搜索过程始终是在群体中进行的，所以，遗传算法具有全局性、并行性、快速性和自适应性，是求解复杂问题最优解的有效方法。 GA于20世纪60年代由美国Michigan大学J.H.Holland教授[1]首先提出。它可广泛应用于人工智能、机器学习、函数的优化、自动控制等领域。GA的突出特点是将问题的解空间通过编码转换为GA的搜索空间，把问题的解转换为生物的个体，并借助生物的遗传和进化理论，对多个个体同时进行选择、交叉和变异操作。这样，可以较快地搜索到最优解。但是，遗传算法易陷入局部最优。搜索效率还不是很高。因此，为了克服这些缺点缺点，本文提出了育种算法，可以较好地解决遗传算法的问题。 2 基础遗传算法及局限 2.1基础遗传算法的主要步骤 ⑴准备工作 使用遗传算法首先将搜索、优化问题转换成求适应度函数最大值的问题，建立适应度函数。目标函数的优化方向应对应于适应度增大的方向。对于最小值优化（）问题可以令适应度函数[2]为 其中，C为大于的最大值的一个常数，这样求的最小值，就变成了求适应度函数最大值的问题。 根据自变量的可能取值范围和自变量的精度δ，确定编码的长度L。若编码为二进制码，则编码长度为 式中，为所有自变量上限的最大值，为所有自变量下限的最小值。编码后，二进制串与自变量的十进制数值的映射关系[3]为 式中，M为二进制串对应的十进制数值。 最后，随机产生N组初始个体（长度为L的二进制字符串），即随机生成N组初始解，为使初始解尽可能分布在解空间的各个角落，N必须足够大，一般N＝20～150。用（3）式算出各个初始解的十进制值，代入适应度函数（1）计算出个体的适应度。就可开始遗传操作，遗传操作分：选择复制、交叉、变异三个步骤。 ⑵选择复制 选择复制的目的是选择适应度大的优秀个体，淘汰部分个体，实现“优胜劣汰”。选择的方法常用轮盘赌法，即按个体适应度占总适应度的比例把整个轮盘划分给各个个体，然后再随机地转动轮盘，随机地选取个体。如图1所示，由于适应度大的个体在轮盘中所占的区域大，故被选中的概率也大，保护了优秀个体。由于优秀个体被大量复制，搜索可以较快地收敛到稳定状态。同时，选择是随机进行的，因此适应度小的个体也有可能被选中，部分地保持了个体的多样性。 图1 轮盘赌法选择 ⑶交叉 交叉是将选择出来的群体按一定的交叉概率随机地选择出一部分个体，随机地两两配对，并按选定的交叉方式，把成对的个体的基因部分地进行交换，形成新的个体。如图2所示，交叉点也是随机选取的。交叉操作使群体在继承父代的基因的同时又不完全等同于父代，有可能产生更优秀的个体，使搜索向最优解靠近。 图2 交叉操作示例 ⑷变异 交叉操作是父代基因的重组，基因全部来源于父代，经过多次交叉后，就很难产生新的个体了。变异是以较小的概率随机地改变一个串位的值。如对于二进制串，就是将随机选取的串位的值由1变成0或者由0变成1。变异操作不依赖于父代的基因，更容易产生新的个体，保持群体的多样性。为了使搜索能够收敛，搜索初期变异率不能太高。 通过不断重复以上的遗传操作，优秀个体的适应度越来越高，直到一个或者多个个体达到最优解。若相同的个体越来越多，直到所有个体均相同，即使这时没有达到全局最优，搜索也很难进行下去，搜索到的就是局部最优。 2.2 基础遗传算法的局限 ⑴容易陷入局部最优 遗传算法的选择复制操作会使优秀个体大量复制，这样种群中会出现许多相同的个体，而相同个体之间即使进行交叉操作也不会产生新的个体。另外，变异出来的更优秀个体由于数量少，很容易在选择复制操作中被淘汰，因此，搜索容易陷入局部最优 ⑵搜索效率低 对于基础遗传算法，优秀个体的存活和发展要靠相同个体的规模来保证，而这种规模反过来又成了新的优秀个体发展起来的障碍，由于轮盘的大部分区域已被旧的优秀个体占据，因此新的优秀个体存活并发展起来的概率很小，过程也较漫长。这种由机制的缺陷所产生的竞争及内耗是不可避免的。这和生物界自然进化过程缓慢的道理是一样的。所以遗传算法的搜索效率不是最高的。 ⑶具有三种操作，运算量大 遗传算法具有选择、交叉、变异三种操作，特别是选择和交叉操作，需要多个操作步骤，实现程序较长，运行时间也较长，因此不便于复杂问题的求解。 7 育种算法的应用实例 育种算法不是针对某一特定函数提出的，因此算法具有普遍意义，适用于各种优化问题。用育种算法进行了许多函数的优化计算，效果均非常良好，下面是其中两例。 例1 具有针状全局最优的函数如下 图2 例1的函数图 该函数的函数图形如图2所示，在(50,50)处取得