遗传算法的数学基础

1、第3章 遗传算法的数学基础 遗传算法在机理方面具有搜索过程和优化机制等属性，数学方面的性质可通过模式定理和构造块假设等分析加以讨论，Markov链也是分析遗传算法的一个有效工具。遗传算法的选择操作是在个体适应度基础上以概率方式进行的，在概率选择方式上与模拟退火法有些类似。 本章将较全局地介绍遗传算法的基础数学理论和分析工具，包括验证基础遗传算法（SGA）的有效性的模式定理，分析遗传算法过程的Walsh模式变换方法，遗传算法的欺骗问题以及遗传算法的动态分析工具Markov链分析。3.1 模式定理1. 模式我们将种群中的个体即基因串中的相似样板称为“模式”，模式表示基因串中某些特征位相同的结构，因

2、此模式也可能解释为相同的构形，是一个串的子集。在二进制编码中，模式是基于三个字符集0，1，*的字符串，符号* 代表0或1。例1 *1*表示四个元的子集010 011 110 111对于二进制编码串，当串长为L时，共有3L个不同的模式。例2 串长L=3，则其模式共有* *1* *0* *1 *0 1* 0* *10 *00 *01 1*1 1*0 0*1 0*0 11* 10* 01* 00* 111 110 101 011 001 010 100 0002 / 31 共27个1+2*3+22*3+23=33遗传算法中串的运算实际上是模式的运算。如果各个串的每一位按等概率生成0或1，则模式为n的

3、种群模式种类总数的期望值为：种群最多可以同时处理个模式，见下例例 一个个体（种群中只有一个），父个体011 要通过变异变为子个体001，其可能影响的模式为：被处理的模式总数为8个，8=1*23如果独立的考虑种群中的各个串，则仅能得到n条信息，然而当把适应值与各个串结合考虑，发掘串群体的相似点，就可得到大量的信息来帮助指导搜索，相似点的大量信息包含在规模不大的种群中。2. 模式阶和定义距 定义1：模式阶 模式H中确定位置的个数成为模式H的模式阶，记作O(H) 例 O(011*1*0)=5定义2 定义阶 模式中第一个确定位置和最后一个确定位置之间的距离，记作 例 3. 模式定理 假定在给定时间步t

4、(即第t代)，种群A(t)中有m个个体属于模式H，记为m=m(H,t),即第t代时，有m个个体属于H模式。在再生阶段（即种群个体的选择阶段），每个串根据它的适应值进行复制（选择），一个串Ai被复制（选中）的概率为：n表示种群中个体总数当采用非重叠的n个串的种群替代种群A(t),可以得到下式：其中：，表示在t 时模式H的平均适应度若用表示种群平均适应度，则前式可表示为：上式表明：一个特定的模式按照其平均适应度值与种群的平均适应度值之间的比率生长，换句话说就是：那些适应度值高于种群平均适应度值的模式，在下一代中将会有更多的代表串处于A(t+1)中，因为在时有m(H,t+1)>m(H,t) 假

5、设从t=0开始，某一特定模式适应度值保持在种群平均适应度值以上，c为常数c>0, 则模式选择生长方程为：上式表明，在种群平均值以上（以下）的模式将按指数增长（衰减）的方式被复制。下面讨论交叉对模式H的影响：例：对串A分别在下面指定点上与H1模式和H2模式进行交叉 A 0111000 H1 *1*0 (被破坏概率：；生存率：1/6) H2 *10* (被破坏概率：；生存率：5/6)显然A与H1交叉后， H1被破坏，而与H2交叉时， H2不被破坏。一般地有 ：模式H被破坏的概率为，故交叉后模式H生存的概率为（）考虑到交叉本身是以随机方式进行的，即以概率Pc进行交叉，故对于模式H的生存概率Pc

6、可用下式表示：同时考虑选择交叉操作对模式的影响，（选择交叉互相独立不影响）则子代模式的估计：上式表明模式增长和衰减依赖于两个因素：一是模式的适应度值f(H)与平均适应度值的相对大小；另一个是模式定义阶的大小（当Pc一定， L一定时）。下面再考察变异操作对模式的影响：变异操作是以概率Pm随机地改变一个位上的值，为了使得模式H可以生存下来，所有特定的位必须存活。因为单个等位基因存活的概率为（1Pm）,并且由于每次变异都是统计独立的，因此，当模式H中O(H)个确定位都存活时，这时模式H才能被保留下来，存活概率为：（为0.01以下）上式表明O(H)个定位值没有被变异的概率。由此我们可得到下式在t+1代

