遗传算法

人工智能张晓伟[e-mail]25.3进化计算进化计算（EvolutionaryComputation,EC）是在达尔文（Darwin）的进化论和孟德尔（Mendel）的遗传变异理论的基础上产生的一种在基因和种群层次上模拟自然界生物进化过程与机制的问题求解技术。它主要包括遗传算法（GeneticAlgorithm，GA）进化策略（EvolutionaryStrategy,ES）进化规划（EvolutionaryProgramming,EP）遗传规划（GeneticProgramming,GP）四大分支。其中，第一个分支是进化计算中最初形成的一种具有普遍影响的模拟进化优化算法。因此我们主要讨论遗传算法。35.3.1进化计算概述——生物学基础什么是进化计算进化计算是一种模拟自然界生物进化过程与机制进行问题求解的自组织、自适应的随机搜索技术。它以达尔文进化论的“物竟天择、适者生存”作为算法的进化规则，并结合孟德尔的遗传变异理论，将生物进化过程中的繁殖（Reproduction）变异（Mutation）竞争（Competition）选择（Selection）引入到了算法中。4进化计算的生物学基础自然界生物进化过程是进化计算的生物学基础，它主要包括遗传(Heredity)、变异(Mutation)和进化(Evolution)理论。进化论进化是指在生物延续生存过程中，逐渐适应其生存环境，使得其品质不断得到改良的这种生命现象。遗传和变异是生物进化的两种基本现象，优胜劣汰、适者生存是生物进化的基本规律。长颈鹿的祖先当中，脖子有长有短。脖子短的无法和脖子长的竞争食物，渐渐被淘汰了。几代之后，所有的长颈鹿都是长颈的。5达尔文的自然选择学说认为：在生物进化中，一种基因有可能发生变异而产生出另一种新的生物基因。这种新基因将依据其与生存环境的适应性而决定其增殖能力。一般情况下，适应性强的基因会不断增多，而适应性差的基因则会逐渐减少。通过这种自然选择，物种将逐渐向适应于生存环境的方向进化，甚至会演变成为另一个新的物种，而那些不适应于环境的物种将会逐渐被淘汰。达尔文，进化论之父6遗传理论遗传是指父代（或亲代）利用遗传基因将自身的基因信息传递给下一代（或子代)，使子代能够继承其父代的特征或性状的这种生命现象。正是由于遗传的作用，自然界才能有稳定的物种。“种瓜得瓜，种豆得豆”“龙生龙，凤生凤，老鼠生儿打地洞”孟德尔（1822—1884），奥地利人，遗传学的奠基人。7在自然界，构成生物基本结构与功能的单位是细胞（Cell）。细胞中含有一种包含着所有遗传信息的复杂而又微小的丝状化合物，人们称其为染色体（Chromosome）。在染色体中，遗传信息由基因（Gene）所组成，基因决定着生物的性状，是遗传的基本单位。染色体的形状是一种双螺旋结构，构成染色体的主要物质叫做脱氧核糖核酸(DNA)，每个基因都在DNA长链中占有一定的位置。一个细胞中的所有染色体所携带的遗传信息的全体称为一个基因组(Genome)。细胞在分裂过程中，其遗传物质DNA通过复制转移到新生细胞中，从而实现了生物的遗传功能。8变异理论变异是指子代和父代之间，以及子代的各个不同个体之间产生差异的现象。变异是生物进化过程中发生的一种随机现象，是一种不可逆过程，在生物多样性方面具有不可替代的作用。引起变异的主要原因有以下两种：杂交指有性生殖生物在繁殖下一代时两个同源染色体之间的交配重组，即两个染色体在某一相同处的DNA被切断后再进行交配重组，形成两个新的染色体。复制差错指在细胞复制过程中因DNA上某些基因结构的随机改变而产生出新的染色体。龙生九子，九子九样95.3.1进化计算概述——产生与发展进化计算自20世纪50年代以来，其发展过程大致可分为三个阶段。萌芽阶段（'50年代后期到'70年代中期）20世纪50年代后期，一些生物学家在研究如何用计算机模拟生物遗传系统中，产生了遗传算法的基本思想，并于1962年由美国密执安（Michigan）大学霍兰德（Holland）提出。1965年德国数学家雷切伯格（Rechenberg）等人提出了一种只有单个个体参与进化，并且仅有变异这一种进化操作的进化策略。同年，美国学者弗格尔（Fogel）提出了一种具有多个个体和仅有变异一种进化操作的进化规划。1969年美国密执安（Michigan）大学的霍兰德（Holland）提出了系统本身和外部环境相互协调的遗传算法。至此，进化计算的三大分支基本形成。10成长阶段（'年代中期到'80年代后期）1975年，霍兰德出版专著《自然和人工系统的适应性（AdaptationinNaturalandArtificialSystem）》，全面介绍了遗传算法。同年，德国学者施韦费尔（Schwefel）在其博士论文中提出了一种由多个个体组成的群体参与进化的，并且包括了变异和重组这两种进化操作的进化策略。1989年，霍兰德的学生戈尔德伯格（Goldberg）博士出版专著《遗传算法——搜索、优化及机器学习（GeneticAlgorithm——inSearchOptimizationandMachineLearning）》，使遗传算法得到了普及与推广。Prof.Holland电气工程、计算机科学领域专家遗传算法提出者11发展阶段（'90年代至今）1989年，美国斯坦福（Stanford）大学的科扎（Koza）提出了遗传规划的新概念，并于1992年出版了专著《遗传规划----应用自然选择法则的计算机程序设计（GeneticProgramming:ontheProgrammingofComputerbyMeansofNaturalSelection）》该书全面介绍了遗传规划的基本原理及应用实例，标志着遗传规划作为计算智能的一个分支已基本形成。进入20世纪90年代以来，进化计算得到了众多研究机构和学者的高度重视，新的研究成果不断出现、应用领域不断扩大。目前，进化计算已成为人工智能领域的又一个新的研究热点。125.3.2遗传算法——研究内容•性能分析。遗传算法的性能分析一直都是遗传算法研究领域中最重要的主题之一。在遗传算法中，群体规模、杂交和变异算子的概率等控制参数的选取是非常困难的，同时它们又是必不可少的实验参数。遗传算法还存在一个过早收敛问题，也就是说遗传算法的最后结果并不总是达到最优解，怎样阻止过早收敛问题是人们感兴趣的问题之一。另外，为了拓广遗传算法的应用范围，人们在不断研究新的遗传染色体表示法和新的遗传算子。•并行遗传算法。遗抟算法在操作上具有高度的并行性，只要通过保持多个群体和恰当地控制群体间的相互作用来模拟并行执行过程，即使不使用并行计算机，我们也能提高算法的执行效率。•分类系统。分类系统属于基于遗传算法的机器学习中的一类型，它包括一个简单的基于串规则的并行生成子系统、规则评价子系统和遗传算法子系统。目前，分类系统是遗传算法研究中的一个非常活跃的领域135.3.2遗传算法——基本概念遗传算法的基本思想是从初始种群出发，采用优胜劣汰、适者生存的自然法则选择个体，并通过杂交、变异来产生新一代种群，如此逐代进化，直到满足目标为止。遗传算法所涉及到的基本概念主要有以下几个：种群（Population）：种群是指用遗传算法求解问题时，初始给定的多个解的集合。遗传算法的求解过程是从这个子集开始的。个体（Individual）：个体是指种群中的单个元素，它通常由一个用于描述其基本遗传结构的数据结构来表示。例如，可以用0、1组成的长度为l的串来表示个体。染色体（Chromos）：染色体是指对个体进行编码后所得到的编码串。染色体中的每1位称为基因，染色体上由若干个基因构成的一个有效信息段称为基因组。适应度（Fitness）函数：适应度函数是一种用来对种群中各个个体的环境适应性进行度量的函数。其函数值是遗传算法实现优胜劣汰的主要依据遗传操作（GeneticOperator）：遗传操作是指作用于种群而产生新的种群的操作。标准的遗传操作包括以下三种基本形式：选择（Selection）交叉（Crosssover）变异（Mutation）14遗传算法与自然进化的比较自然界染色体基因等位基因(allele)染色体位置(locus)基因型(genotype)表型(phenotype)遗传算法字符串字符，特征特征值字符串位置结构参数集译码结构155.3.2遗传算法——基本结构遗传算法主要由染色体编码、初始种群设定、适应度函数设定、遗传操作设计等几大部分所组成，其算法主要内容和基本步骤可描述如下：(1)选择编码策略，将问题搜索空间中每个可能的点用相应的编码策略表示出来，即形成染色体；(2)定义遗传策略，包括种群规模N，交叉、变异方法，以及选择概率Pr、交叉概率Pc、变异概率Pm等遗传参数；(3)令t=0，随机选择N个染色体初始化种群P(0)；(4)定义适应度函数f（f0）；(5)计算P(t)中每个染色体的适应值；(6)t=t+1；(7)运用选择算子，从P(t-1)中得到P(t)；(8)对P(t)中的每个染色体，按概率Pc参与交叉；(9)对染色体中的基因，以概率Pm参与变异运算；(10)判断群体性能是否满足预先设定的终止标准，若不满足则返回(5)。16计算种群中个体的适应度并进行评价满足终止条件吗？终止选择交叉变异Y基本遗传算法的算法流程图编码和生成初始种群N选择175.3.2遗传算法——遗传编码常用的遗传编码算法有二进制码、格雷码（GrayCode）、实数编码和字符编码等。二进制编码（Binaryencoding）二进制编码是将原问题的结构变换为染色体的位串结构。在二进制编码中，首先要确定二进制字符串的长度l，该长度与变量的定义域和所求问题的计算精度有关。例假设变量x的定义域为[5，10]，要求的计算精度为10E-5，则需要将[5，10]至少分为600000个等长小区间，每个小区间用一个二进制串表示。于是，串长至少等于20，原因是：524288=219600000220=1048576这样，对应于区间[5，10]内满足精度要求的每个值x，都可用一个20位编码的二进制串b19,b18,…,b0来表示。二进制编码存在的主要缺点是汉明（Hamming）悬崖。例如，7和8的二进制数分别为0111和1000，当算法从7改进到8时，就必须改变所有的位。18格雷编码（Grayencoding）格雷编码是对二进制编码进行变换后所得到的一种编码方法。这种编码方法要求两个连续整数的编码之间只能有一个码位不同，其余码位都是完全相同的。它有效地解决了汉明悬崖问题，其基本原理如下：设有二进制串b1,b2,…,bn，对应的格雷串为a1,a2,…,an，则从二进制编码到格雷编码的变换为：其中，⊕表示模2加法。而从一个格雷串到二进制串的变换为：例十进制数7和8的二进制编码分别为0111和1000，而其格雷编码分别为0100和1100。1111iiibiabbi-ì=ïï=íï?ïî1(mod2)iijjba==å19实数编码（Realencoding）实数编码是将每个个体的染色体都用某一范围的一个实数（浮点数）来表示，其编码长度等于该问题变量的个数。这种编码方法是将问题的解空间映射到实数空间上，然后在实数空间上进行遗传操作。由于实数编码使用的是变量的真实值，因此这种编码方法也叫做真值编码方法。实数编码适应于那种多维、高精度要求的连续函数优化问题。205.3.2遗传算法——适应度函数适应度函数是一个用于对个体的适应性进行度量的函数。通常，一个个体的适应度值越大，它被遗传到下一代种群中的概率也就越大。常用的适应度函数在遗传算法中，有许多计算适应度的方法，其中最常用的适应度函数有以下两种：原始适应度函数它是直接将待求解问题的目标函数f(x)定义为遗传算法的适应度函数。例如，在求解极值问题时，f(x)即为x的原始适应度函数。采用原始适应度函数的优点是能够直接反映出待求解问题的最初求解目标，其缺点是有可能出现适应度值为负