进化计算文献综述

《进化计算文献综述》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

分数:___________任课教师签字：___________华北电力大学研究生结课作业学年学期：2011-2012第二学期课程名称：人工智能与知识工程学生姓名：刘鹏学号：2112221004提交时间：2012年4月11日 遗传算法介绍1.1遗传算法的基本思想现代科学理论研究与实践中存在着大量与优化、自适应相关的问题，但除了一些简单的情况之外，人们对大型复杂系统的优化和自适应问题仍然无能为力。然而，自然界的生物却在这一方面表现出了气优异的能力，它们能以优胜劣汰、适者生存的进化规则生存和繁衍，并逐步产生对其生存环境自适应很高的优良品种。遗传算法正是借鉴生物的自然选择和遗传进化机制而开发出的一种全局优化自适应概率搜索算法。遗传算法（GeneticAlgorithm）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。基于对自然界中生物遗传与进化机理的模仿，针对不同的问题，很多学者设计了许多不同的编码方法来表示问题的可行解，开发出了许多不同的遗传算子来模仿不同环境的生物遗传特性。这样，由于不同的编码方法和不同的遗传算子就构成了各种不同的遗传方法。但这些遗传方法都有共同的特点，即通过对生物的遗传和进化过程中的选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。遗传算法使用群体搜索技术，通过对当前群体施加选择、交叉、变异等一系列遗传操作，从而产生出新的一代群体，并逐步使群体进化到包含或接近最优解的状态。1.2遗传算法的一般特点遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。其中，遗传算法基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和突变操作。这种特殊的组合方式将遗传算法与其它搜索算法区别开来。遗传算法具有以下几方面的特点：(1)遗传算法从问题解的串集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。　　(2) 许多传统搜索算法都是单点搜索算法，容易陷入局部的最优解。遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。　　(3)遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。　　(4)遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导搜索方向。(5)具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。1.3遗传算法的构成要素（1）染色体的编码方法。基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二进制符号集{0,1}所组成的。初始群体中的各个个体的基因值可用均匀分布的随机数来生成。如：X=1001010001111001就表示一个个体，该个体的染色体长度是n=16。（2）个体适应度评价。遗传算法按与个体适应度的成正比的概率来决定当前群体中每个个体遗传到下一代群体机会多少。为正确计算这个概率，这里要要求所有个体适应度必须为正数或零，必须先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数为负值时的处理方法。（3）遗传算子。基本遗传算法使用下述三种遗传算子：1、选择运算使用比例算子；2、交叉运算使用单点交叉算子；3、变异运算使用基本位变异算子或均匀变异算子；（4）基本遗传算法的运行参数。基本遗传算法有下述4个运行参数需要提前设定：1、群体大小，即群体中所含个体的数量，一般为40~200。2、遗传运算的终止进化代数，一般为200~1000。3、交叉概率，一般为0.4~0.99。4、变异概率，一般为0.001~0.1。 上述4个运算参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合理选择的依据。在遗传算法的实际应用中，往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围。1.4遗传算法的基本操作遗传算法的基本操作主要有如下三个：（1）选择（SelectionOperator）选择算子是从群体中选择优胜的个体，淘汰劣质个体的操作，选择操作保证了优秀的个体可以从父代传到子代。常用的选择算子有：适应度比例方法(赌轮法或叫蒙特卡罗法)、最佳个体保存方法、期望值方法、排序选择法、联赛选择法、排挤法。从群体中选择优胜的个体，淘汰劣质个体的操作叫做选择。选择的目的是把“优化的解”直接遗传到下一代或者通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上，目前常用的选择算子有：1、比例选择。比例选择方法是一种回放式随机采样的方法。其基本思想是：各个个体被选中的概率与其适应度大小成正比。这种选择方法的优点是避免基因的缺失、提高安全收敛性和计算效率；但缺点是由于选择的随机性较大，可能导致概率很大的个体不能够选中，而概率很小的个体被选中，因此可能导致选择误差较大。2、最优保存策略。在遗传算法的运行过程中，由于选择、交叉、变异等遗传操作的随机性，有可能破坏掉当前群体中适应度最好的个体。因此，群体中适应度最高的个体不参与交叉运算和变异运算，而是用来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体。最优保存策略的实施可保证迄今为止所得到的最优个体不会被交叉、变异等遗传操作所破坏。但另一方面，容易使得某种局部最优个体不易被淘汰反而快速扩散，从而使算法的全局搜索能力不强。3、无放回余数随机选择。无放回余数随机选择的基本思想是根据每个个体在下一代群体中的生存期望值来进行随机选择运算。这种选择操作方法可确保适应度比平均适应度大的一些个体能够被遗传到下一代群体中，所以选择误差比较小。 4、排序选择。排序选择方法的主要着眼点是个体适应度之间的大小关系，对个体适应度是否取正值或负值以及个体适应度之间的数值差异程度并无特别要求。排序选择方法的主要思想是：对群体中的所有个体按其适应度大小进行排序，基于这个排序来分配各个个体被选中的概率。该方法的缺点是实施必须根据对所研究问题的分析和理解情况预先设计一个概率分配表，这个设计过程无一定规律可寻，仍具有较大的选择误差。5、随机联赛选择。随机联赛选择也是一种基于个体适应度之间大小关系的选择方法。其基本思想是每次选取几个个体之中适应度最高的一个个体遗传到下一代群体中。在联赛选择操作中，无个体适应度之间的算术运算，所以对个体适应度是取正值还是取负值无特别要求。但是这种方法极易陷入局部最优解。（2）交叉（CrossoverOperator）在生物的进化过程中，两个同源染色体通过交配而重组，形成新的染色体，从而产生新的个体或物种。交配和重组是生物遗传和进化的一个主要环节。模仿这个环节，在遗传算法中也使用交叉算子来产生新的个体。遗传算法中的所谓交叉运算是对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，在遗传算法中起着关键作用，是产生新个体的主要方法。交叉算子的设计和实现与所研究的问题密切相关，一般要求既不要太多的破坏个体编码串中表示优良性状的优良模式，又要能够有效地产生出一些较好的新个体模式，另外，交叉算子的设计要和个体编码设计统一考虑。下面介绍几种交叉算子：1.单点交叉算子单点交叉算子又称为简单交叉，是指在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分基因。如下：A:xxxx|xxxxB:yyyy|yyyy若交叉点再第4位则交叉后产生的新个体为：A`：xxxx|yyyy B`：yyyy|xxxx单点交叉的重要特点是：若邻接基因座之间的关系能够提供较好的个体性状和较高的个体适应度的话，则这种单点交叉操作破坏了这个性状和降低个体适应度的可能最小。2.双点交叉与多点交叉双点交叉是指在个体编码串中随机设置两个交叉点，然后再进行部分基因交叉。他的过程是：（1）在相互配对的两个个体编码串中随机设置两个交叉点。（2）交换这两个个体所设定的两个交叉点之间的部分基因。其操作实例如下：若交叉点分别在第2位和第8位，则交叉后新生成的基因如下：A:xx|xxxxxx|xxA`:xx|yyyyyy|xxàB:yy|yyyyyy|yyB`:yy|xxxxxx|yy将两点交叉的概念加以推广就得到了多点交叉的概念。即多点交叉是指在个体编码串中随机设置多个交叉点，然后进行基因交换。（3）变异(MutationOperator)在生物的遗传和自然进化过程中其细胞分裂复制环节有可能会因为某些偶然因素的影响而产生一些复制错误，这样就会导致某些基因发生某种变异，从而产生出新的个体，表现出新的生物性状。虽然发生这种变异的可能性比较小，但也是产生新物种的一个不可忽视的原因。模仿生物遗传和进化过程中的这个变异环节，在遗传算法中也引入了变异算子来产生出新的个体。遗传算法中的变异运算，是指将将个体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。若是字符集编码如{A,B,C,D….}变异操作就是用这个字符集中的一个随机指定的且与原基因值不相同的符号去替换变异点上的原有符号。 从遗传运算过程中产生新个体的能力方面来说，交叉运算是产生新个体的主要方法，交叉运算决定了遗传算法的全局搜索能力；而变异运算只是产生新个体的辅助方法，但也是一个必不可少的运算步骤，因为变异运算决定了遗传算法的局部搜索能力。交叉算子和变异算子的相互配合，共同完成对搜索空间的全局搜索和局部搜索，从而使得遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。设置变异算子主要有两个目的，一是改善遗传算法的局部搜索能力。遗传算法使用交叉算子已经从全局的角度出发找到了一些较好的个体编码结构，已接近或有助于接近问题的最优解。但使用交叉算子无法对搜索空间的细节进行局部搜索。这时若再使用变异算子来调整个体编码串中的部分基因，就可以从局部的角度出发使个体更加逼近于最优解，从而提高了遗传算法的局部搜索能力。另一个目的是维持群体的多样性，变异算子用新的基因值替换原有的基因值，从而可以改变个体编码串的结构，维持群体的多样性。在一般的遗传算法中常用基本位变异和均匀变异，基本位变异操作是指对个体编码串中以变异率Pm随机指定的某一位或某几位基因座上的基因值作变异运算。基本位变异操作改变的只是个体编码串中的个别几个基因座上的基因值，并且变异发生的概率也比较小，所以其发挥的作用比较慢，作用的效果也不明显。均匀变异操作是指分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中的各个基因座上的原有基因值。均匀变异一般只适合应用于遗传算法的初期阶段，使得搜索点可以在整个搜索空间内自由移动，从而可以增加群体的多样性，使算法处理更多的模式。根据实际应用中的旅行商问题本文变异算子采用的是倒位操作，是指颠倒个体编码串中随机指定的两个基因座之间的基因排列顺序，从而形成一个新的个体。例如：图1.1倒位操作图1.1倒位操作 在个体编码串中随机指定两个基因座之后的位置为倒位点，然后颠倒这两个倒位点之间的基因排列顺序。交换前的基因序列为{a,f,e,d,c,b,g}经过倒位逆序部分基因后形成的新个体的基因序列为{a,b,c,d,e,f,g}。倒位操作改变了个体编码串的部分基因排列顺序，其目的主要是为了能够使遗传算法更有利于产生优良的模式。因为有时对形成一种较好模式有积极意义的基因在个体的编码串中隔离的距离较远，而利用倒位算子就有可能使它们逐渐接近，从而可能形成更好的个体。1.5遗传算法的运算过程图1.2所示为遗传算法的运算过程示意图。图1.2遗传算法运算过程示意图由该图可以看出，遗传算法主要使用上述三种遗传算子（选择算子、交叉算子、变异算子），其主要运算过程如下所述。步骤一：初始化。设置进化代数计数器t←0;设置最大进化代数T；随机生成M个个体作为初始群体P(0)。步骤二：个体评价。计算群体P(t)中各个个体的适应度。步骤三：选择运算。将选择算子作用于群体。步骤四：交叉运算。将交叉算子作用于群体。步骤五：变异运算。将变异算子作用于群体。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。步骤六：终止条件判断。若t≤T，则t←t+1,转到步骤二；若t>T ，则进化过程中所得到的最大适应度的个体作为最优解输出，终止计算。1.6遗传算法的应用领域遗传算法在以下领域有十分广泛的应用：（1）函数优化。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用例子。很多人工构造的各种各样复杂形式的测试函数，有连续函数也有离散函数，有单峰函数也有多峰函数等，利用这些函数来评价遗传算法的性能。对于非线性、多目标的函数优化问题，用其他算法通常较难求解，但使用遗传算法却很方便并可以得到较好的结果。（2）组合优化。随着问题的增大，组合优化问题的搜索空间也急剧扩大，甚者有时无法求到精确最优解。采用传统的优化方法很难得到最优解。遗传算法是寻求这种满意解的最佳工具。例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。（3）生产调度问题。在很多情况下，采用建立数学模型的方法难以对生产调度问题进行精确求解。在现实生产中多采用一些经验进行调度。遗传算法是解决复杂调度问题的有效工具，如在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。（4）自动控制。在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已经在其中得到了初步的应用。例如，利用遗传算法进行控制器参数的优化、基于遗传算法的模糊控制规则的学习、基于遗传算法的参数辨识、基于遗传算法的神经网络结构的优化和权值学习等。（5）机器人。机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于人工自适应系统的研究。所以，机器人学理所当然地成为遗传算法的一个重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方而得到研究和应用。（6）图像处理。 图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会存在一次误差，从而影响图像的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在这些图像处理中的优化计算方面找到了用武之地。目前已在模式识别(包括汉字识别)、图像恢复、图像边缘特征提取等方而得到了应用。总结遗传算法是新发展起来的一门学科，各种理论、方法尚未成熟，有待于进一步地发展和完善，但它却为我们解决许多复杂问题提供了希望。尽管在遗传算法的研究和应用中会出现许多的难题，同时也会产生许多不同的算法设计观点，然而，目前遗传算法的各种应用实践已经展现出了其优异的性能和巨大的发展潜力，它的发展前景激励着各类专业技术人员把遗传算法的理论和方法运用与自己的工作实践中。我相信，随着研究工作的进一步深入和发展，遗传算法越来越广泛应用于机器学习、模式识别、图像处理、神经网络、工业优化控制和社会科学等方面，在不久的将来，它的优化作用将得到更好的发挥。