Optimization based on phylogram analysis

Estimation of Distribution Algorithms (EDAs) is evolutionary algorithms with relevant performance in handling complex problems. Nevertheless, their efficiency and effectiveness directly depends on how accurate the deployed probabilistic models are, which in turn depend on methods of model building. Although the best models found in the literature are often built by computationally complex methods, whose corresponding EDAs require high running time, these methods may evaluate a lesser number of points in the search space. In order to find a better trade-off between running time (efficiency) and the number of evaluated points (effectiveness), this work uses probabilistic models built by algorithms of phylogenetic reconstruction, since some of them are able to efficiently produce accurate models. Then, an EDA, namely, Optimization based on Phylogram Analysis, and a new search technique, namely, Composed Exhaustive Search, are developed and proposed to find solutions for combinatorial optimization problems with different levels of difficulty. Experimental results show that the proposed new EDA features an interesting trade-off between running time and number of evaluated points, attaining solutions near to the best results found in the literature for each one of such performance measures.     

Effective Linkage Learning Using Low-Order Statistics and Clustering

The adoption of probabilistic models for selected individuals is a powerful approach for evolutionary computation. Probabilistic models based on high-order statistics have been used by estimation of distribution algorithms (EDAs), resulting better effectiveness when searching for global optima for hard optimization problems. This paper proposes a new framework for evolutionary algorithms, which combines a simple EDA based on order 1 statistics and a clustering technique in order to avoid the high computational cost required by higher order EDAs. The algorithm uses clustering to group genotypically similar solutions, relying that different clusters focus on different substructures and the combination of information from different clusters effectively combines substructures. The combination mechanism uses an information gain measure when deciding which cluster is more informative for any given gene position, during a pairwise cluster combination. Empirical evaluations effectively cover a comprehensive range of benchmark optimization problems.      

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.     

Model accuracy in the Bayesian optimization algorithm

Evolutionary algorithms (EAs) are particularly suited to solve problems for which there is not much information available. From this standpoint, estimation of distribution algorithms (EDAs), which guide the search by using probabilistic models of the population, have brought a new view to evolutionary computation. While solving a given problem with an EDA, the user has access to a set of models that reveal probabilistic dependencies between variables, an important source of information about the problem. However, as the complexity of the used models increases, the chance of overfitting and consequently reducing model interpretability, increases as well. This paper investigates the relationship between the probabilistic models learned by the Bayesian optimization algorithm (BOA) and the underlying problem structure. The purpose of the paper is threefold. First, model building in BOA is analyzed to understand how the problem structure is learned. Second, it is shown how the selection operator can lead to model overfitting in Bayesian EDAs. Third, the scoring metric that guides the search for an adequate model structure is modified to take into account the non-uniform distribution of the mating pool generated by tournament selection. Overall, this paper makes a contribution towards understanding and improving model accuracy in BOA, providing more interpretable models to assist efficiency enhancement techniques and human researchers.     

Inexact graph matching by means of estimation of distribution algorithms

Estimation of distribution algorithms (EDAs) are a quite recent topic in optimization techniques. They combine two technical disciplines of soft computing methodologies: probabilistic reasoning and evolutionary computing. Several algorithms and approaches have already been proposed by different authors, but up to now there are very few papers showing their potential and comparing them to other evolutionary computational methods and algorithms such as genetic algorithms (GAs). This paper focuses on the problem of inexact graph matching which is NP-hard and requires techniques to find an approximate acceptable solution. This problem arises when a nonbijective correspondence is searched between two graphs. A typical instance of this problem corresponds to the case where graphs are used for structural pattern recognition in images. EDA algorithms are well suited for this type of problems.

This paper proposes to use EDA algorithms as a new approach for inexact graph matching. Also, two adaptations of the EDA approach to problems with constraints are described as two techniques to control the generation of individuals, and the performance of EDAs for inexact graph matching is compared with the one of GAs.     

Exploiting Bivariate Dependencies to Speedup Structure Learning in Bayesian Optimization Algorithm

Bayesian optimization algorithm (BOA) is one of the successful and widely used estimation of distribution algorithms (EDAs) which have been employed to solve different optimization problems. In EDAs, a model is learned from the selected population that encodes interactions among problem variables. New individuals are generated by sampling the model and incorporated into the population. Different probabilistic models have been used in EDAs to learn interactions. Bayesian network (BN) is a well-known graphical model which is used in BOA. Learning a proper model in EDAs and particularly in BOA is distinguished as a computationally expensive task. Different methods have been proposed in the literature to improve the complexity of model building in EDAs. This paper employs bivariate dependencies to learn accurate BNs in BOA efficiently. The proposed approach extracts the bivariate dependencies using an appropriate pairwise interaction-detection metric. Due to the static structure of the underlying problems, these dependencies are used in each generation of BOA to learn an accurate network. By using this approach, the computational cost of model building is reduced dramatically. Various optimization problems are selected to be solved by the algorithm. The experimental results show that the proposed approach successfully finds the optimum in problems with different types of interactions efficiently. Significant speedups are observed in the model building procedure as well.     

