第3章
基于共轭先验分布的
单模分布估计算法
3.概述
1

.................... 

本章主要介绍基于共轭先验分布的两层分布估计(Two-levelHierarchicalEstimationof 
DistributionAlgorithm,THEDA)算法。分布估计算法作为演化算法的一个分支,其全
局搜索与局部搜索的关系仍是一个基本的问题[28]。全局搜索(exploration)是探索新空
间的过程,强调搜索的广度;而局部搜索(exploitation)是探索已搜索空间邻域的过程,强
调搜索的深度。全面而深入地搜索整个决策空间是最理想的方式。但是有限的计算资源
要求算法合理地平衡这两种搜索策略。例如,在传统的遗传算法中,交叉算子主要体现了
全局搜索策略,而变异算子则主要体现了局部搜索策略。仅强调全局搜索会产生质量较
差的解,而过分强调局部搜索会使算法陷入近优解,因此一个演化算法需要合理平衡这两
方面,以利用最少的计算资源获得最好的搜索效果。如果算法可以在计算的开始尽可能
地探索更多的区域,并且随着计算的进行逐步过渡到局部搜索上去,就可以获得较好的性
能。由于分布估计算法是根据已经选择的个体估计种群分布的概率模型,这可以看作一
个根据已有样本推断其分布的过程。受到贝叶斯推断过程的启发,利用Beta分布是二项
分布的共轭先验分布这一性质,本章提出了基于Beta分布的两层分布估计算法。与其他
单变量分布估计算法相同,THEDA 也使用概率向量作为基本模型。但是THEDA 不直
接从种群估计对应的概率向量,而是估计概率向量可能的分布,即先估计一个Beta向量, 
其中每个元素表示对应的概率向量中元素的分布。通过Beta分布采样得到概率向量,最
后通过概率向量采样得到新种群。使用“分布的分布”这一思想使得这种算法框架有两个
主要的优点:首先,利用“分布的分布”有助于直接提高种群的多样性,并且通过限制Beta 
分布中参数的取值范围可以避免变量的收敛,这可以帮助已经陷入局部最优状态的算法
获得改变状态的机会;其次,在这种框架下,通过控制Beta向量的参数更新过程,可以很
好地控制运算中全局搜索和局部搜索的权重。在0-1背包问题和NK-Landscapes问题上
的测试实验说明THEDA 的性能显著优于其他单变量分布估计算法。

本章内容安排如下:3.2节给出共轭先验分布的概念和基本性质,主要介绍Beta分


第3 章 基于共轭先验分布的单模分布估计算法 
15 
布和二项分布的关系;3.3节完整描述两层分布估计算法,包括算法框架以及模型的学习
和演化过程;3.4节利用3个测试问题测试算法的性能;3.5节总结本章的内容。
3.2 Beta分布与二项分布
.................................... 
频率推断和贝叶斯推断[29]是统计推断的两种主要方法。在频率推断方法中,未知参数
被看作具有固定的取值。为了获得准确的结果,使用频率推断的方法需要较大规模的样本。
在贝叶斯推断中,未知参数被看作一个随机变量,并且这个变量具有一个概率分布。这种方
法可以避免极端情况下错误推断的产生。贝叶斯推断的核心是贝叶斯公式[30]: 
p(θ|X ,H )= p(X |θ)p(θ|H ) 
∫θp(X |θ)p(θ|H )dθ (3-1) 
其中,p(θ|X ,H )是后验概率,即根据数据X 更新后的θ 的概率。式(3-1)等号右侧的分
子包含两部分:似然概率p(X|θ)和先验概率p(θ|H )。在p(θ|H )中,H 为超参数。
理论上,先验分布本可以取任意形式的函数。然而选择共轭先验分布会减少计算量。假
设一个n 重伯努利实验具有未知参数θ。可以通过做实验并利用实验结果推断参数θ 的
取值。在实验开始前,假设参数θ 服从某个参数为H 的概率分布,即θ 服从p(θ|H ),这
个分布也称作先验分布。通过n 次实验,获得了实验结果X ,利用式(3-1)可以计算出在
获得实验结果的情况下参数θ 的分布情况。Beta分布[31]是一个定义在区间[0,1]的连续
概率分布,其概率密度函数定义如下: 
p(θ;α,β)= 1 B(α,β)θα-1 (1-θ)β-1 (3-2) 
其中,B(α,β)是Beta函数。Beta分布中的两个参数α 和β 决定了概率密度函数的形状, 
如图3-1所示。
Beta分布的一个重要性质是它为二项分布的共轭先验分布。假设在上述n 重伯努
利实验中出现s 次正例和f=n-s 次反例,那么这组实验的采样分布为
p(s,f|θ)= 
n
s
.
è .
.
.÷θs(1-θ)f (3-3) 
如果选取参数为α 和β 的Beta分布作为θ 的先验分布。利用式(3-1)计算其后验概率: 
p(θ|s,f,α,β)= p(s,f|θ)p(θ|α,β) 
∫θp(s,f|θ)p(θ|α,β)dθ 
= 
(s+f 
s )θs+α-1(1-θ)f+β-1 
B(α,β) 
∫1
0 
(s+f 
s )θs+α-1(1-θ)f+β-1 
B(α,β) dθ

