遗传算法的优缺点

1、遗传算法属于进化算法 ( Evolutionary Algorithms) 的一种 , 它通过模仿自然界的选择与遗 传的机理来寻找最优解 . 遗传算法有三个基本算子 : 选择、交叉和变异 .。数值方法求解这一问题的主要手段是迭代运算。 一般的迭代方法容易陷入局部极小的陷阱 而出现 "死循环 "现象， 使迭代无法进行。 遗传算法很好地克服了这个缺点， 是一种全局优化 算法。生物在漫长的进化过程中， 从低等生物一直发展到高等生物， 可以说是一个绝妙的优化过程。 这是自然环境选择的结果。 人们研究生物进化现象， 总结出进化过程包括复制、 杂交、变异、 竞争和选择。一些学者从生物遗

2、传、进化的过程得到启发，提出了遗传算法(GA)。算法中称遗传的生物体为个体( individual )，个体对环境的适应程度用适应值( fitness )表示。 适应值取决于个体的染色体(chromosome),在算法中染色体常用一串数字表示，数字串中 的一位对应一个基因(gene)。一定数量的个体组成一个群体(population )。对所有个体进行选择、交叉和变异等操作,生成新的群体,称为新一代( new generation )。 遗传算法计算程序的流程可以表示如下 3 ： 第一步 准备工作(i)选择合适的编码方案，将变量(特征)转换为染色体(数字串，串长为m。通常用二进制编码。(2 )

3、选择合适的参数，包括群体大小(个体数M)、交叉概率PC和变异概率Pm(3、确定适应值函数f (x、。f (x、应为正值。第二步形成一个初始群体(含M个个体)。在边坡滑裂面搜索问题中，取已分析的可能滑裂面组作为初始群体。第三步 对每一染色体(串)计算其适应值 fi ,同时计算群体的总适应值 。第四步 选择计算每一串的选择概率 Pi=fi/F 及累计概率。 选择一般通过模拟旋转滚花轮 ( roulette ,其 上按Pi大小分成大小不等的扇形区、的算法进行。旋转M次即可选出M个串来。在计算机上实现的步骤是：产生0,1间随机数r，若r<q1，则第一串v1入选，否则选v2，使满足 qi-1<

4、;r<qi ( 2< i <。可见适应值大的入选概率大。第五步 交叉(1) 对每串产生 0 , 1 间随机数,若 r>pc ,则该串参加交叉操作,如此选出参加交叉的一 组后,随机配对。(2) 对每一对，产生1 , m间的随机数以确定交叉的位置。第六步 变异如变异概率为Pm则可能变异的位数的期望值为Pm x mx M,每一位以等概率变异。具体为对每一串中的每一位产生0 , 1间的随机数r,若r<Pm,则该位发生反转，如对染色体二进 制编码为数字 0 变为 1 ， 1 变为 0。如新个体数达到 M个，则已形成一个新群体，转向第三步；否则转向第四步继续遗传操作。 直到找

5、到使适应值最大的个体或达到最大进化代数为止。由于选择概率是由适应值决定的,即适应值大的染色体入选概率也较大,使选择起到"择优汰劣 "的作用。交叉使染色体交换信息,结合选择规则,使优秀信息得以保存,不良信息被 遗弃。 变异是基因中得某一位发生突变, 以达到产生确实有实质性差异的新品种。 遗传算法 虽是一种随机算法, 但它是有导向的, 它所使用的 "按概率随机选择 "方法是在有方向的搜索 方法中的一种工具。 正是这种独特的搜索方法, 使遗传算法自然地避开了其它最优化算法常 遇到的局部最小陷阱。遗传算法与传统的优化方法(枚举,启发式等)相比较,以生物进化为原型

6、,具有很好的收敛性，在计算精度要求时，计算时间少，鲁棒性高等都是它的优点。遗传算法的优点：1. 与问题领域无关切快速随机的搜索能力。2. 搜索从群体出发，具有潜在的并行性，可以进行多个个体的同时比较， robust.3. 搜索使用评价函数启发，过程简单4. 使用概率机制进行迭代，具有随机性。5. 具有可扩展性，容易与其他算法结合。遗传算法的缺点：1 、遗传算法的编程实现比较复杂 , 首先需要对问题进行编码 , 找到最优解之后还需要对问 题进行解码 ,2 、另外三个算子的实现也有许多参数 , 如交叉率和变异率 , 并且这些参数的选择严重影响 解的品质 , 而目前这些参数的选择大部分是依靠经验 .

7、3 、没有能够及时利用网络的反馈信息 , 故算法的搜索速度比较慢， 要得要较精确的解需要 较多的训练时间。4 、算法对初始种群的选择有一定的依赖性，能够结合一些启发算法进行改进。5 、算法的并行机制的潜在能力没有得到充分的利用，这也是当前遗传算法的一个研究热 点方向。在现在的工作中，遗传算法（ 1972 年提出）已经不能很好的解决大规模计算量问题， 它很容易陷入“早熟” 。常用混合遗传算法，合作型协同进化算法等来替代，这些算法都是 GA的衍生算法。遗传算法具有良好的全局搜索能力， 可以快速地将解空间中的全体解搜索出， 而不会陷 入局部最优解的快速下降陷阱； 并且利用它的内在并行性， 可以方便地进行分布式计算， 加 快求解速度。 但是遗传算法的局部搜索能力较差， 导致单纯的遗传算法比较费时， 在进化后 期搜索效率较低。 在实际应用中， 遗传算法容易产生早熟收敛的问题。 采用何种选择方法既 要使优良个体得以保留，又要维持群体的多样性，一直是遗传算法中较难解决的问题。模拟退火算法虽具有摆脱局部最优解的能力， 能够以随机搜索技术从概率的意义上找出 目标函数的全局最小点。 但是，由于模拟退火