7、种群中存在模式H的个体数目在t代种群中存在模式H的个体数目在t代种群中包含模式H的个体平均适应度t代种群中所有个体的平均适应度个体长度交叉概率变异概率对于k点交叉时，上式可表示为：模式定理：在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。4. 积木块假设（building block hypochesis） 遗传算法通过短定义距、低阶以及高适应度的模式（积木块），在遗传操作作用下相互结合，最终接近全局最优解。满足这个假设的条件有两个：（1）表现型相近的个体基因型类似（2）遗传因子间相关性较低积木块假设指出，遗传算法具备寻找全局最优

8、解的能力，即积木块在遗传算子作用下，能生成低阶、短距、高平均适应度的模式，最终生成全局最优解。模式定理还存在以下缺点：（1） 模式定理只对二进制编码适用（2） 模式定理只是指出具备什么条件的木块会在遗传过程中按指数增长或衰减，无法据此推断算法的收敛性（3） 没有解决算法设计中控制参数选取问题3.2 Walsh模式变换1980年，密歇根大学的A.D.Bethke博士论文“作为函数优化器的遗传算法”，首次应用Walsh函数进行遗传算法的模式处理，采用Walsh函数的离散形式有效地计算模式的平均适应度，从而对遗传算法的优化过程的特征进行分析。3.3 非均匀Walsh模式变换3.4 欺骗问题在遗传算法

9、中，将所有妨碍评价值高的个体生成，从而影响遗传算法正常工作的问题统称为欺骗问题（deceptive problem）,根据模式定理，如果低阶、高适应度模式中包含了最优解的话，遗传算法就可能找出它来，但是如果低阶、高适应度模式中未包含最优串的具体取值，则遗传算法只能找出次优解。定义 竞争模式 若模式H和H中，*位置是完全一致的，但任一确定位的编码均不同，则称H和H互为竞争模式。例 10*与01*是竞争模式 10*与11*不是竞争模式定义 欺骗性 假定f(x)的最大值对应的x集合为x*，H为包含x*的m阶模式， H的竞争模式为H，而且f(H)<f(H),则f为m阶欺骗。例 对于一个三位二进制

10、编码的模式，如果f(111)为最大值，下列12个不等式中任意一个不等式成立，则存在欺骗问题。 模式阶数为1时：f(*1)<f(*0),f(*1*)<f(*0*),f(1*)<f(0*) 模式阶数为2时：f(*11)<f(*00),f(1*1)<f(0*0),f(11*)<f(00*) f(*11)<f(*01),f(1*1)<f(0*1),f(11*)<f(01*) f(*11)<f(*10),f(1*1)<f(1*0),f(11*)<f(10*)造成上述欺骗问题的主要原因有两个：编码不当或适应度函数选择不当。如果它们均是

11、单调关系，则不会存在欺骗性问题，但是对于一个非线性问题，难于实现其单调性。1. 欺骗函数的类型Goldberg曾研究用适应度函数的非单调性来研究欺骗性问题。考虑一个2位二进制最大化问题，假定“11”对应最优解，若H(0*)>H(1*)，则欺骗性存在。该条件可化为：下面以前一种为例进行讨论，设则有：r<1+c-cc>1：称为类欺骗问题，见图1，求最优化时较难c<=1:称为类欺骗问题，见图2，此问题求最优化更难图1图2这两类欺骗性问题应该称为非单调问题，在非单调问题中同时存在欺骗性和非欺骗性问题。过去，将适应度函数的非单调问题与欺骗问题同等看待，认为遗传算法只有在单调问题里