Biasing Bayesian Optimization Algorithm using Case Based Reasoning

Studies show that application of the prior knowledge in biasing the Estimation of Distribution Algorithms (EDAs), such as Bayesian Optimization Algorithm (BOA), increases the efficiency of these algorithms significantly. One of the main advantages of the EDAs over other optimization algorithms is that the former provides a trail of probabilistic models of candidate solutions with increasing quality. Some recent studies have applied these probabilistic models, obtained from previously solved problems in biasing the BOA algorithm, to solve the future problems. In this paper, in order to improve the previous works and reduce their disadvantages, a method based on Case Based Reasoning (CBR) is proposed for biasing the BOA algorithm. Herein, after running BOA for solving optimization problems, each problem, the corresponding solution, as well as the last Bayesian network obtained from the BOA algorithm, will be stored as an entry in the case-base. Upon introducing a new problem, similar problems from the case-base are retrieved and the last Bayesian networks of these solved problems are combined according to the degree of their similarity with the new problem; hence, a compound Bayesian network is constructed. The compound Bayesian network is sampled and the initial population for the BOA algorithm is generated. This network will be applied efficiently for biasing future probabilistic models during the runs of BOA for the new problem. The proposed method is tested on three well-known combinatorial benchmark problems. Experimental results show significant improvements in algorithm execution time and quality of solutions, compared to previous methods.     

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.     

Protein Folding in Simplified Models With Estimation of Distribution Algorithms

Simplified lattice models have played an important role in protein structure prediction and protein folding problems. These models can be useful for an initial approximation of the protein structure, and for the investigation of the dynamics that govern the protein folding process. Estimation of distribution algorithms (EDAs) are efficient evolutionary algorithms that can learn and exploit the search space regularities in the form of probabilistic dependencies. This paper introduces the application of different variants of EDAs to the solution of the protein structure prediction problem in simplified models, and proposes their use as a simulation tool for the analysis of the protein folding process. We develop new ideas for the application of EDAs to the bidimensional and tridimensional (2-d and 3-d) simplified protein folding problems. This paper analyzes the rationale behind the application of EDAs to these problems, and elucidates the relationship between our proposal and other population-based approaches proposed for the protein folding problem. We argue that EDAs are an efficient alternative for many instances of the protein structure prediction problem and are indeed appropriate for a theoretical analysis of search procedures in lattice models. All the algorithms introduced are tested on a set of difficult 2-d and 3-d instances from lattice models. Some of the results obtained with EDAs are superior to the ones obtained with other well-known population-based optimization algorithms.     

A review of message passing algorithms in estimation of distribution algorithms

Message passing algorithms (MPAs) have been traditionally used as an inference method in probabilistic graphical models. Some MPA variants have recently been introduced in the field of estimation of distribution algorithms (EDAs) as a way to improve the efficiency of these algorithms. Multiple developments on MPAs point to an increasing potential of these methods for their application as part of hybrid EDAs. In this paper we review recent work on EDAs that apply MPAs and propose ways to further extend the useful synergies between MPAs and EDAs. Furthermore, we analyze some of the implications that MPA developments can have in their future application to EDAs and other evolutionary algorithms.     

Combinations of estimation of distribution algorithms and other techniques

This paper summaries our recent work on combining estimation of distribution algorithms (EDA) and other techniques for solving hard search and optimization problems:a) guided mutation,an offspring generator in which the ideas from EDAs and genetic algorithms are combined together,we have shown that an evolutionary algorithm with guided mutation outperforms the best GA for the maximum clique problem,b)evolutionary algorithms refining a heuristic,we advocate a strategy for solving a hard optimization problem with complicated data structure,and c) combination of two different local search techniques and EDA for numerical global optimization problems,its basic idea is that not all the new generated points are needed to be improved by an expensive local search.     

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.     

Histogram-Based Estimation of Distribution Algorithm: A Competent Method for Continuous Optimization

Designing efficient estimation of distribution algorithms for optimizing complex continuous problems is still a challenging task. This paper utilizes histogram probabilistic model to describe the distribution of population and to generate promising solutions. The advantage of histogram model, its intrinsic multimodality, makes it proper to describe the solution distribution of complex and multimodal continuous problems. To make histogram model more efficiently explore and exploit the search space, several strategies are brought into the algorithms： the surrounding effect reduces the population size in estimating the model with a certain number of the bins and the shrinking strategy guarantees the accuracy of optimal solutions. Furthermore, this paper shows that histogram-based EDA （Estimation of distribution algorithm） can give comparable or even much better performance than those predominant EDAs based on Gaussian models.     

Estimation of distribution algorithms with Kikuchi approximations

