遗传算法
传统的优化方法 （ 局部优化 ）
共轭梯度法, 拟牛顿法, 单纯形方法
全局优化方法
漫步法 （ Random Walk）, 模拟退火法, GA
关于优化问题
比较,传统的优化方法
1） 依赖于初始条件 。
2） 与求解空间有紧密关系, 促使较快地收敛到局部
解, 但同时对解域有约束, 如可微或连续 。 利用
这些约束, 收敛快 。
3） 有些方法, 如 Davison-Fletcher-Powell直接依
赖于至少一阶导数； 共轭梯度法隐含地依赖于梯
度 。
全局优化方法
1）不依赖于初始条件；
2）不与求解空间有紧密关系，对解域，无可微或连
续的要求。求 解稳健，但收敛速度慢。能获得全
局最优。适合于求解空间不知的情况
⑴ 选择运算
⑵ 交换操作
⑶ 变异
遗传算法的基本运算
遗传算法 基本原理
模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传
空间，把可能的解编码成一个向量 —— 染色体，向量的每个
元素称为基因。
通过不断计算各染色体的适应值，选择最好的染色体，获
得最优解。
● 选择运算
—— 从旧的种群中选择适应度高的染色体，放入匹配集（缓冲
区），为以后染色体交换、变异，产生新的染色体作准备。
选择方法 —— 适应度比例法（转轮法）
按各染色体适应度大小比例来决定其被选择数目的多少。
某染色体被选的概率,Pc
?? )()( iic xfxfP
xi 为种群中第 i个染色体，
具体步骤
1）计算各染色体适应度值
2）累计所有染色体适应度值，记录中间累加值 S - mid 和最
后累加值 sum = ∑f(xi)
3） 产生一个随机数 N,0〈 N 〈 sum
4） 选择对应中间累加值 S - mid 的第一个染色体进入交换集
5） 重复（ 3）和（ 4），直到获得足够的染色体。
举例：
⒈具有 6个染色体的二进制编码、适应度值,Pc累计
值。
染色体的 适应度和所占的比例
用转轮方法进行选择
染色体编号 1 2 3 4 5 6 7 8 9 10
适应度 8 2 17 7 2 12 11 7 3 7
被选概率 0.1 0.02 0.22 0.09 0.02 0.16 0.14 0.09 0.03 0.09
适应度累计 8 10 27 34 36 48 59 66 69 76
随机数 23 49 76 13 1 27 57
所选染色
体号码 3 7 10 3 1 3 7
染色体被选的概率
被选的染色体个数
⒉ 10个染色体种群按比例的选择过程
● 交换操作
方法,随机选择二个染色体 (双亲染色体 ),随机指定一点或多
点,进行交换,可得二个新的染色体 (子辈染色体 ).
新的子辈染色体, A’ 11010001
B’ 01011110
模拟生物在自然界环境变化,引起基因的突变,在染
色体二进制编码中,1变成 0;或 0变成 1.突变产生染色
体的多样性,避免进化中早期成熟,陷入局部极值点,
突变的概率很低,
● 变异
复制不能创新,交换解决染色体的创新
GA的流程
简单遗传算法（ GA）的基本参数
① 种群规模 P,参与进化的染色体总数,
② 代沟 G,二代之间不相同的染色体数目,无重叠 G = 1;
有重叠 0 < G <1
③ 选择方法, 转轮法,精英选择法,竞争法,
④ 交换率, Pc 一般为 60~100%.
⑤ 变异率, Pm 一般为 0.1~10%
举例,
变异概率取 0.001
初始种群和它的适应度值
染色体的交换操纵
举例,
14
步骤 1）编码：确定二进制的位数；组成个体（染色体）
位的二进制的值，的第是相应于
。和分别为和的最大值和最小值。是和或是
，精度二进制位数取决于运算
nqb
qqqqqyxq
qb
qq
q
qq
n
N
n
n
n
nn
08,
2
12
12
m i nm a xm i nm a x
1
0
m i n
m i nm a xm i nm a x ? ????
?
?
?
?
?
?
?
?
?
?
??
?
?
步骤 2）选择种群数 P 和初始个体，计算适应度值，
P = 20；
步骤 3）确定选择方法；交换率 PC；变异率 Pm。
选择方法用竞争法； PC = 0.7,Pm = 0.05
计算结果,① 8代后,f(x,y) =0.998757,
② 41代后,f(x,y) =1.00000,
x =3.000290,y =2.999924.
③ 160次适应度计算，达到最优值。
遗传算法的基本数学问题
一个重要的定理 —— 图式定理
什么叫图式？
—— 描述种群中染色体相似性的字符串。
（插入演示） 演示
12
图式—
染色体子集
10**1**1*1
1001111110
1111101110
1001001010
1001101110
?
?
?
?
?
?
?
? ?
染色体长度—
字符集元素数目—
为图式数目
1
L
k
QkQ L??
图式
*******
0111000
**10***
0****1*
0111000
4
3
2
1
?
?
?
?
?
?
?
?
?
?
?
?
H
H
H
H
A
（ *为通配符）
图式的描述：
⑴ 定义长度 ?（ H)—— H左右二端有定义位置之间的距离；
⑵ 图式的阶次 (或固定长度 )O(H） —— H中非 *位（有定义位）
的个数。
图式定理的推导
① 图式在选择过程中的增加,
,/)(),(
//)(),(
/)(),(
)(
)(
)()1,(
1
,
,
是种群平均适应度）（
）是种群中染色体的个数（
ffHftHm
nfHftHm
nfnHftHm
xf
hf
nhpntHm
i
i
n
i
i
HPhi
i
HPhi
is
i
i
?
?
?
???
?
?
?
?
?
?
??
??
经过选择,在 t+1代,图式 H的数量 m(H,t+1)为,
② 图式在交换中的破坏
③ 图式在变异中的破坏
经过选择、交换、变异后在 t+1中，图式 H的数量：
])(1 )(1[)(),()1,( mc PHOL HP
f
HftHmtHm ?
????
?
图式定理：在选择、交换、变异的作用下，阶次低、定
义长度短、适应度高的图式（模块）将按指数增长的规
律，一代一代地增长。
遗传算法在应用中的一些基本问题
1）知识的编码
2）适应度函数 。
a) 适应度函数值必须非负。根据情况做适当的处理
二进制和十进制的比较：二进制有更多图式和更大的搜索范
围；十进制更接近于实际操作。
12
m i nm a x
?
??
l
UUQ精度
是二进制的长度
小值。分别为变量的最大和最和
m i nm a x
l
UU
3）全局最优和收敛性 。
根据图式定理，对于具有“欺骗性”函数,GA有可
能落入局部最优点。
a v gma v ga v g fCfff
babaff
????
???
m a x
的选择满足以下条件：和
。，所希望的复制的数目是最好种群数目情况下 mC
0.2~2.1?mC
b）为保持种群的多样性，防止“超级”染色体“统治”
种群。
欺骗性函数
图式划分,指引相互之间竞争的 定义位为同一集合 的一组图式。
如 #表示定义位，则 H1=*1*0*,H2=*0*1*, H3=*1*1*，
H4=*0*0* 同属于划分 *#*#*。
总平均适应度（ OAF）,对一个给定图式,OAF即为其成员
的平均适应度。
欺骗性函数 —— 包含全局最优的图式其 OAF不如包含局部
最优的 OAF，这种划分称为欺骗划分，它会使 GA陷入局部最
优。 如最高阶欺骗函数有 k个定义位，则此函数称 k阶欺骗。
举例,3位欺骗函数
● 高级 GA算法
1）操作的改进
2）算法的改进
选择方法改进,精英法（竞赛法）、置换式和非置换式
随机选择法，排序法。
交换方法的改进,多点交换；重组运算
微种群遗传算法（ ?GA）
双种群遗传算法（ DPGA）
重组运算：解决染色体分布过于集中问题。把适应度函数做进
一步处理。
?
?
?
n
j
jiiis xxdsxfxf
1
)),((/)()(
是共享度函数 )( ds
终止条件,1）达到预定指标； 2）达到预定代数。
?GA算法
双种群算法（ DPGA）
基本思想：利用人类社会分工合作的机理。
分成,全局种群 —— 粗搜索，寻找可能存在的最优区域；
局部种群 —— 精搜索在全局划定的区域内，寻找最优点。
100,100
]0.1))(50[ s i n ()(
100,100
)](001.00.1[
5.0s i n
5.0
536.65,536.65
)(
1
0, 0 0 2
2, 0 4 8,2, 0 4 8
) (1 ) ( 100
21
1.02
2
2
1
25.02
2
2
14
21
22
2
2
1
2
2
2
1
3
2 1
25
1j
2
1
6
21
2
1
2
2
2
11
???
????
???
??
??
??
???
??
??
???
????
?
?
?
?
xx
xxxxf
xx
xx
xx
f
xx
axj
f
xx
xxxf
j
iji
s
测试函数：
遗传算法的应用,1）神经网络结构参数的选择
2）滑模控制中应用
3）倒立摆控制中应用
传统的优化方法 （ 局部优化 ）
共轭梯度法, 拟牛顿法, 单纯形方法
全局优化方法
漫步法 （ Random Walk）, 模拟退火法, GA
关于优化问题
比较,传统的优化方法
1） 依赖于初始条件 。
2） 与求解空间有紧密关系, 促使较快地收敛到局部
解, 但同时对解域有约束, 如可微或连续 。 利用
这些约束, 收敛快 。
3） 有些方法, 如 Davison-Fletcher-Powell直接依
赖于至少一阶导数； 共轭梯度法隐含地依赖于梯
度 。
全局优化方法
1）不依赖于初始条件；
2）不与求解空间有紧密关系，对解域，无可微或连
续的要求。求 解稳健，但收敛速度慢。能获得全
局最优。适合于求解空间不知的情况
⑴ 选择运算
⑵ 交换操作
⑶ 变异
遗传算法的基本运算
遗传算法 基本原理
模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传
空间，把可能的解编码成一个向量 —— 染色体，向量的每个
元素称为基因。
通过不断计算各染色体的适应值，选择最好的染色体，获
得最优解。
● 选择运算
—— 从旧的种群中选择适应度高的染色体，放入匹配集（缓冲
区），为以后染色体交换、变异，产生新的染色体作准备。
选择方法 —— 适应度比例法（转轮法）
按各染色体适应度大小比例来决定其被选择数目的多少。
某染色体被选的概率,Pc
?? )()( iic xfxfP
xi 为种群中第 i个染色体，
具体步骤
1）计算各染色体适应度值
2）累计所有染色体适应度值，记录中间累加值 S - mid 和最
后累加值 sum = ∑f(xi)
3） 产生一个随机数 N,0〈 N 〈 sum
4） 选择对应中间累加值 S - mid 的第一个染色体进入交换集
5） 重复（ 3）和（ 4），直到获得足够的染色体。
举例：
⒈具有 6个染色体的二进制编码、适应度值,Pc累计
值。
染色体的 适应度和所占的比例
用转轮方法进行选择
染色体编号 1 2 3 4 5 6 7 8 9 10
适应度 8 2 17 7 2 12 11 7 3 7
被选概率 0.1 0.02 0.22 0.09 0.02 0.16 0.14 0.09 0.03 0.09
适应度累计 8 10 27 34 36 48 59 66 69 76
随机数 23 49 76 13 1 27 57
所选染色
体号码 3 7 10 3 1 3 7
染色体被选的概率
被选的染色体个数
⒉ 10个染色体种群按比例的选择过程
● 交换操作
方法,随机选择二个染色体 (双亲染色体 ),随机指定一点或多
点,进行交换,可得二个新的染色体 (子辈染色体 ).
新的子辈染色体, A’ 11010001
B’ 01011110
模拟生物在自然界环境变化,引起基因的突变,在染
色体二进制编码中,1变成 0;或 0变成 1.突变产生染色
体的多样性,避免进化中早期成熟,陷入局部极值点,
突变的概率很低,
● 变异
复制不能创新,交换解决染色体的创新
GA的流程
简单遗传算法（ GA）的基本参数
① 种群规模 P,参与进化的染色体总数,
② 代沟 G,二代之间不相同的染色体数目,无重叠 G = 1;
有重叠 0 < G <1
③ 选择方法, 转轮法,精英选择法,竞争法,
④ 交换率, Pc 一般为 60~100%.
⑤ 变异率, Pm 一般为 0.1~10%
举例,
变异概率取 0.001
初始种群和它的适应度值
染色体的交换操纵
举例,
14
步骤 1）编码：确定二进制的位数；组成个体（染色体）
位的二进制的值，的第是相应于
。和分别为和的最大值和最小值。是和或是
，精度二进制位数取决于运算
nqb
qqqqqyxq
qb
q
n
N
n
n
n
nn
08,
2
12
12
m i nm a xm i nm a x
1
0
m i n
m i nm a xm i nm a x ? ????
?
?
?
?
?
?
?
?
?
?
??
?
?
步骤 2）选择种群数 P 和初始个体，计算适应度值，
P = 20；
步骤 3）确定选择方法；交换率 PC；变异率 Pm。
选择方法用竞争法； PC = 0.7,Pm = 0.05
计算结果,① 8代后,f(x,y) =0.998757,
② 41代后,f(x,y) =1.00000,
x =3.000290,y =2.999924.
③ 160次适应度计算，达到最优值。
遗传算法的基本数学问题
一个重要的定理 —— 图式定理
什么叫图式？
—— 描述种群中染色体相似性的字符串。
（插入演示） 演示
12
图式—
染色体子集
10**1**1*1
1001111110
1111101110
1001001010
1001101110
?
?
?
?
?
?
?
? ?
染色体长度—
字符集元素数目—
为图式数目
1
L
k
QkQ L??
图式
*******
0111000
**10***
0****1*
0111000
4
3
2
1
?
?
?
?
?
?
?
?
?
?
?
?
H
H
H
H
A
（ *为通配符）
图式的描述：
⑴ 定义长度 ?（ H)—— H左右二端有定义位置之间的距离；
⑵ 图式的阶次 (或固定长度 )O(H） —— H中非 *位（有定义位）
的个数。
图式定理的推导
① 图式在选择过程中的增加,
,/)(),(
//)(),(
/)(),(
)(
)(
)()1,(
1
,
,
是种群平均适应度）（
）是种群中染色体的个数（
ffHftHm
nfHftHm
nfnHftHm
xf
hf
nhpntHm
i
i
n
i
i
HPhi
i
HPhi
is
i
i
?
?
?
???
?
?
?
?
?
?
??
??
经过选择,在 t+1代,图式 H的数量 m(H,t+1)为,
② 图式在交换中的破坏
③ 图式在变异中的破坏
经过选择、交换、变异后在 t+1中，图式 H的数量：
])(1 )(1[)(),()1,( mc PHOL HP
f
HftHmtHm ?
????
?
图式定理：在选择、交换、变异的作用下，阶次低、定
义长度短、适应度高的图式（模块）将按指数增长的规
律，一代一代地增长。
遗传算法在应用中的一些基本问题
1）知识的编码
2）适应度函数 。
a) 适应度函数值必须非负。根据情况做适当的处理
二进制和十进制的比较：二进制有更多图式和更大的搜索范
围；十进制更接近于实际操作。
12
m i nm a x
?
??
l
UUQ精度
是二进制的长度
小值。分别为变量的最大和最和
m i nm a x
l
UU
3）全局最优和收敛性 。
根据图式定理，对于具有“欺骗性”函数,GA有可
能落入局部最优点。
a v gma v ga v g fCfff
babaff
????
???
m a x
的选择满足以下条件：和
。，所希望的复制的数目是最好种群数目情况下 mC
0.2~2.1?mC
b）为保持种群的多样性，防止“超级”染色体“统治”
种群。
欺骗性函数
图式划分,指引相互之间竞争的 定义位为同一集合 的一组图式。
如 #表示定义位，则 H1=*1*0*,H2=*0*1*, H3=*1*1*，
H4=*0*0* 同属于划分 *#*#*。
总平均适应度（ OAF）,对一个给定图式,OAF即为其成员
的平均适应度。
欺骗性函数 —— 包含全局最优的图式其 OAF不如包含局部
最优的 OAF，这种划分称为欺骗划分，它会使 GA陷入局部最
优。 如最高阶欺骗函数有 k个定义位，则此函数称 k阶欺骗。
举例,3位欺骗函数
● 高级 GA算法
1）操作的改进
2）算法的改进
选择方法改进,精英法（竞赛法）、置换式和非置换式
随机选择法，排序法。
交换方法的改进,多点交换；重组运算
微种群遗传算法（ ?GA）
双种群遗传算法（ DPGA）
重组运算：解决染色体分布过于集中问题。把适应度函数做进
一步处理。
?
?
?
n
j
jiiis xxdsxfxf
1
)),((/)()(
是共享度函数 )( ds
终止条件,1）达到预定指标； 2）达到预定代数。
?GA算法
双种群算法（ DPGA）
基本思想：利用人类社会分工合作的机理。
分成,全局种群 —— 粗搜索，寻找可能存在的最优区域；
局部种群 —— 精搜索在全局划定的区域内，寻找最优点。
100,100
]0.1))(50[ s i n ()(
100,100
)](001.00.1[
5.0s i n
5.0
536.65,536.65
)(
1
0, 0 0 2
2, 0 4 8,2, 0 4 8
) (1 ) ( 100
21
1.02
2
2
1
25.02
2
2
14
21
22
2
2
1
2
2
2
1
3
2 1
25
1j
2
1
6
21
2
1
2
2
2
11
???
????
???
??
??
??
???
??
??
???
????
?
?
?
?
xx
xxxxf
xx
xx
xx
f
xx
axj
f
xx
xxxf
j
iji
s
测试函数：
遗传算法的应用,1）神经网络结构参数的选择
2）滑模控制中应用
3）倒立摆控制中应用
