《遗传算法 .doc

遗传算法 摘要：遗传算法（Genetic?Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。? 遗传算法经过不断的发展和改进，又发展出许多新的进化算法，如模拟退火算法，免疫遗传算法，粒子群优化算法等等。 关键字：遗传算法；进化率；寻优方法；组合优化 1、遗传算法的发展及历史? 遗传算法(Genetic?Algorithm，简称GA)起源于对生物系统所进行的计算机模拟研究。????美国Michigan大学的Ho11and教授及其学生受到生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化的自适应概率优化技术——遗传算法。? 1967年，Holland的学生Bagley在其博士论文中首次提出了“遗传算法”一词，他发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用双倍体的编码方法。Holland教授用遗传算法的思想对自然和人工自适应系统进行了研究，提出了遗传算法的基本定理——模式定理(Schcma?Theorem)，并于1975年出版了第一本系统论述遗传算法和人工自适应系统的专著《Adaptation?in?Natural?and?Artificial?Systems》。? 20世纪80年代，Holland教授实现了第一个基于遗传算法的机器学习系统，开创了遗传算法的机器学习的新概念。1975年DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验，建立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。1989年Goldberg出版了专著《Genetic?Algorithm?in?Search Optimization???and?Machine?Learning》，系统地总结了遗传算法的主要研究成果，全面完整地论述了遗传算法的基本原理及其应用。? 1991年，Davis出版了《Handbook?of?Genetic?Algorithms》一书，介绍了遗传算法在科学计算、工程技术和社会经济中的大量实例。? 1992年，Koza将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程(Genetic?Programming，简称GP)的概念。? 在控制系统的离线设计方面遗传算法被众多的使用者证明是有效的策略。例如，Krishnakumar和Goldberg以及Bramlette和Cusin已证明使用遗传优化方法在太空应用中导出优异的控制器结构比使用传统方法如LQR和Powell(鲍威尔)的增音机设计所用的时间要少(功能评估)。Porter和Mohamed展示了使用本质结构分派任务的多变量飞行控制系统的遗传设计方案。与此同时，另一些人证明了遗传算法如何在控制器结构的选择中使用。? 从遗传算法的整个发展过程来看，20世纪70年代是兴起阶段，20世纪80年代是发展阶段，20世纪90年代是高潮阶段。遗传算法作为一种实用、高效、鲁棒性强的优化技术，发展极为迅速，已引起国内外学者的高度重视。 2、遗传算法的计算步骤及关键? 2.1 需求分析 1．本程序演示的是用简单遗传算法随机一个种群，然后根据所给的交叉率，变异率，世代数计算最大适应度所在的代数。? 2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的命令；相应的输入数据和运算结果显示在其后。? 3．测试数据? 输入初始变量后用f(x)=100*(x1*x1-x2)*(x1*x2-x2)+(1-x1)*(1-x1)其中-2.048=x1,x2=2.048作适应度函数求最大适应度即为函数的最大值。 2.2 遗传算法的计算步骤? （1）初始化? 选择一个群体，即选择一个串或个体的集合xi (i=1,2,3……n)。这个初始的群体也就是问题假设解的集合。一般取n=30—60。? 通常以随机方法产生串或个体的集合xi (i=1,2,3……n)问题的最优解将通过这些初始假设解进化而求出。? （2）选择? 根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。给出目标函数f，则f(xi)称为个体xi的适应度。以?