求解RCPSP问题的带分布估计的差异演化算法

提出一种带分布估计的差异演化算法（DEED）用于求解资源受限项目调度问题（RCPSP）。该算法基于差异演化（DE）算法,利用分布估计算法（EDA）能够获得问题解空间的全局信息以及变量间的相互联系,以指导算法搜索过程,并对最优解的分布进行预测。DEED算法充分利用DE收敛速度快和EDA全局搜索优点。经标准问题库（PSPLIB）的单模式问题集验证,并与当前流行的算法进行比较,表明了DEED算法的有效性。     

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

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

分布估计算法研究进展

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

基于分布估计算法的二阶段置换流水车间调度算法*

针对以完工时间最小化为目标的置换流水车间调度问题（PFSP）,提出了一种基于分布估计算法的二阶段置换流水车间调度算法。首先,在算法的第一阶段采用分布估计算法对PFSP进行优化得到一个局部最优解;为了进一步提高解的优化质量,在第二阶段提出了一种新的混合邻域搜索机制对第一阶段获得的局优解进行邻域搜索;最后,对Rec类和Tai类基准测试问题进行了测试,实验结果证实了算法的有效性。     

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

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

基于分布估计的离散差分骨干粒子群优化

粒子群优化（PSO）和差分演化（DE）是两种新兴的优化技术,已经成功地应用于连续优化问题,但是它们至今尚不能像解决连续优化问题那样有效地处理组合优化问题。最近,有人提出差分骨干PSO（DBPSO）用于解决连续优化问题。首先提出离散DBPSO用于组合优化问题,然后在离散DBPSO中引入分布估计算法（EDA）来提高性能,把EDA抽样得到的全局统计信息和DBPSO获得的局部演化信息相结合来产生新解,形成基于EDA的离散DBPSO。实验结果表明EDA能大大提高离散DBPSO的性能。     

分布估计算法综述

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

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

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

基于分布估计算法的弹性飞翼飞行器多操纵面控制分配

针对弹性飞翼飞行器多操纵面控制分配问题,提出了衡量弹性震动的机振力指标,建立了完整的控制分配模型,提出了采用分布估计算法（EDA）对模型进行求解。首先进行舵面结构设计,分析各气动舵面的工作方式及控制能力,并依据气动数据中升降副翼、余度舵、副翼的舵面控制效率,进行舵面功能配置。在进行控制分配时,分析控制分配的主要性能指标,确立总体多目标优化评价函数,并结合等式和不等式约束条件。采用性能优越的EDA进行求解。通过建立概率模型来估计真实分布,在EDA的进化过程中,各个舵面会根据偏转效率进行分配,结合优化函数最终收敛到最优解。最后分析机翼气动弹性对系统静态操纵效能的影响。从不考虑气动弹性系统响应曲线和考虑气动弹性之后的系统响应曲线比较结果可以看出,有弹性情况下系统响应曲线超调量和过渡时间都减小,飞翼式飞行器飞行品质得到显著提高,优化之后系统效能提高了10%。仿真结果表明,EDA能够较好地解决控制分配问题,并能提高系统动态品质,验证了多操纵面控制分配模型和算法的有效性。     

动态环境下基于近似动态规划的分布估计算法研究

论文重点讨论了分布估计算法的理论研究。首先,抽取出分布估计算法的核心思想,然后旨在使用EDA算法解决复杂优化问题,提出基于近似动态规划的分布估计算法。通过Agent与环境的交互,将近似动态规划引入到进化计算中,获得概率模型并进行适应性的更新。测试函数使用六个经典的对比实验,结果表明本算法的鲁棒性,运行时间短并具有较强的全局搜索能力,可以作为解决函数优化问题的有效解决算法。     

DE/EDA: A new evolutionary algorithm for global optimization

