简单的分布估计算法

简单的分布估计算法解决连续函数的最优化问题1问题描述及求解过程1.1问题描述511mincos[(1)]nijijjxj其中-10≤xi≤10,i=1,2,…,n.当n=1、2、3和4时分别有3、18、81和324个不同的全局最优解。1.2问题分析该问题是一个多峰的连续函数，函数的形式为)(xif因此，每一维之间没有相互关系，又因为变量无关的概率模型的学习及采样的过程会比较简单，所以我们采用概率无关的的分布估计算法，函数是连续的，所以我们采用连续域的变量无关的分布估计算法来解决这个问题，求多极值考虑到了两种思路，一种是建立多峰的概率模型，另外一种是建立单峰的概率模型，使之迅速收敛到一个极值，然后再重新初始化模型。由于单峰模型比较简单，所以采用单峰模型。1.3求解算法策略分布估计算法遗传算法和统计学习相结合，该算法通过统计学习的方法来更新一个概率模型，并且用这个概率模型来估计解空间有优秀个体的分布情况。通过不断地学习，使得这个概率模型越来越能反映解空间中的优秀个体的分布情况。分布估计算法的步骤大致可以分为以下两步：1：构建描述解空间的概率模型．通过对种群的评估，得到优秀的个体集合，然后采用统计学习等手段构造一个描述当前解集的概率模型．2：由概率模型随机采样产生新的种群。要设计一个分布估计算法，首先要考虑到以下三个关键问题（1）：概率模型的选择--对于一个多峰的函数，当然多峰的概率模型有更强的描述能力，但是，多峰的概率模型学习起来比较困难，因此，我们采用一个单峰的概率模型，并使用这个概率模型描述一个局部极值点，当求得一个极值点的时候，重新初始化概率模型，寻找其他的极值点。单峰的概率模型设计方法认为每一维都服从一个正态分布即),(~iiiCUNx（2）：采样以及择优方法--单峰的概率模型很容易陷入到局部最优，因此我们需要不断地重新开始以找到更多的局部最优，在这种情况下，单峰的概率模型收敛越快越好，在这里采用的方法是不断地根据该类模型进行采样，知道采到lambda个个体的适应度要好于当前最好的适应度为止，若连续采样很多次仍没有改进，则需要检测该点是不是极值点，检测的方法是将每一维的d设置成一个较小的值，采样多次，若仍没有改进，则认为该点是极值点。每一维的采样的方法iiiUCNx*)1,0(其中N（0,1）是一个服从均值为0，方差为0.5的正态分布。（3）：概率模型更新方法---根据每次得到的有改进的lambda个个体，取其中适应度最高的一个个体，假设其坐标为Xl=)...........2,1(xnxx，并假设在此之前的到的最好的个体的坐标为XC=)''.......2,'1(xnxx令D=XC-X1=)'..,.........'22,'11(xnxnxxxx对D中的每个元素取绝对值C=|)'|...............|'22||,'11(|xnxnxxxx则Xl和C分别为新一代的均值和概率模型，即更新后的概率模型为),(~|'|CiUiNxixixidixiUi4：求全局最优值------设置一个极值点队列，该队列按照极值点对应的y值，从小到大排列，若找到一个极值点，则判断该点是否好于队列中最差的极值点，如果是，则插入该队列，当迭代次数达到一个阈值的时候，队列中是到现在为止取得的最好的点，可以近似地认为队列中最好的点，就是全局最优解，迭代次数越高，得到全局最优的概率就越大。1.4流程图2示例分析求单个极值点示例对于问题函数一维的情况，得到图像如下：假设初试化的U为-5.00则初始化的分布为)5.0,00.5(~1NX如图所设假设经过多次采样之后，得到了三个比-5.0有所改进的点，者三个点的横坐标及函数值分别为-5.40（-3.487），-4.90（-2.686）-5.10（1.81）根据上述方法，我们选择-5.40更新该类模型，从而得到U=-5.40，d=0.40更新之后的概率模型为)40.0,40.5(~1Nx，概率模型对应的图如下，在经过多次采样，得到3个比-5.40有改进的点，分别是，-5.45（-3.74），-5.49（-3.69），-5,42（-3.62），从而根据-5.45来更新概率模型，得到)05.0,45.5(~1Nx如下图所示通过两次学习过程可以看出，在理想状况下，该算法可以使概率模型更好地模拟优秀个体的分布情况，实验证明，这种分布估计算法也可以收敛到局部机制，但是仍然存在着很多问题，例如很有可能存在如下情况，对于同一个函数，同一个维度，同一种初始情况，由于正态分布是无界的，所以进场会出现这样一种亲光，即采样到其他极值点附近的区域，例如上述示例在第二次学习过程中，猜到了一个-7.50，这个点的适应度很好，而且是完全有可能采到的，这个时候概率模型的更新就会成为这样一种情况)1.2,50.7(~1Nx如下图：由此看来，这次的学习会对收敛产生反作用，虽然中心的值更优了，但是d却变得很大，对收敛到某个极值的过程产生了干扰。避免这种方法可以采用有界的概率模型，例如只能在中心的左右某个区间内取值，但是这样就会影响到收敛的速度，因为这样的话每次中心移动的位置有上界，对于这个函数来说，这样的问题不但，但是我们优势后很难确定函数的形状，如果函数的导数很小，或者某个极值的附近的坡度非常缓，就会对收敛产生很大的影响。所以说概率模型的选择是一个很复杂的问题，需要具体问题具体分析。3实验结果分别对1维，2维3维,4维进行实验，更新一次CU为迭代一次，迭代次数上限为维度乘1*104,得到的最好的极值点如下：注意（有可能出现）1维找到3个x-1.42512843Y=-12.87088550x-7.70831374Y=-12.87088550x4.85805688Y=-12.870885502维找到18个(有部分点的Y值有偏差，因为极值判断不可能保证非常精确，可能离极值点很近被认为是极值点)iter=12828x-0.80032110-7.70831373Y=-186.73090883x-7.70831374-7.08350641Y=-186.73090883x-0.800321104.85805688Y=-186.73090883x5.482864214.85805688Y=-186.73090883x4.858056885.48286421Y=-186.73090883x-1.42512843-7.08350641Y=-186.73090883x4.85805688-0.80032111Y=-186.73090883x5.48286421-1.42512843Y=-186.73090883x-7.08350640-7.70831374Y=-186.73090883x-1.425128435.48286419Y=-186.73090883x-7.708313745.48286417Y=-186.73090883x-0.80032106-1.42512843Y=-186.73090883x-7.08350646-1.42512843Y=-186.73090883x5.48286421-7.70831391Y=-186.73090883x-1.42513061-0.80032109Y=-186.73090882x-7.70831374-0.80032358Y=-186.73090882x-7.083500364.85805621Y=-186.73090875x4.85805986-7.08349935Y=-186.73090870三维找到52个x-0.80032110-7.708313745.48286421Y=-2709.09350557x-7.08350641-7.08350641-1.42512843Y=-2709.09350557x5.48286421-0.80032110-1.42512843Y=-2709.09350557x5.48286421-0.800321104.85805688Y=-2709.09350557x5.48286421-7.08350640-7.70831374Y=-2709.09350557x-1.42512843-7.08350640-7.08350641Y=-2709.09350557x-7.083506414.85805688-0.80032110Y=-2709.09350557x-7.08350642-7.08350640-7.70831373Y=-2709.09350557x-7.70831372-7.08350641-0.80032110Y=-2709.09350557x-7.083506435.48286421-1.42512844Y=-2709.09350557x5.48286418-1.42512843-0.80032110Y=-2709.09350557x-1.425128405.48286421-0.80032111Y=-2709.09350557x4.858056885.48286424-7.08350641Y=-2709.09350557x-0.800321105.48286417-1.42512843Y=-2709.09350557x5.482864235.48286424-7.70831374Y=-2709.09350557x-7.08350634-7.083506394.85805688Y=-2709.09350557x5.482864285.482864214.85805688Y=-2709.09350557x-0.80032110-1.425128435.48286412Y=-2709.09350557x5.48286420-7.70831375-0.80032119Y=-2709.09350557x-0.80032120-7.70831374-7.08350642Y=-2709.09350557x-7.70831374-7.083506415.48286409Y=-2709.09350557x-7.083506164.858056885.48286421Y=-2709.09350557x-7.08350644-1.42512815-0.80032109Y=-2709.09350557x-0.80032109-7.083506414.85805720Y=-2709.09350557x4.85805688-0.80032057-0.80032110Y=-2709.09350556x-0.80032110-0.80032110-1.42512895Y=-2709.09350556x-0.800321195.48286360-7.70831374Y=-2709.09350556x-7.08350552-0.80032127-7.70831373Y=-2709.09350555x-7.08350736-0.800321104.85805688Y=-2709.09350554x5.48286523-0.80032110-7.70831374Y=-2709.09350554x-7.70831513-7.08350640-7.08350641Y=-2709.09350551x-1.42512882-0.80032394-0.80031883Y=-2709.09350514x5.48286421-7.08351032-1.42512843Y=-2709.09350508x5.48286413-1.42512453-7.08350661Y=-2709.09350506x-7.08351056-7.70831373-7.08350641Y=-2709.09350502x-1.425128435.482864215.48286856Y=-2709.09350497x-0.80032130-7.70831819-0.80032110Y=-2709.09350490x5.48286741-7.083506294.85805232Y=-27