分布估计算法及其应用研究

• 作 者: 钟润添
• 机 构: 中国科学技术大学
• 出 处: 中国科学技术大学
• 发表日期: 2006年期
• 关键词: 分布估计算法 高斯混合模型 多目标优化 Pareto前沿

在当代科学技术的各个领域都存在各种各样的优化问题，形成的数学模型也各不相同。近年来，进化计算在解决复杂优化问题方面取得了很大的成就。但是在如何根据具体的问题设计有效的进化算法以提高计算速度及解决约束优化问题等方面还有许多工作需要去做。遗传算法中的积木块假设使遗传算法具备了搜索到全局最优解的能力，但遗传操作算子在解决一些问题时却会破坏积木块，使它们无法有效重组，因此无法生成全局最优解。研究如何保护在搜索过程中获得的优良模式(即积木块)不受遗传算子的破坏，并对它们有效重组，成为近年来进化与遗传算法研究领域关注的一个重要课题。这导致了一类新的进化算法的出现，即分布估计算法。本文对分布估计算法进行了研究，论文的主要工作和创新之处有：
(1)提出了两种新的用于连续函数优化的分布估计算法，它们都是利用高斯混合模型(GMM)对解空间中的优良解所在区域进行建模，分别采用“Boosting”技术和贪心的EM算法对GMM进行学习，实现了模型结构和模型参数的自动学习，消除了此前EDAs对模型结构先验知识的依赖。
(2)提出了一种基于高斯概率分布估计和一种基于边缘分布估计的多目标优化算法，它们分别在每一进化代中通过估计较优个体的高斯概率分布和边缘概率分布来引导各自对Pareto最优解的搜索。通过与Pareto排序、基于拥挤机制的多样性保持等技术的有机结合，使得这两种算法在具有良好收敛性能的同时，具有很好的维持群体多样性的能力。由于算法采用了概率模型比较简单，在进化的过程中估计概率分布时不用学习变量间复杂的结构信息，因此它们的计算复杂度较低、速度比较快。
(3)提出了一种解决多目标背包问题的多目标优化算法，该算法通过估计多个概率模型的边缘分布来保持群体的多样性，对于解决这种多目标的组合优化问题具有很强的寻优能力，得到的结果可以非常逼近Pareto前沿，而且分布范围比较广。