遗传算法概述

1遗传算法概述

遗传算法是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的自适应概率性随机化迭代搜索算法。1975 年，美国Michigan 大学的J.H.Holland 教授在从事机器学习时注意到，学习不仅可以通过单个生物体的适应来完成，而且可以通过一个种群的许多进化适应来加以实现，Kenneth De Jong 将这种算法用来解决优化问题。Holland 研究GA 是从设计和实现一种能应付变化的、不确定环境的鲁棒性好的自适应系统开始。他认为这种系统的自适应是从所处的环境中随时得到反馈的函数关系，因而形成了我们今天称之为简单遗传算法的再生计划(Reproductive Plan)。这种简单的GA 只是一类具有固定种群(Population)规模、个体用固定长度的基因链的抽象模型。根据适应度(Fitness)来随机地选择双亲，并按交叉(Crossover)和变异(Mutation)算子来产生 新的种群。遗传算法的特点是它的算法中不包含待解决问题所持有的形态。它是从改变基因的配置来实现问题的整体优化的，因而属于自下而上的优化方法。类似于生物的进化过程，遗传算法处理的是变量集合的编码而非变量本身。它直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些特点已被人们广泛地应用于组合优化、机器学习、信号理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术之一。 2.进化计算

进化计算[19](Evolutionary Computation，简记为EC)是自60 年代开始发展的一门新兴学科。它是指以进化原理为仿真依据，按优胜劣汰的自然选择优化规律和方法，在计算机上解决科技领域中难以用传统优化方法解决的优化计算问题的算法和程序，因此有时也称之为进化算法(Evolutionary Algorithms，EA)。

进化计算最初具有三大分支：遗传算法(Gentic Algorithm ，GA)、进化规划(Evolutionary Programming，EP)和进化策略(Evolutionary Strategy，ES)。它们具有共同的本质，均来源于达尔文的进化论，分别强调了自然进行中的不同层面：遗传算法强调染色体的操作，进化策略强调了体级的行为变化，而进化规

划则强调种群级上的行为变化。90 年代初，在遗传算法的基础上又形成了一个分支：遗传程序设计(GeneticProgramming，GP)。虽然这几个分支在算法实现方面有一些差别，并且这些差别正逐渐缩小，它们一个共同的特点是借助生物进化的思想和原理来解决实际问题。作为进化计算理论体系的中心—遗传算法，其理论和方法不断地完善具有普遍的意义。现在进化算法EC 的研究主要集中于遗传算法GA、进化策略ES 和进行规划EP。国外在遗传编程GP 方面的研究已形成规模，在国内，这方面的研究还处于在探索阶段。

1)遗传算法GA 的基本思想

遗传算法[19](GA)是近几年发展起来的一种崭新的全局优化算法。1962 年霍兰德(Holland)教授首次提出了GA算法的思想，它的基本思想是基于Darwin 进化论和Mendel的遗传演说。Darwin 进化论最重要的是适者生存的原理，它认为每一代种群总是向着前进方向发展，越来越适应环境。每一个个体都有继承前代的特性，但不是完全继承，会产生一些新特性。最终只有适应环境的特征才能被保留下来。Mendel 遗传学说最重要的是基因遗传原理，它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。一条染色体中存在很多基因，每个基因有自己的位置并控制着外部特征；基因的产生和变异直接影响到个体的特性是否能适应环境。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。遗传算法正是借用了仿真生物遗传学和自然选择机理，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。这一点体现了自然界中\"物竞天择、适者生存\"进化过程。与自然界相似，遗传算法对求解问题的本身一无所知，从代表问题可能潜在解集的一个种群(population)开始，每一个种群则由经过基因(gene)编码(coding)的一定数目的个体(individual)构成。每个个体实际上是染色体(chromosome)带有特征的实体。把问题的解表示成染色体，并基于适应值来选择染色体，遗传算法所需要的仅是对算法所产生的每个染色体进行评价，使适应性好的染色体有更多的繁殖机会。在算法中也就是以二进制编码的串。并且，在执行遗传算法之前，给出一群染色体，也就是假设解。然后，把这些假设解置于问题的“环境”中，也即在一个适应度函数中来评价。并按适者生存的原则，从中选择出较适应环境的染色体进行复制, 淘汰低适应度的个体，再通过交叉，变异

过程产生更适应环境的新一代染色体群。对这个新种群进行下一轮进化，直到最适合环境的值。

2.3 遗传算法的基本概念

由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中要用到各种进化和遗传学的概念。这些概念如下：

1)染色体(Chromosome) 生物细胞中含有的一种微小的丝状化合物。这是遗传物质

的主要载体，由多个遗传因子－基因组成。

2)个体(Individual) 指染色体带有特征的实体。

3)串(String) 它是个体(Individual)的形式，在算法中为二进制，并且对应于遗传学中的染色体(Chromosome)。

4)基因(Gene) 基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝81011，则其中的1，0，1，1 这4 个元素分别称为基因。其值称为等位基因(Alletes)。

5)种群(Population) 染色体带有特征的个体的集合称为种群。该集合内个体数称为群体的大小。有时个体的集合也称为个体群。

6)群体大小(Population Size) 在群体中个体的数量称为群体的大小。 7)表现型(Phenotype) 由染色体决定性状的外部表现，或者说，根据遗传子型形成的个体。

8)基因位置(Gene Position) 一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101 中，0 的基因位置是3。基因位置对应于遗传学中的地点(Locus)。

9)基因特征值(Gene Feature) 在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011 中，基因位置3 中的1，它的基因特征值为2；基因位置1 中的1，它的基因特征值为8。

