遗传算法问题综述.doc

遗传算法综述（湘潭大学材料与光电物理学院2009级物理学二班 2009700206）摘 要：遗传算法近年来广泛应用于计算机及自动化领域。本文介绍了遗传算法的起源、发展简史和研究现状，对遗传算法的基本原理和编码问题进行了阐述，介绍了其特点，最后对其发展方向进行了分析和展望。关键词：遗传算法；编码；并行；进化1 引言遗传算法(Genetic Algorithms 简称GA) 是模拟遗传选择和自然淘汰的生物进化过程的计算模型, 是由Michigan大学Holland教授于1975年首次提出的。这是一种新的全局优化搜索算法, 因其简单通用, 鲁棒性强, 适于并行处理, 已广泛应用于计算机科学、优化调度、运输问题、组合优化等领域。2 遗传算法的起源与发展遗传算法来源于达尔文的进化论、魏茨曼的物种选择学说和孟德尔的群体遗传学说。其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法。早在上个世纪40年代，就有学者开始研究如何利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。进入60年代后，美国密歇根大学的Holland教授在对细胞自动机（英文：cellular automata）进行研究时率先提出, 并于1975年出版了颇有影响的专著Adaptation in Natural and Artificial Systems，GA这个名称才逐渐为人所知，约翰霍兰德教授所提出的GA通常为简单遗传算法（SGA）。在二十世纪八十年代中期之前，对于遗传算法的研究还仅仅限于理论方面，直到在伊利诺伊大学召开了第一届世界遗传算法大会，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。3 GA理论与方法3.1 基本原理遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。长度为L的n个二进制串bi(i1，2，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：1选择(Selection)这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。2交叉(Crossover)这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。3变异(Mutation)这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。遗传算法的原理可以简要给出如下：choose an intial populationdetermine the fitness of each individualperform selectionrepeatperform crossoverperform mutationdetermine the fitness of each individualperform selectionuntil some stopping criterion applies这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。3.2 GA的流程图GA的流程图如下图所示3.2.1 编码 遗传算法不能直接处理问题空间的参数，必须把它们转换成遗传空间的由基因按一定结构组成的染色体或个体。这一转换操作就叫做编码，也可以称作(问题的)表示(representation)。评估编码策略常采用以下3个规范: a)完备性(completeness):问题空间中的所有点(候选解)都能作为GA空间中的点(染色体)表现。b)健全性(soundness): GA空间中的染色体能对应所有问题空间中的候选解。c)非冗余性(nonredundancy):染色体和候选解一一对应。目前的几种常用的编码技术有二进制编码，浮点数编码，字符编码，变成编码等。而二进值编码是目前遗传算法中最常用的编码方法。即是由二进值字符集0, 1产生通常的0, 1字符串来表示问题空间的候选解。它具有以下特点:a)简单易行；b)符合最小字符集编码原则；c)便于用模式定理进行分析，因为模式定理就是以基础的。3.2.2 交叉运算所谓交叉运算，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。遗传算法中，在交叉运算之前还必须对群体中的个体进行配对，目前常用的配对策略是随机配对。交叉算子的设计包括两个方面的内容：如何确定交叉点的位置?如何进行部分基因的交换? 下面介绍几种适用于二进制编码或实数编码的交叉算子。（1）单点交叉。又称为简单交叉，它是指在个体编码串中随机设置一个交叉点，然后在该点相互交换两个配对个体的部分基因。（2）双点交叉。它的具体操作过程是：在相互配对的两个个体编码串中随机设置两个交叉点；交换两个交叉点之间的部分基因。（3）均匀交叉。它是指两个配对个体的每一位基因都以相同的概率进行交换，从而形成两个新个体。具体操作过程如下：随机产生一个与个体编码长度相同的二进制屏蔽字W=ww w；按下列规则从A 、B两个父代个体中产生两个新个体X、Y：若w=0，则X的第i个基因继承A 的对应基因，Y的第i个基因继承B的对应基因；若w=1，则A、B的第i个基因相互交换，从而生成X、Y的第i个基因。（4）算术交叉。它是指由两个个体的线性组合而产生出新的个体。设在两个个体A、B之间进行算术交叉，则交叉运算后生成的两个新个体X、Y为：X=+(1-)B；Y=+(1-)A。3.2.3 变异运算根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。例如有个体S101011。对其的第1，4位置的基因进行变异，则有S=001111单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。4 遗传算法的特点GA是一种利用自然选择和进化思想在高维空间中寻优的方法，它不一定能寻得最优点，但是它可以找到更优点。因此GA可能会暂时停留在某些非最优点上，直到变异发生使它跃居到另一个更优点上。GA寻优过程的一个重要特点是它始终保持整个种群的进化，这样即使某个体在某时刻丧失了有用的特征，这种特征也会被其他个体所保留并延续发展下去。由于GA仅需知道目标函数的信息，而不需要其连续可微等要求，因而具有广泛的适应性。同时它又是一种采用启发性知识的智能搜索算法，所以往往能在搜索空间高度复杂的问题上取得比其他算法更好的效果。5 遗传算法的发展动向遗传算法作为一种对生物进化现象进行仿真的程序，取得了人工遗传的模拟效果，具有自适应性。在遗传算法的结构中遗传操作和选择机制是两个重要的因素，其联系可用遗传算法=遗传操作+选择过程这个逻辑关系来表示。如果一个应用问题不能求得目标函数的全局最优值,而只能或只希望求一定意义下的满意解，这时,可供选择的方法之一自然是遗传算法，因为遗传算法比其他算法有更多的优势。可喜的是,近年来遗传算法在商业应用方面取得了一系列重要成果。遗传算法的商业应用五花八门,覆盖面甚广,比如通用电器公司的计算机辅助设计系统Engeneous,这是一个采用了遗传算法以及其他传统的优化技术做为寻优手段的混合系统(hybrid system)。Engeneous已成功地应用于汽轮机设计,并改善了新的波音777发动机的性能，这是目前正在研究和应用的一个重要方面。遗传算法具有隐并行性，它可容易改造成为并行/分布式算法，用来解决那些复杂性问题。到目前，遗传算法的理论机制仍不是很清楚，这可能和生命科学的研究一样，将是一个永恒的研究课题。6 结束语遗传算法的研究归纳起来分为理论与技术研究、应用研究两个方面。理论与技术研究主要从遗传操作、群体大小、参数控制、适应度评价以及并行实现技术等方面来提高遗传算法的性能。应用研究则是遗传算法的主要方向，开发遗传算法的商业软件、开拓更广泛的遗传算法应用领域是今后应用研究的主要任务。参考文献：1 王小平,曹立明,等遗传算法理论、应用与软件实现M.西安:西安交通大学出版 社,2002.2 李敏强等.遗传算法的基本理论与应用M.北京:科学出版社,2002.3 吉根林.遗传算法研究综述J.计算机