数据挖掘与技术ch遗传算法专家讲座

生物进化理论和遗传学基本知识生命基本特征包含：生长、繁殖、新陈代谢和遗传与变异。达尔文用自然选择(naturalselection)来解释物种起源和生物进化，其自然选择学说包含以下三个方面：遗传变异生存斗争和适者生存数据挖掘与技术ch遗传算法专家讲座第1页生物进化理论和遗传学基本知识遗传生物普遍特征，“种瓜得瓜，种豆得豆”，亲代把生物信息交给子代，子代按照所得信息而发育、分化，因而子代总是和亲代含有相同或相同形状。生物有了这个特征，物种才能稳定存在。变异亲代和子代之间以及子代不一样个体之间总有些差异，这种现象称为变异。变异是随机发生，变异选择和积累是生命多样性根源。数据挖掘与技术ch遗传算法专家讲座第2页生物进化理论和遗传学基本知识生存斗争和适者生存自然选择来自繁殖过剩和生存斗争。因为弱肉强食生存斗争不停进行，其结果是适者生存，含有适应性变异个体被保留下来，不含有适应性变异个体被淘汰，经过一代代生存环境选择作用，物种变异被定向着一个方向积累，演变成新物种。数据挖掘与技术ch遗传算法专家讲座第3页生物进化理论和遗传学基本知识遗传算法效法基于自然选择生物进化，是一个摹仿生物进化过程随机方法。遗传算法是从代表问题可能潜在解集一个种群开始，一个种群由经过基因编码一定数目标个体组成。按照适者生存和优胜劣汰原理，逐代演化产生出越来越好近似解。在每一代，依据问题域中个体适应度大小挑选个体，并借助于自然遗传学遗传算子进行组合交叉和变异，产生出代表新解集种群。这个过程将造成种群像自然进化一样后生代种群比前代愈加适应于环境，末代种群中最优个体经过解码能够作为问题近似最优解。数据挖掘与技术ch遗传算法专家讲座第4页生物进化理论和遗传学基本知识一定数目N个个体随机地初始化，并计算每个个体适应度函数，初始代产生。按照适应度选择个体，父代要求基因重组（交叉）而产生子代。全部子代按一定概率变异。子代适应度又被重新计算，子代被插入到种群中将父代取而代之，组成新一代。直到满足优化准则为止。数据挖掘与技术ch遗传算法专家讲座第5页遗传算法可定义为一个8元组：GA=(C,E,P0,M,,,,T)式中， C—个体编码方法；

E—个体适应值评价函数；

P0—初始种群；

M—群体大小；

—选择算子；

—交叉算子；

—变异算子；

T—遗传算法终止条件。遗传算法基本原理

数据挖掘与技术ch遗传算法专家讲座第6页初始化种群编码为染色体种群计算各染色体适应值遗传操作(选择、交叉、变异)种群停机条件满足？种群←种群NY结束图遗传算法工作原理示意图遗传算法基本原理

数据挖掘与技术ch遗传算法专家讲座第7页遗传算法关键技术包含：编码问题；初始种群产生；确定适应值函数；选择遗传操作算子；停机条件。遗传算法基本原理

数据挖掘与技术ch遗传算法专家讲座第8页编码问题因为遗传算法不能直接处了解空间解数据，所以必须经过编码将它们表示成遗传空间基因型串结构数据。编码方法在很大程度上决定了怎样进行群体遗传进化运算以及遗传进化效率。因为不一样编码方法含有不一样特点，为了提升遗传算法效率，应依据不一样情况采取不一样编码方式。主要编码方法有二进制编码、浮点数编码、符号编码、多参数编码、可变长染色体编码等。遗传算法关键技术

数据挖掘与技术ch遗传算法专家讲座第9页编码问题在遗传算法中普通用二值（0，1）向量表示染色体，故先要对规则进行编码。编码采取二进制，将由特征和类别组成训练例子集编码成二进制字符串遗传样本。一个样本Mi是一个二元组，其形式以下：Mi=[xi，yi]，其中：i为样本号；x为条件部分，即训练例子各特征编码；y为结论部分，即训练例子类别。遗传算法关键技术

