分布估计算法综述

分布估计算法是进化计算领域新兴起的一类随机优化算法,是当前国际进化计算领域的研究热点. 分布估计算法是遗传算法和统计学习的结合,通过统计学习的手段建立解空间内个体分布的概率模型,然后对概率模型随机采样产生新的群体,如此反复进行,实现群体的进化. 分布估计算法中没有传统的交叉、变异等遗传操作,是一种全新的进化模式;这种优化技术能够通过概率图模型对变量之间的关系进行建模,从而能有效的解决多变量相关的优化问题. 根据概率模型的复杂性,本文按照变量无关、双变量相关、多变量相关等三类分别介绍相应的分布估计算法. 作为一篇综述性文章,本文旨在全面系统的向国内读者介绍这一新技术,并总结分布估计算法的研究现状和未来的研究方向.     

一种基于混合因子分析的分布估计算法

提出了一种基于混合因子分析的分布估计算法．首先用次胜者受罚的竞争学习算法对选出的最优个体集合聚类，然后对每个类用因子分析模型进行分布信息的估计．为了保持种群的多样性，算法保留那些具有较好适应值并且与所选的最优个体集合较远的个体，并利用聚类的参数来减少计算量．试验结果证实了算法的性能．     

分布估计算法研究进展

作为一种新颖的基于概率模型的进化算法,近年来分布估计算法（EDA）得到了广泛的研究和发展.在介绍分布估计算法原理和特点的基础上,重点综述了近些年分布估计算法的研究进展,包括改进概率模型、保持种群多样性以及设计混合算法,进而总结了分布估计算法在理论及应用方面的研究现状,最后提出了有待进一步研究的若干方向和内容.     

一种求解多维背包问题的混合分布估计算法

针对多维背包问题（MKP）,提出一种基于分布估计算法的混合求解算法,该算法基于优势种群构建概率模型,并基于概率模型采样产生新个体;同时,提出一种基于MKP问题信息的修复机制,有效修复采样后种群中的不可行解．另外,设计了一种自适应的局部搜索操作,以增强算法的局部搜索能力,基于标准测试集的仿真结果和算法比较验证了所提出的混合算法的有效性和鲁棒性．     

一种结合贪婪因子求解0-1背包问题的分布估计算法

针对0-1背包问题,在分布估计算法的基础上提出了一种结合传统贪婪方法的新算法。通过计算物品的重量价值比后获得物品的贪婪因子值,并将贪婪因子融入基本的分布估计算法之中,在保证收敛速度的基础上进一步平衡了个体间的竞争,相较对比算法而言取得了更好的优化结果。     

求解多维背包问题的改进分布估计算法

研究分布估计算法可以解决难优化问题,且具有很好的全局搜索能力,但存在局部搜索能力差以及因种群多样性容易丧失从而导致的早熟收敛问题.针对上述问题对分布估计算法进行改进,将优势解集克隆,对优势个体进行搜索,从而增强局部搜索能力,并对概率模型进行修正以改善种群多样性损失问题,通过对多维背包问题的标准问题进行测试比较,结果表明了改进的有效性,改进后的算法增加了局部搜索能力、有效保持了种群多样性,获得好的优化结果.     

一种多目标优化的多概率模型分布估计算法

提出了一种用于多目标优化的多概率模型分布估计算法,该算法在进化的每一代中使用多个概率模型来引导多目标优化问题柏拉图(Pareto)最优域的搜索.分布估计算法使用概率模型引导算法最优解的搜索,而使用多个概率模型可以保持所得多目标优化问题最优解集的多样性.该算法具有很强的寻优能力,所得结果可以很好地覆盖Pareto前沿.实验通过优化一组测试函数来评价该算法的性能,并与其它多目标优化算法进行了比较,结果表明该算法相比于其它同类算法可以更好地解决多目标优化问题.     

分布估计算法求解集装箱装载问题

集装箱装载是一个空间优化分解的布局问题,其约束条件多,属于典型的NP完全问题,求解难度大。在考虑实际应用中的约束条件下,使用三空间分割的布局方法对剩余空间进行分解,并采用空间合并原则将闲置空间与可用空间进行合并达到充分利用,并结合分布估计算法（ EDA）求解多约束装箱问题。分布估计算法采用统计学习的方法建立一个描述解分布的概率模型,再对概率模型进行随机采样产生新的种群,如此反复进行,实现种群的进化,最终获取最优解。实验仿真结果表明该算法应用于实际空间规划设计中具有重要的实际意义。     

求解混合流水车间调度问题的分布估计算法

针对混合流水车间调度问题(Hybrid flow-shop scheduling problem, HFSP)的特点, 设计了基于排列的编码和解码方法, 建立了描述问题解空间的概率模型, 进而提出了一种有效的分布估计算法(Estimation of distribution algorithm, EDA). 该算法基于概率模型通过采样产生新个体, 并基于优势种群更新概率模型的参数. 同时, 通过实验设计方法对算法参数设置进行了分析并确定了有效的参数组合. 最后, 通过基于实例的数值仿真以及与已有算法的比较验证了所提算法的有效性和鲁棒性.     

