分布估计算法教案.ppt

4. 高斯概率模型（续） 以 PBILc 为例介绍高斯概率模型解决连续空间的优化问题的流程。 PBILc 对每个变量 xj 定义一个一元高斯分布 N (μj ,σj2) 然后根据每个 N (μj ,σj2)在整个定义域空间产生一个样本。构建概率模型的过程主要包括μj 和σj 的确立， μj 约束了样本的中心，而σj 则控制着样本的多样性。 随着种群的进化， μj 将逐渐逼近全局的最优解所在的位置，而σj 将越来越小，从而使种群聚拢到全局最优解附近。 31 4. 高斯概率模型（续） 第一步: 随机产生初始种群并计算种群中所有个体的适应度，同时根据公式(8. 7) 初始化概率模型。 其中: V[ i ][ j ] 为种群中个体 i 的变量 xj 的值， N 为种群的规模。 32 4. 高斯概率模型（续） 第二步: 采用线性学习方式更新高斯分布的均值。设在第 t 代时 ， xj 对应的高斯分布的均值为μj t，则有: 其中 α 为学习因子 ， xbestl、 xbest2 和 xjworst 分别表示种群中最优个体、次优个体和最差个体所对应的 xj 值。 33 4. 高斯概率模型（续） 第三步: 采用线性学习方式更新高斯分布的方差。 设在第 t 代时 ， xj 对应的高斯分布的方差为 σjt; ，则有: 其中 xjk 为种群按适应度从大到小排名第(k-1)的个体的 xj值， 为选出的 K 个较优种群的 xjk 的均值，即: 第四步: 根据更新的高斯分布产生新样本。 2 34 0 作业： 用高斯概率模型的分布估计算法求解下面函数的极大值 已知种群规模N=4，K=2，α = 0.5， 初始值为： 求通过一次迭代计算得到的新的高斯概率模型（适应函数值精确到0.01；其它变量计算精确到0.1） 35 二、混合分布估计算法 1. 分布估计算法与遗传算法结合 分布估计算法与遗传算法都是基于种群的进化算法，它们的不同之处在于生成种群的机制不同 。 没有一个算法对解决所有问题都是最优的 。 一种简单有效的混合分布估计算法GA- EDA，新的种群由 GA 和 EDA 共同生成。 具体地说， GA 和 EDA 是在 同 一个种群的基础上按照各自的机制分别产生两个子种群 ，然后再将这两个子种群组合成新的种群，完成一代的进化过程 35 36 2. 分布估计算法与差分进化算法结合 差分进化算法 (Differential Evolution , DE) 也是一种 基于 种群的随机有哪些信誉好的足球投注网站 算法， 它利用当前种群之间的差异信息来引导有哪些信誉好的足球投注网站 。 随着进化代数的增加，个体之间的差异性将越来越小，而简单的差分进化算法缺乏有效的机制利用和产生有哪些信誉好的足球投注网站空间中的全局的信息，因而常常会收敛于局部最优解。 另一方面，分布估计算法利用种群的全局信息建立概率模型，从宏观上控制算法有哪些信誉好的足球投注网站。因而结合差分进化算法和分布估计算法可以有效地利用局部信息和全局信息，形成功能更加强大的混合算法。 37 2. 分布估计算法与差分进化算法结合（续） DE- EDA 中的新种群以 DE 或 EDA 方式生成。 记第 k 代种群的第 j 个个体为 ujk ，则第 k +l 代的种群的产生过程如下。 第一步: 从当前种群中选出 M 个较优的个体，并如下建立概率模型 。 38 第二步: 产生一个 0~ 1 之间的随机值v ， 若 v≤a ，则 新个体按照 DE 的机制产生，否则按照 EDA 的方式从概率模型pk (x) 中取样。其中 a 为控制参数，最终产生的新个体为 u 第三步: 若 u 的适应度大于ukt 的适应度，则 ukt+1 =u ， 否则 ukt+1 = ukt 。 第四步: 若产生了足够数量的新种群则终止 ，否则执行第一步。 39 2. 分布估计算法与差分进化算法结合（续） 40 三、并行分布估计算法 1. 种群级别并行化 种群级别的并行分布估计算法是最直观、最易于在实际中应用的并行分布估计算法 该类算法通常将种群分成多个子种群，每个子种群在不同的机器上运行，然后各个子种群通过迁移等机制进行通信，达到综合信息的目的。 基于岛屿模型的并行分布估计算法 dEDA ， 该算法首先将种群分散于多个岛屿中，然后采用不同概率模型的EDA 对不同岛屿上的子种群进行进化， 每个岛屿上的子种群进化到一定代数后，即通过同步和迁移机制与相邻的孤岛屿上的种群进行相互通信。 该类算法通常采用主从模式，主机向从机分配评估适应度的任务，并最终综合各从机反馈回来的结果，继续执行 EDA 算法进行其他模块的计算。 而分机则专门负责完成主机分发过来的评估任务。 2. 适应度评估并行化 采用多台机器并行计算种群中的适应度是提高进化算法有哪些信誉好的足球投注网站速度最直接有