演化机器学习(第
2 
版) 


图3-
1 
不同参数下Beta分布的概率密度函数

s+α-1(f+β-1

θB(
1-θ)

= 

s+α,f+β) 
=p(β+f) 34)

θ|α+s,(
θ 
的后验分布也是一个Beta分布,只是两个参数变为α+
s 
和β+f。在这个问题上,Beta 
分布的两个参数具有直观的物理意义,分别表示实验中正例和反例出现的次数。需要指
出的是,这两个参数可以取非整数值。Beta分布的概率函数的方差为

vaθ)(2(α+β+1) (3-5)

r(
= 
α+β)
αβ 

方差表明参数
θ 
的不确定性。参数
α 
和
β 
同时增加会导致方差减小。其物理意义是,当
实验结果中正例和反例的数量都增加时,参数的不确定性减小。参数α=1、β=1的Beta 
分布被称作贝叶斯先验分布,这时Beta分布为区间[0,1]上的均匀分布。这时熵最大,表
明没有关于
θ 
的信息,0,上的取值是均匀的。

θ 
在区间[1] 

3.两层分布估计算法
3

................................ 

3.1 
算法框架
3.
基于共轭先验分布的两层分布估计算法与其他算法的最大区别是采用了层次化模

型。分布估计算法一般直接利用选择的个体估计概率模型并用以产生新个体。在两层分

布估计算法中,选择的个体用来估计一个Beta向量,其定义如下。

16
定义3-
1 
Beta向量是由Beta分布组成的,每个分量包含定义在[1,+∞)区间上的


第3 章 基于共轭先验分布的单模分布估计算法 
17 
两个实数。如下所示: 
BetaV= 
α1 α2 … αn 
β1 β2 … βn 
é
. êê
ù
. úú 
其中,(αi,βi)确定了一个Beta分布。因此,Beta向量表示由n 个Beta分布组成的概率
分布数组。Beta向量中每个参数的定义域为[1,+∞),这是因为,Beta分布的参数的定
义域为[0,+∞),并且当参数大于或等于1时,可以保证概率密度的最大值不会出现在两
端。可以通过对Beta向量采样产生一个概率向量,再对这个概率向量采样得到新解。图3-2 
是THEDA 的基本框架。其中,Pop代表种群(Population),Sel代表选择(Selection), 
Best代表最优的或最好的个体。由图3-2可以看出,该算法的基本框架是一个两层结
构,第一层是从BetaV 到PV,第二层是从PV 到种群,因此该算法称为两层分布估计算
法。在利用子种群估计下一代BetaV 时,学习速率显式地由学习速率函数控制。模型更
新和学习速率函数将在3.3.2节详细介绍。
图3-2 THEDA 的基本框架
计算过程中适应度最高的解将保留下来并作为算法最后的输出。算法3-1给出了
THEDA的伪代码。算法具体过程描述如下。第1~4行为算法的初始化过程。首先,变
量t 为算法当前的迭代次数,初始化为0。更新过程中的学习速率函数将根据t 确定学习
速率。算法开始时,学习速率较小,这时的算法倾向于随机搜索;随着t 的增大,通过增大
学习速率使模型尽可能多地进行局部搜索。第2~4行的循环用于将概率向量PV 的每
个元素初始化为0.5。在这个条件下,算法采样得到的初始种群是符合均匀分布的。第
5~18行是迭代的主循环。循环开始时,首先通过对PV 采样得到本轮迭代的初始种群。
对每个采样得到的个体Pj,利用目标函数评价得到其适应度Fj。在THEDA 中,使用截
断选择(truncationselection)算子从种群中选取最优秀的ps×n=m 个个体组成子种
群S。
算法3-1 THEDA 
1:t←0 
2:fori=1,2,…,ldo 
3: PVi←0.5

演化机器学习(第
2 
版) 

4:endfor 
5:while未达到终止条件do 

6: forj=1,2,…,
nd

7: 1,2,…,(o) 
fori=ldo 

8: Pji 
←sampleBernouli(PVi)
9: dfr 
10: aluate(Pj )Fj(e) ←ev(o) (n) 
11: endfor 
12: S←slct(P,F)
13: BtaeModl(t)
eaV←upd(e) (e) teS,

14: fori=1,2,…,o
ld

15: PVi 
←sampleBernouli(BetaVi)
16: endfor 
17: t←t+1 
18:endwhile 
利用选取的个体更新Ba向量,其具体方法如算法32所示。模型更新过程在3.2节
介绍。主循环的最后一步是通过Beta向量采样得到一个新的概率向量。

et-3.

算法3-
2 
THEDA的模型更新过程

:prcdrpdtel(S,

oeueuaeModt)
: 2,…
,


fori=1,ldo
: num1←
0
: num0←
0
: forj=1,2,…,
m 
do
: ifSji 
=1then
: num1←num1+
1
: else
: num0←num0+
1


10: endif 
11: endfor 
12: (eaV.t)
Bti)α←1+num1×fL(

13: (BetaVi).t)
β←1+num0×fL(

14: endfor 
15: returnBetaV 
16:endprocedure 
18 


第
3 
章基于共轭先验分布的单模分布估计算法


3.2 
模型更新过程
3.
如2.模型与相应的模型更新策略是一个分布估计算法区别于其他分布估

3节所述, 
计算法的主要部分。理想的模型具有相对简单的形式并且可以通过较少的计算资源实现
更新。模型更新的过程就是通过选取的子种群学习模型的过程。这个过程与贝叶斯推断
有相似性。THEDA 从选取的个体推断其模型的分布。

Beta分布的两个参数具有直观的物理意义。在贝叶斯推断中,参数
α 
和
β 
表示观测
结果中正例和负例出现的次数。在二进制编码条件下,因

α 
和
β 
可以看作0和1的个数, 
此可通过统计每个决策变量上所有个体中0和1的个数作为Beta向量对应元素的参数。
但是直接将统计结果赋予参数
α 
和
β 
并不能产生理想的更新结果,因此要使用学习速率
函数显式控制这个更新过程。学习速率函数的定义如下。
t)。

