下载掌阅APP，畅读海量书库
立即打开
1.算法基本思想
尽管上述几种进化算法在求解各种组合优化和连续优化问题中都取得了一定的成效，但它们仍面临一些挑战。一方面，对于特定问题，进化算法的参数选取对算法性能有重要影响，但缺乏经验的研究者难以选取合适的参数，因为参数选取本身就是一个优化问题。另一方面，种群在搜索空间中的移动难以预测。针对这两个挑战，Mühlenbein和Paaß于1996年提出分布估计算法（Estimation of Distribution Algorithm，EDA）。
类似于演化策略和进化规划，分布估计算法也构建了搜索空间的概率分布模型，但不同的是，分布估计算法没有交叉和变异算子，而是直接通过构建概率分布模型和采样得到新种群。由于分布估计算法中不包含交叉和变异算子，因此算法中的个体不再用基因来描述个体所包含的信息，而通过变量（variable）来表示个体。概率分布的构建是基于之前历次迭代所选择的个体形成的数据库，通过分析数据库中较优的种群所包含的变量，构建符合这些变量分布的概率分布模型，然后基于该概率模型采样得到新的种群。由于概率模型是使用较优的种群来构建的，由该模型采样得到的新种群在整体质量上往往会优于原来的种群，由此，随着算法的迭代，种群的整体质量会不断提高，从而使分布估计算法得以逐渐逼近全局最优解。
2.算法流程
分布估计算法的流程图和伪代码如图1-14所示，具体步骤如下。
图1-14 分布估计算法的流程图和伪代码
1）设置迭代次数 g =0，初始化包含 N 个个体的历史种群 P （ g ）。
2）采用某种选择方法从历史种群 P （ g ）中选择 M 个个体构成 S （ g ）。
3）学习所选个体 S （ g ）的联合概率分布 p g （ x ）。
4）从学习的联合概率分布 p g （ x ）中采样 M 个个体构成新种群 P （ g +1）。
5）将新种群 O （ g ）的个体加入历史种群 P （ g ）中。
6）设置 g 增加1，若达到停止迭代的标准，则停止运行，否则返回步骤2。