遗传--算法--论文--设计

《遗传算法》论文专业信息与计算科学班级计算072学号3070811045姓名赵茹任课教师闵涛时间2010年秋级学期1摘要遗传算法（GeneticAlgorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。遗传算法经过不断的发展和改进，又发展出许多新的进化算法，如模拟退火算法，免疫遗传算法，粒子群优化算法等等。本文针对粒子群算法做进一步介绍。粒子群优化算法(ParticleSwarmoptimization,PSO)又翻译为粒子群算法、微粒群算法、或微粒群优化算法。是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。关键字：遗传算法；粒子群优化算法2AbstractThegoalsofGeneticProgramming(GP)aretousetheconceptsofgeneticsandDarwiniannaturalselectiontogenerateandevolveentirecomputerprograms.GPlargelyresemblesGAintermsofitsbasicalgorithm.Thenotionsofmutation,reproduction(crossover)andfitnessareessentiallythesame,withGPrequiringabitofspecialcarewhenusingthoseoperations.WhileGeneticAlgorithms(GA)isconcernedwithmodifyingfixed-lengthstrings,usuallyassociatedwithparameterstoafunction,GeneticProgrammingisconcernedwithactuallycreatingandmanipulatingthe(non-fixedlength)structureoftheprogram(orfunction).Asaresult,GPisamuchmorecomplexanddifficulttopic.Keyword：GeneticAlgorithm；ParticleSwarmOptimization3遗传算法1.遗传算法的发展及历史遗传算法(GeneticAlgorithm，简称GA)起源于对生物系统所进行的计算机模拟研究。美国Michigan大学的Ho11and教授及其学生受到生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化的自适应概率优化技术——遗传算法。1967年，Holland的学生Bagley在其博士论文中首次提出了“遗传算法”一词，他发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用双倍体的编码方法。Holland教授用遗传算法的思想对自然和人工自适应系统进行了研究，提出了遗传算法的基本定理——模式定理(SchcmaTheorem)，并于1975年出版了第一本系统论述遗传算法和人工自适应系统的专著《AdaptationinNaturalandArtificialSystems》。20世纪80年代，Holland教授实现了第一个基于遗传算法的机器学习系统，开创了遗传算法的机器学习的新概念。1975年DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验，建立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。1989年Goldberg出版了专著《GeneticAlgorithminSearchOptimizationandMachineLearning》，系统地总结了遗传算法的主要研究成果，全面完整地论述了遗传算法的基本原理及其应用。1991年，Davis出版了《HandbookofGeneticAlgorithms》一书，介绍了遗传算法在科学计算、工程技术和社会经济中的大量实例。1992年，Koza将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程(GeneticProgramming，简称GP)的概念。在控制系统的离线设计方面遗传算法被众多的使用者证明是有效的策略。例如，Krishnakumar和Goldberg以及Bramlette和Cusin已证明使用遗传优化方法在太空应用中导出优异的控制器结构比使用传统方法如LQR和Powell(鲍威尔)的增音机设计所用的时间要少(功能评估)。Porter和Mohamed展示了使用本质结构分派任务的多变量飞行控制系统的遗传设计方案。与此同时，另一些人证明了遗传算法如何在控制器结构的选择中使用。从遗传算法的整个发展过程来看，20世纪70年代是兴起阶段，20世纪80年代是发展阶段，20世纪90年代是高潮阶段。遗传算法作为一种实用、高效、鲁棒性强的优化技术，发展极为迅速，已引起国内外学者的高度重视。42.遗传算法的计算步骤及关键2.1遗传算法的计算步骤（1）初始化选择一个群体，即选择一个串或个体的集合nibi,,2,1。这个初始的群体也就是问题假设解的集合。一般取6030n。通常以随机方法产生串或个体的集合nibi,,2,1问题的最优解将通过这些初始假设解进化而求出。（2）选择根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。给出目标函数f，则)(ibf称为个体ib的适应度。以nbfbfbPnjjii1)()(}{选中为选中ib是下一代个体的次数。显然，从上式可知：①适应度较高的个体，繁殖下一代的数目较多。②适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。这样，就产生了对环境适应能力较强的后代。从问题求解角度来讲，就是选择出和最优解较接近的中间解。（3）交叉对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。例如有个体01011121001011SS选择它们的左边3位进行交叉操作，则有10011120101011SS.一般而言，交叉概率P，取值为0.25—0.75。（4）变异根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01－0.2。5例如有个体101011S,对其的第1，4位置的基因进行变异，则有101011S单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质（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），求得问题的最优解。6图1遗传算法流程图（1）编码解空间中的解数据，作为遗传算法的表现型形式。从表现型到基因型的映射称为编码。遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合就构成了不同的点。（2）初始群体的生成随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。遗传算法以这N个串结构作为初始点开始迭代。设置进化代数计数器0t；设置最大进化代数T；随机生成M个个体作为初始群体)0(P。（3）适应度值评价检测适应度函数表明个体或解的优劣性。对于不同的问题，适应度函数的定义方式不同。根据具体问题，计算群体中各个个体的适应度。实际问题参数集编码成为串计算适应值统计结果种群二经过优化的一个或多个参数集（有解码得到）种群一选择与遗传改善或解决实际问题种群一→种群二随机算子7（4）选择将选择算子作用于群体。（5）交叉将交叉算子作用于群体。（6）变异将变异算子作用于群体。群体)(tP经过选择、交叉、变异运算后得到下一代群体)1(tP。（7）终止条件判断若Tt，则1tt，转到步骤（2）；若Tt，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止运算。从遗传算法运算流程可以看出，进化操作过程简单，容易理解，它给其他各种遗传算法提供了一个基本框架。一个简单的遗传算法被Goldberg用来进行轮廓描述并用来举例说明遗传算法的基本组成。t代种群用变量)(tP表示，初始群体)0(P是随机设计的。4.遗传算法的应用——粒子群优化算法与求解粒子群优化算法(ParticleSwarmoptimization,PSO)又翻译为粒子群算法、微粒群算法、或微粒群优化算法。是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。4.1粒子群优化算法与遗传算法粒子群优化算法与遗传算法有多共同之处。①种群随机初始化。②对种群内的每一个个体计算适应值(fitnessvalue)。适应值与最优解的距离直接有关。③种群根据适应值进行复制。④如果终止条件满足的话，就停止，否则转步骤②。PSO和遗传算法两者都随机初始化种群，而且都使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一定找到最优解。但是，PSO没有遗传操作如交叉和变异，而是根据自己的速度来决定搜索。粒子还有一个重要的特点，就是有记忆。与遗传算法比较，PSO的信息共享机制是很不同的。在遗传算法中，染色体互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动。在PSO中,只有gBest(orlBest)给出信息给其他的粒子，这是单向的信息流动。整个搜索更新过程是跟随当8前最优解的过程。与遗传算法比较,在大多数的情况下，所有的粒子可能更快的收敛于最优解。4.2粒子群优化算法过程PSO模拟鸟群的捕食行为，设想这样一个场景：一群鸟在随机搜索食物，在这个区域里只有一个食物，所有的鸟都不知道食物在哪里。但是他们知道当前的位置离食物还有多远，那么找到食物的最优策略是什么，最简单有效的方法就是搜寻目前离食物最近的鸟的周围区域。POS从这个场景中得到启示并用于解决优化问题，在POS中，每个优化