运用改进直方图模型的分布估计算法求解连续空间优化问题

摘要

近些年来，越来越多的学者和研究人员关注智能优化领域，智能优化算法因而得到广泛地研究，并且应用到多个领域，例如生物信息学、数据挖掘、模式识别、城市规划和软件工程管理优化，等等。在智能优化算法中，很多算法都是大家熟悉或者有所听闻的，其中包括遗传算法(Genetic Algorithm，GA)、粒子群算法(Particle Swarm Optimization，PSO)、蚁群算法(Ant ColonyOptimization，ACO)、量子演化算法(Quantum Evolutionary Algorithm，QEA)，尽管这些算法在解决传统的离散问题或者传统的连续问题都有较好的效果，但是对于一些更复杂的问题，这些算法很难使用传统方式进行解决。现实生活中的很多问题都可以抽象为连续优化问题，如果算法能够很好的解决这些连续优化问题，那么现实生活中的很多问题就游刃而解了。
　　 分布估计算法是智能优化领域的一个新兴的随机优化算法，也是当前智能优化领域的研究热点。分布估计算法是将概率统计理论和遗传算法思路相结合，形成的一种全新的智能进化模式。分布估计算法通过概率统计的手段建立解空间内种群个体分布的概率模型，然后对概率模型随机采样产生新的群体，接着更新概率模型，如此反复进行。分布估计算法摒弃了传统遗传算法的交叉操作(Crossover Operation)和变异操作(Mutation Operation)，是一种全新的先进的进化模式，它通过概率图模型对变量之间的关系进行建模，从而能够解决多变量相关的优化问题。
　　 然而，传统的分布估计算法用于解决离散问题(例如背包问题、最大团问题)。实际上，现实生活中很多领域都属于连续问题，因此将分布估计算法应用到连续问题是一个很有用的研究。实际上，已经有一些学者和研究人员尝试将分布估计算法改进为能够解决连续问题的算法，但是效果都不是很好，因此分布估计算法也不能应用到实际的连续问题中(例如求解基于TOY模型的蛋白质折叠结构预测问题)。这篇文章则提出了一种新颖的方式改进传统分布估计算法使其能够很好地解决连续问题，在这篇文章里，我们称其为基于直方图的分布估计算法(Population Based Incremental Learning algori thm using Hi stogramprobabilistic model for Continuous optimization，HPBILc)。我们使用了直方图概率模型(Histogram Model)作为变量的概率分布，通过使用基于群体的累计增量技术(Population Based Accumulation Strategy)和区域细分技术(Sub-dividing Strategy)来更新直方图模型，使用均匀分布法(UniformDistribution Strategy)进行个体采样。其中，直方图概率模型可以理解为将待解决问题的某一变量的连续空间细分为多个小区间，每个小区间拥有一个取值概率，取值概率的大小就是该空间的柱状高度。基于群体的累计增量技术主要是能够根据算法抽取出来的优秀候选解的双向反馈信息更新柱状的高度，使得较有可能获取更优解的小区间的柱状高度更高，较少可能获取更优解的小区间的柱状高度更低。区域细分技术则是针对某一特定小区间的柱状高度高于某一临界值，则对该小区间细分为更小的小区间，使得区间不断细化，在不断细化过程中，算法可以得到更为精确的解。在实验部分，我们使用了经典的23个连续函数问题进行测试，并将测试结果和经典的FEP，最近几年文献中的分布估计算法进行了比较，并且用图示分析HPBILc的收敛性。我们也将HPBILc应用到基于TOY模型的蛋白质折叠结构预测问题上，这是该研究领域第一次将分布估计算法应用到基于TOY模型的蛋白质折叠结构预测问题，这为生物信息学提供了一种有效的解决方案。实验证明，本文提出的HPBILc在求解和优化连续问题时，明显优于对比文献中的智能优化算法。

目录

文摘

英文文摘

声明

第1章 引言

1.1研究背景

1.2问题的提出：分布估计算法解决连续问题

1.3研究现状

1.4本文的主要工作与组织结构

第2章 分布估计算法综述

2.1一个简单的分布估计算法例子

2.2分布估计算法的基本框架

2.3分布估计算法的分类

2.4分布估计算法的应用

2.5分布估计算法的最新进展

2.6分布估计算法的尚未解决的领域

第3章 基于直方图的分布估计算法(HPBILc)

3.1分布估计算法解决连续问题

3.2 HPBILc详细介绍

第4章 蛋白质折叠结构预测应用综述

4.1蛋白质折叠结构预测的由来

4.2蛋白质折叠结构预测的方法

4.3蛋白质折叠结构预测的优化模型

第5章 实验结果与分析

5.1 HPBILc和FEP比较

5.2 HPBILc和最近几年文献中的分布估计算法比较

5.3分析HPBILc的收敛性

5.4 HPBILc应用到蛋白质折叠结构预测领域

5.5 HPBILc参数设置的说明

5.6本章小节

第6章 总结与展望

6.1总结

6.2展望

参考文献

硕士期间论文及科研情况

致谢