多样化损失（loss of diversity）：在选择阶段未选 中个体数目占种群的比例；
智能优化计算
数学与统计学院 2013年
4.2 基本遗传算法
4.2.4 遗传操作——选择
几个概念

选择强度（selection intensity）:将正规高斯分布应 用于选择方法，期望平均适应度；
适应度函数的设计

单值、连续、非负、最大化
合理、一致性 计算量小 通用性强
智能优化计算
数学与统计学院 2013年
4.2 基本遗传算法
4.2.3 适应度函数及其尺度变换
适应度函数的线性变换法
f’=α*f+β
系数的确定满足以下条件： ① ② f’avg= favg f’max= cmult f’avg cmult =1.0~2.0
智能优化计算
数学与统计学院 2013年
4.2 基本遗传算法
4.2.1 简单函数优化的实例
编码
表现型：x
基因型：二进制编码（串长取决于求解精度） 串长与精度之间的关系： 若要求求解精度到6位小数，区间长度为2-(-1)＝3， 即需将区间分为3/0.000001=3×106等份。
2097152 221 3000000 222 4194304 所以编码的二进制串长应为22位。
若目标函数为最小化问题：
cmax f ( x), f ( x) cmax Fit( f ( x)) 0, 其他 式中，cmax为f ( x)的最大估计值。
智能优化计算
数学与统计学院 2013年
4.2 基本遗传算法
4.2.3 适应度函数及其尺度变换
几种常见的适应度函数

界限构造法2
4.2 基本遗传算法
4.2.1 简单函数优化的实例
模拟结果
世代数 1 9 17 30 50 80 120 200 自变量 1.4495 1.8395 1.8512 1.8505 1.8506 1.8506 1.8506 1.8506 适应度 3.4494 3.7412 3.8499 3.8503 3.8503 3.8503 3.8503 3.8503
4.2.1 4.2.2 4.2.3 4.2.4 4.2.5 4.2.6 4.2.7 4.2.8 简单函数优化的实例 遗传基因型 适应度函数及其尺度变换 遗传操作——选择 遗传操作——交叉/基因重组 遗传操作——变异 算法的设计与实现 模式定理
智能优化计算
数学与统计学院 2013年
4.3 遗传算法的改进
2
P 0.18 0.03 0.04 0.13
某个体i，其适应度为fi，则其被选取的概率Pi为： 3 3.0 9.00 0.26
Pi fi
4 5
i
2
1.0 1.2 2.1
1.00 1.44 4.41
f
i 1
M
6
7 8 9 10
0.8
2.5 1.3 0.9 1.8
0.64
6.25 1.69 0.81 3.24

在交叉操作时，二进制编码比浮点数编码产生新个 体的可能性多，而且产生的新个体不受父个体所构 成的超体的限制；
在变异操作时，二进制编码的种群稳定性比浮点数 编码差。

智能优化计算
数学与统计学院 2013年
4.2 基本遗传算法
4.2.3 适应度函数及其尺度变换
适应度函数的重要性
适应度函数的选取直接影响遗传算法的收敛速度以 及能否找到最优解。
4.3.1 CHC算法 4.3.2 自适应遗传算法 4.3.3 基于小生境技术的遗传算法
4.4 遗传算法的应用
4.4.1 4.4.2 4.4.3 4.4.4 4.4.5 解决带约束的函数优化问题 解决多目标优化问题 解决组合优化问题 遗传算法在过程建模中的应用 遗传算法在模式识别中的应用
智能优化计算
f(x)=xsin(10πx)+2.0=2.586345
智能优化计算
数学与统计学院 2013年
4.2 基本遗传算法
4.2.1 简单函数优化的实例
计算适应度
(0000000000000000000000)→-1 (1111111111111111111111)→2
二进制与十进制之间的转换：
第一步，将一个二进制串（b21b20…b0）转化为10进制 21 数： (b21b20 b0 ) 2 ( bi 2i )10 x'
智能优化计算
数学与统计学院 2013年
4.2 基本遗传算法
4.2.3 适应度函数及其尺度变换
适应度函数的幂函数变换法
f’= f k
k与所求优化相关
k
智能优化计算
数学与统计学院 2013年
4.2 基本遗传算法
4.2.3 适应度函数及其尺度变换
适应度函数的指数变换法
f’= e-af
a决定了复制的强制性，其值越小，复制的强制性 就越趋向于那些具有最大适应性的个体。
α
智能优化计算
数学与统计学院 2013年
4.2 基本遗传算法
4.2.4 遗传操作——选择
几个概念

