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

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

分布估计算法研究进展

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

一种求解聚类问题的分布估计算法

提出一种求解聚类问题的分布估计算法。基于PBIL算法定义聚类矩阵,建立对应的概率矩阵模型,引入遗传算法的基因变异算子,设计适用于分布估计算法的变异操作,改进概率模型的更新方式。实验结果表明,与Kmeans、Kmedioid、Clarans和遗传算法相比,该算法的聚类质量较好。     

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

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

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

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

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

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

基于混合分布估计算法的载波路由研究

为了提高低压电力线载波通信可靠性,解决载波信道资源紧张、传输能力下降等问题,针对复杂的低压电力线网络拓扑结构,提出一种基于混合分布估计算法的电力线载波通信路由方法。根据网络服务质量(QoS)设计电力线网络传输加权目标函数,采用二进制编码方式表示解,使用分布估计算法和遗传算法并行搜索最优解,其中,分布估计算法通过种群增量学习(PBIL)概率模型对解空间采样,对2种算法的每一代新生种群设计动态比例进行混合,以此更新产生下一代种群,提高算法全局和局部搜索能力。将所提算法与遗传算法、蚁群算法、分布估计算法进行仿真比较,结果表明,所提算法能更快地建立起网络中主节点到各从节点的最优路由,提高了抄表采集系统中数据包的传输实时性和成功率,以动态网络验证了算法的鲁棒性。     

经验分布函数概率模型的分布估计算法

连续域分布估计算法普遍采用高斯概率模型;假设变量服从高斯分布。该假设并不具有普遍意义。提出一个任意分布的连续多变量耦合分布估计算法;利用经验分布函数从样本估计分布;采样产生新的个体。描述经验分布函数和逆变换法采样;讨论用样本构造经验分布函数并采样的基本思想;给出一次采样算法及完整的分布估计算法;通过典型函数的仿真实验;说明方法的正确性和有效性。
     

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

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

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

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

基于用户兴趣模型的协同过滤推荐算法

协同过滤推荐算法是目前应用最广泛个性化推荐技术,其中用户相似度的计算方法是影响推荐算法质量的关键因素。针对传统协同过滤算法中稀疏评分数据造成的用户相似度计算不准确问题,提出一种基于用户兴趣模型的协同过滤推荐算法。该算法使用分布估计算法建立用户兴趣模型,并使用用户兴趣模型计算用户间相似度。实验表明,该算法的准确性受数据稀疏性影响较小,同时在收敛速度和推荐准确性方面有明显提高。     

Extended artificial chromosomes genetic algorithm for permutation flowshop scheduling problems

In our previous researches, we proposed the artificial chromosomes with genetic algorithm (ACGA) which combines the concept of the Estimation of Distribution Algorithms (EDAs) with genetic algorithms (GAs). The probabilistic model used in the ACGA is the univariate probabilistic model. We showed that ACGA is effective in solving the scheduling problems. In this paper, a new probabilistic model is proposed to capture the variable linkages together with the univariate probabilistic model where most EDAs could use only one statistic information. This proposed algorithm is named extended artificial chromosomes with genetic algorithm (eACGA). We investigate the usefulness of the probabilistic models and to compare eACGA with several famous permutation-oriented EDAs on the benchmark instances of the permutation flowshop scheduling problems (PFSPs). eACGA yields better solution quality for makespan criterion when we use the average error ratio metric as their performance measures. In addition, eACGA is further integrated with well-known heuristic algorithms, such as NEH and variable neighborhood search (VNS) and it is denoted as eACGA_hybrid to solve the considered problems. No matter the solution quality and the computation efficiency, the experimental results indicate that eACGA_hybrid outperforms other known algorithms in literature. As a result, the proposed algorithms are very competitive in solving the PFSPs.     

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.     

A novel ensemble of classifiers for microarray data classification

Micorarray data are often extremely asymmetric in dimensionality, such as thousands or even tens of thousands of genes and a few hundreds of samples. Such extreme asymmetry between the dimensionality of genes and samples presents several challenges to conventional clustering and classification methods. In this paper, a novel ensemble method is proposed. Firstly, in order to extract useful features and reduce dimensionality, different feature selection methods such as correlation analysis, Fisher-ratio is used to form different feature subsets. Then a pool of candidate base classifiers is generated to learn the subsets which are re-sampling from the different feature subsets with PSO (Particle Swarm Optimization) algorithm. At last, appropriate classifiers are selected to construct the classification committee using EDAs (Estimation of Distribution Algorithms). Experiments show that the proposed method produces the best recognition rates on four benchmark databases.     

Univariate marginal distribution algorithm dynamics for a class of parametric functions with unitation constraints

In this paper, we introduce a mathematical model for analyzing the dynamics of the univariate marginal distribution algorithm (UMDA) for a class of parametric functions with isolated global optima. We prove a number of results that are used to model the evolution of UMDA probability distributions for this class of functions. We show that a theoretical analysis can assess the effect of the function parameters on the convergence and rate of convergence of UMDA. We also introduce for the first time a long string limit analysis of UMDA. Finally, we relate the results to ongoing research on the application of the estimation of distribution algorithms for problems with unitation constraints.     

Sporadic model building for efficiency enhancement of the hierarchical BOA

Efficiency enhancement techniques—such as parallelization and hybridization—are among the most important ingredients of practical applications of genetic and evolutionary algorithms and that is why this research area represents an important niche of evolutionary computation. This paper describes and analyzes sporadic model building, which can be used to enhance the efficiency of the hierarchical Bayesian optimization algorithm (hBOA) and other estimation of distribution algorithms (EDAs) that use complex multivariate probabilistic models. With sporadic model building, the structure of the probabilistic model is updated once in every few iterations (generations), whereas in the remaining iterations, only model parameters (conditional and marginal probabilities) are updated. Since the time complexity of updating model parameters is much lower than the time complexity of learning the model structure, sporadic model building decreases the overall time complexity of model building. The paper shows that for boundedly difficult nearly decomposable and hierarchical optimization problems, sporadic model building leads to a significant model-building speedup, which decreases the asymptotic time complexity of model building in hBOA by a factor of to where n is the problem size. On the other hand, sporadic model building also increases the number of evaluations until convergence; nonetheless, if model building is the bottleneck, the evaluation slowdown is insignificant compared to the gains in the asymptotic complexity of model building. The paper also presents a dimensional model to provide a heuristic for scaling the structure-building period, which is the only parameter of the proposed sporadic model-building approach. The paper then tests the proposed method and the rule for setting the structure-building period on the problem of finding ground states of 2D and 3D Ising spin glasses.     

使用遗传算法的信息检索动态参数学习方法

信息检索系统中的参数设定在很大程度上决定着系统的检索性能．参数的数据相关性和敏感性使得经验值往往不可靠．另一方面,由于在检索过程中缺乏当前查询的相关文档信息,因而不可能进行有指导的参数学习．因此,自动无指导的参数学习方法是极为必要和重要的．首先考察传统上根据经验值设定固定的系统参数的效果,结果表明其泛化能力差,效果不稳定且不可靠．其次,提出一种使用遗传算法进行动态参数学习的方法．在TREC11,TREC10和TREC9三组大规模Web标准测试数据集上进行了实验,数据集规模均超过10GB．实验结果表明,经过动态参数学习,系统性能总是能够接近甚至达到可能实现的最优性能．