并行遗传算法的应用

廊坊师范学院本科生毕业论文题目：并行遗传算法的应用学生姓名：李金城导师姓名：范利强院别：数学与信息科学学院系别：信息与计算科学系专业：信息与计算科学年级：2008级本科1班学号：08040341013完成日期2012年4月25日I廊坊师范学院本科生毕业论文论文题目：并行遗传算法的应用论文摘要：遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型．传统的遗传算法虽然具有隐含的并行性,但目前大多为串行遗传算法．串行遗传算法在解决一些实际问题时,由于需要较多的个体数量和大量的计算,使得进化过程比较缓慢,难以达到实时的要求．因此并行遗传算法就受到了较大的重视,并且已经成为目前遗传算法研究的主要课题．遗传算法与并行计算机相结合,能把并行机的高速性和遗传算法固有的并行性两者的长处彼此结合起来．本文举例了一种遗传算法的最优双阈值搜索算法．将种群个体设计成一行两列的向量,以类间方差比作为个体的适应度,生成若干初始子种群进行并行计算；同时,将每代的最大适应度个体直接复制进入下一代,适当增大变异概率,在种群的多样性环境下实施有条件的最佳保留策略,保证算法收敛于最优解．实验结果表明,该算法具有良好的分割效果和较高的运算效率．关键词：遗传算法；并行遗传算法；图像分割IITitle：TheDesignandParallelRealizationofGeneticAlgorithmAbstract：GeneticAlgorithmisthecomputationmodelwhichsimulatingthebiologicalevolutionprocessofDarwin’shereditychoiceandthenaturalselection．Althoughthetraditionalgeneticalgorithmhastheconcealmentparallelism,butrealizedthemethodinessentiallystillwasactuallyserial．Whenthiskindofserialgeneticalgorithmsolvessomeactualproblems,itwillneedlotsofindividualsandcomputations,andthiswillcausestheevolutionprocesstobesoslowthatdifficulttomeetsthereal-timerequirements．Therefore,theParallelGeneticAlgorithmhasreceivedabigvalue,andalreadybecomesthemaintopicatgeneticalgorithmresearch．WiththePGA,youcanunitestheparallelmachine’shighspeedwithgeneticalgorithm’sinherentparallelism．Eachindividualinthepopulationisdesignedasavectorofonerowandtwocolumns,inwhicheachelementisencodedtobinaryandusingvarianceratiobetweenclustersasitsfitnessvalue,andseveralsub-populationsaregeneratedandcalculatedparallelly．Meanwhile,inthegeneticoperations,themaximumfitnessindividualineachpopulationisreproduceintothenextgenerationandthemutationfactorisincreasedproperly．Conditionedbest-reservestrategyisimplementedintheenvironmentofpopulationvarietyinordertoensurethatthealgorithmconvergetothebestsolution．Experimentresultshowsthatthealgorithmhasnotonlygoodeffectbutalsohigherefficiencyforimagesegmentation．Keywords：GenticAlgorithmGA;ParallelGeneticAlgorithmPGA;Imgagesegmentation;1并行遗传算法的应用1．遗传算法简介遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法．在遗传算法里,优化问题的解被称为个体,它表示为一个变量序列,叫做染色体或者基因串．染色体一般被表达为简单的字符串或数字串,不过也有其他的依赖于特殊问题的表示方法适用,这一过程称为编码．首先,算法随机生成一定数量的个体,有时候操作者也可以对这个随机产生过程进行干预,以提高初始种群的质量．在每一代中,每一个个体都被评价,并通过计算适应度函数得到一个适应度数值．种群中的个体被按照适应度排序,适应度高的在前面．随着优化问题种类的不同以及问题规模的扩大,要寻求一种能以有限的代价来解决搜索和优化的通用方法．遗传算法为我们提供的一个有效的途径．应用遗传算法求解问题时．在编码方案、适应度函数及遗传算子确定后．算法将利用进化过程中获得的信息自行组织搜索．由于基于自然的选择策略为“适者生存．不适应者被淘汰”,因而适应度大的个体具有较高的生存概率．通常,适应度大的个体具有更适应环境的基因结构再通过基因重组和基因突变等遗传操作,就可能产生更适应环境的后代．进化算法的这种自组织、自适应特征,使它同时具有能根据环境变化来自动发现环境的特性和规律的能力,自然选择消除了算法设计过程中的一个最大障碍,即需要事先描述问题的全部特点．并要说明针对问题的不同特点算法应采取的措施．因此,利用遗传算法的方法．我们可以解决那些复杂的非结构化问题[1]．1.1遗传算法本质的并行性虽然在许多领域成功地应用遗传算法,通常能在合理的时间内找到满意解,但随着求解问题的复杂性及难度的增加,提高GA的运行速度便显得尤为突出,采用并行遗传算法（PGA）是提高搜索效率的方法之一．实现PGA不仅要把串行GA等价地变换成一种并行方案,更重要的是要将GA的结构修改成易于并行化实现的形式,形成并行种群模型．并行种群模型对传统GA的修改涉及到两个方面：一是要把串行GA的单一种群分成多个子种群,分而治之；二是要控制、管理子种群之间的信息交换．不同的分治方法产生不同的PGA结构．这种结构上的差异导致了不同的PGA模型：全局并行模型、粗粒度模型、细粒度模型和混合模型．遗传算法按并行方式搜索一个种群数目的点,而不是单点．它的并行性表现在两个方面,一是遗传算法是内在并行的(inherentparallelism)即遗传算法本身非常适合大规模并行．最简单的并行方式是让几百甚至数千台计算机各自进行独立种群的演化计算．运行过程2中甚至不进行任何通信(独立的种群之间若有少量的通信一般会带来更好的结果)．等到运算结束时才通信比较．选取最佳个体．这种并行处理方式对并行系统结构没有什么限制和要求,可以说,遗传算法适合在目前所有的并行机或分布式系统上进行并行处理．而且对并行效率没有太大影响．二是遗传算法的内含并行性(implicitparallelism)．由于遗传算法采用种群的方式组织搜索,因而可同时搜索解空间内的多个区域,并相互交流信息．使用这种搜索方式,虽然每次只执行与种群规模n成比例的计算,但实质上已进行了大约O(n3)次有效搜索．这就使遗传算法能以较少的计算获得较大的收益．并且具有以下特点：遗传算法不需要求导或其他辅助知识,而只需要影响搜索方向的目标函数和相应的适应度函数．遗传算法强调概率转换规则,而不是确定的转换规则．遗传算法可以更加直接地应用．遗传算法对给定问题,可以产生许多的潜在解,最终选择可以由使用者确定(在某些特殊情况下,如多目标优化问题不止一个解存在,有一组paretic最优解．这种遗传算法对于确认可替代解集而言是特别合适的)．2.遗传算法的应用情况遗传算法提供了一种求解复杂系统优化问题的通用框架．它不依赖于问题的具体领域,对问题的种类有很强的鲁棒性,所以广泛应用于很多学科．下面是一些应用领域.2.1函数优化遗传算法与纯数值函数优化计算，对很多实际问题进行数学建模后，可将其抽象为一个数值函数的优化问题．遗传算法提供了一种求解这种优化问题的通用框架．遗传算法通过对群体所施加的迭代进化过程，不断地将当前群体中具有较高适应度的个体遗传到下一代群体中，并且不断地淘汰适应度较低的个体，从而最终寻找出合适度最大的个体．这个适应度最大的个体经解码处理之后所对应的个体表现型就是这个实际应用问题的最优解或近似最优解．2.2组合优化随着问题规模的扩大,组合优化问题的搜索空间急剧扩大,有时在目前的计算机上用枚举法很难或者甚至不可能得到其精确最优解．对于这类复杂问题,人们已意识到应把精力放在寻求其满意解上,而遗传算法则是寻求这种满意解的最佳工具之一.实践证明,遗传算法对于组台优化中的NP完全问题非常有效,例如,遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用.2.3生产调度问题生产调度问题在许多情况下所建立起来的数学模型难以精确求解,即使经过一些简化之3后可以进行求解．也会因简化太多而使得求解结果与实际相差甚远.因此,目前在现实生产中也主要靠一些经验进行调度,遗传算法已成为解决复杂调度问题的有效工具,在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用.2.4自动控制在自动控制领域中许多与优化相关的问题需要求解,遗传算法的应用日益增加．并显示了良好的效果．倒如用遗传算法进行航空控制系统的优化、基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习,部显示出了遗传算法在这些领域中应用的可能性.2.5机器人调度控制机器人是一类复杂的难以精确建模的人工系统．而遗传算法的起源就来自于对人工自适应系统的研究．所以机器人智能控制理所当然地成为遗传算法的一个重要应用领域．例如遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等方面得到研究和应用.2.6图像处理和模糊识别图像处理和模式识别是计算机视觉中的一个重要研究领域．在图像处理过程中．如扫描、特征提取、图像分割等不可避免地会产生一些误差．这些误差会影响到图像处理和识别的效果．如何使这些误差最小是使计算机视觉达到实用化的重要要求．遗传算法在图像处理中的优化计算方面是完全胜任的．目前已在图像恢复、图像边缘特征提取、几何形状识别等方面得到了应用．2.7人工生命人工生命是用计算机等人工媒体模拟或构造出具有自然生物系统特有行为的人造系统,自组织能力和自学习能力是人工生命的两大主要特征.人工生命与遗传算法有着密切的关系,基于遗传算法的进化模型是研究人工生命现象的重要理论基础．虽然人工生命的研究尚处于启蒙阶段,但遗传算法已在其进化模型、学习模型、行为模型等方面显示了初步的应用能力．可以预见．遗传解法在人工生命及复杂自适应系统的模拟与设计、复杂系统突现性理论研究中,将得到更为深入的发展.2.8遗传程序设计Koza发展了遗传程序设计的概念,他使用了以LISP语言所表示的编码方法．基于对一种树型结构所进行的遗传操作自动生成计算机程序．虽然遗传程序设计的理论尚未成熟,应用也有一些限制,但它已有一些成功的应用.2.9机器学习4学习能力是高级自适应系统所应具备的能力之一、基于遗传算法的机器学习．特别是分类器系统,在许多领域得到了应用．例如．遗传算法被用于模糊控制规则