《并行遗传算法的应用.doc》由会员分享，可在线阅读，更多相关《并行遗传算法的应用.doc（16页珍藏版）》请在金锄头文库上搜索。
1、廊坊师范学院本科生毕业论文 题 目：并行遗传算法的应用 学生姓名：李金城 导师姓名：范利强 院 别：数学与信息科学学院 系别：信息与计算科学系 专 业：信息与计算科学 年 级：2008级本科1班 学 号：08040341013完成日期 2012年 4月 25日 廊坊师范学院本科生毕业论文论文题目：并行遗传算法的应用论文摘要：遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型传统的遗传算法虽然具有隐含的并行性,但目前大多为串行遗传算法串行遗传算法在解决一些实际问题时,由于需要较多的个体数量和大量的计算,使得进化过程比较缓慢,难以达到实时的要求因此并行遗传算法就受到了较大的重视,并且
2、已经成为目前遗传算法研究的主要课题遗传算法与并行计算机相结合,能把并行机的高速性和遗传算法固有的并行性两者的长处彼此结合起来 本文举例了一种遗传算法的最优双阈值搜索算法将种群个体设计成一行两列的向量,以类间方差比作为个体的适应度,生成若干初始子种群进行并行计算；同时,将每代的最大适应度个体直接复制进入下一代,适当增大变异概率,在种群的多样性环境下实施有条件的最佳保留策略,保证算法收敛于最优解实验结果表明,该算法具有良好的分割效果和较高的运算效率关键词： 遗传算法；并行遗传算法；图像分割Title： The Design and Parallel Realization of Genetic A
3、lgorithmAbstract：Genetic Algorithm is the computation model which simulating the biological evolution process of Darwins heredity choice and the natural selection Although the traditional genetic algorithm has the concealment parallelism, but realized the method in essentially still was actually ser
4、ial When this kind of serial genetic algorithm solves some actual problems, it will need lots of individuals and computations, and this will causes the evolution process to be so slow that difficult to meets the real-time requirements Therefore, the Parallel Genetic Algorithm has received a big valu
5、e, and already becomes the main topic at genetic algorithm research With the PGA, you can unites the parallel machines high speed with genetic algorithms inherent parallelism Each individual in thepopulation is designed as a vector of one row and two columns, in which each element is encodedto binar
6、y and using variance ratio between clusters as its fitness value, and several sub-populationsare generated and calculated parallelly Meanwhile, in the genetic operations, the maximum fitnessindividual in each population is reproduce into the next generation and the mutation factor isincreased proper
7、ly Conditioned best-reserve strategy is implemented in the environment ofpopulation variety in order to ensure that the algorithm converge to the best solution Experimentresult shows that the algorithm has not only good effect but also higher efficiency for imagesegmentationKeywords：GenticAlgorithm
8、GA;ParallelGeneticAlgorithm PGA;Imgagesegmentation; II并行遗传算法的应用1遗传算法简介遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法在遗传算法里,优化问题的解被称为个体,它表示为一个变量序列,叫做染色体或者基因串染色体一般被表达为简单的字符串或数字串,不过也有其他的依赖于特殊问题的表示方法适用,这一过程称为编码首先,算法随机生成一定数量的个体,有时候操作者也可以对这个随机产生过程进行干预,以提高初始种群的质量在每一代中,每一个个体都被评价,并通过计算适应度函数得到一个
9、适应度数值种群中的个体被按照适应度排序,适应度高的在前面随着优化问题种类的不同以及问题规模的扩大,要寻求一种能以有限的代价来解决搜索和优化的通用方法遗传算法为我们提供的一个有效的途径应用遗传算法求解问题时在编码方案、适应度函数及遗传算子确定后算法将利用进化过程中获得的信息自行组织搜索由于基于自然的选择策略为“适者生存不适应者被淘汰”,因而适应度大的个体具有较高的生存概率通常,适应度大的个体具有更适应环境的基因结构再通过基因重组和基因突变等遗传操作,就可能产生更适应环境的后代进化算法的这种自组织、自适应特征,使它同时具有能根据环境变化来自动发现环境的特性和规律的能力,自然选择消除了算法设计过程中
10、的一个最大障碍,即需要事先描述问题的全部特点并要说明针对问题的不同特点算法应采取的措施因此,利用遗传算法的方法我们可以解决那些复杂的非结构化问题11.1 遗传算法本质的并行性虽然在许多领域成功地应用遗传算法,通常能在合理的时间内找到满意解,但随着求解问题的复杂性及难度的增加,提高GA的运行速度便显得尤为突出,采用并行遗传算法（PGA）是提高搜索效率的方法之一实现PGA不仅要把串行GA等价地变换成一种并行方案,更重要的是要将GA的结构修改成易于并行化实现的形式,形成并行种群模型并行种群模型对传统GA的修改涉及到两个方面：一是要把串行GA的单一种群分成多个子种群,分而治之；二是要控制、管理子种群之
11、间的信息交换不同的分治方法产生不同的PGA结构这种结构上的差异导致了不同的PGA模型：全局并行模型、粗粒度模型、细粒度模型和混合模型遗传算法按并行方式搜索一个种群数目的点,而不是单点它的并行性表现在两个方面,一是遗传算法是内在并行的(inherent parallelism)即遗传算法本身非常适合大规模并行最简单的并行方式是让几百甚至数千台计算机各自进行独立种群的演化计算运行过程中甚至不进行任何通信(独立的种群之间若有少量的通信一般会带来更好的结果)等到运算结束时才通信比较选取最佳个体这种并行处理方式对并行系统结构没有什么限制和要求,可以说,遗传算法适合在目前所有的并行机或分布式系统上进行并行
12、处理而且对并行效率没有太大影响二是遗传算法的内含并行性(implicit parallelism)由于遗传算法采用种群的方式组织搜索,因而可同时搜索解空间内的多个区域,并相互交流信息使用这种搜索方式,虽然每次只执行与种群规模n成比例的计算,但实质上已进行了大约O(n3)次有效搜索这就使遗传算法能以较少的计算获得较大的收益并且具有以下特点：遗传算法不需要求导或其他辅助知识,而只需要影响搜索方向的目标函数和相应的适应度函数遗传算法强调概率转换规则,而不是确定的转换规则遗传算法可以更加直接地应用遗传算法对给定问题,可以产生许多的潜在解,最终选择可以由使用者确定(在某些特殊情况下,如多目标优化问题不止
13、一个解存在,有一组paretic最优解这种遗传算法对于确认可替代解集而言是特别合适的)2. 遗传算法的应用情况 遗传算法提供了一种求解复杂系统优化问题的通用框架它不依赖于问题的具体领域,对问题的种类有很强的鲁棒性,所以广泛应用于很多学科下面是一些应用领域.2.1 函数优化遗传算法与纯数值函数优化计算，对很多实际问题进行数学建模后，可将其抽象为一个数值函数的优化问题遗传算法提供了一种求解这种优化问题的通用框架遗传算法通过对群体所施加的迭代进化过程，不断地将当前群体中具有较高适应度的个体遗传到下一代群体中，并且不断地淘汰适应度较低的个体，从而最终寻找出合适度最大的个体这个适应度最大的个体经解码处理
14、之后所对应的个体表现型就是这个实际应用问题的最优解或近似最优解2.2 组合优化随着问题规模的扩大,组合优化问题的搜索空间急剧扩大,有时在目前的计算机上用枚举法很难或者甚至不可能得到其精确最优解对于这类复杂问题,人们已意识到应把精力放在寻求其满意解上,而遗传算法则是寻求这种满意解的最佳工具之一.实践证明,遗传算法对于组台优化中的NP完全问题非常有效,例如,遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用.2.3 生产调度问题生产调度问题在许多情况下所建立起来的数学模型难以精确求解,即使经过一些简化之后可以进行求解也会因简化太多而使得求解结果与实际相差甚远.因此,
15、目前在现实生产中也主要靠一些经验进行调度,遗传算法已成为解决复杂调度问题的有效工具,在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用.2.4 自动控制在自动控制领域中许多与优化相关的问题需要求解,遗传算法的应用日益增加并显示了良好的效果倒如用遗传算法进行航空控制系统的优化、基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习,部显示出了遗传算法在这些领域中应用的可能性.2.5 机器人调度控制机器人是一类复杂的难以精确建模的人工系统而遗传算法的起源就来自于对人工自适应系统的研究所以机器人智能控制理所当然地成为遗传算法的一个重要应用领域例如遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等方面得到研究和应用.2.6 图像处理和模糊