12、有效。但是，如果单调问题不使用遗传算法或者不使用概率搜索，一般的搜索法可能是适用的，没有遗传算法存在的必要。即使是单调的，只有存在需要高机能交叉操作（非单调且非欺骗问题），才能使遗传算法存在有意义，这不外乎使交叉操作成为遗传算法本质作用的一个证明。2. 欺骗性化解可以采用Grey 编码或纠正适应度函数3. 遗传算法的困难问题容易问题：采用基本的遗传算法，易于得到最优解的场合或问题困难问题;与上相反遗传算法的欺骗性与遗传算法的困难性不存在对等或等价关系，这是由于遗传算法的欺骗性是从静态超平面分析给出的，并且假设个体数无偏差，而遗传算法的困难性来源于不适当的问题表示、交叉和变异的扰动作用、有限的种

13、群大小、复杂的多模型状态图等。3.5 遗传算法动态分析从随机过程和数理统计角度讨论遗传算法较为一般的规律，有助于较好地把握遗传算法的特性，以提高求解效率和改善求解效果。铃木（1995年）从Markov链的角度分析了基本遗传算法（SGA）的统计规律，并得到了一些有意义的结论。SGA的当前种群只与前一代种群有关，因此SGA可以用一个Markov链来描述。第四章 遗传算法的改进自从1975年J.H.Holland系统地提出遗传算法的完整结构和理论以来，总多学者一直致力于推动遗传算法的发展，对编码方式、控制参数的确定、选择方式和交叉机理等进行了深入的探究，引入了动态策略和自适应策略以改善遗传算法的性能

14、，提出了各种变形的遗传算法（Variants of Canonical Genetic Algorithm,简称VCGA）.其基本途径概括起来有以下几个方面：（1） 改变遗传算法的组成成分或使用技术，如选用优化控制参数、适合问题特性的编码技术等。（2） 采用混合遗传算法（3） 采用动态自适应技术，在进化过程中调整算法控制参数和编码力度（4） 采用非标准的遗传操作算子（5） 采用并行遗传算法本章将介绍这些方面的典型思路和集中改进的遗传算法。4.1 分层遗传算法对于一个问题，首先随机生成N*n各样本(n>=2,N>=2),然后将它们分成N个子种群，每个子种群包括n各样本，对每个子种群独

15、立的运行各自的遗传算法，记它们为GAi(i=1,2,.N)。这N个遗传算法最好在设置特性上有较大差异，这样就可以为将来的高层遗传算法产生更多种类的优良模式。在每个子种群的遗传算法运行到一定代数后，将N个遗传算法的结果种群记录到二维数组R1.N,1n中，则Ri,j（i=1N,j=1n）表示GAi的结果种群的第j个个体。同时将N各结果种群的平均适应度值记录到数组A1.N中，Ai表示GAi的结果种群平均适应度。高层遗传算法与普通遗传算法的操作相类似，也可以分为以下三个步骤：1.选择（种群之内选择）基于数组A1.N，即N个遗传算法的平均适应度值，对数组R代表结果种群进行选择操作，一些结果种群由于它们的

16、平均适应度值高而被复制，甚至复制多次；另一些结果种群由于它们的种群平均适应度值低而被淘汰。2. 交叉（种群之间交叉）如果Ri,1.n和Rj,1.n被随机地匹配到一起，而且从位置x进行交叉（）则Ri,x+1.n和Rj,x+1.n相互交换相应的部分。这一步骤相当于交换GAi和GAj中结果种群的n-x个个体。3.变异以很小的概率将少量随机生成的新个体替换R1N,1n中随机抽取的个体。至此，高层遗传算法的第一轮运行结束，N各遗传算法GAi(i=1N)可以从相应于新的R1.N,1n种群继续各自的操作。分层遗传算法的流程图如下：4.2 CHC算法CHC算法是shelman于1991年提出的遗传算法的缩写，

17、第一个C代表（Cross generational elitist selection）策略，H 代表异物种重组（Heterogeneous recombination），第二个C代表大变异（Cataclysmic mutation）。CHC算法与基本遗传算法SGA不同点在于：SGA的遗传操作比较单纯，简单地实行并行处理；而CHC算法牺牲这种单纯性，换取遗传操作的较好效果，并强调优良个体的保留。下面分别介绍其遗传操作的改进之处。1. 选择通常遗传算法是依据个体的适应度复制个体完成选择操作的，而在CHC算法中，上世代种群于通过新的交叉方法产生的个体种群混合起来，从中按一定概率选择较优的个体。 这