一种求解社区检测问题的改进分布估计算法

在分析网络模块性函数局部单调性的基础上,设计局部搜索变异算子,提出-种求解社区检测问题的改进分布估计算法.基于基准测试网络和大规模复杂网络对算法进行测试,实验结果表明,对于不同网络,该算法运行100次得到的Q函数平均值均优于Girvan-Newman算法、Newman快速算法和Tasgin遗传算法.     

一种求解RCPSP的协同进化分布估计算法

针对大规模资源受限项目调度问题计算复杂的特点,提出一种合作式协同进化分布估计算法(CCEDA)。将合作式协同进化框架与分布估计算法相结合,将复杂问题分解为子问题,利用改进的分布估计算法对每个子问题进行协同优化求解。为提高分布估计算法的局部搜索能力,给出一种对解进行局部搜索的方法。将CCEDA用于求解标准问题库PSPLIB,并与GAPS、GA-DBH、GA-hybrid与GA-FBI算法进行比较,结果证明CCEDA拥有更好的求解性能。     

解决0-1背包问题的遗传分布估计算法

0-1背包问题是典型的NP难问题,针对0-1背包问题提出分布估计算法（EDA）与遗传算法（GA）相结合的算法（E-GA）。该算法在每一次迭代中由二者共同产生种群,并行搜索,两种方法产生的个体数目动态变化,将EDA的全局搜索与GA的局部搜索能力、EDA的快速收敛性与GA的种群多样性结合,实现优势互补。通过三个背包问题算例进行算法验证,与以往文献相比,结果显示该算法所获最优值优于文献最优值,运行时间短且收敛速度快。     

基于改进分布估计算法的二维航迹规划

为在较短时间内规划出性能指标最优的攻击轨迹、提高飞行器作战效能,研究一种基于改进分布估计算法的二维航迹规划方法。引入坐标变化和候选节点,针对采用分布估计算法进行问题求解容易陷入局部收敛的缺点,提出模拟退火的分布估计算法,其退火温度以信息熵表示。     

基于粒子群优化和遗传算法的协同聚类算法

为充分发挥粒子群优化算法和遗传算法各自的优势,提出一种新的基于粒子群和遗传算法的协同进化算法,并将其应用于聚类分析。通过构建2个相互竞争的种群,采用相对适应度度量方法,在一个纯自举的过程中产生最优竞争个体。在现实世界数据集上的仿真实验表明,该算法在收敛精度方面优于基于遗传算法的聚类方法和基本粒子群优化聚类算法。     

集合划分问题的分布估计求解

集合划分问题对日常生活中的仓库装填问题,生产线排程问题有很大意义,但是无论采用精确算法还是启发式算法都不能很好求解。提出一种改进的分布估计算法,采用实数编码和基于矩阵的概率向量存储方式,并且引入权值的概念,改进了概率向量的更新方式。将它与标准DM（the Differencing Method）算法进行了比较,实验结果证明,它可以有效解决DM算法在25维以下得不到正解的问题。另外,算法还延伸到高维和多分类问题上,这里给出了实验结果。     

Hybrid Estimation of Distribution Algorithm for the Quay Crane Scheduling Problem

The competitiveness of a container terminal is highly conditioned by the time that container vessels spend on it. The proper scheduling of the quay cranes can reduce this time and allows a container terminal to be more attractive to shipping companies. The goal of the Quay Crane Scheduling Problem (QCSP) is to minimize the handling time of the available quay cranes when performing the tasks of loading and unloading containers onto/from a container vessel. This paper proposes a hybrid Estimation of Distribution Algorithm with local search to solve the QCSP. This approach includes a priori knowledge about the problem in the initialization step to reach promising regions of the search space as well as a novel restarting strategy with the aim of avoiding the premature convergence of the search. Furthermore, an approximate evaluation scheme is applied in order to reduce the computational burden. Moreover, its performance is statistically compared with the best optimization method from the literature. Numerical testing results demonstrate the high robustness and efficiency of the developed technique. Additionally, some relevant components of the scheme are individually analyzed to check their effectiveness.     

Hybrid Estimation of Distribution Algorithm for solving Single Row Facility Layout Problem

The layout positioning problem of facilities on a straight line is known as Single Row Facility Layout Problem (SRFLP). The objective of SRFLP, categorized as NP Complete problem, is to arrange the layout so that the sum of distances between all facilities’ pairs can be minimized.     

用于多维数据实视图选择的分布估计算法

在数据仓库中,为选择合适的视图加以实体化,提出一种新的分布估计算法。在解空间随机产生初始群体,根据适应值选择部分好的解集,利用这些优势群体建立概率模型并估计联合概率分布,再从新的概率分布中抽样得到下一代。实验结果表明,该算法能减少查询响应时间和视图维护代价,并且其寻优性能优于经典遗传算法。