遗传算法
传统的优化方法 ( 局部优化 )
共轭梯度法, 拟牛顿法, 单纯形方法
全局优化方法
漫步法 ( 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)倒立摆控制中应用