Differential evolution (DE) was very successful in solving the global continuous optimization problem. It mainly uses the distance and direction information from the current population to guide its further search. Estimation of distribution algorithm (EDA) samples new solutions from a probability model which characterizes the distribution of promising solutions. This paper proposes a combination of DE and EDA (DE/EDA) for the global continuous optimization problem. DE/EDA combines global information extracted by EDA with differential information obtained by DE to create promising solutions. DE/EDA has been compared with the best version of the DE algorithm and an EDA on several commonly utilized test problems. Experimental results demonstrate that DE/EDA outperforms the DE algorithm and the EDA. The effect of the parameters of DE/EDA to its performance is investigated experimentally.     

The estimation of distributions and the minimum relative entropy principle

Estimation of Distribution Algorithms (EDA) have been proposed as an extension of genetic algorithms. In this paper we explain the relationship of EDA to algorithms developed in statistics, artificial intelligence, and statistical physics. The major design issues are discussed within a general interdisciplinary framework. It is shown that maximum entropy approximations play a crucial role. All proposed algorithms try to minimize the Kullback-Leibler divergence KLD between the unknown distribution p(x) and a class q(x) of approximations. However, the Kullback-Leibler divergence is not symmetric. Approximations which suppose that the function to be optimized is additively decomposed (ADF) minimize KLD(q||p), the methods which learn the approximate model from data minimize KLD(p||q). This minimization is identical to maximizing the log-likelihood. In the paper three classes of algorithms are discussed. FDA uses the ADF to compute an approximate factorization of the unknown distribution. The factors are marginal distributions, whose values are computed from samples. The second class is represented by the Bethe-Kikuchi approach which has recently been rediscovered in statistical physics. Here the values of the marginals are computed from a difficult constrained minimization problem. The third class learns the factorization from the data. We analyze our learning algorithm LFDA in detail. It is shown that learning is faced with two problems: first, to detect the important dependencies between the variables, and second, to create an acyclic Bayesian network of bounded clique size.     

Continuous probabilistic model building genetic network programming using reinforcement learning

Recently, a novel probabilistic model-building evolutionary algorithm (so called estimation of distribution algorithm, or EDA), named probabilistic model building genetic network programming (PMBGNP), has been proposed. PMBGNP uses graph structures for its individual representation, which shows higher expression ability than the classical EDAs. Hence, it extends EDAs to solve a range of problems, such as data mining and agent control. This paper is dedicated to propose a continuous version of PMBGNP for continuous optimization in agent control problems. Different from the other continuous EDAs, the proposed algorithm evolves the continuous variables by reinforcement learning (RL). We compare the performance with several state-of-the-art algorithms on a real mobile robot control problem. The results show that the proposed algorithm outperforms the others with statistically significant differences.     

基于免疫算法和EDA 的混合多目标优化算法

在免疫多目标优化算法的基础上,引入了分布估计算法(EDA)对进化种群进行建模采样的思想,提出了一种求解复杂多目标优化问题的混合优化算法HIAEDA(hybrid immune algorithm with EDA for multi-objectiveoptimization).HIAEDA 的进化过程混合了两种后代产生策略:一种是基于交叉变异的克隆选择算子,用于在父代种群周围进行局部搜索的同时开辟新的搜索区域;另一种是基于EDA 的模型采样算子,用于学习多目标优化问题决策变量之间的相关性,提高算法求解复杂多目标优化问题的能力.在分析两种算子搜索行为的基础上,讨论了两者在功能上的互补性,并利用有限马尔可夫链的性质证明了HIAEDA 算法的收敛性.对测试函数和实际工程问题的仿真实验结果表明,HIAEDA 与NSGAII 算法和基于EDA 的进化多目标优化算法RM-MEDA 相比,在收敛性和多样性方面均表现出明显优势,尤其是对于决策变量之间存在非线性关联的复杂多目标优化问题,优势更为突出.     

FaSa: A fast and stable quadratic placement algorithm

Placement is a critical step in VLSI design because it dominates overall speed and quality of design flow.In this paper,a new fast and stable placement algorithm called FaSa is proposed.It uses quadratic programming model and Lagrange multiplier method to solve placement problems.And an incremental LU factorization method is used to solve equations for speeding up.The experimental results show that FaSa is very stable,much faster than previous algorithms and its total wire length is comparable with other algorithms.     