选择压力（selection pressure）:最佳个体选中的概 率与平均个体选中概率的比值；
偏差（bias）：个体正规化适应度与其期望再生概 率的绝对差值； 个体扩展（spread）：单个个体子代个数的范围；
选择方差（selection variance）：将正规高斯分布 应用于选择方法，期望种群适应度的方差。

智能优化计算
数学与统计学院 2013年
4.2 基本遗传算法
4.2.4 遗传操作——选择
个体选择概率的常用分配方法

按比例的适应度分配（proportional fitness f f 个体 assignment） 1 2.5 6.25
f ' ( x) sin(10 x) 10 x cos(10 x) 0 即 tan( x) 10 x 10
解有无穷多个：
2i 1 xi i , i 1,2, 20 i (i 1,2, 及i 1,2,)是 ， x0 0 一接近于0的实数递减序列。 2i 1 i , i 1,2, xi 20
数学与统计学院 2013年
4.2 基本遗传算法
4.2.1 简单函数优化的实例
问题的提出
一元函数求最大值：
f ( x) x sin(10 x) 2.0 x [1,2]
智能优化计算
数学与统计学院 2013年
4.2 基本遗传算法
4.2.1 简单函数优化的实例
问题的提出
用微分法求取f(x)的最大值：
智能优化计算
数学与统计学院 2013年
4.2 基本遗传算法
4.2.1 简单函数优化的实例
问题的提出
当i为奇数时xi对应局部极大值点，i为偶数时xi对应 局部极小值。x19即为区间[-1,2]内的最大值点：
37 x19 19 1.85 19 20
此时，函数最大值f(x19)比f(1.85)=3.85稍大。
数学与统计学院 2013年
4.2 基本遗传算法
4.2.3 适应度函数及其尺度变换
适应度函数的作用
适应度函数设计不当有可能出现欺骗问题：
（1）进化初期，个别超常个体控制选择过程； （2）进化末期，个体差异太小导致陷入局部极值。
智能优化计算
数学与统计学院 2013年
4.2 基本遗传算法
4.2.3 适应度函数及其尺度变换
智能优化计算
数学与统计学院 2013年
4.2 基本遗传算法
4.2.3 适应度函数及其尺度变换
几种常见的适应度函数

界限构造法1
若目标函数为最大化问题：
f ( x) cmin , f ( x) cmin Fit( f ( x)) 0, 其他 式中，cmin为f ( x)的最小估计值。
一般而言，适应度函数是由目标函数变换而成的， 对目标函数值域的某种映射变换称为适应度的尺度 变换（fitness scaling）。
智能优化计算
数学与统计学院 2013年
4.2 基本遗传算法
4.2.3 适应度函数及其尺度变换
几种常见的适应度函数

直接转换
若目标函数为最大化问题：Fit ( f (x) )= f (x) 若目标函数为最小化问题：Fit ( f (x) )= - f (x)
智能优化计算
数学与统计学院 2013年
4.2 基本遗传算法
4.2.1 简单函数优化的实例
产生初始种群
产生的方式：随机
产生的结果：长度为22的二进制串 产生的数量：种群的大小（规模），如30，50，…
1111010011100001011000 1100110011101010101110 1010100011110010000100 1011110010011100111001 0001100101001100000011 0000011010010000000000 ……
若目标函数为最大化问题：
1 Fit( f ( x)) 1 c f ( x) 1 1 c f ( x) c 0, c f ( x) 0
若目标函数为最小化问题：
Fit( f ( x)) c 0, c f ( x) 0
c为目标函数的保守估计值。
智能优化计算


智能优化计算
数学与统计学院 2013年
4.2 基本遗传算法
4.2.2 遗传基因型
多种编码方式

二进制编码；