分布估计算法

关于分布估计算法第1页，讲稿共32页，2023年5月2日，星期三综述最近几年，在进化计算领域兴起的一类新型的优化算法，即分布估计算法（EstimationofDistributionAlgorithm）简称EDA，提出了一种全新的进化模式，并迅速成为进化计算领域的研究热点和解决工程问题的有效方法．分布估计算法的概念最初在1996年提出，在2000年前后迅速发展，成为当前进化计算领域前沿的研究内容。第2页，讲稿共32页，2023年5月2日，星期三综述基本思想--遗传算法和统计学习相结合基本方法--通过统计学习的手段建立解空间内个体分布的概率模型，然后对概率模型随即采样产生新的群体，如此反复，实现群体的进化第3页，讲稿共32页，2023年5月2日，星期三综述基本概念1个体与种群 ●个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。 ●种群(population)就是模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。第4页，讲稿共32页，2023年5月2日，星期三综述基本概念概率模型--用于描述取值域中优秀个体分布情况的一系列函数或其他数学工具（包括概率密度函数、条件概率、边缘概率等等）第5页，讲稿共32页，2023年5月2日，星期三综述基本概念适应度与适应度函数●适应度(fitness)就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。●适应度函数(fitnessfunction)就是问题中的全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。第6页，讲稿共32页，2023年5月2日，星期三综述主要步骤（虽然有很多具体的实现方法，但是分布估计算法可以归纳为以下两步）1：构建描述解空间的概率模型．通过对种群的评估，选择优秀的个体集合，然后采用统计学习等手段构造一个描述当前解集的概率模型．2：由概率模型随机采样产生新的种群。第7页，讲稿共32页，2023年5月2日，星期三综述分布估计算法的与遗传算法的不同生物进化的数学模型遗传算法是对于个体进行遗传操作（交叉、变异等），"微观"层面模拟生物的进化。分布估计算法是对于整个群体的分布建立一个概率模型，通过这个概率模型来描述进化的方向，是“宏观”层面的模拟。第8页，讲稿共32页，2023年5月2日，星期三综述

