遗传 算法 论文 设计

《遗传 算法 论文 设计》由会员分享，可在线阅读，更多相关《遗传 算法 论文 设计（11页珍藏版）》请在金锄头文库上搜索。

1、遗传算法论文专 业 信息与计算科学 班 级 计算 072 学 号 3070811045 姓 名 赵茹 任课教师 闵涛 时 间 2010 年秋级学期 1摘要遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的 J.Holland 教授 1975 年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学

2、习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。遗传算法经过不断的发展和改进，又发展出许多新的进化算法，如模拟退火算法，免疫遗传算法，粒子群优化算法等等。本文针对粒子群算法做进一步介绍。粒子群优化算法(Particle Swarm optimization,PSO)又翻译为粒子群算法、微粒群算法、或微粒群优化算法。是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。关键字：遗传算法；粒子群优化算法2AbstractThe goals of Genetic Programming (GP) are to use the concepts of genet

3、ics and Darwinian natural selection to generate and evolve entire computer programs. GP largely resembles GA in terms of its basic algorithm. The notions of mutation, reproduction (crossover) and fitness are essentially the same, with GP requiring a bit of special care when using those operations. W

4、hile Genetic Algorithms (GA) is concerned with modifying fixed-length strings, usually associated with parameters to a function, Genetic Programming is concerned with actually creating and manipulating the (non-fixed length) structure of the program (or function). As a result, GP is a much more comp

5、lex and difficult topic.Keyword： Genetic Algorithm；Particle Swarm Optimization3遗传算法1. 遗传算法的发展及历史遗传算法(Genetic Algorithm，简称 GA)起源于对生物系统所进行的计算机模拟研究。 美国 Michigan 大学的 Ho11and 教授及其学生受到生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化的自适应概率优化技术遗传算法。1967 年，Holland 的学生 Bagley 在其博士论文中首次提出了“遗传算法”一词，他发展了复制、交叉、变异、显性、倒位等遗传算子

6、，在个体编码上使用双倍体的编码方法。Holland 教授用遗传算法的思想对自然和人工自适应系统进行了研究，提出了遗传算法的基本定理模式定理(Schcma Theorem)，并于 1975 年出版了第一本系统论述遗传算法和人工自适应系统的专著 Adaptation in Natural and Artificial Systems 。20 世纪 80 年代，Holland 教授实现了第一个基于遗传算法的机器学习系统，开创了遗传算法的机器学习的新概念。1975 年 DeJong 基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验，建立了遗传算法的工作框架，得到了一些重要且具有指导意义的

7、结论。1989 年 Goldberg 出版了专著 Genetic Algorithm in Search Optimization and Machine Learning ，系统地总结了遗传算法的主要研究成果，全面完整地论述了遗传算法的基本原理及其应用。1991 年，Davis 出版了Handbook of Genetic Algorithms一书，介绍了遗传算法在科学计算、工程技术和社会经济中的大量实例。1992 年，Koza 将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程(Genetic Programming ，简称 GP)的概念。在控制系统的离线设计方面遗传算法被众多

8、的使用者证明是有效的策略。例如，Krishnakumar 和 Goldberg 以及 Bramlette 和 Cusin 已证明使用遗传优化方法在太空应用中导出优异的控制器结构比使用传统方法如 LQR 和 Powell(鲍威尔)的增音机设计所用的时间要少(功能评估) 。Porter 和 Mohamed 展示了使用本质结构分派任务的多变量飞行控制系统的遗传设计方案。与此同时，另一些人证明了遗传算法如何在控制器结构的选择中使用。从遗传算法的整个发展过程来看，20 世纪 70 年代是兴起阶段，20 世纪 80 年代是发展阶段，20 世纪 90 年代是高潮阶段。遗传算法作为一种实用、高效、鲁棒性强的优

