遗传 算法 论文 设计.doc

_遗传算法论文专 业 信息与计算科学 班 级 计算072 学 号 3070811045 姓 名 赵茹 任课教师 闵涛 时 间 2010年秋级学期 摘要遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。遗传算法经过不断的发展和改进，又发展出许多新的进化算法，如模拟退火算法，免疫遗传算法，粒子群优化算法等等。本文针对粒子群算法做进一步介绍。粒子群优化算法(Particle Swarm optimization,PSO)又翻译为粒子群算法、微粒群算法、或微粒群优化算法。是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。关键字：遗传算法；粒子群优化算法AbstractThe goals of Genetic Programming (GP) are to use the concepts of genetics 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. While 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 complex and difficult topic. Keyword：Genetic Algorithm；Particle Swarm Optimization遗传算法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）交叉对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置 ，按交叉概率P。在选中位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。例如有个体选择它们的左边3位进行交叉操作，则有 .一般而言，交叉概率P，取值为0.250.75。（4）变异根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.010.2。 例如有个体,对其的第1，4位置的基因进行变异，则有 单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质（5）全局最优收敛 当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛，算法结束。否则，用经过选择、交叉、变异得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。2.2遗传算法的关键遗传算法在应用中最关键的问题有如下3个：（1）串的编码方式 它本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长及编码形式对算法收敛影响极大。（2）适应函数的确定 适应函数也称对象函数，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模式函数作为对象函数；但有时需要另行构造。 （3）遗传算法自身参数设定 遗传算法自身参数有3个，即群体大小n，交叉概率和变异概率。群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n=30-160。交叉概率太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm=0.01-0.2。3.遗传算法的程序设计遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从任一初始种群（Population）出发，通过随机选择、交叉和变异操作，产生一群更适应环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代地不断繁衍进化，最后收敛到一群最适合环境的个体（Individual），求得问题的最优解。 实际问题参数集编码成为串计算适应值统计结果种群二经过优化的一个或多个参数集（有解码得到）种群一选择与遗传改善或解决实际问题种群一种群二随机算子图1 遗传算法流程图（1）编码解空间中的解数据，作为遗传算法的表现型形式。从表现型到基因型的映射称为编码。遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合就构成了不同的点。（2）初始群体的生成随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。遗传算法以这N个串结构作为初始点开始迭代。设置进化代数计数器；设置最大进化代数T ；随机生成M个个体作为初始群体。（3）适应度值评价检测适应度函数表明个体或解的优劣性。对于不同的问题，适应度函数的定义方式不同。根据具体问题，计算群体中各个个体的适应度。（4）选择将选择算子作用于群体。（5）交叉将交叉算子作用于群体。（6）变异将变异算子作用于群体。群体经过选择、交叉、变异运算后得到下一代群体。 （7）终止条件判断若，则，转到步骤（2）；若，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止运算。 从遗传算法运算流程可以看出，进化操作过程简单，容易理解，它给其他各种遗传算法提供了一个基本框架。 一个简单的遗传算法被Goldberg用来进行轮廓描述并用来举例说明遗传算法的基本组成。t代种群用变量表示，初始群体是随机设计的。 4.遗传算法的应用粒子群优化算法与求解粒子群优化算法(Particle Swarm optimization,PSO)又翻译为粒子群算法、微粒群算法、或微粒群优化算法。是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。4.1粒子群优化算法与遗传算法粒子群优化算法与遗传算法有多共同之处。种群随机初始化。 对种群内的每一个个体计算适应值(fitness value)。适应值与最优解的距离直接有关。 种群根据适应值进行复制 。 如果终止条件满足的话，就停止，否则转步骤 。 PSO和遗传算法两者都随机初始化种群，而且都使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一定找到最优解。但是，PSO没有遗传操作如交叉和变异，而是根据自己的速度来决定搜索。粒子还有一个重要的特点，就是有记忆。与遗传算法比较，PSO的信息共享机制是很不同的。在遗传算法中，染色体互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动。在PSO中, 只有gBest (orlBest) 给出信息给其他的粒子， 这是单向的信息流动。整个搜索更新过程是跟随当前最优解的过程。与遗传算法比较, 在大多数的情况下，所有的粒子可能更快的收敛于最优解。4.2粒子群优化算法过程PSO模拟鸟群的捕食行为，设想这样一个场景：一群鸟在随机搜索食物，在这个区域里只有一个食物，所有的鸟都不知道食物在哪里。但是他们知道当前的位置离食物还有多远，那么找到食物的最优策略是什么，最简单有效的方法就是搜寻目前离食物最近的鸟的周围区域。POS从这个场景中得到启示并用于解决优化问题，在POS中，每个优化问题的解都是搜索空间中的一只鸟，我们称之为粒子。所有粒子都有一个由被优化的函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离，然后粒子们就追随当前的最优粒子。初始化一群随机粒子，然后通过迭代找到最优解，在每一次迭代中，粒子通过跟踪两个极值来更新自已。一个是粒子本身找到的最优解叫做个体最优值，另一个是整个种群找到的最优解叫做种群最优值。假设在某个区域内有一个食物（全局最优点），有位于随机初始位置的若干个鸟（或粒子），每一个粒子有到目前为止自已的个体最优值，整个粒子群有到目前为止群体的最优值，这样每个粒子可以根据下面的式子更新自已的速度和位置。其中，为0,1区间内均匀分布的随机数，为惯量函数，和为加速常数。在基于粒子群优化算法的matlab工具箱，调用格式为：sol,tr=pso_Trelea_vectorized(fun,n,vM,xm,xM,key,options)其中fun为描述目标函数的matlab函数名，求解函数不支持匿名函数。n是x向量的维数，这两个量是求解最优化问题必须提供的，其他的变量是可选的；变量vM是最大允许速度，其默认值为4；xm，xM是每个变量的最小值和最大值向量，默认为；key为极值类型变量；返回列向量sol由两个部分构成，前n个元素为搜索到的x向量，第n+1个元素师目标函数的最优值；返回的tr记录了优化的中间结果。主函数基于Trelea算法实现了粒子群优化功能。该函数调用了神经网络工具箱，并将寻优的中间训练过程用图形显示出来，比较直观。其中函数的形式是向量化的，允许一次性运行一组粒子向量的目标函数求值，故其效率远远高于非向量化的函数。在目标函数的描述上与传统的最优化目标函数有不同之处。目标函数中x为向量，每个元素对应xi的当前值，而这里的x为矩阵，其第i列为各个粒子的xi值，所以在原来目标函数程序中用x(i)变量应该改为x(:,i)，且相应的进行点运算。4.3算法示例用粒子群算法求解的最小值。将函数形式写成向量化形式，如下：f=(x(:,1)+x(:,2).2+5*(x(:,3)-x(:,4).2+. (x(:,2)-2*x(:,3).4+10*(x(:,1)-x(:,4).4;运算结果如下：PSO: 1/2000 iterations, GBest = 156259.42512216736.PSO: 100/2000 iterations, GBest = 0.21906183010951347.PSO: 200/2000 iterations, GBest = 0.012788809865128216.PSO: 300/2000 iterations, GBest = 0.00095047109461812945.PSO: 400/2000 iterations, GBest = 6.4933025034724724e-005.PSO: 500/2000 iterations, GBest = 4.447856203753539e-006.PSO: 600/2000 iterations, GBest = 4.8477190873322015e-007.PSO: 700/2000 iterations, GBest = 7.3980687588783106e-008.PSO: 800/2000 iterations, GBest = 2.6464791970694049e-008.PSO: 900/2000 iterations, GBest = 2.1837236542779329e-008.PSO: 1000/2000 iterations, GBest = 1.4885093045145257e-008.PSO: 1100/2000