6
智能优化计算
2011之遗传算法（改进与应用） 1.遗传算法的改进
1.1 CHC算法
★变异

在进化前期不采取变异操作，当种群进化到一定收敛时期， 从最优个体中选择一部分个体进行初始化；
初始化：选择一定比例（扩散率，一般0.35）的基因座，随 机地决定它们的位值。

7
智能优化计算
2011之遗传算法（改进与应用） 1. 遗传算法的改进
18
智能优化计算
2011之遗传算法（改进与应用） 2. 遗传算法的应用
2.1 解带约束的函数优化问题
★罚函数法

交叉运算：设父个体为x=[x1,x2,…,xn]和y=[y1,y2,…,yn]
简单交叉 单点算术交叉
整体算术交叉
基于方向的交叉：x’=r(x-y)+x，r为(0,1)之间的随机数，并 假设f(x)≥f(y)。
关键是如何设计罚函数，需要谨慎地在过轻或过重惩罚之间 找到平衡，针对不同问题设计罚函数。
15
智能优化计算
2011之遗传算法（改进与应用） 2. 遗传算法的应用
2.1 解带约束的函数优化问题
★一般方法

协同进化遗传算法（Coevolutionary Genetic Algorithm,1997）
以食物链关系、共生关系等为基础的生物进化现象称为协同 进化； 一个种群由问题的解组成，另一个种群由约束组成，两个种 群协同进化，较好的解应满足更好的约束，较优的约束则 被更多的解所违背。
23
智能优化计算
2011之遗传算法（改进与应用） 2. 遗传算法的应用
2.1 解带约束的函数优化问题
★求解线性约束优化问题的遗传算法
例：7×7运输规划问题
Minimize subject to f ( x ij )
x 11 x 12 x 13 x 14 x 15 x 16 x 17 27 x 21 x 22 x 23 x 24 x 25 x 26 x 27 28 x 31 x 32 x 33 x 34 x 35 x 36 x 37 25 x 41 x 42 x 43 x 44 x 45 x 46 x 47 20 x 51 x 52 x 53 x 54 x 55 x 56 x 57 20 x 61 x 62 x 63 x 64 x 65 x 66 x 67 20 x 71 x 72 x 73 x 74 x 75 x 76 x 77 20
16
智能优化计算
2011之遗传算法（改进与应用） 2. 遗传算法的应用
2.1 解带约束的函数优化问题
★罚函数法

评价函数的构造：
加法
f ( x ) rP ( x ) 0, x X P ( x) 0, x X
乘法
f (x)P (x) 1, x X P ( x) 1, x X


8
智能优化计算
2011之遗传算法（改进与应用） 1. 遗传算法的改进
1.2 自适应遗传算法
★自适应策略

Srinvivas等提出一种自适应遗传算法，Pc和Pm能够随适应 度自动改变：
当种群各个体适应度趋于一致或趋于局部最优时，使Pc和 Pm增加；而当群体适应度比较分散时，使Pc和Pm减少； 对于适应度较高的个体，对应于较低的Pc和Pm ；而较低适 应度的个体，对应于较高的Pc和Pm 。


