遗传算法论文

论文名称：遗传算法姓名：徐庆地学号：20112212478班级：计算机科学与技术1班院系：信息与电气工程学院日期：2014年6月18日第1页摘要................................................................................................................................2第一章引言..................................................................................................................31．1搜索法............................................................................................................31.2遗传算法...........................................................................................................3第二章遗传算法(GeneticAlgorithms，GA)..............................................................42.1遗传算法的基本概念.......................................................................................42.2遗传算法的实现步骤.......................................................................................6第三章遗传算法的特点及应用..................................................................................93.1遗传算法的特点...............................................................................................93.2遗传算法的应用...............................................................................................9第四章遗传算法的缺点及发展................................................................................124.1遗传算法的缺点.............................................................................................12第五章遗传算法代码实现........................................................................................13附录遗传算法代码（GACode）.........................................................................14第2页摘要智能搜索算法包括遗传算法、禁忌算法、模拟退火算法等。其中遗传算法（GA）是人类从基因遗传的生物进化思想的启发下提出的，它是一种进化计算，进化计算实质上是自适应的机器学习方法，遗传算法根据基因遗传时候的变化，它在运算的时候也分为选择、交叉、变异三种行为。它比盲目的搜索效率高的多，又比专门的针对特定问题的算法通用性强，它是一种于问题无关的求解模式。但是遗传算法又有很大的不确定性，以及过早的收敛性，所以可以和其他算法一起使用来对问题求解。关键词：遗传算法；GA；实现；应用；改进第3页第一章引言1．1搜索法人工智能问题广义地说，都可以看作是一个问题求解问题，在问题的求解过程中，人们所面临的大多数现实问题往往没有确定性的算法，通常需要用搜索算法来解决。搜索法是人工智能中问题的求解的基本方法，搜索法可大致分为有信息搜索和无信息搜索，约束满足问题和博弈问题的求解均可表述为搜索过程。搜索法的本质是再状态空间中从问题的初始状态搜索到通向目标状态的路径。当前的智能搜索算法本质上也是搜索法，如遗传算法、蚁群算法、神经网络等。一般搜索可以根据是否使用启发式信息分为盲目搜素和启发式搜索，也可以根据问题的表示方式分为状态空间搜索和与/或树搜索。盲目搜索一般是指从当前状态到目标状态需要走多少步或者并不知道每条路径的花费，所能做的只是可以区分出哪个是目标状态。启发式搜索时在搜索过程中加入了与问题有关的启发式信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解并找到最优解。很显然盲目搜索不如启发式搜索效率高，但是由于启发式搜索需要和问题本身特性有关的信息而对很多问题这些信息很少，或者根本就没有，或者很难抽取，所以盲目搜索仍然是很重要的搜索策略。1.2遗传算法进化计算（EvolutionaryComputation，EC）是在达尔文的进化论和孟德尔的遗传变异理论的基础上产生的一种在基因和种群层次上模拟自然界生物进化过程与机制的问题求解技术。它主要包括遗传算法（GeneticAlgorithm，GA）进化策略（EvolutionaryStrategy,ES）进化规划（EvolutionaryProgramming,EP）遗传规划（GeneticProgramming,GP）它将生物进化过程中的繁殖（Reproduction）变异（Mutation）竞争（Competition）选择（Selection）引入到了算法中。从而诞生了遗传算法。第4页第二章遗传算法(GeneticAlgorithms，GA)2.1遗传算法的基本概念2.1.1遗传算法的由来生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。自然界生物进化过程是进化计算的生物学基础，它主要包括遗传(Heredity)、变异(Mutation)和进化(Evolution)理论。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。遗传算法的概念最早是由BagleyJ.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的J.H.Holland所实行。当时，其主要目的是说明自然和人工系统的自适应过程。遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些能适应环境的个体特征方能保留下来。Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。2.1.2遗传算法的原理遗传算法的基本思想是从初始种群出发，采用优胜劣汰、适者生存的自然法则选择个体，并通过杂交、变异来产生新一代种群，如此逐代进化，直到满足目标为止。遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码(后来发展出了整数编码、实数编码等)的串。并且，在执行遗传算法之前，给出一第5页群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。根据进化术语，对群体执行的操作有三种：1．选择(Selection)这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differentialreproduction)。2．交叉(Crossover)这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。3．变异(Mutation)这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。2.1.3遗传算法涉及的基本因素种群（Population）：种群是指用遗传算法求解问题时，初始给定的多个解的集合。遗传算法的求解过程是从这个子集开始的。个体（Individual）：个体是指种群中的单个元素，它通常由一个用于描述其基本遗传结构的数据结构来表示。例如，可以用0、1组成的长度为l的串来表示个体。染色体（Chromosome）：染色体是指对个体进行编码后所得到的编码串。染色体中的每1位称为基因，染色体上由若干个基因构成的一个有效信息段称为基因组。适应度(fitness)：借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。适应度（Fitness）函数：适应度函数是一种用来对种群中各个个体的环境适第6页应性进行度量的函数。它一般是一个实值函数，该函数就是遗传算法中指导搜索的评价函数。其函数值是遗传算法实现优胜劣汰的主要依据。遗传操作（GeneticOperator）：遗传操作是指作用于种群而产生新的种群的操作。标准的遗传操作包括以下3种基本形式：选择（Selection）杂交（Crosssover）变异（Mutation）2.2遗传算法的实现步骤2.2.1遗传算法的流程框图，如图1所示：图1：基本遗传算法的算法流程图第7页2.2.2遗传算法的具体步骤，如：遗传算法的具体步骤所示图2：遗传算法的具体步骤第1步.初始种群的产生：可以随机产生(用编码方法表示);种群的大小(依赖于计算机的计算能力和计算复杂度)。第2步．编码方法：编码方法有二进制编码(只允许出现01)，顺序编码(编码不允许重复)，实数编码(运算简单，但反映不出基因的特性)，整数编码(编码可以重复)等。第3步．适值函数:在遗传算法中，适应函数是用来区分群体中个体好坏的标准，是算法演化过程的驱动力，同时也是进行自然选择的唯一依据。第4步．遗传运算:针对适值函数得到的适值概率，选择进行遗传的双亲进行杂交和变异以得到新的种群第5步．选择策略(见下节)第6步．停止准则:可以人为的设定遗传进行的代数，或者设定计算终止的条件，如数据精确度等。当停止准则满足，遗传算法终止。2.2.3遗传算法中的选择策略不同的选择策略将导致不同的选择压力，即下一代中父代个体的复制数目的不同分配关系。一．转盘式选择1.转盘式选择是基于适应值比例的选择中比较重要的选择策略。终止条件个体评价群体P(t)选择交叉变异群体P(t＋1)解码解集合初始化结束满足不满足iiff/第8页2.先计算个体的相对适应值pi=3.根据选择概率把一个圆盘分成N份4.生成一个内的随机数r(0≤r≤1)，若r(0≤r≤1)，则选择个体i从统计角度看，个体的适应度值越大，其对应的扇区的面积越大，被选中的可能性也越大。这种方法有点类似于发放奖品使用的轮盘，并带有某种赌博的意思，因此亦