The question of finding feasible ways for estimating probability distributions is one of the main challenges for Estimation of Distribution Algorithms (EDAs). To estimate the distribution of the selected solutions, EDAs use factorizations constructed according to graphical models. The class of factorizations that can be obtained from these probability models is highly constrained. Expanding the class of factorizations that could be employed for probability approximation is a necessary step for the conception of more robust EDAs. In this paper we introduce a method for learning a more general class of probability factorizations. The method combines a reformulation of a probability approximation procedure known in statistical physics as the Kikuchi approximation of energy, with a novel approach for finding graph decompositions. We present the Markov Network Estimation of Distribution Algorithm (MN-EDA), an EDA that uses Kikuchi approximations to estimate the distribution, and Gibbs Sampling (GS) to generate new points. A systematic empirical evaluation of MN-EDA is done in comparison with different Bayesian network based EDAs. From our experiments we conclude that the algorithm can outperform other EDAs that use traditional methods of probability approximation in the optimization of functions with strong interactions among their variables.     

A Self-guided Genetic Algorithm for permutation flowshop scheduling problems

In this paper we develop a Self-guided Genetic Algorithm (Self-guided GA), which belongs to the category of Estimation of Distribution Algorithms (EDAs). Most EDAs explicitly use the probabilistic model to sample new solutions without using traditional genetic operators. EDAs make good use of the global statistical information collected from previous searches but they do not efficiently use the location information about individual solutions. It is recently realized that global statistical information and location information should complement each other during the evolution process. In view of this, we design the Self-guided GA based on a novel strategy to combine these two kinds of information. The Self-guided GA does not sample new solutions from the probabilistic model. Instead, it estimates the quality of a candidate offspring based on the probabilistic model used in its crossover and mutation operations. In such a way, the mutation and crossover operations are able to generate fitter solutions, thus improving the performance of the algorithm. We tested the proposed algorithm by applying it to deal with the NP-complete flowshop scheduling problem to minimize the makespan. The experimental results show that the Self-guided GA is very promising. We also demonstrate that the Self-guided GA can be easily extended to treat other intractable combinatorial problems.     

构建在最大熵原理上的分布估计算法及其应用研究

分布估计算法是进化计算领域的一个新方向.它主要用概率模型来建造进化计算中的遗传算法,它不再依赖于交叉与变异,而是估计较好个体的概率分布,用概率分布来引导对搜寻空间的探索.本文提出一类基于最大熵的分布估计算法.实验结果表明,在解决某些较复杂问题时,本文算法比遗传算法更具优势.     

一种基于递增估计GMM的连续优化算法

目前的分布估计算法(estimation of distribution algorithms)中概率模型的学习或多或少存在着对先验知识的依赖,而这些先验知识往往是不可预知的.针对这一问题,文中提出采用集成学习(ensemble learning)的思想实现EDAs中概率模型结构和参数的自动学习,并提出了一种基于递增学习策略的连续域分布估计算法,该算法采用贪心EM算法来实现高斯混合模型(GMM)的递增学习,在不需要任何先验知识的情况下,实现模型结构和参数的自动学习.通过一组函数优化实验对该算法的性能进行了考查,并与其它同类算法进行了比较.实验结果表明该方法是有效的,并且,相比其它同类EDAs,该算法用相对少的迭代,可以得到同样或者更好的结果.     

A block based estimation of distribution algorithm using bivariate model for scheduling problems

Recently, estimation of distribution algorithms (EDAs) have gradually attracted a lot of attention and have emerged as a prominent alternative to traditional evolutionary algorithms. In this paper, a block-based EDA using bivariate model is developed to solve combinatorial problems. Instead of generating a set of chromosomes, our approach generates a set of promising blocks using bivariate model and these blocks are reserved in an archive for future use. These blocks will be updated every other k generation. Then, two rules, i.e., AC1 and AC2, are developed to generate a new chromosome by combining the set of selected blocks and rest of genes. This block based approach is very efficient and effective when compared with the traditional EDAs. According to the experimental results, the block based EDA outperforms EDA, GA, ACO and other evolutionary approaches in solving benchmark permutation problems. The block based approach is a new concept and has a very promising result for other applications.     

Regularized continuous estimation of distribution algorithms

Regularization is a well-known technique in statistics for model estimation which is used to improve the generalization ability of the estimated model. Some of the regularization methods can also be used for variable selection that is especially useful in high-dimensional problems. This paper studies the use of regularized model learning in estimation of distribution algorithms (EDAs) for continuous optimization based on Gaussian distributions. We introduce two approaches to the regularized model estimation and analyze their effect on the accuracy and computational complexity of model learning in EDAs. We then apply the proposed algorithms to a number of continuous optimization functions and compare their results with other Gaussian distribution-based EDAs. The results show that the optimization performance of the proposed RegEDAs is less affected by the increase in the problem size than other EDAs, and they are able to obtain significantly better optimization values for many of the functions in high-dimensional settings.     

Duple-EDA and sample density balancing

In this paper,a new method is proposed to overcome the problem of local optima traps in a class of evolutionary algorithms,called estimation of distribution algorithms(EDAs) ,in real-valued function optimization. The Duple-EDA framework is proposed in which not only the current best solutions but also the search history are modeled,so that long-term feedback can be taken into account. Sample Density Balancing(SDB) is proposed under the framework to alleviate the drift phenomenon in EDA. A selection scheme b...