9
智能优化计算
2011之遗传算法（改进与应用） 1 遗传算法的改进
1.2 自适应遗传算法 自适应方法
k 1 ( f max f ' ) , f f avg Pc f max f avg k , f f avg 2 k 3 ( f max f ) , f f avg Pm f max f avg k , f f avg 4
2011之遗传算法（改进与应用）
遗传算法（改进与应用）
国防科技大学理学院数学系 成礼智 2011年夏季学期数学建模竞赛讲座
智能优化计算
2011之遗传算法（改进与应用）
主 要 内
1. 遗传算法的改进
容
1.1 CHC算法
1.2 自适应遗传算法 2 遗传算法的应用 2.1 解带约束的函数优化问题 2.2 解多目标优化问题
fmax——群体中最大的适应度值； favg——每代群体的平均适应度值； f’——要交叉的两个个体中较大的适应度值； f——要交叉或变异的个体适应度值；
k1、k2、k3、k4 取(0,1)的值
10
智能优化计算
2011之遗传算法（改进与应用） 1 . 遗传算法的改进
1.2 自适应遗传算法
★自适应方法进一步改进
f ( x) i 1, , m j 1, , n
13
智能优化计算
2011之遗传算法（改进与应用） 2. 遗传算法的应用
2.1 解带约束的函数优化问题
★解决途径

将有约束问题转化为无约束问题（罚函数法，penalty function method），历史较长；
改进无约束问题的方法，使之能用于有约束的情况（梯度 投影算法），发展较晚。 遗传算法解决有约束问题的关键是对约束条件的处理（直 接按无约束问题处理是行不通的：随机生成的初始点中可 能有大量不可行解；遗传算子作用于可行解后可能产生不 可行解）。
3
智能优化计算
2011之遗传算法（改进与应用） 1 遗传算法的改进
1.1 CHC算法 ★改进思路

1991年Eshelman提出的一种改进遗传算法；
C：跨代精英选择（Cross generational elitist selection）策 略；

H：异物种重组（Heterogeneous recombination）；
x 11 x 21 x 31 x 41 x 51 x 61 x 71 20 x 12 x 22 x 32 x 42 x 52 x 62 x 72 20 x 13 x 23 x 33 x 43 x 53 x 63 x 73 20 x 14 x 24 x 34 x 44 x 54 x 64 x 74 23 x 15 x 25 x 35 x 45 x 55 x 65 x 75 26 x 16 x 26 x 36 x 46 x 56 x 66 x 76 25 x 17 x 27 x 37 x 47 x 57 x 67 x 77 26 x ij 0 , i 1, 2 , , 7 , j 1, 2 , 7

适用于进化后期，不适于进化前期，因为前期的优秀个体 有可能是局部最优点；
使最大适应度个体的交叉概率和变异概率由0提高到Pc2和 Pm2 ； 采用精英选择策略；


11
智能优化计算
2011之遗传算法（改进与应用） 1. 遗传算法的改进
1.2 自适应遗传算法
自适应方法进一步改进
( Pc 1 Pc 2 )( f ' f avg ) , f f avg Pc 1 Pc f max f avg P , f f avg c1 ( Pm 1 Pm 2 ) k 3 ( f max f ) , f f avg Pm 1 Pm f max f avg P , f f avg m1 Pc 1 0 . 9 , Pc 2 0 . 6 , Pm 1 0 . 1, Pm 2 0 . 001
设计特别的遗传操作
22
智能优化计算
2011之遗传算法（改进与应用） 2. 遗传算法的应用
2.1 解带约束的函数优化问题
★求解线性约束优化问题的遗传算法
例：7×7运输规划问题
将物品由7个起运站运到7个目的地； 已知由 i 站运到 j 地的单位运费是Cij， ai表示 i 站的供应量， bj表示 j 地的需求量， xij表示从 i 站到 j 地的运量。 （i, j =1,2,…,7）
19
智能优化计算
2011之遗传算法（改进与应用） 2. 遗传算法的应用
2.1 解带约束的函数优化问题
★罚函数法

变异运算：设父个体为x=[x1,x2,…,xn]
均匀变异 非均匀变异（动态变异） 边界变异： x’=[x1,x2,…,xk’,…,xn]，xk’等概率地取用变异量的 上界或下界，当最优解在可行域边界上或附近时，边界变异 算子较为有效； 基于方向的变异：x’=x+r•d，d为目标函数的近似梯度。
20
智能优化计算
2011之遗传算法（改进与应用） 2. 遗传算法的应用
2.1 解带约束的函数优化问题 ★求解线性约束优化问题的遗传算法
线性约束优化问题一般形式为：
Minimize subject to f ( x1 , , x n )
Minimize subject to
f (x)
a 11 x 1 a 1 n x n b1 a m 1 x 1 a mn x n b m c 11 x 1 c 1 n x n d 1 c l 1 x 1 c ln x n d l l i x i u i , i 1, , n
12
智能优化计算
2011之遗传算法（改进与应用） 2. 遗传算法的应用
2.1 解带约束的函数优化问题
★约束最优化问题（Constrained Optimization Problems）的
表述
Minimize g i ( x ) 0, h j ( x ) 0, li x i u i