定义3-
2 
学习速率函数是一个定义域为正整数、值域为实数的单调函数,记为fL(
在THEDA 中,学习速率函数的自变量为当前迭代的次数t。理想的演化算法应该
随着计算的进行由全局搜索逐步过渡到局部搜索。由3.可以通过同时增加

2节可知, 
Beta分布的两个参数减小其方差,直接减小第一层采样的不确定性,进而加强局部搜索。
因此,学习速率函数应该为单调增函数。这个性质可以保证算法随着计算的进行而逐渐
加强局部搜索。

算法3-2为模型更新过程的伪代码。在更新过程中,首先统计选取的子种群中每个
决策变量上所有个体中0和1的个数。为了利用学习速率函数控制算法的搜索,将0和
1的个数乘以学习速率作为对应的Beta分布的参数,这样,Beta分布的方差会随着计算
的进行而逐步减小,算法逐渐加强局部搜索。在定义3-2中,Beta分布的参数定义域为
[1,+∞), 这本质上是一种加一平滑[32](add-oneSmoothing)方法,广泛应用于自然语言
处理等领域。当num0 或者num1 为0时,对于一个决策变量来说,种群中的所有个体都
具有相同的取值。在这种情况下,若不使用平滑技术,那么这个变量会收敛到一个值上。
从此以后,这个变量不会发生改变,进而使算法陷入近优解而无法跳出。例如,当Beta分
布的一个参数为0时,不妨假设α=这时Bt即p(1)1。

0, ea分布退化为一个单点分布, x==
在随后的采样中,概率向量中的对应分量只会为1,这个分量已经收敛,随后所有产生的
个体都具有相同的取值。所以,

α 
和
β 
的值要再加上1以避免这种情况的发生。通过这
种限制,可以保证Bt0,上的连续分布,

ea分布是在区间[1] 且概率最大值不会出现在区间
两端。在THEDA 中,学习速率函数为简单的线性函数: 

c 
为决定学习速率的系数,
fL(t)=c×t 
(3-6) 
其中,
t 
为当前迭代的次数。


19 


演化机器学习(第2 版) 
20 
3.4 测试与实验
........................ 
3.4.1 测试问题
1.Onemax问题 
Onemax问题是简单的与变量无关的单峰问题。其搜索空间为{0,1}n ,其中n 是问
题的规模。目标函数定义如下: 
fOnemax(z)=Σn 
i=1
zi (3-7) 
优化目标是求解最大值,全局最优解为z=[11…1],对应的目标函数值为n。在本
节中使用问题规模n=1000的实例,记为POnemax1000。这个简单的问题用于测试算法参数
对算法性能的影响。
2.0-1背包问题
0-1背包问题是著名的组合优化问题[33]。问题描述如下:有一个物品的集合,其中
每个物品具有重量和价值两个属性;同时有一个背包,具有一定容量。问题的求解目标是
找到一个选取物品的方案,即选取一个物品集合的子集,最大化所有选取物品的价值并且
满足总重量不超过背包的容量这一限制条件。0-1背包问题的形式化定义如下: 
maxf(x)=ΣN 
i=1
pixi 
subjecttoΣN 
i=1
wixi (3-8) 
其中,wi 和pi 分别是第i 个物品的重量和价值。这里使用了文献[22]中所采用的问题
实例生成方法,即
wi =uniformly_random[1,10] (3-9) 
pi =wi +5 (3-10) 
在测试中,使用了两种不同类型的背包容量:一种是将背包容量设定为所有物品总重量
的一半;另一种是将背包容量设定为固定值20。这两种容量分别记为Ch 和Cf。
Ch =12
ΣN 
i=1
wi (3-11) 
Cf=20 (3-12) 
在计算中生成的解可能不满足问题的限制条件,即不在可行域内。为了保证解满足
限制条件,需要使用随机修复算子[22]。对于一个方案,随机修复算子的作用如下:当物

第 
3 
章基于共轭先验分布的单模分布估计算法


品总重量超过背包容量时,随机去除一些物品,直到满足限制条件;在物品总重量不超过
背包容量时,随机增加一些物品以尽可能提高解的适应度。其具体过程如算法3-3所示。

算法3-
3 
0-1背包问题的随机修复算子

1:procedurerepairOperator(x)

N 

2: ifΣwixi 
≤Cthen 
i=1

3: feasible=true 
4: else 
5: feasible=false 
6: endif 
7: while!feasibledo 
8: 随机将
x 
中的一个为1的元素改写为0 
N 

9: ifΣwixi 
≤Cthen 
i=1

10: feasible=true 
11: endif 
12: endwhile 
13: whilefibledo 
14: 假设改写的元素为xi随机(e) 将(s) x中的一个为0的元素改写为1,(a) 
N 

15: ifΣwixi 
>Cthen 
i=1

16: feasible=false 
17: xi 
=0 
18: endif 
19: endwhile 
20:endprocedure 
修复算子首先判断给定解是否满足限制条件。当不满足限制条件时,随机将解向量
中值为1的元素改写为0,直到满足限制条件为止。这时再尝试增加1的个数,以尽可能
提高解的质量。当解满足限制条件时,随机将解向量中值为0的元素改写为1,以尽可能
提高解的质量。

在章节实验中,问题的规模分别为250 、500 、1000和2000 。将实例记为Pknp_Ch或者
Pknp_D_Cf 。其中,
D 
为问题规模的大小,Ch和Cf分别表示Ch 和Cf两种背包容量。(D_) 

3.NK-Landscapes问题
[34,
NK-Landscapes是一个产生不同目标函数的模型35]。它由Kaufman提出并且广
泛应用在演化算法性能测试上[26,36-38]。其适应度函数定义如下: 


21 


演化机器学习(第2 版) 
22 
F(x)=1 NΣN 
i=1
Fi(xi;xi1 ,xi2 ,…,xiK ) (3-13) 
其中,{i1,i2,…,iK }.{1,…,i-1,i+1,…,N }。N 是问题的规模;K 为每个变量邻域
的大小,表示变量之间的相关程度。邻域的生成有两种方法:一种是选取位置相邻的K 
个基因位作为邻域;另一种是随机选取K 个基因位组成邻域。Kauffman研究了生成邻
域的两种方法的性质。适应度贡献(fitnesscontribution)函数Fi(xi;xi1 ,xi2 ,…,xiK )是
一个从二进制字符串到实数的映射,具体的对应关系由模型生成时随机产生。有研究从
理论上已经证明[39],当K ≥3并且采用随机邻域生成方法时,NK-Landscapes模型产生
的优化问题实例是NP-完全的。本章实验使用随机邻域生成方法。问题的规模设定为
256、512、1024、2048和4096,K 取0~8的所有整数,因此,总共有5×9=45个实例用于
测试算法。
3.4.2 参数研究
THEDA 包含3个参数,分别为种群规模n、选择压力Ps 和学习速率fL(t)。本节
将在Onemax问题上探究3个参数的选取对算法性能的影响。根据单一变量原则,本节
的实验分为3部分。
为了测试种群大小的影响,将选择压力和学习速率函数设定为Ps=0.1,fL(t)= 
0.5t,参见式(3-6),问题的规模设定为1000,测试中种群规模n 设定为20、100、200和
500。记录算法在50次独立运算中的最好结果并求其均值和方差,结果如图3-3所示。
实验结果表明,当种群规模n 设定为20、100和200时,算法性能相近;当n=500时,算法
性能出现下降。这说明种群规模对算法性能的影响有限。
图3-3 种群规模的影响

第 
3 
章基于共轭先验分布的单模分布估计算法


为了测试选择压力的影响,将种群规模
n 
设定为200,将学习速率函数设定为fL(
05 、1、2和0.结果如图305 、
t)= 

t,将选择压力设定为0.5, 4所示。当Pc 等于0.1和0.50.0.-0.

0.当Ps5时,
2时,算法性能相近; 等于0.算法性能较差。导致这个结果有两个原因:首
先,选择压力过小的时候无法有效驱使种群移动;其次,较小的选择压力会产生较大的子
种群。模型的参数增长很快,Beta向量中每个Beta分布的方差快速减小。这不利于多样
性保持,影响了算法对搜索空间的搜索能力。


图3-
4 
选择压力的影响

为了测试学习速率的影响,将种群大小设定为200, 1。学习速

将选择压力设定为0.
率函数的系数
c 
分别设定为0.0和2.5所示。

1、2、5、

0.0.1.0。实验结果如图3
图3-
5 
学习速率的影响

首先将c=5的实验结果作为基线。当系数减小时,算法的整体性能下降;当系数

0.
增加时,计算的开始阶段和基线的表现相近,评价次数超过5000 次时算法的性能下降。
23

演化机器学习(第
2 
版) 

3.3 
实验设置
4.
本节将THEDA 与cGA 、PBIL 和QEA 进行对比。算法的性能都受到其参数设定的
影响。后
3种算法的参数设定如下: 

.对于cGA,其唯一的参数为虚拟种群规模n。在本节实验中采用文献[40]中推荐
的设置。在文献[26]中也使用了这个设置。
.PBIL 具有4个参数:学习速率L、变异概率Pm、变异偏移量
S 
和种群规模n。前
3个参数分别设定为0.02 和0.的设置相同。在本节所涉及
1、0.05,这与文献[26] 
两个实验中,PBIL 的性能受到种群规模的影响较大。通过在实例Pknp_500_Ch 测试
n=

了10,20,…,100 共10 个参数的结果,最终选取效果最好的取值,20 。

.QEA 的所有参数采用其原始文献中的推荐设置[22]。
在THEDA 中,根据3.2节的实验结果,种群规模、选择压力和学习速率3个参
数分别设置为n=200,4.1以及L=0.

Ps=0.5。本节涉及的4个算法的参数如表3-1 
所示。

表3-
1 4 
个算法的参数设置

算法参数
cGA n= π 
2 Dlog2D 
PBIL n=20,L=0.1,Pm=0.02,S=0.05 
QEA n=10,Δθ=0.01π,Sg=100,Sl=1 
THEDA n=200,Ps=0.1,fL(t)使用式(3-6) 

算法在每个实例上独立运行50 次。为了实现公平的比较,终止条件设定为最大的目
标函数调用次数。对于所有0-1背包问题的实例,最大评价次数为40000;而对于NK-
Landscapes问题的实例,最大评价次数设定为10000 。算法发现的最好结果都被记录以
用于计算统计信息(包括均值和方差)并用来比较显著性。在本节实验中,使用了α=0.

05, 
即显著性为95% 的威尔科克森符号秩检验(Wilcoxonsigned-ranktest)计算算法得到结
果是否存在的显著差异。

3.4 
实验结果
4.
对于背包容量为Ch 的实例,实验结果如图3-6~图3-9所示。对于背包容量为Cf 

24

第
3 
章基于共轭先验分布的单模分布估计算法


的实例,实验结果如图3-10~图3-13 所示。表3-2给出了4个算法在NK-Landscapes 
问题上的实验结果。

在图3-6~图3-9中,均值用虚线表示,标准差用围绕在均值附近的实线表示。在实
例Pknp_250_Ch 和Pknp_500_Ch 上,cGA 、PBIL 和THEDA 的性能相近。对于Pkp_250_Ch 实例, 
cGA 和PBIL 的收敛速度较THEDA 快,但是THEDA 得到的最终结果较好。(n) 


图3-
6 
Pknp_250_Ch 
的实验结果


图3-
7 
Pknp_500_Ch 
的实验结果

对于Pknp_1000_Ch 和Pknp_2000_Ch,THEDA 具有性能上的优势。cGA 可以得到和


25 


演化机器学习(第
2 
版) 


图3-
8 
Pknp_1000_Ch 
的实验结果


图3-
9 
Pknp_2000_Ch 
的实验结果

THEDA 相近的最终结果,但是cGA 的收敛速度比THEDA 慢。PBIL 由于早熟导致最
终结果比THEDA 差。这说明THEDA 在速度和解的质量上取得了平衡,其原因在于
THEDA 通过学习速率很好地控制了不同阶段的搜索侧重。

对于背包容量为Cf 的实例,PBIL 和THEDA 的表现优于cGA 和QEA 。在实例
PkpCf 上,PBIL 在前4000 次函数调用时比THEDA 的收敛速度快,但是随后其收敛速度减(n) 慢(250) 。(_) THEDA的最终结果比PBIL好,(_) 体现在两方面:首先,其最优结果的均值优于
26PBIL;其次,THEDA 计算结果的方差较PBIL 的小。这说明THEDA 在这一类问题上


第
3 
章基于共轭先验分布的单模分布估计算法


图3-10 
Pknp_250_Cf 
的实验结果


图3-11 
Pknp_500_Cf 
的实验结果

的性能稳定。

整体观察图3-10~图3-13,可以发现如下规律:早熟是PBIL 存在的主要问题,并且
这种现象随着问题规模的增大而增大。特别地,在实例Pknp__Cf 上,PBIL 在前10000 次
评价时都具有较快的速度,但是它陷入了局部最优结果中,平均(2000) 适应度为75;而THEDA 
的最优结果可以保持持续增长,直到评价次数达到30000 次。THEDA 在Pknp_2000_Cf 上的
结果均值为109.对应标准差为1.

091, 8311 。
表3-2中每个算法有两行数据,上面的数据是对应问题实例最优结果的均值,下面括
27


演化机器学习(第
2 
版) 


图3-12 
Pknp_1000_Cf 
的实验结果


图3-13 
Pknp_2000_Cf 
的实验结果

号内的数据为方差。对于问题的每个实例,用威尔科克森符号秩检验对4个算法的结果
进行两两比较。如果一个算法的结果显著优于其他3个算法,则结果用粗体标明。对于
N 
=256,
K 
=1,2,4,5的实例,没有算法显著优于其他3个算法。对于
N 
=512,
K 
=0,1 
的实例,GA 得到了最好的结果。在
N 
=4096 的所有实例上,THEDA 均显
著优于ccGA 、PBIL 和QEA 。
1024,2048,


28 


第
3 
章基于共轭先验分布的单模分布估计算法


29
!!"#!$%"&'()*+',-*"#$%&'
()
!
./#!01234
!!"#$
%&'
()$*+"#"()$,--""()-+#..,()-+/#-/()-"-.#/()-+*"./()-++(//()-(.,,#()$,/,+,
!()((($.,"!()((.((#"!()((#$-$"!()((-,+("!()((/(/""!()((,+-+"!()((/(.*"!()((/*,#"!()((-+-*"
0123
()$*"+-(()$,-.*"()-+,$(+()-"*#,.()-.#(#(()-"#+**()-"#-,+()-"(/"*()-+#"+*
!()(((*-."!()((.+-#"!()(($."#"!()(($$*-"!()((-$#""!()(+(($+"!()(+($$#"!()((/.-."!()((-$+("
45'
()$.-#-(()$/+.,#()$,."/*()$,+-((()-(+(*+()$,+$-*()$,".(#()$,"-(*()$/-,+,
!()((+*"."!()((#*$-"!()((-//("!()((/(,""!()((-$$$"!()((,---"!()((/$#-"!()((/#,#"!()((/*$-"
6758'
.)20#0!/()$,-*-,()-+,-*..)3#324!()-.-,.-()-"/-.".)3!##/5.)3#11.5.)3#/343
!.)....00"!()((.$/#"!()(($.$,"!.)..25#!"!()((/#,/"!()((,#+-"!.)..41.."!.)..5.50"!.)..5145"
!!#+"
%&'
.)210##0.)3.5!2.()-(,#*.()-+./,,()$,,(+(()$/+/+.()$$+#+$()$..,((()$+*$".
!.)...#42"!.)..#/1#"!()((*+-("!()((#,+."!()(($$"/"!()((-+$,"!()((-,#,"!()((,$*,"!()((-"##"
0123
()$#+*,,()-((/.(()-(.+.*()-+"$+.()-++*-$()-+(.,/()-(-#,"()-(+(--()$,$"(+
!()(((-$+"!()(("/$/"!()((*,,$"!()((##/""!()((-(+-"!()(($/-."!()((--*+"!()((#//."!()(($#-+"
45'
()$.*./"()$$""(-()$##/."()$#/,"(()$#$--*()$##("(()$#$**(()$#",./()$#"(/+
!()((.("*"!()((#+++"!()((*-#$"!()((-#+,"!()((-(+$"!()((#$.,"!()((#$,#"!()((#$.,"!()(($++/"
6758'
()$#*(--()-($+-,.)3/#/4/.)3#.!.4.)3/3343.)3/5!/0.)3/0/2#.)3.43!0.)3.!045
!()((("--"!()(("-#+"!.)..0542"!.)..3.00"!.)..3.!0"!.)..1!55"!.)..20#0"!.)..21.2"!.)..2/#5"
!!+("*
%&'
()$*/"."()$*("-*()$.##-*()$+*($*()#/$##$()#$/$.,()##$-/$()#*-.+/()#*+/"+
!()((+"-+"!()((".-#"!()((.--/"!()((*$$("!()((*++$"!()((./+/"!()((.*","!()((.*.$"!()((".$-"
0123
()$#/$-.()$$/#*+()$/$#/"()$,(-+(()$/*#(-()$/($##()$-,(/*()$-.$+-()$$/#/(
!()((++-("!()((",//"!()((*+"("!()((.,$$"!()((*$#("!()((*--."!()((.--""!()((*$.$"!()((..,-"

演化机器学习(第
2 
版) 

30
!"
!"
!
!"#$%&'()
!"#
$%&'(()*$%&)++$+$%&',-).$%&'+*-($%&'$*+'$%&)&*&&$%&)*&('$%&)-)$&$%&)-$'.
!$%$$'*$'"!$%$$(')&"!$%$$+,*'"!$%$$($()"!$%$$(-$."!$%$$(())"!$%$$,++."!$%$$(,$*"!$%$$(-&,"
/0"1#
!%''&"'!!%'('*)*!%'*'"&"!%(!")%*!%'*&'*%!%'*$!)'!%')**"%!%')$'$)!%'(%%("
!!%!!!*(&"!!%!!#")!"!!%!!$$"%"!!%!!&"!$"!!%!!%!*%"!!%!!&("""!!%!!%"&""!!%!!&$"%"!!%!!&#!#"
!2'$(.
34#
$%+.*$,)$%+.)+,$$%+&-*$($%++,***$%+(+$'*$%+,++',$%+'*&'.$%+'-,-'$%+'&,)'
!$%$$)()*"!$%$$'$.."!$%$$,.+)"!$%$$'+$$"!$%$$''(("!$%$$'-)*"!$%$$'-**"!$%$$)--$"!$%$$)*)&"
5678
$%&,(-,*$%&(*.$+$%&+-,*&$%&+&.$'$%&+&,'($%&(.-'+$%&('*,-$%&,-.)&$%&,'(,(
!$%$$)+*."!$%$$'((-"!$%$$,('*"!$%$$,*(,"!$%$$,-,)"!$%$$(,$("!$%$$,-('"!$%$$,*,&"!$%$$,&&-"
!"#
$%+*)-&,$%+*''$($%+*'.+-$%+*),&$$%+*)-++$%+.*,+'$%+..,*$$%+.-+))$%+.&*$-
!$%$$,)$&"!$%$$,()'"!$%$$,)*("!$%$$,.$."!$%$$'*.)"!$%$$,).."!$%$$'.$+"!$%$$,'')"!$%$$'*-$"
/0"1#
!%'%&&*&!%''#)*!!%'(!)%'!%''*(##!%''((((!%''!*$(!%'&#!"#!%'%&"!*!%'$(%"$
!!%!!"$"%"!!%!!#&&#"!!%!!#)**"!!%!!$###"!!%!!%#%("!!%!!$'()"!!%!!%&#("!!%!!%"'*"!!%!!%"&""
!2($*&
34#
$%+(+**&$%+('&,($%+,).+$$%+'&$-+$%+',..-$%+'))&,$%+)..-$$%+).,'-$%+)-.-&
!$%$$)'.*"!$%$$',-+"!$%$$)&$'"!$%$$)('("!$%$$)+)&"!$%$$)$,'"!$%$$),*&"!$%$$))(,"!$%$$),')"
5678
$%&$+$,-$%&)*..*$%&'$$,*$%&)*,).$%&)-.('$%&)',(,$%&$&',+$%&$)'&+$%+*+)(*
!$%$$),-'"!$%$$)+.*"!$%$$''-."!$%$$'&-*"!$%$$,$('"!$%$$'-',"!$%$$'.+,"!$%$$,',."!$%$$'&-,"
!"#
$%+&(&$'$%+&-'&*$%+&,+*+$%+&,*).$%+&+-.,$%+&+().$%+&,-'($%+&'*(&$%+&'&&.
!$%$$'(.("!$%$$',)'"!$%$$',,'"!$%$$',&("!$%$$',(("!$%$$'(&&"!$%$$',)+"!$%$$'),,"!$%$$'()."
/0"1#
!%'"(!'*!%'$#%'%!%'$"("&!%'$""%'!%'#('!(!%'#"$"$!%'"#&'(!%'!%%)'!%&*(**!
!!%!!"&")"!!%!!#""!"!!%!!#&*%"!!%!!#$)#"!!%!!#%%("!!%!!#&#*"!!%!!#*!("!!%!!$'#!"!!%!!#*"("

第
3 
章基于共轭先验分布的单模分布估计算法


综合上述实验可以得到几个结论。首先,在0-1背包问题上的实验说明总体上
THEDA 和PBIL 性能优于cGA 和QEA 。THEDA 和PBIL 之间存在一个超越点,在大
约6000 次评价之前PBIL 所得到的结果较好,随后THEDA 的结果超过了PBIL,在不同
的实例上都有类似的现象。其次,Pknp__Cf 上的实验表明THEDA 可以很好地平衡全局
搜索和局部搜索。最后,THEDA 在所有实(2000) 验中使用了相同的参数,并且随着问题规模的
增大,其相对其他算法的优势也越来越显著。

3.本章小结
5

........................ 

本章主要介绍了两层分布估计算法。利用共轭先验分布构造两层分布估计算法框
架,方便地引入了控制模型演化的方法。在0-1背包问题和NK-Landscapes问题上的实
验表明,两层分布估计算法的性能优于其他单变量分布估计算法。并且其性能优势随着
问题规模的增大而增加。


31