遗传算法的应用

期末论文课程名称：人工智能设计题目：遗传算法院系：xxxxxxxx班级：xxxxxxxx设计者：xxxxxxx学号：xxxxxxxxxxxxx指导教师：xxxxxxxxx昆明学院遗传算法的发展及其应用摘要：遗传算法GA（GeneticAlgorithms）由美国学者J.H.Holland提出，它是建立在达尔文的生物进化论和孟德尔的遗传学说基础上的算法。基因杂交和基因突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选择，适应值高的基因结构就保存下来。它是一种模拟自然界生物进化过程的计算模型。它的求解问题是从多个可行解开始，然后通过一定的法则进行迭代以产生新解，直到得到最优结果。就实质而言，遗传算法是一种具有内在并行性，能有效解决计算量大的问题。关键词：遗传算法，最优化方法，遗传算法的应用TheDevelopmentAndApplicationofGeneticAlgorithms(SchoolofControlScienceandEngineering,ShandongUniversity,Jinan,250061)Abstract:GeneticAlgorithms(GA)isputforwardbytheAmericanscholarsJ.H.Holland,itisbasedontheDarwin'stheoryofevolutionandMendel'sbiologicalGenetictheoryonthebasisofthealgorithm.Geneandgenemutationsmayproducehybridofenvironmentadaptableoffspringofthesurvivalofthefittest,throughnaturalselection,adapttothegeneticstructureofhighvalueispreserved.Itisanaturalevolutionprocessofthesimulationcalculationmodel.ItwassolvedDuoGefeasiblesolutionfromthestart,andthenthroughthecertainprinciplesoftheiterationtoproducenew,gettheoptimalresultsuntil.Justparenchyma,geneticalgorithmisahasintrinsicparallelism,caneffectivelysolvetheproblemoflargeamountofcalculation.Keywords:GeneticAlgorithms,optimizationmethod,thedevelopmentofGeneticAlgorithms遗传算法的生物学基础生物在其延续生存的过程中，逐渐适应于其生存环境，使得其品质不断得到改良，这种生命现象称为进化（Evolution）生物进化是以集团形式进行的，这样的一个团体称为群体（Population），组成群体的单个生物称为个体（Individual），每个个体对其生存环境都有不同的适应能力，这种适应能力称为个体适应（Fitness）。达尔文（Darwin）把在生存斗争适者生存，不适者淘汰的过程叫做自然选择（NaturalSelection）[1]。达尔文的自然选择学说表明，遗传和变异是决定生物进化的内在因素，生物发展进化主要有三个原因：遗传、变异和选择。遗传是指父代与子代之间，在性状上存在的相似现象。变异是指父代与子代之间，以及子代的个体之间，在性状上或多或少地存在的差异现象。选择是指具有精选的能力，它决定生物进化的方向。遗传算法的产生和发展50年代末60年代初，生物学家Fraser试图通过计算的方法来模拟生物界遗传与选择的进化过程，这便是GA的雏形。受此启发，Holland教授认识到自然遗传可以转化为人工遗传算法。1967年Bagley在其博士论文中首次提出了遗传算法这一术语。1975年，Holland出版了《自然与人工系统中的适应性行为》。该书系统地阐述了遗传算法的基本理论和方法，提出了遗传算法的基本定理-模式定理，从而奠定了遗传算法的理论基础。20世纪80年代初，Holland教授实现了第一个基于遗传算法的机器学习系统--分类器系统(ClassifierSystem简称CS)，开创了基于遗传算法的机器学习的新概念。l992年，JohnR．Koza出版了专著《遗传编程》，提出了遗传编程的概念，并成功地把遗传编程的方法应用于人工智能、机器学习、符号处理等方面。随着遗传算法的不断发展，关于遗传算法的国际学术活动越来越多，遗传算法已成为一个多学科、多领域的重要研究方向。遗传算法是一种基于生物的自然选择和群体遗传机理的搜索算法。它模拟了自然选择和自然遗传过程中发生的繁殖、交配和突变现象。它将每个可能的解看做是群体（所有可能解）中的一个个体，并将每个个体编码成字符串的形式，根据预定的目标函数对每个个体进行评价，给出一个适应度值。开始时总是随机地产生一些个体（即候选解），根据这些个体的适应度利用遗传算子对这些个体进行操作，得到一群新个体，这群新个体由于继承了上一代的一些优良性状，因而明显优于上一代，这样逐步朝着更优解的方向进化。遗传算法在每一代同时搜索参数空间的不同区域，然后把注意力集中到解空间中期望值最高的部分，从而使找到全局最优解的可能性大大增加。遗传算法的特点作为进化算法的一个重要组成部分，遗传算法不仅包含了进化算法的基本形式和全部优点，同时还具备若干独特的性能：1)在求解问题时，遗传算法首先要选择编码方式，它直接处理的对象是参数的编码集而不是问题参数本身，搜索过程既不受优化函数连续性的约束，也没有函数导数必须存在的要求。通过优良染色体基因的重组，遗传算法可以有效地处理传统上非常复杂的优化函数求解问题。2)若遗传算法在每一代对群体规模为n的个体进行操作，实际上处理了大约O（n3）个模式，具有很高的并行性，因而具有明显的搜索效率。3)在所求解问题为非连续、多峰以及有噪声的情况下，能够以很大的概率收敛到最优解或满意解，因而具有较好的全局最优解求解能力。4)对函数的性态无要求，针对某一问题的遗传算法经简单修改即可适应于其他问题，或者加入特定问题的领域知识，或者与已有算法相结合，能够较好地解决一类复杂问题，因而具有较好的普适性和易扩充性。5)遗传算法的基本思想简单，运行方式和实现步骤规范，便于具体使用。遗传算法的基本思想遗传算法的思路和自然进化的思路是同出一辙的。遗传算法主要借用生物进化中“适者生存”的规律：最适合自然环境的群体往往产生了更大的后代群个种群所获得的“知识”都被嵌入其成员的染色体组成当中。遗传算法体。在进化过程中，每个种群所面临的问题是寻找一种对复杂和变化着的环境最有利的适应方式。每的思想正是做自然界想做的事情。我们以兔子作为例子：在一给定时间里，有一群兔子，其中一些比另外一些兔子跑得快，而且更加聪明，这些兔子被狐狸吃掉的可能性比较小，因此它们中的多数就存活下来并繁殖更多的兔子。当然，一些慢而愚笨的兔子也会活下来，只是因为它们比较幸运。这些存活的兔子群体开始生育。生育的结果是兔子遗传材质的充分融合：一些慢的兔子生出快的兔子，一些快的兔子生出更快的，一些聪明的兔子生出愚笨的兔子，等等。在最顶层，自然界时不时地变异一些兔子的基因材质。所产生的小兔子平均来说要比原始的群体更快更聪明，因为从狐狸口中生存下来的父代多数是跑得更快也更聪明的兔子。同样，狐狸也经历相似的过程——否则兔子可能跑得太快又太聪明以致狐狸根本抓不到了。可见，遗传算法遵循着和兔子的故事极相似的过程。遗传算法的构成要素对一给定的问题，遗传算法必须经过下面的五个步骤：·对问题潜在解的遗传表达。·产生潜在解初始群体的方法。·起环境作用的用“适应值”评价解的适应程度的评价函数。·改变后代组成的各种遗传算子。·遗传算法所使用的各种参数：群体规模、应用遗传算子的概率等。由此可见，基本遗传算法的构成要素有以下几个：（1）染色体编码方法。基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二值符号集{0，1}组成的。初始群体中的各个个体的基因值可用均匀分布的随机数来生成。（2）个体适应度评价。基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。（3）遗传算子(geneticoperators)。基本遗传算法只使用下述三种遗传算子：选择算子(SelectionOperator)使用比例选择算子，交叉算子(CrossoverOperator)使用单点交叉算子，变异算子(MutationOperator)使用基本位变异算子或均匀变异算子。（4）基本遗传算法的运行参数。基本遗传算法有下述4个运行参数需要提前设定：M：群体大小，即群体中所含个体的数量，一般取为20~100。T：遗传运算的终止进化代数，一般取为100~500。Pc：交叉概率(crossoverrate)，一般取为0.4~0.99。Pm：变异概率(mutationrate)，一般取为0.0001~0.1。需要说明的是，这4个运行参数对遗传算法的求解结果和效率都会有一定的影响，在遗传算法的实际应用中，往往需要经过多次试算后才能确定出这些参数合理的取值大小和取值范围。遗传算法的一般结构遗传算法借助生物遗传学的观点，通过对生物遗传和进化过程中的选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程，以实现各个个体的适应性的提高。遗传算法提供了一种求解复杂系统优化问题的通用框架，对一个需要进行优化计算的实际应用问题，一般可按下述步骤来构造求解该问题的遗传算法。第一步：确定决策变量及其各种约束条件，即确定个体的表现型X和问题的解空间。第二步：建立优化模型，即确定目标函数的类型（是求目标函数的最大值还是最小值）及其数学描述形式。第三步：确定表示可行解的染色体编码方法，即确定个体的基因型X及遗传算法的搜索空间。第四步：确定解码方法，即确定由个体基因型X到个体表现型X的对应关系或转换方法。第五步：确定个体适应度的量化评价方法，即确定由目标函数值)(xf到个体适应度F(x)的转换规则。第六步：设计遗传算子，即确定选择运算、交叉运算、变异运算等遗传算子的具体操作方法。第七步：确定遗传算法的有关运行参数，即确定遗传算法的M、T、Pc、Pm等参数。基本遗传算法是一个迭代过程，它模仿生物在自然环境中的遗传和进化机理，反复将选择算子、交叉算子、变异算子作用于群体，最终可得到问题的最优解或近似最优解。虽然算法的思想比较单纯，结构也比较简单，但它却也具有一定的实用价值，能够解决一些复杂系统的优化计算问题。遗传算法的运行参数遗传算法中需要选择的运行参数重要有个体编码串长度l、群体大小M、交叉概率Pc、变异概率Pm、终止代数T、代沟G等。（1）编码串长度l。使用二进制编码来表示个体时，编码串长度l的选取与问题所要求的求解精度有关；使用浮点数编码来表示个体时，编码串长度l与决策变量n的个数相等；使用符号编码来表示个体时，编码串长度l由问题的编码方式来确定；另外，也可使用变长度的编码来表示个体。具体采用何种编码示具体情况而定。（2）群体大小M。群体大小M表示群体中所含个体的数量。当M取值较小时，可提高遗传算法的运算速度，但却降低了群体的多样性，有可能会引起遗传算法的早熟现象；而当M取值较大时，又会使得遗传算法的运行效率降低。一般建议的取值范围是20~100。（3）交叉概率Pc。交叉操作是遗传算法中产生新个体的主要方法，所以交叉概率一般应取较大值。但若取值过大的话，它又会破坏群体中的优良模式，对进化运算反而产生不利影响；若取值过小的话，产生新个体的速度又较慢