9、化技术，发展极为迅速，已引起国内外学者的高度重视。42.遗传算法的计算步骤及关键2.1 遗传算法的计算步骤（1）初始化选择一个群体，即选择一个串或个体的集合 。这个初始的群体也就nib,21是问题假设解的集合。一般取 。603n通常以随机方法产生串或个体的集合 问题的最优解将通过这些初始i,假设解进化而求出。（2）选择根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。给出目标函数 ，则 称为个体f)(ibf的适应度。以ib nbfPnjjii1)(选 中为选中 是下一代个体的次数。ib显然，从上式可知：适应度较高的个体，繁殖下一代

10、的数目较多。适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。这样，就产生了对环境适应能力较强的后代。从问题求解角度来讲，就是选择出和最优解较接近的中间解。（3）交叉对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置 ，按交叉概率P。在选中位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。例如有个体 选择它们的左边 3 位进行交叉操作，则有 01210SS.一般而言，交叉概率 P，取值为 0.250.75。201S5（4）变异根据生物遗传中基因变异的原理，以变异概率 Pm 对某些个体的某些位执行变异。在变异时，对执

11、行变异的串的对应位求反，即把 1 变为 0，把 0 变为 1。变异概率 Pm与生物变异极小的情况一致，所以，Pm 的取值较小，一般取 0.010.2。例如有个体 ,对其的第 1，4 位置的基因进行变异，则有10S 0S单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质（5）全局最优收敛当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛，算法结束。否则，用经过选择、交叉、变异得到的新一代群体取代上一代群体，并

12、返回到第 2 步即选择操作处继续循环执行。2.2 遗传算法的关键遗传算法在应用中最关键的问题有如下 3 个：（1）串的编码方式它本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长及编码形式对算法收敛影响极大。（2）适应函数的确定适应函数也称对象函数，这是问题求解品质的测量函数；往往也称为问题的“环境” 。一般可以把问题的模式函数作为对象函数；但有时需要另行构造。 （3）遗传算法自身参数设定遗传算法自身参数有 3 个，即群体大小 n，交叉概率和变异概率。群体大小 n 太小时难以求出最优解，太大则增长收敛时间。一般 n=30-160。交叉概率太小时难以

13、向前搜索，太大则容易破坏高适应值的结构。一般取 Pc=0.25-0.75。变异概率太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取 Pm=0.01-0.2。3.遗传算法的程序设计遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从任一初始种群（Population）出发，通过随机选择、交叉和变异操作，产生一群更适应环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代地不断繁衍进化，最后收敛到一群最适合环境的个体（Individual） ，求得问题的最优解。 6实际问题参数集编码成为串计算适应值统计结果种群二经过优化的一个或多个参数集（有解码得到）种群一选

14、择与遗传改善或解决实际问题种群一种群二随机算子图 1 遗传算法流程图（1）编码解空间中的解数据，作为遗传算法的表现型形式。从表现型到基因型的映射称为编码。遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合就构成了不同的点。（2）初始群体的生成随机产生 N 个初始串结构数据，每个串结构数据称为一个个体， N 个个体构成了一个群体。遗传算法以这 N 个串结构作为初始点开始迭代。设置进化代数计数器；设置最大进化代数 T ；随机生成 M 个个体作为初始群体 。0t )0(P7（3）适应度值评价检测适应度函数表明个体或解的优劣性。对于不同的问题，适应度函数

15、的定义方式不同。根据具体问题，计算群体中各个个体的适应度。（4）选择将选择算子作用于群体。（5）交叉将交叉算子作用于群体。（6）变异将变异算子作用于群体。群体 经过选择、交叉、变异运算后得到下一代群体)(tP。 )1(tP（7）终止条件判断若 ，则 ，转到步骤（2） ；若 ，则以进化过程中所得到的具有最Tt1t Tt大适应度的个体作为最优解输出，终止运算。从遗传算法运算流程可以看出，进化操作过程简单，容易理解，它给其他各种遗传算法提供了一个基本框架。一个简单的遗传算法被 Goldberg 用来进行轮廓描述并用来举例说明遗传算法的基本组成。t 代种群用变量 表示，初始群体 是随机设计的。 )(tP)0(P4.遗传算法的应用粒子群优化算法与求解粒子群优化算法(Particle Swarm optimization,PSO)又翻译为粒子群算法、微粒群算法、或微粒群优化算法。是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。4.1 粒子群优化算法与遗传算法粒子群优化算法与遗传算法有多共同之处。种群随机初始化 。 对种群内的每一个个体计算适应值(fitness value)。适应值与最优解的距离直接有关。 种群根据适应值进行复制 。 如果终止条件满足的话，就停止，否则转步骤 。 PSO 和遗传算法两者都随机初始化种群，而且都使用适应值来评价系统，而且都根据适应值