文档介绍：关于分布估计算法
第1页，讲稿共32张，创作于星期日
综述
最近几年，在进化计算领域兴起的一类新型的优化算法，即分布估计算法（Estimation of Distribution Algorithm）简称EDA，提出了一种X=5)=
P2''(X=6)= P2''(X=7)=
P2''(X=8)= P2''(X=9)=
P2''(X=10)=
第14页，讲稿共32张，创作于星期日
示例
更新概率模型
P1=θ*P1''+(1-θ)P1
P2=θ*P2''+(1-θ)P2
其中θ是遗忘因子，
第15页，讲稿共32张，创作于星期日
示例
学****之前
学****之后
第16页，讲稿共32张，创作于星期日
示例
说明
可以看出，经过学****之后，优秀个体对应的坐标的概率会变高，平滑处理可以保证:若一个个体位置若和优秀个体距离较近，那么该位置会受惠于该优秀个体，概率也会比较高（基于这样一个假设--若个体相差不大，则其适应度应该也相差不大）。
第17页，讲稿共32张，创作于星期日
示例
重复以上步骤
从示例中可以看出，所谓的分布估计算法就是一个不断地更新概率模型，使概率模型越来越能反映优秀个体的分布的过程。
第18页，讲稿共32张，创作于星期日
基于不同概率模型的EDA
变量无关的EDA
如示例所示，X1和X2的概率是无关的，也可以认为为在概率模型中X1和X2两个变量相互独立。在这种情况下，联合概率密度是边缘概率密度的积，采样的时候可以对于每个变量分别进行采样，概率模型可以认为是：
第19页，讲稿共32张，创作于星期日
基于不同概率模型的EDA
双变量相关的EDA
在实际问题中，变量之间并不总是相互独立的，最先考虑的是最多两个变量相关的情况。
这种情况下，其概率模型为
代表算法 MIMC
采样方法如下
1)J=n，根据第ij个变量的概率分布P(xij)，
随机采样产生第ij个变量
2)根据第ij个变量的条件概率分布
p(xij-1|xij)随机采样产生第ij-1个变量；
3)J=J-1，如果J=1，则一个完整的解向
量构造完成；否则转2)．
第20页，讲稿共32张，创作于星期日
基于不同概率模型的EDA
多变量相关EDA
变量之间的关系更加复杂，需要更加复杂的概率模型来描述。
代表算法EIGA，BOA
连续域的EDA
在示例中，我们解决了一个离散的问题，如果X1和X2的取值域是连续的，我们就需要一个连续的概率模型来描述解空间的分布。如正态分布、柯西分布
代表算法 CMAES
第21页，讲稿共32张，创作于星期日
EDA的关键问题
概率模型
选择合适的概率模型，是发挥分布估计算法性能的关键所在，对于连续域的比较复杂问题来说，如果采用单峰的概率模型，会取得比较好的收敛速度，但是非常容易收敛到局部最优。如果采用多峰的概率模型（如混合高斯模型），对与比较复杂的优化问题可能有更强的描述能力，但是这种模型的更新会相对困难。
第22页，讲稿共32张，创作于星期日
EDA的关键问题
学****方法
如何根据每一代取得的优秀个体来更新概率模型,随着待解决问题的复杂化和概率图模型的复杂化，分布估计算法中概率模型的学****占用了大部分的时间和空间开销，这必然将成为分布估计算法发展的瓶颈．
采样方法
如何根据一个概率模型来采样得到符合该概率模型的样本，如Gibbs抽样。
第23页，讲稿共32张，创作于星期日
EDA的并行化
1：将整个取值区域分成若干子区域，每个子区域并行。
2：个体产生的采样--由于每个个体都是根据概率模型随机产生的，因此每个个体可以看做独立的，所以个体可以并行产生。
第24页，讲稿共32张，创作于星期日
EDA的优缺点
优点：为人们解决复杂的优化问题提供了工具。分布估计算法能更加有效的解决高维问题，降低时间复杂性。
缺点：同遗传算法一样，理论研究比较困难，很难从理论上解决它适合解决什么问题，概率模型的学****会占用很多时间和空间。
第25页，讲稿共32张，创作于星期日
示例2
求下列函数的所有极值点
y=
---------试着使用变量无关的EDA解决这个问题
第26页，讲稿共32张，创作于星期日
示例2
概率模型确定
对于每一维度对应于一正态分布，那么
~
第27页，讲稿共32张，创作于星期日
示例2