遗传算法综述

《遗传算法综述》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、遗传算法综述史俊杰摘要：遗传算法来源于进化论和群体遗传学，是计算智能的重要组成部分，正受到众多学科的高度重视。本文主要回顾了遗传算法的起源和发展历程，并对遗传算法的基本原理及特点作了简要阐述。进一步指出了遗传算法存在的问题及相应的改进措施，讨论了遗传算法在实际中的应用，并对遗传算法的未来的发展进行了探讨。关键字：遗传算法，适应度函数，神经网络1.遗传算法的起源遗传算法(GeneticAlgorithm，GA)是模拟自然界生物进化机制的一种算法，即遵循适者生存、优胜劣汰的法则，也就是寻优过程中有用的保留，无用的则去除。在科学和生产实践中表现

2、为，在所有可能的解决方法中找出最符合该问题所要求的条件的解决方法，即找出一个最优解。这种算法是1960年由Holland提出来的，其最初的目的是研究自然系统的自适应行为，并设计具有自适应功能的软件系统。2.遗传算法的发展过程从二十世纪六十年代开始，密切根大学教授Holland开始研究自然和人工系统的自适应行为，在这些研究中，他试图发展一种用于创造通用程序和机器的理论。在六十年代中期至七十年代末期，Bagly发明“遗传算法”一词并发表了第一篇有关遗传算法应用的论文。1975年竖立了遗传算法发展史上的两块里程碑，一是Holland出版了经典著

3、作“AdaptationinNatureandArtifieialSystem”，二是Dejong完成了具有指导意义的博士论文“AnAnalysisoftheBehaviorofaClassofGenetieAdaptiveSystem”。进入八十年代，随着以符号系统模仿人类智能的传统人工智能暂时陷入困境，神经网络、机器学习和遗传算法等从生物系统底层模拟智能的研究重新复活并获得繁荣。进入九十年代，以不确定性、非线性、时间不可逆为内涵，以复杂问题为对象的科学新范式得到学术界普遍认同，如广义进化综合理论。由于遗传算法能有效地求解属于、NPC类

4、型的组合优化问题及非线性多模型、多目标的函数优化问题，从而得到了多学科的广泛重视。3.遗传算法特点遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。遗传算法具有进化计算的所有特征，同时又具有自身的特点：（1）搜索过程既不受优化函数的连续性约束，也没有优化函数导数必须存在的要求。（2）遗传算法采用多点搜索或者说是群体搜索，具有很高的隐含并行性，因而可以提高计算速度。（3）遗传算法是一种自适应搜索技术，其选择、交叉、变异等运算都是以一种概率方式来进行，从而增加了搜索过程的灵活性，具有较好的全局优化求解能力。（4）遗传算

5、法直接以目标函数值为搜索信息，对函数的性态无要求，具有较好的普适性和易扩充性。（5）遗传算法更适合大规模复杂问题的优化。4.遗传算法研究理论在自然界，由于组成生物群体中各个体之间的差异，对所处环境有不同的适应和生存能力，遵照自然界生物进化的基本原则，适者生存、优胜劣汰，将要淘汰那些最差个体，通过交配将父本优秀的染色体和基因遗传给子代，通过染色体核基因的重新组合产生生命力更强的新的个体与由它们组成的新群体。在特定的条件下，基因会发生突变，产生新基因和生命力更强的新个体；但突变是非遗传的，随着个体不断更新，群体不断朝着最优方向进化，遗传算法是

6、真实模拟自然界生物进化机制进行寻优的。在此算法中，被研究的体系的响应曲面看作为一个群体，相应曲面上的每一个点作为群体中的一个个体，个体用多维向量或矩阵来描述，组成矩阵和向量的参数相应于生物种组成染色体的基因，染色体用固定长度的二进制串表述，通过交换、突变等遗传操作，在参数的一定范围内进行随机搜索，不断改善数据结构，构造出不同的向量，相当于得到了被研究的不同的解，目标函数值较优的点被保留，目标函数值较差的点被淘汰。由于遗传操作可以越过位垒，能跳出局部较优点，到达全局最优点。遗传算法是一种迭代算法，它在每一次迭代时都拥有一组解，这组解最初是随

7、机生成的，在每次迭代时又有一组新的解由模拟进化和继承的遗传操作生成，每个解都有一目标函数给与评判，一次迭代成为一代。典型的算法的流程图如图1所示，步骤有：Step1初始化：采用随机法生成个初始串作为初始群体，每个初始串称为一个个体。Step2计算适应度：根据适应度函数计算第代种群每个个体的适应值，记具有最高适应值的个体为。Step3选择：由父种群采用适应度比例法选出子种群，其中被选中的概率为。Step4交叉变异：交叉运算，从子种群中以相同的概率选出两个个体，这两个个体之间以事先给定的概率执行重组运算，产生两个新个体，重复这一过程。变异运算

8、根据一定的变异率P~f随机地对一个体的某一位进行翻转，产生一个新的个体，重复这一过程。然后并入Step2中最高适应值的个体最终形成新一代群体记：中具有最高适应度的个体为。Step5若遗传代数满