数据挖掘与技术ch遗传算法专家讲座第10页详细编码规则以下：若属性为范围型，定义属性段宽度等于属性取值个数。对于每个属性段，若第一位为‘*’，表示该属性取值能够为任意；不然，各位若取值为1，表示取该属性值，0表示不取该属性值。比如，某条件属性Ci对应编码二进制串为011001，表示该属性取第二个属性值或第三个属性值或第六个属性值，即若属性为数值型，定义属性段宽度，其中n为该属性取值个数。对于每个属性段，若第一位为‘*’，表示该属性取值能够为任意遗传算法关键技术

数据挖掘与技术ch遗传算法专家讲座第11页初始种群产生GA以初始种群作为初始点开始迭代。初始种群大小表示群体中所含个体数量。当个体数量取值较小时，可提升遗传算法运算速度，但搜索空间分布范围有限，降低了群体多样性，有可能会引发遗传算法早熟现象；当个体数量取值较大时，首先计算复杂，会使遗传算法运行效率降低，另首先，部分高适应值个体可能被淘汰，影响交叉。初始种群普通取值范围是20~100。遗传算法关键技术

数据挖掘与技术ch遗传算法专家讲座第12页产生初始种群方法通常有两种：（1）对问题解无任何先验知识情况，采取随机产生样本方法；（2）对于含有一些先验知识情况，可首先将这些先验知识转变为必须满足一组要求，然后在满足这些要求解中随机地选取样本。这么选择初始种群可使遗传算法更加快地到达最优解。遗传算法关键技术

数据挖掘与技术ch遗传算法专家讲座第13页遗传算法关键技术确定适应值函数遗传算法设计要素之一是怎样确定适应值函数，在遗传算法中，利用适应值来衡量个体优劣，采取适者生存标准决定哪些个体进行繁殖，哪些个体被淘汰。数据挖掘与技术ch遗传算法专家讲座第14页遗传算法关键技术选择遗传操作算子遗传算子包含三个基本算子：选择算子(SelectionOperator)、交叉算子(CrossoverOperator)、变异算子(MutationOperator)。数据挖掘与技术ch遗传算法专家讲座第15页选择遗传操作算子选择用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。选择依据是计算适应度。适应度计算之后是实际选择，按照适应度进行父代个体选择，能够挑选以下算法：轮盘赌选择随机遍历抽样局部选择等数据挖掘与技术ch遗传算法专家讲座第16页遗传算法关键技术轮盘赌选择

一组二进制基因码组成个体组成初始种群，个体适用度评价值经计算由括号内数值表示，适应度越大代表个体越好00011000000101111001000000010110011101001010101010（8）（5）（2）（10）（7）11100101101001011011110000000110011101000001010011（12）（5）（19）（10）（14）数据挖掘与技术ch遗传算法专家讲座第17页遗传算法关键技术轮盘赌选择轮盘赌选择方法类似于博彩游戏中轮盘赌。个体适应度转化为选中概率，将轮盘分成10个扇区，因为要进行10次选择，所以产生10个[0，1]之间随机数，相当于转动10次轮盘，取得10次转盘停顿时指针位置，指针停顿在某一扇区，该扇区代表个体即被选中。数据挖掘与技术ch遗传算法专家讲座第18页遗传算法关键技术轮盘赌选择个体染色体适应度选择概率累计概率1000110000080.0869570.0869572010111100150.0543480.1413043000000010120.0217390.16304341001110100100.1086960.2717395101010101070.0760870.34782661110010110120.1304350.4782617100101101150.0543480.53260981100000001190.2065220.73913091001110100100.1086960.847826100001010011140.1521741.000000数据挖掘与技术ch遗传算法专家讲座第19页遗传算法关键技术轮盘赌选择0.070221、0.545929、0.7845671、8、971234568910个体选择概率累计概率10.0869570.08695720.0543481014130430.0217390.16304340.1086960.27173950.0760870.34782660.1304350.47826170.0543480.53260980.2065220.73913090.1086960.847826100.1521741.000000数据挖掘与技术ch遗传算法专家讲座第20页遗传算法关键技术轮盘赌选择71234568910显然，适应度高个体被选中概率越大，而且可能被选中；而适应度低个体则很有可能被淘汰。数据挖掘与技术ch遗传算法专家讲座第21页遗传算法关键技术交叉或基因重组杂交率就是用来确定2个染色体进行局部位（bit）交换以产生2个新子代概率。试验表明这一数值通常取为0.7左右是理想，尽管一些问题领域可能需要更高一些或较低一些值。数据挖掘与技术ch遗传算法专家讲座第22页遗传算法关键技术交叉或基因重组每一次，从群体中选择2个染色体，同时生成其值在0到1之间一个随机数，然后依据此数据值来确定两个染色体是否要进行杂交。假如数值低于杂交率(0.7)就进行杂交，然后沿着染色体长度随机选择一个位置，并把此位置后面全部位进行交换。数据挖掘与技术ch遗传算法专家讲座第23页遗传算法关键技术交叉或基因重组比如，设给定2个染色体为:1000100111001001001010001001000011沿着它们长度随机选择一个位置，比如说10，然后交换第10位之后全部位。这么两个染色体就变成了（我已在开始交换位置加了一个空格）：1000100110100001101010001010010010