10)串结构空间ss 在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。

11)参数空间sr 这是串空间的物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。

12)非线性 它对应遗传学中的异位显性(Epistasis)。 13)适应度(Fitness) 表示某一个体对于环境的适应程度。

14)选择(Selection) 指决定以一定的概率从种群中选择若干个体的操作。一般而言，选择的过程是一种基于适应度的优胜劣汰的过程。

15)复制(Reproduction) 细胞在分裂时，遗传物质DNA 通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因。

16)交叉(Crossover) 有性生物在繁殖下一代时两个同源染色体之间通过交叉而重组，亦即在两个染色体的某一相同位置处DNA 被切断，其前后两串分别交叉组合形成两个新的染色体。这个过程又称基因重组recombination，俗称“杂交”。

17)变异(Mutation) 在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA 发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。

18)编码(Coding) DNA 中遗传信息在一个长链上按一定的模式排列，也即进行了遗传编码。遗传编码可以看作从表现型到遗传子型的映射。

19)解码(Decoding) 从遗传子型到表现型的映射。 2.4 遗传算法的模式定理

模式定理是遗传算法的理论基础，它描述了遗传算法的搜索策略。 1) 模式

定义2.1 设GA 的个体p∈Bl ，记集合S={0,1,*}l ，则称∀S ∈S 为一个模式

(Schemata)，其中，“*”代表通配符，l 表示个体染色体长度。由以上定义可见，所谓“模式”就是指编码的字符串中具有类似特征的子集。在二进9制编码的串中，模式是基于三个字符集(0,1,*)的字符串，字符“*”是通配符，它表示可以取“1”，又可以取“0”。对于一个模式s，我们至少可以找到一个和它相匹配的个体q。

例如：s 为10**101*1010，个体q 可为：100110101010。2)模式阶和定义距

定义2.2 若一个个体q 的每一位与模式s 相配，则称q 是s 的一个表示。一

个模式代表一个个体的集合，这个集合中的每一个个体都是这个模式的一个表示。所有的模式并不是以同等机会产生的。有些模式比起其他模式更确定，如模式011**1 与模式0*****相比，在相似性方面有明确的表示。有些模式的跨度要比其他的长，如与模式1*1***相比，1****1 要跨越整个串长更大的部分。 2）模式阶(schema order)和定义距(defining length)。

定义2.3 一个模式s 的阶就是指模式中已有明确含意(二进制字符时指0 或1)的字符个数，记为Ο(s)。

例如，模式“0****”的阶为1，模式“10*0*”的阶为3。

定义2.4 一个模式的定义距就是模式中第一个确定位置和最后一个确定位置间的距离，记为δ (s)。

例如：模式“10***”的定义距为1，模式“1***0”的定义距为4。模式的定义距代表该模式在今后遗传操作(交叉、变异)中被破坏的可能性：模式长度越短，被破坏的可能性越小，长度为0 的模式最难被破坏。

3)模式定理[20]

定理2.1(模式定理) 在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式在子代中得到以指数级增长。模式定理是遗传算法的理论基础，是由J.H.Holland 教授创立的，该理论揭示了遗传算法的基本机理。为了很好地理解该定理，下面我们通过一个实例来加深理解。

例：求 max f(x)= x2 x ∈{0,31}[23]，则x 可编码为5 位二进制数。给定4 个初始串，然后施加选择、交叉、变异操作，有关的过程由表2-2 表示。让我们考察3 个模式：H1 =1***、H2 =*10** 和H3 =1***0 的运行情况。首先来看H1在遗传操作下的变化。在选择阶段，各串按照其适应度在群体适应度中所占的比例进行复制(比例复制法)。观察表2-2，可以看出，由于串2 的适应度大，其复制概率高，经过选择被复制成2 份，而串3 则丢失了。注意到串2、4 都是H1的样本，这样通过选择后，H1的样本增至为3。由模式定理，理论上应有m• f (H) / favg 个样本，其中f (H) =(576+361)/2=468.5 ， 而favg =293 ， 则H1 在选择算子作用下应有2• 468.5/293=3.2≈3 个样本，与实际相符。由于

H1的定义距离为0，交叉操作对H1的样本没有任何影响。而对于变异操作，在

变异概率为Pm =0.001 的情况下，H1的3 个样本遭破坏的概率为3• 0.001=0.003，可以认为不发生变异。事实上，子代中有3 个H1的样本11001、11011、10000，H1的样本数的确如模式定理所预计的呈指数级增长。那么模式

H2、H3呢？H2的初始样本数为2，在选择算子作用下，样本数仍为2。10这与模式定理所预计的2• 320/293=2.18≈2 与实际一致。而模式H3的样本数为1，预期值为1• 576/293=1.91≈2 与实际值相符。下面来看交叉操作。尽管H2和

H3的阶数相同，选择后的样本数也相同，但由于两个模式的定义距不同，在交叉算子作用下的结果也不同。对于H2，由模式定理，其预期值应为m(H2 ,t+1)=2.18• (1-1/4)=2.18• 0.75=1.64≈2，实际上， 最终H2 的两个样本都得以保留。而对于H3 ， 其预期值为m(H3 ,t+1)=1.97• (1-4/4)=0，但事实上，H3有一个样本得以保留(10000)。这似乎与模式定理不相符，但应该强调的是，模式定理给出的只是一个下界，H3之所以有一个样本能生存，是因为H3的样本11000的配偶10011 在H2的确定位(位置1、5)并不互补。尽管如此，我们也可以看出，由于H2具有较短的定义距，其生命力强于H3。