遗传算法的提出理论及应用课件.ppt

1、遗传算法的提出、理论及应用1.遗传算法简介2.基本遗传算法3.遗传算法的理论基础4.遗传算法的改进5.遗传算法的应用1.遗传算法简介1.1.遗传算法的提出1.2.遗传算法的基本思想1.3.遗传算法的基本操作1.4.遗传算法的应用情况1.1.遗传算法的提出1.1.1.遗传算法(Genetic Algorithm,GA)1975年由Michigan大学的John Holand教授与其同事、学生一起首先提出。模拟生物进化的机制来构造人工的模型。已形成较完整的理论体系。1.1.2.进化策略（Evolutionary Strategy,ES)于60年代由柏林工业大学的I.Rechenberg和H.P.S

2、chwefel等人引入。1.1.3.进化规划（Evolutionary Programming,EP)在60年代由L.J.Fogel 等人提出。1.1.4.进化计算（Evolutionary Computation)是指包含如下算法的一个“算法组”：遗传算法(GA)、进化策略(GS)、进化规划(GP)和遗传程序设计（Genetic Programming,GP)。1.1.5.计算智能(Computational Intelligence,CI)是一个新的研究方向，它包括：进化计算、人工神经网络（Artificial Neural Network)和模糊系统理论。1.2.遗传算法的基本思想1.2

3、.1.遗传算法的基本思想源于达尔文的自然选择（natural selection）、优胜劣汰：遗传、变异和生存斗争。1.2.2.遗传算法的基本思想是基于种群（population)优化的,包括：先择、重组交叉、变异。进化成最优种群。以下是生物学的几个概念：n染色体(chromosome)：遗传物质的主要载体，由多个遗传因子-基因组成。n遗传因子(gene)：也称基因。是在DNA或RNA长链结构中占有一定位置的基本遗传单位。n基因座(locus)：遗传基因（gene)在染色体中所占据的位置。n个体(individual)：指染色体带有特征的实体。n适应度(fitness)：度量某个物种对于生存环

4、境的适应程度。n选择(selection)：以一定的概率从种群中选择若干个个体的操作。n复制(reproduction)：一个个体分裂成两个个体，其遗传物质不变。n交叉(crossover)：有性生殖生物在繁殖下一代时两个同源染色体之间通过交叉而重组。n变异(mutation)：细胞进行复制时可以很小的概率产生某些复制差错，从而使DNA发生某种变异。1.2.3.遗传算法的特点：（1）自组织、自适应和自学习（智能性）；（2）遗传算法的本质并行性；（3）遗传算法不需要求导或其他辅助知识，而指需要影响搜索方向的目标函数和相应的适应度函数。1.3.遗传算法的基本操作1.3.1.选择(selection

5、)1.3.2.交叉或基因重组（crossover/recombination)1.3.3.变异（mutation）1.4.遗传算法的应用情况1.4.1.函数优化1.4.2.组和优化1.4.3.自动控制。1.4.4.机器人智能控制1.4.5.图像处理和模式识别1.4.6.人工生命1.4.7.遗传程序设计1.4.8.机器学习2.基本遗传算法2.1.函数优化的实例2.2.基因和编码2.3.适应度函数及其尺度变换2.4.遗传操作2.1.函数优化实例2.1.1.下列一元函数求最大值的优化问题：2.1.2.编码：从表现型到基因型 二进制串：2.1.3.产生初始种群：随即产生串长为22的二进制串组成染色体的

6、基因码。2.1.4.计算适应度函数：2.1.5.选择：轮盘赌方法。2.1.6.交叉：随机选取交叉点，单点。并按事先选定的小概率 进行交叉。2.1.7.随机选择变异位，并按事先选定的小概率 进行变异。获得下一代。2.1.8.检查终止函数是否满足，结束进化。mp2,10.2)10sin()(xxxxf41943032103220971522262111110101000110001011101s)()(xfsfcp2.2.基因和编码2.2.1.浮点数编码：n设种群个数为n，表示第t代第i 个个体。n每个个体的基因位数L=m，由m个实体构成，个体 ，可以表示m为向量，即n可构成一实矩阵itxitxn

7、i,2,1mitRx mititititxxxx212.2.2.二进制编码n设种群个数为n，表示第t代第i 个个体。n每个个体重的每一位分量均用l维二进制表示。itxni,2,12.3.适应度函数及其尺度变换2.3.1.适应度函数(fitness function)是由目标函数变换而成的：包括最大化问题和最小化问题等。2.3.2.适应度函数的作用：n在进化初期，通常会产生一些超常个体；要防止竞争力台突出，使其控制了选择过程。n在进化后期，种群中个体适应督差异较小时，易收敛到局部最优解。即欺骗问题。2.3.3.适应度函数的设计：n单值、连续、非负、最大化；n合理、一致性；n计算良宵。2.3.4.

8、适应度函数的尺度变换n线性变换法：F=a*f+bn幂函数变换法：n指数变换法：2.4.遗传操作2.4.1.选择：选择：n分配方法分配方法：(1)按比例的适应度分配(proportional fitness assignment)（2）基于排序的适应度分配(rank-based fitness assignment)n选择方法：选择方法：(1)轮盘赌方法(roulette wheel selection);(2)随机遍历抽样法(stochastic universal sampling);(3)局部选择法（local selection)：线性邻集（整环形和半环形）；两对角邻集。(4)锦标赛选择

9、法（tournament selection)：随机地选择最好的个体为父题。2.4.2.交叉交叉/基因重组：基因重组：n二进制交叉：单点交叉；多点交叉。n实值重组：离散重组；中间重组。2.4.3.变异：变异：n二进制变异；n实值变异。3.遗传算法的理论基础3.1.模式：模式表示基因传中某些特征为相同的结构3.2.模式阶(schema order)：模式H中确定位置的个数称为模式H的模式阶。记为O(H);3.3.定义矩(defining length)：模式H中的一个确定位置和最一个确定位置之间的距离称为模式的定义矩，记为3.4.模式定理：在遗传算子选择、交叉、变异的作用下，具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代忠呈指数增长。4.遗传算法的改进4.1.分层遗传算法4.2.混合遗传算法5.遗传算法的应用