分布估计算法.ppt

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