遗传算法(第9).ppt

培训大纲 一、简介 二、原理 三、步骤 四、样例 遗传学之父 奥地利生物学家Mendel(孟德尔),（1822-7-20~1884-1-6）出生于奥地利西里西亚，是遗传学的奠基人，被誉为现代遗传学之父。Mendel通过豌豆实验，发现了遗传规律、分离规律以及自由组合规律。 Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质。所以，每个基因产生的个体对环境具有某中适应性。基因突变和基因杂交可产生更适应于环境的后代，经过存优劣的自然淘汰，适应性高的基因结构得以保存下来。 遗传算法的搜索机制 遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。 从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能 培训大纲 一、简介 二、原理 三、步骤 四、样例 遗传学相关概念 遗传学相关概念 遗传算法基本原理 遗传算法的步骤 遗传算法具体步骤 培训大纲 一、简介 二、原理 三、步骤 四、样例 适应度函数 适应度函数（评估函数） 适应度函数设计是模拟自然选择，进行遗传进化操作的基础，它的评估是遗传操作的依据。适应度函数值即适应度。由于下面定义的选择概率以适应度为基础，因此适应度是非负的。几种常见的适应度定义为： 对f(x),取Cmin,Cmax使Cminmin{f(x)},Cmaxmax{f(x)},Cmax0 (1)求f(x)最大值问题：如果对应解x的个体为X,可以定义个体X的适应度为 (2)求f(x)最小值问题：可以定义个体X的适应度为 选择标准 两点交叉 与单点交叉类似，只是需设置两个交叉点，然后两个染色体相互交换两点之间的部分，从而生成两个新染色体。一个两点交叉的示例如下： 父辈个体:aaa|aaaa|aaa ?aaa|bbbb|aaa 父辈个体:bbb|bbbb|bbb ?bbb|aaaa|bbb 对于两点交叉，若染色体长为n,则可能有(n-1)(n-2)/2种交叉点的设置。 均匀交叉 均匀交叉则是依概率交换两个父辈个体基因串的每一位。其过程是：先随机的产生一个与父辈个体基因串同样长度的二进制串，其中0表示不交换，1表示交换。这个二进制串称为交叉模版；然后根据该模版对两个父辈基因串进行交叉，得到的两个新基因串即为后代新个体。例如： 父辈个体 1:110010111000 父辈个体 2:101011101011 模版 001101011100 后代个体 1:111011101000 后代个体 2:100010111011 由于均匀交叉在交换位时并不考虑其所在位置，破坏模式的可能性较大。但另一方面它能搜索到一些前面基于点的交叉方法无法搜索到的模式。 基于实向量算术运算的交叉 设两向量x1,x2,则有 凸交叉： x1’=λ1x1+ λ2x2 x2’=λ1x2+ λ2x1 λ1= λ2=0.5 仿射交叉： x1’=λ1x1+ λ2x2 x2’=λ1x2+ λ2x1 λ1=1.5 λ2=-0.5 线性交叉： x1’=λ1x1+ λ2x2 x2’=λ1x2+ λ2x1 λ1+λ2=0, λ10, λ20 培训大纲 一、简介 二、原理 三、步骤 四、样例 实验举例 定义适应函数和适应值 由于目标函数 f(x) 在 [-1, 2] 内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下基础。 定义适应函数 ： 为了便于计算，这里的 Fmin 采用了一个特定的输入值 例：如果取 Fmin=-1，则 f(x)=1 对应的适应值为 g(x)=2 确定选择标准