18、一策略成为跨世代精英选择。其明显特征表现在：（1） 健壮性 由于这一选择策略，即使当交叉操作产生较劣个体偏多时，由于原种群多数个体残留，不会引起个体的评价值降低。（2） 遗传多样性保持由于大个体群操作，可以更好的保持遗传过程中的遗传多样性。（3） 排序方法克服了比例适应度计算的尺度计算2.交叉 CHC算法使用的重组操作是对均匀交叉的一种改进。均匀交叉对父个体位值的各位位置以相同概率实行交叉操作，这里改进之处是：当两个父个体的位置相异的位数为m时，从中随机选取m/2个位置，实行父个体位置的互换。显然，这样的操作对模式具有很强的破坏性，因此，确定一阈值，当个体间的海明距离低于该阈值时，不进行交叉操

19、作。并且，与种群进化收敛的同时，逐渐地减小该阈值。3.变异CHC算法在进化前期不采取变异操作，当种群进化到一定的收敛时期，从优秀个体中选择一部分个体进行初始化。初始化的方法是选择一定比例的基因座，随机的决定它们的位置。这个比例值称为扩散率，一般取0.35。4.3 messy GA根据积木块假设，SGA中，定义距长的模式容易受到破坏，只有从小积木块的模式中才能最终构成最优解，这对进化模拟而言是十分不利的。为克服这一缺点，Goldberg等在1989年提出了一种变长度染色体遗传算法，该算法在不影响模式定义距的情况下，是优良的模式得以增殖。在生物进化过程中，其染色体长度比不是固定不变的，而是随着进化

20、过程也在慢慢的变化。另一方面，在遗传算法的实际应用中，有时为了简化描述问题的解， 也需要使用不同长度的编码串。例如，用遗传算法对模糊控制器规则库进行优化设计时，事先一般不知道规则数目，这样一个规则库对应一个个体，个体的染色体长度可以描述为变化的。用染色体算法对人工神经网络结构进行优化设计时，如果各层的节点数是未知的，同样，个体染色体长度也可以描述为变化的。变长染色体的编码采用二元编制，同时用一个二元数组表示，二元数组的第一位为固定座序号，第二位是基因座上的数值。变长度染色体中可能在交叉操作中出现缺失位（缺失位上的值用0表示）和重复位（重复位用左边的值表示）。例. X1 (1,0) (2,1)

21、(3,1) (4,0) (5,1)X2 (1,1) (2,1) (3,0)X1 (1,0) (2,1) (3,1) (4,0) (2,1) (3,0)X2 (1,1) (5,1)X1染色体为 0 1 1 0 X2染色体为 1 0 0 0 1（位码已变）X1染色体为 0 1 1 0 1 X2染色体为 1 1 0 其交叉操作是切断和拼接两部分完成的。4.4自适应遗传算法遗传算法的参数中交配概率Pc和变异概率Pm的选择是影响遗传算法行为和性能的关键所在，直接影响算法的收敛性，Pc越大，新个体产生速率就越快。然而，Pc过大时遗传模式被破坏的可能也越大，使得具有高适应度的个体结构很快就会被破坏，但是如果

22、Pc过小，就不易产生新的个体结构；若Pm取值过大，那么遗传算法就变成了纯粹的随机搜索算法，Pc和Pm的确定在实际应用中是个繁琐和困难的事情。Srinvivas等提出的自适应遗传算法（Adaptive GA）,Pc和Pm能够随适应度自动改变：1. 当种群个体适应度趋于一致或趋于局部最优时，使Pc,Pm增大，反之减小。2. 对于适应度高于种群平均适应度的个体，使Pc，Pm减小，反之增大。即好的个体尽量保持，差的个体尽量被替代而淘汰当Pc，Pm恰当时，AGA算法能够在保持群体多样性的同时保证遗传算法的收敛性。Pc，Pm可按如下简单公式计算：（多有） K：是要选定的上式虽然简单但存在问题，当f或f趋于

23、fmax时，Pc，Pm趋于0，f越小则Pc,Pm大。这种调整方法对于种群处于进化后期比较合适，但在进化初期是不当的，这会使初期较优的个体处于几乎不变的状态，从而以使进化走向局部最优解。为此对前式假如作如下修改便使f或f趋于fmax时，Pc，Pm不会为0。4.5 基于小生境技术的遗传算法生物学上，小生境（niche）是指特定环境中的一种组织功能。在自然界中，往往特征、性状相似的物种相聚在一起，并在同类中交配繁殖后代。在SGA中，交配完全是随机的，虽然这种随机化的交配形式在寻优的初级阶段保持了解的多样性，但在进化的后期，大量个体集中于某一极值点上，它们的后代造成近亲繁殖。在用遗传算法求解多峰值函数

