优化原理与方法13选编.ppt

优化原理与方法;一、遗传算法概述 二、遗传算法原理 三、遗传算法的应用;一、遗传算法概述 ;遗传算法起源 ;1、遗传算法的有哪些信誉好的足球投注网站机制 ;2、基本遗传算法;基本遗传算法的组成 ; 编码 ;函数优化示例 ;SGA对于本例的编码 ;几个术语 ;初始种群 ; 适应度函数 ;选择算子;轮盘赌选择方法;轮盘赌选择方法的实现步骤;交叉算子 ;单点交叉运算 ;变异算子 ;基本位变异算子 ;基本位变异算子的执行过程 ;运行参数 ;;;;;;;;;GA算法流程图 ;3、遗传算法的特点 ;二、遗传算法原理;1、遗传算法的数学基础;模式;两个定义;模式的阶和定义距的含义;模式定理;模式定理;积木块假设 ;2、遗传算法的收敛性分析;随机模型理论 对于有限的编码空间和有限的群体，遗传算法的有哪些信誉好的足球投注网站过程可以表示为离散时间的马尔可夫链模型（Markov chain model），从而可以采用已有的随机过程理论进行严密分析。 Rudolph用齐次有限马尔可??链证明了标准遗传算法收敛不到全局最优解，但是如果采用精英保留策略，那么遗传算法是收敛的。;进化动力学理论 基于某种具体运算形式的遗传算法的进化行为分析构成了进化动力学理论的基本内容。 由Holland提出的模式定理可以视为遗传算法进化动力学的基本定理。 模式定理和积木块假设构成了求解优化问题时遗传算法具备发现全局最优解的能力，也是分析遗传算法的进化行为的基本理论，统称为模式理论。 ;2、遗传算法的收敛性分析;种群规模对收敛性的影响;选择操作对收敛性的影响;交叉概率对收敛性的影响;变异概率对收敛性的影响;遗传算法的本质 ;3、遗传算法的改进;3、遗传算法的改进;遗传算法的改进途径; 在遗传算法进化过程中，有时会产生一些超常的个体，这些个体因竞争力太突出而控制了选择运算过程，从而影响算法的全局优化性能，导致算法获得某个局部最优解。 ;对编码方式的改进;对编码方式的改进;浮点编码染色体的交叉;浮点编码染色体的交叉;浮点编码染色体的变异;对遗传算子 的改进;对遗传算子 的改进;对遗传算子 的改进;对控制参数的改进;对控制参数的改进;;三、遗传算法的应用领域;遗传算法的基本术语;位串结构空间（bit String Space）：等位基因任意组合构成的位串集合，基因操作在位串结构空间进行，对应于遗传学中的基因型的集合。 参数空间（Parameters Space）：是位串空间在物理系统中的映射。对应于遗传学中的表现型的集合。 适应度值（fitness）：某一个体对于环境的适应程度，或者在环境压力下的生存能力，取决于遗传特性。 复制、选择（reproduction or selection）：在有限资源空间上的排他性竞争。;交叉、交换、交配、重组（crossover or recombination）：一组位串或者染色体上对应基因段的交换。 变异（mutation）：位串或染色体水平上的基因变化，可以遗传给子代个体。 逆转或倒位（inversion）：反转位串上的一段基因的排列顺序。对应于染色体上的一部分，在脱离之后反转 180o再连接起来。 单倍体（haploid，monoploid）：细胞核中有n个正常的不配对染色体。;二倍体（diploid）、多倍体（polyploid）：细胞核中有2n或更多个正常的配对染色体。 基因型（genotype）：或称遗传型，指用基因组定义遗传特征和表现。对应于GA中的位串。 表现型（phenotype）：生物体的基因型在特定环境下的表现特性。对应于GA中的位串解码后的参数。 基因连结（linkage）：两个或更多的等位基因出现在同一个染色体上。对应于 GA中的模式的概念。;上位遗传或者基因关联（即epistasis）：两个非等位基因之间的相互作用，使得其中之一（上位基因）对另一个（下位基因）的表现型产生干扰或抑制。对应于优化函数的非线性特征（nonlinearity）。 基因多效性（pleiotropy）：指单一基因对生物体多个物理性状的影响。对应于GA求解多目标优化问题中，某个变量对多个目标函数的影响。 多基因效性（polygeny）：指生物体某个物理性状由多个基因共同决定。对应于GA求解多目标优化问题中，某个目标函数的值由多个变量的状态所决定。 ;遗传源变或遗传漂移（genetic dift）：指群体的遗传组成的随机变化，不含自然选择的影响。 遗传（heredity）：父代个体通过有性方式向子代个体的特征传递过程。 局部环境或者环境小生境（environmental niches）：具有某种特征的子环境，其中生物体具有特定的染色体结构，表现出特定的物理性状。对应于多模态函数中局部极值点的邻域。