基于转移概率的分布估算算法在p-median问题上的应用

分布估算算法(EDA)是近几年出现的一种启发式进化算法,在组合优化问题中得到了广泛、有效的应用.概率模型直接决定着该算法的性能,如何构建一个高性能的概率模型成为分布估算算法的研究核心.把转移概率模型引入分布估算算法,并对p-median问题进行求解,结果表明,基于转移概率模型的分布估算算法能够有效地求解p-median问题,并极大地提高了算法的效率与精确性.     

改进DE/EDA算法在求解难约束优化问题中的应用研究*

针对约束优化问题13个Benchmark函数中最难求解的Bump函数,利用简单罚函数算子对DE/EDA算法进行改进,提出了改进DE/EDA算法。仿真实验结果表明,求解Bump函数最优解时,改进DE/EDA算法优于其他文献的算法,且比DE算法收敛速度更快,求解效果更好。     

A hybrid multi-objective PSO–EDA algorithm for reservoir flood control operation

Reservoir flood control operation (RFCO) is a complex multi-objective optimization problem (MOP) with interdependent decision variables. Traditionally, RFCO is modeled as a single optimization problem by using a certain scalar method. Few works have been done for solving multi-objective RFCO (MO-RFCO) problems. In this paper, a hybrid multi-objective optimization approach named MO-PSO–EDA which combines the particle swarm optimization (PSO) algorithm and the estimation of distribution algorithm (EDA) is developed for solving the MO-RFCO problem. MO-PSO–EDA divides the particle population into several sub-populations and builds probability models for each of them. Based on the probability model, each sub-population reproduces new offspring by using PSO based and EDA methods. In the PSO based method, a novel global best position selection method is designed. With the help of the EDA based reproduction, the algorithm can lean linkage between decision variables and hence have a good capability of solving complex multi-objective optimization problems, such as the MO-RFCO problem. Experimental studies on six benchmark problems and two typical multi-objective flood control operation problems of Ankang reservoir have indicated that the proposed MO-PSO–EDA performs as well as or superior to the other three competitive multi-objective optimization algorithms. MO-PSO–EDA is suitable for solving MO-RFCO problems.     

基于协同回归模型的矩阵分解推荐

推荐系统是解决信息过载的有效途径。传统的推荐系统难以从海量数据中推选出 符合用户个性化偏好的项目,推荐质量不高。为此,通过优化传统的协同过滤推荐算法,针对 数据稀疏性等问题,提出协同回归模型的矩阵分解算法(CLMF)。通过机器学习算法发掘内容信 息的深层次特征,提升了原始数据的信息量;并构建辅助特征矩阵,通过融合特征矩阵,CLMF 最大化了特征标签的作用,并结合数据标签,语义信息和评分矩阵得到推荐算法框架。在真实 数据集上实验结果显示,新型推荐算法可有效解决特征值缺失问题,改善了数据稀疏性,提升 了算法扩展性,并显著增强覆盖性。     

A double-distribution statistical algorithm for composite laminate optimization

The paper proposes a new evolutionary algorithm termed Double-Distribution Optimization Algorithm (DDOA). DDOA belongs to the family of estimation of distribution algorithms (EDA) that build a statistical model of promising regions of the design space based on sets of good points and use it to guide the search. The efficiency of these algorithms is heavily dependent on the model accuracy. In this work, a generic framework for enhancing the model accuracy by incorporating statistical variable dependencies is presented. The proposed algorithm uses two distributions simultaneously: the marginal distributions of the design variables, complemented by the distribution of physically meaningful auxiliary variables. The combination of the two generates more accurate distributions of promising regions at a low computational cost. The paper demonstrates the efficiency of DDOA for three laminate optimization problems where the design variables are the fiber angles, and the auxiliary variables are integral quantities called lamination parameters. The results show that the reliability of DDOA in finding the optima is greater than that of simple EDA and a standard genetic algorithm, and that its advantage increases with the problem dimension.