24、的优化计算时，经常是只能找到个别的几个最优解，甚至往往的得到的是局部最优解。我们希望优化算法能够找出全部最优解，引进小生境的概念，有助于实现这样的目的。小生境技术就是将每一类个体划分为若干类，每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个种群，再在种群中以及不同种群之间通过杂交、变异产生新一代个体群。小生境技术特别适合于复杂多峰函数的优化问题。小生境的模拟方法主要建立在常规选择操作的改进基础上。1.1970年，Cavichio：当新产生的子代个体的适应度越过其父代个体的适应度时，所产生的子代个体才能替代父代个体而遗传到下一代个体中，否则父代个体仍保留在下一代种群中。预选择机制的选

25、择策略。2. 1975年，Do Jong :排列机制的选择策略一个有限的生存空间中，各种不同的生物为了能够延续生存，它们之间必须相互竞争有限的资源设计一个排挤因子CF(一般取2或3)，由种群中随机选择的1/CF个个体组成排挤成员，然后依据新产生的个体与排挤成员的相似性来排挤一些与排挤成员相类似的个体，个体之间的类似性是由海明距离来度量。随着排挤过程的进行，群体中的个体逐渐被分类，从而形成一个个小的生成环境，并维持群体的多样性。3共享法的选择策略（暂略，较难）4.6 混合遗传算法众所周知，梯度法、模拟退火法等一些优化算法具有很强的局部搜索能力，而另一些含有问题相关的启发知识的启发式算法的运行效率

26、也比较高。如果融合这些优化方法的思想，构成一个新的混合遗传算法（hybrid genetic algorithm）,是提高遗传算法运行效率和求解质量的一个有效手段。目前，混合遗传算法体现在两个方面：一是引入局部搜索过程，二是增加编码变换操作过程。在构成混合遗传算法时，De Jong提出下面三个基本原则；1. 尽量采用原有算法的编码（这个原有指遗传原有）2. 利用原有算法全局搜索的优点3. 改进遗传算子第五章 进化计算初步进化计算有三个分支：（1）遗传算法（GA）（2）进化规划（Evolutionary Programing ）(3)进化策略（Evolutionary Strategy）本章将讨

27、论进化计算的理论框架及分支的构成技术，主要介绍遗传程序设计技术。5.1 进化计算理论的基本框架进化计算是指以进化原理为仿真依据，在计算机上实现的具有进化机制的算法和程序。目前进化计算侧重于算法的研究，因此有时称为进化算法（Evolutionary Algorithm）若有性质来区分， 现有的进化算法可细分为：（1） 具有代表性的、最基本的遗传算法（genetic algorithm）(第二章)（2） 侧重于数值分析的进化策略（evolutionary strategy）(5.2节)（3） 介于数值分析和人工智能间的进化规划（evolutionary strategy）（5.3节）（4） 偏向进

28、化自组织和系统动力学特性的进化动力学（evolutionary dynamics）（5） 偏向以程式表现人工智能行为的遗传程序设计（genetic programming）(5.4节)（6） 适应动态环境学习的分类系统（classifier system）(第8章)（7） 用以观察复杂系统交互的各种生态模拟系统（echo system and etc）（8） 研究人工生命（artifical life）的元胞自动机（cellualar automata）（9） 模拟蚂蚁群体行为的蚁元系统（ant system）(10.3节)基因型与表现型之间的关系是进化计算中的一个基本关系，在其复杂的非线性关系中“一因多果”和“一果多因”是突出的两个特点。 表现型的变化是对对象遗传结构和当时环境条件交互作用所致的结果，非线性效果很明显，甚至相差很大的遗传结构可能会导致类似的行为。这样在研究基因型表现型相互关系及其在进化过程中的规律时就必须充分利用非线性系统工具和随机过程的统计测度理论，动力学机制也是必须加以研究的动态属性。适应度状态图描述了适应度和基因型间的关系，