数据挖掘与技术ch遗传算法专家讲座第24页遗传算法关键技术变异

变异率（突变率）就是在一个染色体中将位实施翻转（flip，即0变1，1变0）几率。这对于二进制编码基因来说通常都是很低值，比如0.001。所以，不论从群体中怎样选择染色体，首先是检验是否要杂交，然后再从头到尾检验子代染色体各个位，并按所要求几率对其中一些位实施突变（翻转）。数据挖掘与技术ch遗传算法专家讲座第25页遗传算法关键技术停机条件遗传算法是一个重复迭代搜索算法，它经过屡次进化逐步迫近最优解，所以需要确定停机条件。最惯用停机条件是要求遗传代数，即迭代次数。数据挖掘与技术ch遗传算法专家讲座第26页遗传算法关键技术停机条件当遗传算法是用来产生新规则时，停机条件不能简单地用遗传代数确定。一次学习过程结束是当当前工作规则已收敛，停机条件应该定义为：子代种群规则与其父代完全相同，而且各规则适应值已连续M次保持不变。也就是说，当前工作种群已不再进化了。其中，M是依据不一样应用情况事先设置一个参数。数据挖掘与技术ch遗传算法专家讲座第27页遗传算法步骤代数计数器初始化：t←0；产生初始种群；评价群体P(t)适应值；依据当前群体每个个体适应值进行选择生成中间群体P1(t)；个体交叉(重组)操作：P2(t)←crossover[P1(t)]；个体变异操作：P3(t)←mutation[P2(t)]；评价群体P3(t)适应值；终止条件判断，若不满足终止条件，则：t←t+1，转向第3步，继续进行遗传操作过程；若满足终止条件，则：输出当前最优个体，算法结束。数据挖掘与技术ch遗传算法专家讲座第28页遗传算法实例问题：求解在[0，31]上最大值。1）编码：用5位二进制表示x，有x=0即00000x=31即111112）初始种群随机产生4个个体：13，24，8，19（分别用二进制表示）。3）适应值f直接用目标函数作为适应值：a.非负；b.逐步增大。数据挖掘与技术ch遗传算法专家讲座第29页4）选择率和期望值选择率：平均适应值：期望值：5）实选值期望值取整数。以下表：遗传算法实例数据挖掘与技术ch遗传算法专家讲座第30页表1：初始种群参数计算编号初始种群位串参数值x值目标适应值选择率期望值实选值1234011011100001000100111324819169576643610.140.490.060.310.581.970.221.231201总和平均值最大值11702935761.000.250.494.001.001.974.01.02.0数据挖掘与技术ch遗传算法专家讲座第31页表2：初始种群遗传过程选择后交配池交叉对象交叉位置新种群x值f(x)=x201101110001100010011214344220110011001110111000012252716144625729256总和平均值最大值1754439729数据挖掘与技术ch遗传算法专家讲座第32页表3：新种群参数计算编号初始种群位串参数值x值目标适应值选择率期望值实选值123401100110011101110000122527161446257292560.080.360.420.150.331.421.660.580121总和平均值最大000.250.424.001.001.664.01.02.0数据挖掘与技术ch遗传算法专家讲座第33页表4：新种群遗传过程选择后交配池交叉对象交叉位置新种群x值f(x)=x211011110011101110000214311331101111001110001001127252419729625576361总和平均值最大值2291572729数据挖掘与技术ch遗传算法专家讲座第34页遗传算法在适应度函数选择不妥情况下有可能收敛于局部最优