第9页，讲稿共32页，2023年5月2日，星期三示例在这里，举一个最简单的离散的优化的问题作为示例。Z=X1+X2，其中X1的取值域为1,2,3,4,5，x2的取值域为6,7,8,9,10第10页，讲稿共32页，2023年5月2日，星期三示例建立模型建立一个概率模型。在这里我们只需要建立一个离散的概率模型（设X1，X2相互独立），初始化如下（只列出边缘概率）。第11页，讲稿共32页，2023年5月2日，星期三示例采样与择优根据概率模型，采样若干个点（6个）。假设采到的点为2,7；3,9；3,10；4,8；2,9；5,6评估这六个点，带入函数（适应度函数），分别得到9,12,13，12,11,11。因此我们选择2,7；2,9和5,6来更新概率模型。第12页，讲稿共32页，2023年5月2日，星期三示例更新概率模型（根据2,7；2,9和5,6三个点）更新X1的分布总共有3个个体，三个个体对应的X1为2,2,5P1'（x1=1）=0;P1'（x1=2）=2/3;P1'（x1=5）=1/3;P1'（x1=3）=0;P1'（x1=4）=0同理得到P2'（x2=6）=1/3;P2'（x1=7）=1/3;P2'（x1=9）=1/3;P2'（x1=8）=0;P2'（x1=10）=0第13页，讲稿共32页，2023年5月2日，星期三示例更新概率模型对分布函数进行平滑处理（防止有一些点的概率为零，自变量的值相差较近则概率应该相差不大）以X1为例P1''（X1=i）=并归一化同理求P2’得到P1''(X=1)=0.139861 P1''(X=2)=0.380183P1''(X=3)=0.16124 P1''(X=4)=0.117459P1''(X=5)=0.201247P2''(X=6)=0.27714 P2''(X=7)=0.27955P2''(X=8)=0.125736 P2''(X=9)=0.108491P2''(X=10)=0.209084第14页，讲稿共32页，2023年5月2日，星期三示例更新概率模型P1=θ*P1''+(1-θ)P1P2=θ*P2''+(1-θ)P2其中θ是遗忘因子，取0.5第15页，讲稿共32页，2023年5月2日，星期三示例学习之前学习之后第16页，讲稿共32页，2023年5月2日，星期三示例说明可以看出，经过学习之后，优秀个体对应的坐标的概率会变高，平滑处理可以保证:若一个个体位置若和优秀个体距离较近，那么该位置会受惠于该优秀个体，概率也会比较高（基于这样一个假设--若个体相差不大，则其适应度应该也相差不大）。第17页，讲稿共32页，2023年5月2日，星期三示例重复以上步骤从示例中可以看出，所谓的分布估计算法就是一个不断地更新概率模型，使概率模型越来越能反映优秀个体的分布的过程。第18页，讲稿共32页，2023年5月2日，星期三基于不同概率模型的EDA变量无关的EDA如示例所示，X1和X2的概率是无关的，也可以认为为在概率模型中X1和X2两个变量相互独立。在这种情况下，联合概率密度是边缘概率密度的积，采样的时候可以对于每个变量分别进行采样，概率模型可以认为是：第19页，讲稿共32页，2023年5月2日，星期三基于不同概率模型的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页，2023年5月2日，星期三基于不同概率模型的EDA多变量相关EDA变量之间的关系更加复杂，需要更加复杂的概率模型来描述。代表算法EIGA，BOA连续域的EDA在示例中，我们解决了一个离散的问题，如果X1和X2的取值域是连续的，我们就需要一个连续的概率模型来描述解空间的分布。如正态分布、柯西分布代表算法CMAES第21页，讲稿共32页，2023年5月2日，星期三EDA的关键问题概率模型选择合适的概率模型，是发挥分布估计算法性能的关键所在，对于连续域的比较复杂问题来说，如果采用单峰的概率模型，会取得比较好的收敛速度，但是非常容易收敛到局部最优。如果采用多峰的概率模型（如混合高斯模型），对与比较复杂的优化问题可能有更强的描述能力，但是这种模型的更新会相对困难。第22页，讲稿共32页，2023年5月2日，星期三EDA的关键问题学习方法如何根据每一代取得的优秀个体来更新概率模型,随着待解决问题的复杂化和概率图模型的复杂化，分布估计算法中概率模型的学习占用了大部分的时间和空间开销，这必然将成为分布估计算法发展的瓶颈．采样方法如何根据一个概率模型来采样得到符合该概率模型的样本，如Gibbs抽样。第23页，讲稿共32页，2023年5月2日，星期三EDA的并行化1：将整个取值区域分成若干子区域，每个子区域并行。2：个体产生的采样--由于每个个体都是根据概率模型随机产生的，因此每个个体可以看做独立的，所以个体可以并行产生。第24页，讲稿共32页，2023年5月2日，星期三EDA的优缺点优点：为人们解决复杂的优化问题提供了工具。分布估计算法能更加有效的解决高维问题，降低时间复杂性。缺点：同遗传算法一样，理论研究比较困难，很难从理论上解决它适合解决什么问题，概率模型的学习会占用很多时间和空间。第25页，讲稿共32页，2023年5月2日，星期三示例2求下列函数的所有极值点y= ---------试着使用变量无关的EDA解决这个问题第26页，讲稿共32页，2023年5月2日，星期三示例2概率模型确定对于每一维度对应于一正态分布，那么

~第27页，讲稿共32页，2023年5月2日，星期三示例2取得优秀个体连续采样，直到采到N个个体的适应度比当前已经取得的最佳适应度要好。如果连续采样次数大于某个阈值，仍没有得到比目前最好的点，则检验是否是极值点。检验的方法为令每一维的方差为一个极小值（设为1e-5），采样多次，若无改进，则认为是极值点，记录该极值点，若不是极值点，则考虑适当将方差变小，继续采样。第28页，讲稿共32页，2023年5月2日，星期三示例2概率模型的更新根据得到的N个优秀个体，求这N个点适应度最好的点，得到A=[xu1,xu2......xun]假设在此之前得到的最好的点为A'=[xb1,xb2....xb5]令C=[d1,d2.....dn]=A-A'xui为第i维的正态分布的均值。di为第i维的正太分布的方差。第29页，讲稿共32页，