《遗传算法论文：浅谈遗传算法的研究与改进》由会员分享，可在线阅读，更多相关《遗传算法论文：浅谈遗传算法的研究与改进（12页珍藏版）》请在金锄头文库上搜索。
1、遗传算法论文：浅谈遗传算法的研究与改进【摘 要】遗传算法是模拟自然界生物进化机制的概率性搜索算法，可以处理传统搜索方法难以解决的非线性问题。但是经典遗传算法存在局部收敛、收敛速度慢等缺点，这使得经典遗传算法有时很难找到全局最优解。本文针对经典遗传算法中所存在的缺点，采用阶段式的适应度函数、基于竞争机制的交叉方式和仿粒子群变异操作，使遗传算法的收敛速率、全局收敛概率都得到了较大的提高。【关键词】遗传算法 适应度 交叉操作 仿粒子群变异一 遗传算法遗传算法（genetic algorithm，简称 ga）是 holland在研究自然遗传现象与人工系统的自适应行为时，模拟生物进化现象，并采用自然进化
2、机制来表现复杂现象的一种全局群体搜索算法。遗传算法的基本思想起源于 darwin 进化论和 mendel 的遗传学说。作为一类智能计算工具和学习算法，由于其实现简单、对目标函数要求不高等特性，遗传算法已广泛应用于如人工智能、组合优化等研究领域。1遗传算法的优越性遗传算法（genetic algorithm）利用某种编码技术作用在称为染色体的二进制串上，模拟由这些串组成的个体的进化过程。通过有组织的、随机的信息交换来重新结合那些适应性好的串，在每一代中，利用上一代串结构中适应性好的位和段来形成一个新的串的群体，同时在串结构中尝试用新的位和段来代替原来的部分以形成新的个体，以增加种群的多样性。遗传
3、算法的最大优点是能够通过群体间的相互作用，保存已经搜索到的信息，这是基于单次搜索过程的优化方法所无法比拟的。但是，遗传算法也存在着计算速度较慢，并且容易陷入局部最优解的问题中。遗传算法的优越性归功于它与传统搜索方法不同的特定结构。第一，遗传算法的操作对象是编码，对问题的限制极少，对函数的一些约束条件如连续性、可导性等不做要求，减少了要解决问题的复杂性。第二，遗传算法同时搜索解空间内的许多点，因而可以有效地防止搜索过程中收敛到局部最优解，并获得全局最优解，与其他单点搜索的方法相比，在计算时间上也有较大的优势。第三，遗传算法使用遗传操作时是按概率在解空间进行搜索，因而既不同于随机搜索，也不同于枚举
4、法那样盲目地举例，而是一种有目标、有方向的启发式搜索。2遗传算法的基本步骤遗传算法的实现中包括复制、交叉、变异三个算子，需要确定关键的几个参数与标准包括：种群规模、基因编码、适值函数、选择概率、遗传算子以及停机准则。下面分别对其进行说明：第一，表示法与适应度计算。标准遗传算法（二进制编码）作用于确定长度的二进制位串上，即 i0，1l。假设需要解决如下函数优化问题 ，一般是将位串分为 n 段，每段长度为 lx，即 lnlx，每段表示分量xiui，vi的二进制代码。位段译码函数 的常见形式为：（1）其中 记为个体 的第i 段。把位段译码函数 组合成一个个体的译码函数 ，则适应度函数可设置为 ，其中
5、 为比例变换函数，作用之一是确保适应值为正值，并且最好使个体的适应度值最大。常见的比例变换有线性比例、幂比例和指数比例等。第二，交叉。交叉操作是将已有个体组合出新个体，使两个个体的有效信息得以遗传到下一代，并可能得到新的个体信息。在遗传算法中，交叉操作是主要的遗传操作，它把两个不同个体上的有用段组合在一起，ga 的性能在很大的程度上依赖所使用的交叉算子。交叉操作算子 ri i 也是作用在位串上，以概率 pc 对两个个体进行交叉，pc 的作用范围一般为0.6，1.0 。两个父辈个体s（s1，sl） ，v（v1，vl）被随机地从群体中选择而进行交叉，产生了两个子代个体：s（s1，sh1，sh，vh
6、1，vl， ） （2）v（v1，vh1，vh，sh1，sl， ） （3）其中交叉点 h 为 1 到 l 之间的一个随机整数。这种交叉即为一点交叉，通过选择更多的交叉点并交替地变换交叉点之间的位段，就可以把一点交叉扩展到 m 点交叉算子。另外还有一些其他形式的交叉算子，如一致交叉算子等。不过目前还没有明确的理论或可靠的实验证据来决定哪一种交叉算子是最适合的。第三，变异。变异操作的目的是通过随机改变染色体的某些基因来引入新个体，增加种群多样性，并在一定程序上进行局部搜索。相对于交叉操作，变异操作的设计和实现更为简单和灵活。在标准遗传算法中，变异一般被看作为辅助算子，它作用在位串上，以较小的概率 p
7、m 随机地改变串上的每一位（即相应位上的 0 变为 1，或者 1 变为0） 。变异概率 pm 的值一般为 0.001 到 0.01 之间，它不依赖目标变量的维数和位串的总长。个体（s1，sl）经变异算子 作用后变为（ ） ，其中：（4）这里 i 是 0 与 1 之间的一致随机数，对串上的每一位都要重新采样。常用的变异操作包括：（1）互换：随机变换若干不同位置上的不同基因。 （2）逆序：将某两随机位置间的基因串逆序。 （3）插入：即将某一位置上的基因（或某一段位置上的基因串）插入到另一位置之前或之后，若两位置相邻，则该操作也称为漂移。第四，选择。标准遗传算法采用的是一种依据概率复制的选择算子 s
8、i i ，个体 ai 的复制概率由它的相对适应度给出：（5）按照这个概率分布选取 个个体产生下一代父辈群体。显然该选择算子不适于出现负适应度值和最小化任务的情况，此时需采用适应度值比例转换。综上所述，标准遗传算法的主要步骤可描述如下：二 遗传算法的改进1一般自适应遗传算法经典遗传算法（cga）采用的都是固定参数，由于遗传算法从本质上说是一种动态自适应的进化过程，因此固定的参数设置则是对遗传算法性能的一种局限和束缚。经典遗传算法在进化过程中，各遗传算子的参数保持不变。由于在进化后期，种群内个体的多样性大幅度减小，适应值接近，因此选择操作的选择压力可能不够，致使算法接近随机搜索状态。针对 cga
9、存在的这些问题，srinvivas 等人提出自适应遗传算法（adaptive ga，aga） ，即交叉概率 pc 和变异概率 pm 能够随适应度自动改变，遗传算法的参数中交叉概率pc 和变异概率 pm 的选择是影响遗传算法行为和性能的关键所在，直接影响算法的收敛性，pc 越大，新个体产生的速度就越快。然而，pc 过大时遗传模式被破坏的可能性也越大，使得具有高适应度的个体结构很快就会被破坏；但是如果 pc 过小，会使搜索过程缓慢，以至停滞不前。对于变异概率 pm，如果 pm 过小，就不易产生新的个体结构；如果pm 取值过大，那么遗传算法就变成了纯粹的随机搜索算法。当种群中每个个体的适应度趋于一致
10、或趋于局部最优时，使二者增加，而当种群适应度比较分散时，使二者减小，同时对适应度高于群体平均适应度的个体，采用较低的交叉和变异概率，使性能优良的个体进入下一代，而低于平均适应度的个体，采用较高的交叉和变异概率，使性能较差的个体被淘汰。因此，自适应的 pc 和 pm 能够提供相对某个解的最佳 pc 和 pm。自适应遗传算法在保持群体多样性的同时，保证遗传算法的收敛性。自适应遗传算法由于改进了各遗传算子的参数，使算法能够适应于种群进化各个阶段的特征，使算法的优化效率和解的质量得到提高。2改进的遗传算法经典遗传算法的局部搜索能力较差，一般对经典遗传算法进行适当的改进或将遗传算法与传统的基于问题的启发
11、式搜索技术相结合形成混合遗传算法来解决这个问题。设计混合遗传算法有三条指导性原则：（1）采用原有算法中的编码技术；（2）吸收原有算法的优点；（3）改造遗传算子。根据这三个指导原则本文在保留一般自适应算法的编码方式、变异和交叉概率设定的基础上，对一般的自适应算法的适应度函数、交叉方式、变异方式做出改进，提出了改进的混合遗传算法（hybrid ga, hga） 。最后，通过实验说明了改进算法的优越性。 （1）适应度函数的改进。适应度函数是评价个体适应环境的能力，是选择操作的依据，它的好坏能直接影响遗传算法的性能。适应度函数是由目标函数转换而成的。 （2）交叉方式的改进。ga 交叉算子是模仿自然界有
12、性繁殖的基因重组过程，在该过程中群体的个体品质得以提高。直观来讲，选择算子将原有的优良基因遗传给下一代个体，而交叉算子则可以生成包含更多优良基因的新个体。交叉方式的设计，一般与所求问题的特征有关。通常需要考虑如下因素：第一，必须保证优良基因能够在下一代中有一定的遗传和继承的机会；第二，必须保证通过交叉操作存在一定的生成优良基因的机会；第三，交叉方式的设计与问题编码紧密相关，必须结合编码的结构来设计高效的交叉算子。 （3）变异方式的改进。变异即对群体中个体的某些基因作出变动。变异的目的有两个：一个是使遗传算法具有局部的随机搜索能力；另一个是保持群体的多样性。变异在 ga 中的作用是第二位，与交叉
13、算子相比，当变异概率较小时，在进化初期模式存活概率比较高；在进化稳定期，与交叉算子下的模式存活概率基本相同；当变异概率比较大时，变异算子作用下模式的存活概率比交叉算子下要小得多。3算法步骤step1 采用实数编码产生初始种群，在函数定义域内按照均匀分布随机产生 个个体xi（i1，2，） ，设定最大进化代数设为 t。step2 计算每个个体的函数值，之后根据计算种群函数的平均值，最后按照本文设定的适应度函数计算当前种群中每个个体的适应度。step3 最优保存策略，结合文献本文将最优保存策略算法做如下修改：第一步计算每个个体的函数值，然后排序，找出最优解，最差解；第二步若上一代最优解的函数值比当前
14、最优解的函数值大，则用上一代的最优解替换当前最优解；若上一代的最优解函数值小，则用上一代的最优解替换当前中的最差解。step4 根据每个个体的适应度，采用比例选择法。通过转换，使得在进化前期原本函数值小的个体将有更大的概率被选择，保持了种群的多样性。step5 计算交叉概率，然后在种群中按照交叉概率随机选择父代个体，然后应用本文改进的交叉操作进行交叉，最后通过竞争选取两个最好的个体作为子代个体。step6 计算变异概率，选定变异个体，将选定的个体依照本文采用的拟粒子群变异方法进行变异操作。step7 满足迭代次数即停止，否则代数加 1，转入step2。三 实验分析1实验参数设定为了验证改进遗传
15、算法的效果，选用以下三个典型函数进行测试：（1）问题 p1g3 是 schaffer 函数，由函数图像可以看出当（x1，x2）（0，0）时有全局最小值 0。为方便编程将问题 p3 转化为求全局最大值，得到问题 p3：分别用经典遗传算法（cga） 、一般自适应遗传算法（aga）和改进遗传算法（hga）对这些函数进行优化。为了方便编程，函数均设定为求其全局最大值，然后将三种算法运行的参数设置如下：问题 p1算法运行的参数如表 1 所示：采用上述参数用三种算法对每个函数各自独立运行 50 次，当算法达到最大迭代次数，或者所得结果与函数全局最优解的误差|e|10-2 时算法终止。表 4 列出了三种算法
16、的平均收敛代数，最小收敛代数和全局收敛概率。三种算法运行收敛的代数，见图 1、图 2、图 3。2结果分析通过表 4 可以看出，本文的改进算法 hga 无论是收敛代数还是收敛概率都全面优于经典遗传算法。与一般自适应算法相比，达到最优值的收敛代数减少，得到了令人满意的效果。四 小结在本节中详细介绍了本文改进的遗传算法（hga）流程，通过对几组数据的测试结果分析得出本算法的优越性。虽然对个别函数在全局收敛概率方面略显不足，但是对于大部分函数本文改进的算法在减少收敛代数和提高全局收敛概率方面都是优于经典遗传算法（cga）与一般自适应遗传算法（aga）的。参考文献1冯红娟.基于遗传算法的车间作业调度问题研究d.长春理工大学，2008.32赵蕾.遗传算法在通信网优化中的实现d.山东大学，2005.33goldberg d e.ge
