An introduction and survey of estimation of distribution algorithms
---
paper_title: Real-coded ECGA for economic dispatch

paper_content:

In this paper, we propose a new approach that consists of the extended compact genetic algorithm (ECGA) and split-on-demand (SoD), an adaptive discretization technique, to economic dispatch (ED) problems with nonsmooth cost functions. ECGA is designed for handling problems with decision variables of the discrete type, while the decision variables of ED problems are oftentimes real numbers. Thus, in order to employ ECGA to tackle ED problems, SoD is utilized for discretizing the continuous decision variables and works as the interface between ECGA and the ED problem. Furthermore, ED problems in practice are usually hard for traditional mathematical programming methodologies because of the equality and inequality constraints. Hence, in addition to integrating ECGA and SoD, in this study, we devise a repair operator specifically for making the infeasible solutions to satisfy the equality constraint. To examine the performance and effectiveness, we apply the proposed framework to two different-sized ED problems with nonsmooth cost function considering the valve-point effects. The experimental results are compared to those obtained by various evolutionary algorithms and demonstrate that handling ED problems with the proposed framework is a promising research direction.
---
paper_title: A new epsilon-dominance hierarchical Bayesian optimization algorithm for large multiobjective monitoring network design problems

paper_content:

Abstract This study focuses on the development of a next generation multiobjective evolutionary algorithm (MOEA) that can learn and exploit complex interdependencies and/or correlations between decision variables in monitoring design applications to provide more robust performance for large problems (defined in terms of both the number of objectives and decision variables). The proposed MOEA is termed the epsilon-dominance hierarchical Bayesian optimization algorithm ( e -hBOA), which is representative of a new class of probabilistic model building evolutionary algorithms. The e -hBOA has been tested relative to a top-performing traditional MOEA, the epsilon-dominance nondominated sorted genetic algorithm II ( e -NSGAII) for solving a four-objective LTM design problem. A comprehensive performance assessment of the e -NSGAII and various configurations of the e -hBOA have been performed for both a 25 well LTM design test case (representing a relatively small problem with over 33 million possible designs), and a 58 point LTM design test case (with over 2.88 × 10 17 possible designs). The results from this comparison indicate that the model building capability of the e -hBOA greatly enhances its performance relative to the e -NSGAII, especially for large monitoring design problems. This work also indicates that decision variable interdependencies appear to have a significant impact on the overall mathematical difficulty of the monitoring network design problem.
---
paper_title: Population Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitve Learning

paper_content:

Genetic algorithms (GAs) are biologically motivated adaptive systems which have been used, with varying degrees of success, for function optimization. In this study, an abstraction of the basic genetic algorithm, the Equilibrium Genetic Algorithm (EGA), and the GA in turn, are reconsidered within the framework of competitive learning. This new perspective reveals a number of different possibilities for performance improvements. This paper explores population-based incremental learning (PBIL), a method of combining the mechanisms of a generational genetic algorithm with simple competitive learning. The combination of these two methods reveals a tool which is far simpler than a GA, and which out-performs a GA on large set of optimization problems in terms of both speed and accuracy. This paper presents an empirical analysis of where the proposed technique will outperform genetic algorithms, and describes a class of problems in which a genetic algorithm may be able to perform better. Extensions to this algorithm are discussed and analyzed. PBIL and extensions are compared with a standard GA on twelve problems, including standard numerical optimization functions, traditional GA test suite problems, and NP-Complete problems.
---
paper_title: Evaluation of Advanced Genetic Algorithms Applied to Groundwater Remediation Design

paper_content:

Optimal design of a groundwater pump and treat system is a difficult task, especially given the computationally intensive nature of field-scale remediation design. Genetic algorithms (GAs) have been used extensively for remediation design because of their flexibility and global search capabilities, but computational intensity is a particularly difficult issue with GAs. This paper discusses a new competent GA, the hierarchical Bayesian Optimization Algorithm (hBOA), which is designed to reduce the computational effort. GAs operate by assembling highly fit segments of chromosomes (potential solutions), called building blocks. The hBOA enhances the efficiency of this process by using a Bayesian network to create models of the building blocks. The building blocks are nodes on the network, and the algorithm uses the network to generate new solutions, retaining the best building blocks of the parents. This work compares the performance of hBOA to a simple genetic algorithm (SGA) in solving a case study to determine if any benefit can be gained through the use of this approach. This work demonstrates that hBOA more reliably identifies the optimal solution to this groundwater remediation design problem.
---
paper_title: Searching for Ground States of Ising Spin Glasses with Hierarchical BOA and Cluster Exact Approximation

paper_content:

Summary. This chapter applies the hierarchical Bayesian optimization algorithm (hBOA) to the problem of finding ground states of Ising spin glasses with ±J and Gaussian couplings in two and three dimensions. The performance of hBOA is compared to that of the simple genetic algorithm (GA) and the univariate marginal distribution algorithm (UMDA). The performance of all tested algorithms is improved by incorporating a deterministic hill climber based on single-bit flips. The results show that hBOA significantly outperforms GA and UMDA on a broad spectrum of spin glass instances. Cluster exact approximation (CEA) is then described and incorporated into hBOA and GA to improve their efficiency. The results show that CEA enables all tested algorithms to solve larger spin glass instances and that hBOA significantly outperforms other compared algorithms even in this case.
---
paper_title: A survey of optimization by building and using probabilistic models

paper_content:

Summarizes the research on population-based probabilistic search algorithms based on modeling promising solutions by estimating their probability distribution and using the constructed model to guide the exploration of the search space. It settles the algorithms in the field of genetic and evolutionary computation where they have been originated. All methods are classified into a few classes according to the complexity of the class of models they use. Algorithms from each of these classes are briefly described and their strengths and weaknesses are discussed.
---
paper_title: Optimising cancer chemotherapy using an estimation of distribution algorithm and genetic algorithms

paper_content:

This paper presents a methodology for using heuristic search methods to optimise cancer chemotherapy. Specifically, two evolutionary algorithms - Population Based Incremental Learning (PBIL), which is an Estimation of Distribution Algorithm (EDA), and Genetic Algorithms (GAs) have been applied to the problem of finding effective chemotherapeutic treatments. To our knowledge, EDAs have been applied to fewer real world problems compared to GAs, and the aim of the present paper is to expand the application domain of this technique.We compare and analyse the performance of both algorithms and draw a conclusion as to which approach to cancer chemotherapy optimisation is more efficient and helpful in the decision-making activity led by the oncologists.
---
paper_title: Automated alphabet reduction method with evolutionary algorithms for protein structure prediction

paper_content:

This paper focuses on automated procedures to reduce the dimensionality ofprotein structure prediction datasets by simplifying the way in which the primary sequence of a protein is represented. The potential benefits ofthis procedure are faster and easier learning process as well as the generationof more compact and human-readable classifiers.The dimensionality reduction procedure we propose consists on the reductionof the 20-letter amino acid (AA) alphabet, which is normally used to specify a protein sequence, into a lower cardinality alphabet. This reduction comes about by a clustering of AA types accordingly to their physical and chemical similarity. Our automated reduction procedure is guided by a fitness function based on the Mutual Information between the AA-based input attributes of the dataset and the protein structure featurethat being predicted. To search for the optimal reduction, the Extended Compact Genetic Algorithm (ECGA) was used, and afterwards the results of this process were fed into (and validated by) BioHEL, a genetics-based machine learningtechnique. BioHEL used the reduced alphabet to induce rules forprotein structure prediction features. BioHEL results are compared to two standard machine learning systems. Our results show that it is possible to reduce the size of the alphabet used for prediction fromtwenty to just three letters resulting in more compact, i.e. interpretable,rules. Also, a protein-wise accuracy performance measure suggests that the loss of accuracy acrued by this substantial alphabet reduction is not statistically significant when compared to the full alphabet.
---
paper_title: Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation

paper_content:

List of Figures. List of Tables. Preface. Contributing Authors. Series Foreword. Part I: Foundations. 1. An Introduction to Evolutionary Algorithms J.A. Lozano. 2. An Introduction to Probabilistic Graphical Models P. Larranaga. 3. A Review on Estimation of Distribution Algorithms P. Larranaga. 4. Benefits of Data Clustering in Multimodal Function Optimization via EDAs J.M. Pena, et al. 5. Parallel Estimation of Distribution Algorithms J.A. Lozano, et al. 6. Mathematical Modeling of Discrete Estimation of Distribution Algorithms C. Gonzalez, et al. Part II: Optimization. 7. An Empiricial Comparison of Discrete Estimation of Distribution Algorithms R. Blanco., J.A. Lozano. 8. Results in Function Optimization with EDAs in Continuous Domain E. Bengoetxea, et al. 9. Solving the 0-1 Knapsack Problem with EDAs R. Sagarna, P. Larranaga. 10. Solving the Traveling Salesman Problem with EDAs V. Robles, et al. 11. EDAs Applied to the Job Shop Scheduling Problem J.A. Lozano, A. Mendiburu. 12. Solving Graph Matching with EDAs Using a Permutation-Based Representation E. Bengoetxea, et al. Part III: Machine Learning. 13. Feature Subset Selection by Estimation of Distribution Algorithms I. Inza, et al. 14. Feature Weighting for Nearest Neighbor by EDAs I. Inza, et al. 15. Rule Induction by Estimation of Distribution Algorithms B. Sierra, et al. 16. Partial Abductive Inference in Bayesian Networks: An Empirical Comparison Between GAs and EDAs L.M. de Campos, et al.17. Comparing K-Means, GAs and EDAs in Partitional Clustering J. Roure, et al. 18. Adjusting Weights in Artificial Neural Networks using Evolutionary Algorithms C. Cotta, et al. Index.
---
paper_title: Military Antenna Design Using a Simple Genetic Algorithm and hBOA

paper_content:

A bath composition for cataphoretic electrocoating of conductive surfaces contains coating agents which have been rendered soluble or dispersible with acid, contain basic nitrogen groups and carry groups of the general formulae (1) and (11) (I) (II) and, optionally, also groups of the general formulae (III) and/or (IV) (III) (IV) where R1 and R2 are each alkyl, hydroxyalkyl or alkoxyalkyl, R3 and R4 are each hydrogen or methyl, R5 and R6 are each hydrogen, alkyl or a divalent radical of a polymer molecule which is bonded to a phenol or phenol ether, n1 is 1, 2 or 3 and n2 is 1 or 2, and where the oxygen bonded to the phenyl radical is either in the form of the OH group or etherified.
---
paper_title: Population Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitve Learning

paper_content:

Genetic algorithms (GAs) are biologically motivated adaptive systems which have been used, with varying degrees of success, for function optimization. In this study, an abstraction of the basic genetic algorithm, the Equilibrium Genetic Algorithm (EGA), and the GA in turn, are reconsidered within the framework of competitive learning. This new perspective reveals a number of different possibilities for performance improvements. This paper explores population-based incremental learning (PBIL), a method of combining the mechanisms of a generational genetic algorithm with simple competitive learning. The combination of these two methods reveals a tool which is far simpler than a GA, and which out-performs a GA on large set of optimization problems in terms of both speed and accuracy. This paper presents an empirical analysis of where the proposed technique will outperform genetic algorithms, and describes a class of problems in which a genetic algorithm may be able to perform better. Extensions to this algorithm are discussed and analyzed. PBIL and extensions are compared with a standard GA on twelve problems, including standard numerical optimization functions, traditional GA test suite problems, and NP-Complete problems.
---
paper_title: A survey of optimization by building and using probabilistic models

paper_content:

Summarizes the research on population-based probabilistic search algorithms based on modeling promising solutions by estimating their probability distribution and using the constructed model to guide the exploration of the search space. It settles the algorithms in the field of genetic and evolutionary computation where they have been originated. All methods are classified into a few classes according to the complexity of the class of models they use. Algorithms from each of these classes are briefly described and their strengths and weaknesses are discussed.
---
paper_title: Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation

paper_content:

List of Figures. List of Tables. Preface. Contributing Authors. Series Foreword. Part I: Foundations. 1. An Introduction to Evolutionary Algorithms J.A. Lozano. 2. An Introduction to Probabilistic Graphical Models P. Larranaga. 3. A Review on Estimation of Distribution Algorithms P. Larranaga. 4. Benefits of Data Clustering in Multimodal Function Optimization via EDAs J.M. Pena, et al. 5. Parallel Estimation of Distribution Algorithms J.A. Lozano, et al. 6. Mathematical Modeling of Discrete Estimation of Distribution Algorithms C. Gonzalez, et al. Part II: Optimization. 7. An Empiricial Comparison of Discrete Estimation of Distribution Algorithms R. Blanco., J.A. Lozano. 8. Results in Function Optimization with EDAs in Continuous Domain E. Bengoetxea, et al. 9. Solving the 0-1 Knapsack Problem with EDAs R. Sagarna, P. Larranaga. 10. Solving the Traveling Salesman Problem with EDAs V. Robles, et al. 11. EDAs Applied to the Job Shop Scheduling Problem J.A. Lozano, A. Mendiburu. 12. Solving Graph Matching with EDAs Using a Permutation-Based Representation E. Bengoetxea, et al. Part III: Machine Learning. 13. Feature Subset Selection by Estimation of Distribution Algorithms I. Inza, et al. 14. Feature Weighting for Nearest Neighbor by EDAs I. Inza, et al. 15. Rule Induction by Estimation of Distribution Algorithms B. Sierra, et al. 16. Partial Abductive Inference in Bayesian Networks: An Empirical Comparison Between GAs and EDAs L.M. de Campos, et al.17. Comparing K-Means, GAs and EDAs in Partitional Clustering J. Roure, et al. 18. Adjusting Weights in Artificial Neural Networks using Evolutionary Algorithms C. Cotta, et al. Index.
---
paper_title: Analyzing Deception in Trap Functions

paper_content:

Abstract A flat-population schema analysis is performed to find conditions for full deception in trap functions. It is found that the necessary and sufficient condition for an l-bit fully deceptive trap function is that all order l — 1 schemata are misleading, and it is observed that the trap functions commonly used in a number of test suites are not fully deceptive. Further analysis suggests that in a fully deceptive trap function, the locally optimal function value may be as low as 50% of the globally optimal function value. In this context, the limiting ratio of the locally and the globally optimal function value for a number of fully deceptive functions currently in use are calculated. The analysis indicates that trap functions allow more flexibility in designing a deceptive function. It is also found that the proportion of fully deceptive functions in the family of trap functions is only O(l−1 ln l)) and that more than half of the trap functions are fully easy functions.
---
paper_title: FDA -A Scalable Evolutionary Algorithm for the Optimization of Additively Decomposed Functions

paper_content:

The Factorized Distribution Algorithm (FDA) is an evolutionary algorithm which combines mutation and recombination by using a distribution. The distribution is estimated from a set of selected points. In general, a discrete distribution defined for n binary variables has 2(n) parameters. Therefore it is too expensive to compute. For additively decomposed discrete functions (ADFs) there exist algorithms which factor the distribution into conditional and marginal distributions. This factorization is used by FDA. The scaling of FDA is investigated theoretically and numerically. The scaling depends on the ADF structure and the specific assignment of function values. Difficult functions on a chain or a tree structure are solved in about O(n radical n) operations. More standard genetic algorithms are not able to optimize these functions. FDA is not restricted to exact factorizations. It also works for approximate factorizations as is shown for a circle and a grid structure. By using results from Bayes networks, FDA is extended to LFDA. LFDA computes an approximate factorization using only the data, not the ADF structure. The scaling of LFDA is compared to the scaling of FDA.
---
paper_title: The gambler's ruin problem, genetic algorithms, and the sizing of populations

paper_content:

The paper presents a model for predicting the convergence quality of genetic algorithms. The model incorporates previous knowledge about decision making in genetic algorithms and the initial supply of building blocks in a novel way. The result is an equation that accurately predicts the quality of the solution found by a GA using a given population size. Adjustments for different selection intensities are considered and computational experiments demonstrate the effectiveness of the model.
---
paper_title: From Recombination of Genes to the Estimation of Distributions I. Binary Parameters

paper_content:

The Breeder Genetic Algorithm (BGA) is based on the equation for the response to selection. In order to use this equation for prediction, the variance of the fitness of the population has to be estimated. For the usual sexual recombination the computation can be difficult. In this paper we shortly state the problem and investigate several modifications of sexual recombination. The first method is gene pool recombination, which leads to marginal distribution algorithms. In the last part of the paper we discuss more sophisticated methods, based on estimating the distribution of promising points.
---
paper_title: Population Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitve Learning

paper_content:

Genetic algorithms (GAs) are biologically motivated adaptive systems which have been used, with varying degrees of success, for function optimization. In this study, an abstraction of the basic genetic algorithm, the Equilibrium Genetic Algorithm (EGA), and the GA in turn, are reconsidered within the framework of competitive learning. This new perspective reveals a number of different possibilities for performance improvements. This paper explores population-based incremental learning (PBIL), a method of combining the mechanisms of a generational genetic algorithm with simple competitive learning. The combination of these two methods reveals a tool which is far simpler than a GA, and which out-performs a GA on large set of optimization problems in terms of both speed and accuracy. This paper presents an empirical analysis of where the proposed technique will outperform genetic algorithms, and describes a class of problems in which a genetic algorithm may be able to perform better. Extensions to this algorithm are discussed and analyzed. PBIL and extensions are compared with a standard GA on twelve problems, including standard numerical optimization functions, traditional GA test suite problems, and NP-Complete problems.
---
paper_title: The compact genetic algorithm

paper_content:

This paper introduces the "compact genetic algorithm" (cGA). The cGA represents the population as a probability distribution over the set of solutions, and is operationally equivalent to the order-one behavior of the simple GA with uniform crossover. It processes each gene independently and requires less memory than the simple GA.
---
paper_title: MIMIC: Finding Optima by Estimating Probability Densities

paper_content:

In many optimization problems, the structure of solutions reflects complex relationships between the different input parameters. For example, experience may tell us that certain parameters are closely related and should not be explored independently. Similarly, experience may establish that a subset of parameters must take on particular values. Any search of the cost landscape should take advantage of these relationships. We present MIMIC, a framework in which we analyze the global structure of the optimization landscape. A novel and efficient algorithm for the estimation of this structure is derived. We use knowledge of this structure to guide a randomized search through the solution space and, in turn, to refine our estimate ofthe structure. Our technique obtains significant speed gains over other randomized optimization procedures.
---
paper_title: Using Optimal Dependency-Trees for Combinatorial Optimization: Learning the Structure of the Search Space

paper_content:

Many combinatorial optimization algorithms have no mechanism for capturing inter-parameter dependencies. However, modeling such dependencies may allow an algorithm to concentrate its sampling more effectively on regions of the search space which have appeared promising in the past. We present an algorithm which incrementally learns pairwise probability distributions from good solutions seen so far, uses these statistics to generate optimal (in terms of maximum likelihood) dependency trees to model these distributions, and then stochastically generates new candidate solutions from these trees. We test this algorithm on a variety of optimization problems. Our results indicate superior performance over other tested algorithms that either (1) do not explicitly use these dependencies, or (2) use these dependencies to generate a more restricted class of dependency graphs.
---
paper_title: Approximating discrete probability distributions with dependence trees

paper_content:

A method is presented to approximate optimally an n -dimensional discrete probability distribution by a product of second-order distributions, or the distribution of the first-order tree dependence. The problem is to find an optimum set of n - 1 first order dependence relationship among the n variables. It is shown that the procedure derived in this paper yields an approximation of a minimum difference in information. It is further shown that when this procedure is applied to empirical observations from an unknown distribution of tree dependence, the procedure is the maximum-likelihood estimate of the distribution.
---
paper_title: The Bivariate Marginal Distribution Algorithm

paper_content:

The paper deals with the Bivariate Marginal Distribution Algorithm (BMDA). BMDA is an extension of the Univariate Marginal Distribution Algorithm (UMDA). It uses the pair gene dependencies in order to improve algorithms that use simple univariate marginal distributions. BMDA is a special case of the Factorization Distribution Algorithm, but without any problem specific knowledge in the initial stage. The dependencies are being discovered during the optimization process itself. In this paper BMDA is described in detail. BMDA is compared to different algorithms including the simple genetic algorithm with different crossover methods and UMDA. For some fitness functions the relation between problem size and the number of fitness evaluations until convergence is shown.
---
paper_title: A Bayesian Approach to Learning Bayesian Networks with Local Structure

paper_content:

Recently several researchers have investigated techniques for using data to learn Bayesian networks containing compact representations for the conditional probability distributions (CPDs) stored at each node. The majority of this work has concentrated on using decision-tree representations for the CPDs. In addition, researchers typically apply non-Bayesian (or asymptotically Bayesian) scoring functions such as MDL to evaluate the goodness-of-fit of networks to the data. ::: ::: In this paper we investigate a Bayesian approach to learning Bayesian networks that contain the more general decision-graph representations of the CPDs. First, we describe how to evaluate the posterior probability-- that is, the Bayesian score--of such a network, given a database of observed cases. Second, we describe various search spaces that can be used, in conjunction with a scoring function and a search procedure, to identify one or more high-scoring networks. Finally, we present an experimentd evaluation of the search spaces, using a greedy algorithm and a Bayesian scoring function.
---
paper_title: Hierarchical Bayesian optimization algorithm: toward a new generation of evolutionary algorithms

paper_content:

Over the last few decades, genetic and evolutionary algorithms (GEAs) have been successfully applied to many problems of business, engineering, and science. This paper discusses probabilistic model-building genetic algorithms (PMBGAs), which are among the most important directions of current GEA research. PMBGAs replace traditional variation operators of GEAs by learning and sampling a probabilistic model of promising solutions. The paper describes two advanced PMBGAs: the Bayesian optimization algorithm (BOA), and the hierarchical BOA (hBOA). The paper argues that BOA and hBOA can solve an important class of nearly decomposable and hierarchical problems in a quadratic or subquadratic number of function evaluations with respect to the number of decision variables.
---
paper_title: FDA -A Scalable Evolutionary Algorithm for the Optimization of Additively Decomposed Functions

paper_content:

The Factorized Distribution Algorithm (FDA) is an evolutionary algorithm which combines mutation and recombination by using a distribution. The distribution is estimated from a set of selected points. In general, a discrete distribution defined for n binary variables has 2(n) parameters. Therefore it is too expensive to compute. For additively decomposed discrete functions (ADFs) there exist algorithms which factor the distribution into conditional and marginal distributions. This factorization is used by FDA. The scaling of FDA is investigated theoretically and numerically. The scaling depends on the ADF structure and the specific assignment of function values. Difficult functions on a chain or a tree structure are solved in about O(n radical n) operations. More standard genetic algorithms are not able to optimize these functions. FDA is not restricted to exact factorizations. It also works for approximate factorizations as is shown for a circle and a grid structure. By using results from Bayes networks, FDA is extended to LFDA. LFDA computes an approximate factorization using only the data, not the ADF structure. The scaling of LFDA is compared to the scaling of FDA.
---
paper_title: Learning Bayesian Networks with Local Structure

paper_content:

We examine a novel addition to the known methods for learning Bayesian networks from data that improves the quality of the learned networks. Our approach explicitly represents and learns the local structure in the conditional probability distributions (CPDs) that quantify these networks. This increases the space of possible models, enabling the representation of CPDs with a variable number of parameters. The resulting learning procedure induces models that better emulate the interactions present in the data. We describe the theoretical foundations and practical aspects of learning local structures and provide an empirical evaluation of the proposed learning procedure. This evaluation indicates that learning curves characterizing this procedure converge faster, in the number of training instances, than those of the standard procedure, which ignores the local structure of the CPDs. Our results also show that networks learned with local structures tend to be more complex (in terms of arcs), yet require fewer parameters.
---
paper_title: Propagating Uncertainty in Bayesian Networks by Probabilistic Logic Sampling

paper_content:

Bayesian belief networks and influence diagrams are attractive approaches for representing uncertain expert knowledge in coherent probabilistic form. But current algorithms for propagating updates are either restricted to singly connected networks (Chow trees), as the scheme of Pearl and Kim, or they are liable to exponential complexity when dealing with multiply connected networks. Probabilistic logic sampling is a new scheme employing stochastic simulation which can make probabilistic inferences in large, multiply connected networks, with an arbitrary degree of precision controlled by the sample size. A prototype implementation, named Pulse, is illustrated, which provides efficient methods to estimate conditional probabilities, perform systematic sensitivity analysis, and compute evidence weights to explain inferences.
---
paper_title: Learning Factorizations in Estimation of Distribution Algorithms Using Affinity Propagation

paper_content:

Estimation of distribution algorithms (EDAs) that use marginal product model factorizations have been widely applied to a broad range of mainly binary optimization problems. In this paper, we introduce the affinity propagation EDA (AffEDA) which learns a marginal product model by clustering a matrix of mutual information learned from the data using a very efficient message-passing algorithm known as affinity propagation. The introduced algorithm is tested on a set of binary and nonbinary decomposable functions and using a hard combinatorial class of problem known as the HP protein model. The results show that the algorithm is a very efficient alternative to other EDAs that use marginal product model factorizations such as the extended compact genetic algorithm (ECGA) and improves the quality of the results achieved by ECGA when the cardinality of the variables is increased.
---
paper_title: An EDA based on local markov property and gibbs sampling

paper_content:

The key ideas behind most of the recently proposed Markov networks based EDAs were to factorise the joint probability distribution in terms of the cliques in the undirected graph. As such, they made use of the global Markov property of the Markov network. Here we presents a Markov Network based EDA that exploits Gibbs sampling to sample from the Local Markov property, the Markovianity, and does not directly model the joint distribution. We call it Markovianity based Optimisation Algorithm. Some initial results on the performance of the proposed algorithm shows that it compares well with other Bayesian network based EDAs.
---
paper_title: The Bivariate Marginal Distribution Algorithm

paper_content:

The paper deals with the Bivariate Marginal Distribution Algorithm (BMDA). BMDA is an extension of the Univariate Marginal Distribution Algorithm (UMDA). It uses the pair gene dependencies in order to improve algorithms that use simple univariate marginal distributions. BMDA is a special case of the Factorization Distribution Algorithm, but without any problem specific knowledge in the initial stage. The dependencies are being discovered during the optimization process itself. In this paper BMDA is described in detail. BMDA is compared to different algorithms including the simple genetic algorithm with different crossover methods and UMDA. For some fitness functions the relation between problem size and the number of fitness evaluations until convergence is shown.
---
paper_title: Linkage Problem, Distribution Estimation, and Bayesian Networks

paper_content:

This paper proposes an algorithm that uses an estimation of the joint distribution of promising solutions in order to generate new candidate solutions. The algorithm is settled into the context of genetic and evolutionary computation and the algorithms based on the estimation of distributions. The proposed algorithm is called the Bayesian Optimization Algorithm (BOA). To estimate the distribution of promising solutions, the techniques for modeling multivariate data by Bayesian networks are used. The BOA identifies, reproduces, and mixes building blocks up to a specified order. It is independent of the ordering of the variables in strings representing the solutions. Moreover, prior information about the problem can be incorporated into the algorithm, but it is not essential. First experiments were done with additively decomposable problems with both nonoverlapping as well as overlapping building blocks. The proposed algorithm is able to solve all but one of the tested problems in linear or close to linear time with respect to the problem size. Except for the maximal order of interactions to be covered, the algorithm does not use any prior knowledge about the problem. The BOA represents a step toward alleviating the problem of identifying and mixing building blocks correctly to obtain good solutions for problems with very limited domain information.
---
paper_title: Learning Bayesian Networks: The Combination of Knowledge and Statistical Data

paper_content:

We describe a Bayesian approach for learning Bayesian networks from a combination of prior knowledge and statistical data. First and foremost, we develop a methodology for assessing informative priors needed for learning. Our approach is derived from a set of assumptions made previously as well as the assumption oflikelihood equivalence, which says that data should not help to discriminate network structures that represent the same assertions of conditional independence. We show that likelihood equivalence when combined with previously made assumptions implies that the user's priors for network parameters can be encoded in a single Bayesian network for the next case to be seen—aprior network—and a single measure of confidence for that network. Second, using these priors, we show how to compute the relative posterior probabilities of network structures given data. Third, we describe search methods for identifying network structures with high posterior probabilities. We describe polynomial algorithms for finding the highest-scoring network structures in the special case where every node has at mostk=1 parent. For the general case (k>1), which is NP-hard, we review heuristic search algorithms including local search, iterative local search, and simulated annealing. Finally, we describe a methodology for evaluating Bayesian-network learning algorithms, and apply this approach to a comparison of various approaches.
---
paper_title: Learning Bayesian networks: the combination of knowledge and statistical data

paper_content:

We describe scoring metrics for learning Bayesian networks from a combination of user knowledge and statistical data. We identify two important properties of metrics, which we call event equivalence and parameter modularity. These properties have been mostly ignored, but when combined, greatly simplify the encoding of a user's prior knowledge. In particular, a user can express his knowledge--for the most part--as a single prior Bayesian network for the domain.
---
paper_title: Dependency trees, permutations, and quadratic assignment problem

paper_content:

This paper describes and analyzes an estimation of distribution algorithm based on dependency tree models (dtEDA), which can explicitly encode probabilistic models for permutations. dtEDA is tested on deceptive ordering problems and a number of instances of the quadratic assignment problem. The performance of dtEDA is compared to that of the standard genetic algorithm with the partially matched crossover (PMX) and the linear order crossover (LOX). In the quadratic assignment problem, the robust tabu search is also included in the comparison.
---
paper_title: Solving the Traveling Salesman Problem with EDAs

paper_content:

In this chapter we present an approach for solving the Traveling Sales man Problem using Estimation of Distribution Algorithms (EDAs). This approach is based on using discrete and continuous EDAs to find the best possible solution. We also present a method in which domain knowledge (based on local search) is combined with EDAs to find better solutions. We show experimental results obtained on several standard examples for discrete and continuous EDAs both alone and combined with a heuristic local search.
---
paper_title: Probabilistic Model-Building Genetic Algorithms in Permutation Representation Domain Using Edge Histogram

paper_content:

Recently, there has been a growing interest in developing evolutionary algorithms based on probabilistic modeling. In this scheme, the offspring population is generated according to the estimated probability density model of the parent instead of using recombination and mutation operators. In this paper, we have proposed probabilistic model-building genetic algorithms (PMBGAs) in permutation representation domain using edge histogram based sampling algorithms (EHBSAs). Two types of sampling algorithms, without template (EHBSA/WO) and with template (EHBSA/WT), are presented. The results were tested in the TSP and showed EHBSA/WT worked fairly well with a small population size in the test problems used. It also worked better than well-known traditional two-parent recombination operators.
---
paper_title: Genetic Algorithms and Random Keys for Sequencing and Optimization

paper_content:

In this paper we present a general genetic algorithm to address a wide variety of sequencing and optimization problems including multiple machine scheduling, resource allocation, and the quadratic assignment problem. When addressing such problems, genetic algorithms typically have difficulty maintaining feasibility from parent to offspring. This is overcome with a robust representation technique called random keys . Computational results are shown for multiple machine scheduling, resource allocation, and quadratic assignment problems. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
---
paper_title: Getting the best of both worlds: discrete and continuous genetic and evolutionary algorithms in concert

paper_content:

This paper describes an evolutionary algorithm for optimization of continuous problems that combines advanced recombination techniques for discrete representations with advanced mutation techniques for continuous representations. Discretization is used to transform solutions between the discrete and continuous domains. The proposed algorithm combines the strengths of purely continuous and purely discrete approaches and eliminates some of their disadvantages. The paper tests the proposed algorithm with the recombination operator of the Bayesian optimization algorithm, σ-self-adaptive mutation, and three discretization methods. The empirical results on three problems suggest that the tested variant of the algorithm scales up well on all tested problems, indicating good scalability over a broad range of continuous problems.
---
paper_title: Problem Definitions and Evaluation Criteria for the CEC 2005 Special Session on Real-Parameter Optimization

paper_content:

An elevating conveyor having a first endless belt entrained around a plurality of spaced support or guide drums for elevating material through an elevating section to a discharge station and a second endless loading belt also entrained around guide drums to cooperate with the first belt at least where a loading station and the elevating section merge so that in this vicinity the belts are in overlying relationship with each other so that material on the upper surface of one belt is held on the surface by the other belt. The two belts are moved at similar speeds in the same direction and a fixed plate cooperates with the first belt in the elevating section so that material located between the belt and plate is elevated to the discharge station by upward movement of the first belt through the elevating section. The conveyor may be of C, L or Z shape and the first belt preferably has upstanding side walls, the top faces of which bear against low friction material supported on the plate.
---
paper_title: Adaptive discretization for probabilistic model building genetic algorithms

paper_content:

This paper proposes an adaptive discretization method, called Split-on-Demand (SoD), to enable the probabilistic model building genetic algorithm (PMBGA) to solve optimization problems in the continuous domain. The procedure, effect, and usage of SoD are described in detail. As an example, the integration of SoD and the extended compact genetic algorithm (ECGA), named real-coded ECGA (rECGA), is presented and numerically examined. The experimental results indicate that rECGA works well and SoD is effective. The behavior of SoD is analyzed and discussed, followed by the potential future work for SoD.
---
paper_title: Enabling the Extended Compact Genetic Algorithm for Real-Parameter Optimization by Using Adaptive Discretization

paper_content:

An adaptive discretization method, called split-on-demand (SoD), enables estimation of distribution algorithms (EDAs) for discrete variables to solve continuous optimization problems. SoD randomly splits a continuous interval if the number of search points within the interval exceeds a threshold, which is decreased at every iteration. After the split operation, the nonempty intervals are assigned integer codes, and the search points are discretized accordingly. As an example of using SoD with EDAs, the integration of SoD and the extended compact genetic algorithm (ECGA) is presented and numerically examined. In this integration, we adopt a local search mechanism as an optional component of our back end optimization engine. As a result, the proposed framework can be considered as a memetic algorithm, and SoD can potentially be applied to other memetic algorithms. The numerical experiments consist of two parts: (1) a set of benchmark functions on which ECGA with SoD and ECGA with two well-known discretization methods: the fixed-height histogram (FHH) and the fixed-width histogram (FWH) are compared; (2) a real-world application, the economic dispatch problem, on which ECGA with SoD is compared to other methods. The experimental results indicate that SoD is a better discretization method to work with ECGA. Moreover, ECGA with SoD works quite well on the economic dispatch problem and delivers solutions better than the best known results obtained by other methods in existence.
---
paper_title: Evolutionary Algorithm Using Marginal Histogram Models Continuous Domain

paper_content:

Recently, there has been a growing interest in developing evolutionary algorithms based on probabilistic modeling. In this scheme, the offspring population is generated according to the estimated probability density model of the parents instead of using recombination and mutation operators. In this paper, we propose an evolutionary algorithm using a marginal histogram to model the parent population in a continuous domain. We propose two types of marginal histogram models: the fixed-width histogram (FWH) and the fixed-height histogram (FHH). The results showed that both models worked fairly well on test functions with no or weak interactions among variables. Especially, FHH could find the global optimum with very high accuracy effectively and showed good scale-up with the problem size.
---
paper_title: Real-valued Evolutionary Optimization using a Flexible Probability Density Estimator

paper_content:

Population-Based Incremental Learning (PBIL) is an abstraction of a genetic algorithm, which solves optimization problems by explicitly constructing a probabilistic model of the promising regions of the search space. At each iteration the model is used to generate a population of candidate solutions and is itself modified in response to these solutions. Through the extension of PBIL to Real-valued search spaces, a more powerful and general algorithmic framework arises which enables the use of arbitrary probability density estimation techniques in evolutionary optimization. To illustrate the usefulness of the framework, we propose and implement an evolutionary algorithm which uses a finite Adaptive Gaussian mixture model density estimator. This method offers considerable power and flexibility in the forms of the density which can be effectively modeled. We discuss the general applicability of the framework, and suggest that future work should lead to the development of better evolutionary optimization algorithms.
---
paper_title: Real-Coded Bayesian Optimization Algorithm: Bringing the Strength of BOA into the Continuous World

paper_content:

This paper describes a continuous estimation of distribution algorithm (EDA) to solve decomposable, real-valued optimization problems quickly, accurately, and reliably. This is the real-coded Bayesian optimization algorithm (rBOA). The objective is to bring the strength of (discrete) BOA to bear upon the area of real-valued optimization. That is, the rBOA must properly decompose a problem, efficiently fit each subproblem, and effectively exploit the results so that correct linkage learning even on nonlinearity and probabilistic building-block crossover (PBBC) are performed for real-valued multivariate variables. The idea is to perform a Bayesian factorization of a mixture of probability distributions, find maximal connected subgraphs (i.e. substructures) of the Bayesian factorization graph (i.e., the structure of a probabilistic model), independently fit each substructure by a mixture distribution estimated from clustering results in the corresponding partial-string space (i.e., subspace, subproblem), and draw the offspring by an independent subspace-based sampling. Experimental results show that the rBOA finds, with a sublinear scale-up behavior for decomposable problems, a solution that is superior in quality to that found by a mixed iterative density-estimation evolutionary algorithm (mIDEA) as the problem size grows. Moreover, the rBOA generally outperforms the mIDEA on well-known benchmarks for real-valued optimization.
---
paper_title: A Mixed Bayesian Optimization Algorithm with variance adaptation

paper_content:

This paper presents a hybrid evolutionary optimization strategy combining the Mixed Bayesian Optimization Algorithm (MBOA) with variance adaptation as implemented in Evolution Strategies. This new approach is intended to circumvent some of the deficiences of MBOA with unimodal functions and to enhance its adaptivity. The Adaptive MBOA algorithm - AMBOA - is compared with the Covariance Matrix Adaptation Evolution Strategy (CMA-ES). The comparison shows that, in continuous domains, AMBOA is more efficient than the original MBOA algorithm and its performance on separable unimodal functions is comparable to that of CMA-ES.
---
paper_title: Grammar model-based program evolution

paper_content:

In evolutionary computation, genetic operators, such as mutation and crossover, are employed to perturb individuals to generate the next population. However these fixed, problem independent genetic operators may destroy the sub-solution, usually called building blocks, instead of discovering and preserving them. One way to overcome this problem is to build a model based on the good individuals, and sample this model to obtain the next population. There is a wide range of such work in genetic algorithms; but because of the complexity of the genetic programming (GP) tree representation, little work of this kind has been done in GP. In this paper, we propose a new method, grammar model-based program evolution (GMPE) to evolved GP program. We replace common GP genetic operators with a probabilistic context-free grammar (SCFG). In each generation, an SCFG is learnt, and a new population is generated by sampling this SCFG model. On two benchmark problems we have studied, GMPE significantly outperforms conventional GP, learning faster and more reliably.
---
paper_title: An information measure for classification

paper_content:

1. The class to which each thing belongs. 2. The average properties of each class. 3. The deviations of each thing from the average properties of its parent class. If the things are found to be concentrated in a small area of the region of each class in the measurement space then the deviations will be small, and with reference to the average class properties most of the information about a thing is given by naming the class to which it belongs. In this case the information may be recorded much more briefly than if a classification had not been used. We suggest that the best classification is that which results in the briefest recording of all the attribute information. In this context, we will regard the measurements of each thing as being a message about that thing. Shannon (1948) showed that where messages may be regarded as each nominating the occurrence of a particular event among a universe of possible events, the information needed to record a series of such messages is minimised if the messages are encoded so that the length of each message is proportional to minus the logarithm of the relative frequency of occurrence of the event which it nominates. The information required is greatest when all frequencies are equal. The messages here nominate the positions in measurement space of the 5 1 points representing the attributes of the things. If the expected density of points in the measurement space is everywhere uniform, the positions of the points cannot be encoded more briefly than by a simple list of the measured values. However, if the expected density is markedly non-uniform, application
---
paper_title: Avoiding the Bloat with Stochastic Grammar-based Genetic Programming

paper_content:

The application of Genetic Programming to the discovery of empirical laws is often impaired by the huge size of the search space, and consequently by the computer resources needed. In many cases, the extreme demand for memory and CPU is due to the massive growth of non-coding segments, the introns. The paper presents a new program evolution framework which combines distribution-based evolution in the PBIL spirit, with grammar-based genetic programming; the information is stored as a probability distribution on the grammar rules, rather than in a population. Experiments on a real-world like problem show that this approach gives a practical solution to the problem of introns growth.
---
paper_title: Genetic Programming: On the Programming of Computers by Means of Natural Selection

paper_content:

Background on genetic algorithms, LISP, and genetic programming hierarchical problem-solving introduction to automatically-defined functions - the two-boxes problem problems that straddle the breakeven point for computational effort Boolean parity functions determining the architecture of the program the lawnmower problem the bumblebee problem the increasing benefits of ADFs as problems are scaled up finding an impulse response function artificial ant on the San Mateo trail obstacle-avoiding robot the minesweeper problem automatic discovery of detectors for letter recognition flushes and four-of-a-kinds in a pinochle deck introduction to biochemistry and molecular biology prediction of transmembrane domains in proteins prediction of omega loops in proteins lookahead version of the transmembrane problem evolutionary selection of the architecture of the program evolution of primitives and sufficiency evolutionary selection of terminals evolution of closure simultaneous evolution of architecture, primitive functions, terminals, sufficiency, and closure the role of representation and the lens effect. Appendices: list of special symbols list of special functions list of type fonts default parameters computer implementation annotated bibliography of genetic programming electronic mailing list and public repository.
---
paper_title: Probabilistic Incremental Program Evolution: Stochastic Search Through Program Space

paper_content:

Probabilistic Incremental Program Evolution (PIPE) is a novel technique for automatic program synthesis. We combine probability vector coding of program instructions [Schmidhuber, 1997], Population-Based Incremental Learning (PBIL) [Baluja and Caruana, 1995] and tree-coding of programs used in variants of Genetic Programming (GP) [Cramer, 1985; Koza, 1992]. PIPE uses a stochastic selection method for successively generating better and better programs according to an adaptive "probabilistic prototype tree". No crossover operator is used. We compare PIPE to Koza's GP variant on a function regression problem and the 6-bit parity problem.
---
paper_title: Combining Convergence and Diversity in Evolutionary Multiobjective Optimization

paper_content:

Over the past few years, the research on evolutionary algorithms has demonstrated their niche in solving multiobjective optimization problems, where the goal is to find a number of Pareto-optimal solutions in a single simulation run. Many studies have depicted different ways evolutionary algorithms can progress towards the Pareto-optimal set with a widely spread distribution of solutions. However, none of the multiobjective evolutionary algorithms (MOEAs) has a proof of convergence to the true Pareto-optimal solutions with a wide diversity among the solutions. In this paper, we discuss why a number of earlier MOEAs do not have such properties. Based on the concept of e-dominance, new archiving strategies are proposed that overcome this fundamental problem and provably lead to MOEAs that have both the desired convergence and distribution properties. A number of modifications to the baseline algorithm are also suggested. The concept of e-dominance introduced in this paper is practical and should make the proposed algorithms useful to researchers and practitioners alike.
---
paper_title: A new epsilon-dominance hierarchical Bayesian optimization algorithm for large multiobjective monitoring network design problems

paper_content:

Abstract This study focuses on the development of a next generation multiobjective evolutionary algorithm (MOEA) that can learn and exploit complex interdependencies and/or correlations between decision variables in monitoring design applications to provide more robust performance for large problems (defined in terms of both the number of objectives and decision variables). The proposed MOEA is termed the epsilon-dominance hierarchical Bayesian optimization algorithm ( e -hBOA), which is representative of a new class of probabilistic model building evolutionary algorithms. The e -hBOA has been tested relative to a top-performing traditional MOEA, the epsilon-dominance nondominated sorted genetic algorithm II ( e -NSGAII) for solving a four-objective LTM design problem. A comprehensive performance assessment of the e -NSGAII and various configurations of the e -hBOA have been performed for both a 25 well LTM design test case (representing a relatively small problem with over 33 million possible designs), and a 58 point LTM design test case (with over 2.88 × 10 17 possible designs). The results from this comparison indicate that the model building capability of the e -hBOA greatly enhances its performance relative to the e -NSGAII, especially for large monitoring design problems. This work also indicates that decision variable interdependencies appear to have a significant impact on the overall mathematical difficulty of the monitoring network design problem.
---
paper_title: A Mixed Bayesian Optimization Algorithm with variance adaptation

paper_content:

This paper presents a hybrid evolutionary optimization strategy combining the Mixed Bayesian Optimization Algorithm (MBOA) with variance adaptation as implemented in Evolution Strategies. This new approach is intended to circumvent some of the deficiences of MBOA with unimodal functions and to enhance its adaptivity. The Adaptive MBOA algorithm - AMBOA - is compared with the Covariance Matrix Adaptation Evolution Strategy (CMA-ES). The comparison shows that, in continuous domains, AMBOA is more efficient than the original MBOA algorithm and its performance on separable unimodal functions is comparable to that of CMA-ES.
---
paper_title: Comparative analysis of multiobjective evolutionary algorithms for random and correlated instances of multiobjective d-dimensional knapsack problems

paper_content:

This study analyzes multiobjective d-dimensional knapsack problems (MOd-KP) within a comparative analysis of three multiobjective evolutionary algorithms (MOEAs): the e-nondominated sorted genetic algorithm II (e-NSGAII), the strength Pareto evolutionary algorithm 2 (SPEA2) and the e-nondominated hierarchical Bayesian optimization algorithm (e-hBOA). This study contributes new insights into the challenges posed by correlated instances of the MOd-KP that better capture the decision interdependencies often present in real world applications. A statistical performance analysis of the algorithms uses the unary e-indicator, the hypervolume indicator and success rate plots to demonstrate their relative effectiveness, efficiency, and reliability for the MOd-KP instances analyzed. Our results indicate that the e-hBOA achieves superior performance relative to e-NSGAII and SPEA2 with increasing number of objectives, number of decisions, and correlative linkages between the two. Performance of the e-hBOA suggests that probabilistic model building evolutionary algorithms have significant promise for expanding the size and scope of challenging multiobjective problems that can be explored.
---
paper_title: Bayesian Optimization Algorithms for Multi-objective Optimization

paper_content:

In recent years, several researchers have concentrated on using probabilistic models in evolutionary algorithms. These Estimation Distribution Algorithms (EDA) incorporate methods for automated learning of correlations between variables of the encoded solutions. The process of sampling new individuals from a probabilistic model respects these mutual dependencies such that disruption of important building blocks is avoided, in comparison with classical recombination operators. The goal of this paper is to investigate the usefulness of this concept in multi-objective optimization, where the aim is to approximate the set of Pareto-optimal solutions. We integrate the model building and sampling techniques of a special EDA called Bayesian Optimization Algorithm, based on binary decision trees, into an evolutionary multi-objective optimizer using a special selection scheme. The behavior of the resulting Bayesian Multi-objective Optimization Algorithm (BMOA) is empirically investigated on the multi-objective knapsack problem.
---
paper_title: Multi-Objective Bayesian Optimization Algorithm

paper_content:

Recently, signi cant development in the theory and design of competent genetic algorithms (GAs) has been achieved. By competent GA we mean genetic algorithms that can solve boundedly diAEcult problems quickly, accurately, and reliably. However, most of the existing competent GAs focus only on single-objective optimization although many real-world problems contain more than one objective. Independently of the development of competent genetic algorithms, a number of approaches to solve such multiobjective problems have been proposed. However, there has been little or no e ort to develop competent multiobjective operators that eAEciently identify, propagate, and combine important partial solutions of the problem at hand.
---
paper_title: Multi-objective Optimization with the Naive MIDEA

paper_content:

Summary. EDAs have been shown to perform well on a wide variety of single-objective optimization problems, for binary and real-valued variables. In this chapter we look into the extension of the EDA paradigm to multi-objective optimization. To this end, we focus the chapter around the introduction of a simple, but effective, EDA for multi-objective optimization: the naive MIDEA (mixture-based multi-objective iterated density-estimation evolutionary algorithm). The probabilistic model in this specific algorithm is a mixture distribution. Each component in the mixture is a univariate factorization. As will be shown in this chapter, mixture distributions allow for wide-spread exploration of a multi-objective front, whereas most operators focus on a specific part of the multi-objective front. This wide-spread exploration aids the important preservation of diversity in multi-objective optimization. To further improve and maintain the diversity that is obtained by the mixture distribution, a specialized diversity preserving selection operator is used in the naive MIDEA. We verify the effectiveness of the naive MIDEA in two different problem domains and compare it with two other well-known efficient multi-objective evolutionary algorithms (MOEAs).
---
paper_title: Multiobjective hBOA, clustering, and scalability

paper_content:

This paper describes a scalable algorithm for solving multiobjective decomposable problems by combining the hierarchical Bayesian optimization algorithm (hBOA) with the nondominated sorting genetic algorithm (NSGA-II) and clustering in the objective space. It is first argued that for good scalability, clustering or some other form of niching in the objective space is necessary and the size of each niche should be approximately equal. Multiobjective hBOA (mohBOA) is then described that combines hBOA, NSGA-II and clustering in the objective space. The algorithm mohBOA differs from the multiobjective variants of BOA and hBOA proposed in the past by including clustering in the objective space and allocating an approximately equally sized portion of the population to each cluster. The algorithm mohBOA is shown to scale up well on a number of problems on which standard multiobjective evolutionary algorithms perform poorly.
---
paper_title: Optimization of Computer Simulation Models with Rare Events

paper_content:

Discrete event simulation systems (DESS) are widely used in many diverse areas such as computer-communication networks, flexible manufacturing systems, project evaluation and review techniques (PERT), and flow networks. Because of their complexity, such systems are typically analyzed via Monte Carlo simulation methods. This paper deals with optimization of complex computer simulation models involving rare events. A classic example is to find an optimal (s, S) policy in a multi-item, multicommodity inventory system, when quality standards require the backlog probability to be extremely small. Our approach is based on change of the probability measure techniques, also called likelihood ratio (LR) and importance sampling (IS) methods. Unfortunately, for arbitrary probability measures the LR estimators and the resulting optimal solution often tend to be unstable and may have large variances. Therefore, the choice of the corresponding importance sampling distribution and in particular its parameters in an optimal way is an important task. We consider the case where the IS distribution comes from the same parametric family as the original (true) one and use the stochastic counterpart method to handle simulation based optimization models. More specifically, we use a two-stage procedure: at the first stage we identify (estimate) the optimal parameter vector at the IS distribution, while at the second stage we estimate the optimal solution of the underlying constrained optimization problem. Particular emphasis will be placed on estimation of rare events and on integration of the associated performance function into stochastic optimization programs. Supporting numerical results are provided as well.
---
paper_title: Genetic Algorithms and the Optimal Allocation of Trials

paper_content:

This study gives a formal setting to the difficult optimization problems characterized by the conjunction of (1) substantial complexity and initial uncertainty, (2) the necessity of acquiring new i...
---
paper_title: RM-MEDA: A Regularity Model-Based Multiobjective Estimation of Distribution Algorithm

paper_content:

Under mild conditions, it can be induced from the Karush-Kuhn-Tucker condition that the Pareto set, in the decision space, of a continuous multiobjective optimization problem is a piecewise continuous (m - 1)-D manifold, where m is the number of objectives. Based on this regularity property, we propose a regularity model-based multiobjective estimation of distribution algorithm (RM-MEDA) for continuous multiobjective optimization problems with variable linkages. At each generation, the proposed algorithm models a promising area in the decision space by a probability distribution whose centroid is a (m - 1)-D piecewise continuous manifold. The local principal component analysis algorithm is used for building such a model. New trial solutions are sampled from the model thus built. A nondominated sorting-based selection is used for choosing solutions for the next generation. Systematic experiments have shown that, overall, RM-MEDA outperforms three other state-of-the-art algorithms, namely, GDE3, PCX-NSGA-II, and MIDEA, on a set of test instances with variable linkages. We have demonstrated that, compared with GDE3, RM-MEDA is not sensitive to algorithmic parameters, and has good scalability to the number of decision variables in the case of nonlinear variable linkages. A few shortcomings of RM-MEDA have also been identified and discussed in this paper.
---
paper_title: Incorporating a priori Knowledge in Probabilistic-Model Based Optimization

paper_content:

This invention provides heat curable compositions comprising a high viscosity, peroxide curable polydiorganosiloxane, a relatively low viscosity liquid diorganoalkenylsiloxy endblocked polydiorganosiloxane, a reinforcing filler and an effective amount of a vinyl specific organic peroxide. The tensile and recovery properties of the cured elastomer are optimized when the concentration of diorganoalkenylsiloxy groups on the liquid polydiorganosiloxane relative to the concentration of repeating units in the peroxide curable polydiorganosiloxane is within specified limits.
---
paper_title: Using Previous Models to Bias Structural Learning in the Hierarchical BOA

paper_content:

Estimation of distribution algorithms (EDAs) are stochastic optimization techniques that explore the space of potential solutions by building and sampling explicit probabilistic models of promising candidate solutions. While the primary goal of applying EDAs is to discover the global optimum or at least its accurate approximation, besides this, any EDA provides us with a sequence of probabilistic models, which in most cases hold a great deal of information about the problem. Although using problem-specific knowledge has been shown to significantly improve performance of EDAs and other evolutionary algorithms, this readily available source of problem-specific information has been practically ignored by the EDA community. This paper takes the first step toward the use of probabilistic models obtained by EDAs to speed up the solution of similar problems in the future. More specifically, we propose two approaches to biasing model building in the hierarchical Bayesian optimization algorithm (hBOA) based on knowledge automatically learned from previous hBOA runs on similar problems. We show that the proposed methods lead to substantial speedups and argue that the methods should work well in other applications that require solving a large number of problems with similar structure.
---
paper_title: Searching for Ground States of Ising Spin Glasses with Hierarchical BOA and Cluster Exact Approximation

paper_content:

Summary. This chapter applies the hierarchical Bayesian optimization algorithm (hBOA) to the problem of finding ground states of Ising spin glasses with ±J and Gaussian couplings in two and three dimensions. The performance of hBOA is compared to that of the simple genetic algorithm (GA) and the univariate marginal distribution algorithm (UMDA). The performance of all tested algorithms is improved by incorporating a deterministic hill climber based on single-bit flips. The results show that hBOA significantly outperforms GA and UMDA on a broad spectrum of spin glass instances. Cluster exact approximation (CEA) is then described and incorporated into hBOA and GA to improve their efficiency. The results show that CEA enables all tested algorithms to solve larger spin glass instances and that hBOA significantly outperforms other compared algorithms even in this case.
---
paper_title: Adaptive Estimation of Distribution Algorithms

paper_content:

Estimation of distribution algorithms (EDAs) are evolutionary methods that use probabilistic models instead of genetic operators to lead the search. Most of current proposals on EDAs do not incorporate adaptive techniques. Usually, the class of probabilistic model employed as well as the learning and sampling methods are static. In this paper, we present a general framework for introducing adaptation in EDAs. This framework allows the possibility of changing the class of probabilistic models during the evolution. We present a number of measures, and techniques that can be used to evaluate the effect of the EDA components in order to design adaptive EDAs. As a case of study we present an adaptive EDA that combines different classes of probabilistic models and sampling methods. The algorithm is evaluated in the solution of the satisfiability problem.
---
paper_title: Difficulty of linkage learning in estimation of distribution algorithms

paper_content:

This paper investigates the difficulty of linkage learning, an essential core, in EDAs. Specifically, it examines allelicpairwise independent functions including the parity, paritywith-trap, and Walsh-code functions. While the parity function was believed to be difficult for EDAs in previous work, our experiments indicate that it can be solved by CGA within a polynomial number of function evaluations to the problem size. Consequently, the apparently difficult paritywith-trap function can be easily solved by ECGA, even though the linkage model is incorrect. A convergence model for CGA on the parity function is also derived to verify and support the empirical findings. Finally, this paper proposes a socalled Walsh-code function, which is more difficult than the parity function. Although the proposed function does deceive the linkage-learning mechanism in most EDAs, EDAs are still able to solve it to some extent.
---
paper_title: Efficient Linkage Discovery by Limited Probing

paper_content:

This paper addresses the problem of discovering the structure of a fitness function from binary strings to the reals under the assumption of bounded epistasis. Two loci (string positions) are epistatically linked if the effect of changing the allele (value) at one locus depends on the allele at the other locus. Similarly, a group of loci are epistatically linked if the effect of changing the allele at one locus depends on the alleles at all other loci of the group. Under the assumption that the size of such groups of loci are bounded, and assuming that the function is given only as a "black box function", this paper presents and analyzes a randomized algorithm that finds the complete epistatic structure of the function in the form of the Walsh coefficients of the function.
---
paper_title: Linkage Identification by Non-monotonicity Detection for Overlapping Functions

paper_content:

This paper presents the linkage identification by non-monotonicity detection (LIMD) procedure and its extension for overlapping functions by introducing the tightness detection (TD) procedure. The LIMD identifies linkage groups directly by performing order-2 simultaneous perturbations on a pair of loci to detect monotonicity/non-monotonicity of fitness changes. The LIMD can identify linkage groups with at most order of k when it is applied to O(2k) strings. The TD procedure calculates tightness of linkage between a pair of loci based on the linkage groups obtained by the LIMD. By removing loci with weak tightness from linkage groups, correct linkage groups are obtained for overlapping functions, which were considered difficult for linkage identification procedures.
---
paper_title: Why is parity hard for estimation of distribution algorithms?

paper_content:

We describe a k-bounded and additively separable test problem on which the hierarchical Bayesian Optimization Algorithm (hBOA) scales exponentially.
---
paper_title: Hierarchical Bayesian optimization algorithm: toward a new generation of evolutionary algorithms

paper_content:

Over the last few decades, genetic and evolutionary algorithms (GEAs) have been successfully applied to many problems of business, engineering, and science. This paper discusses probabilistic model-building genetic algorithms (PMBGAs), which are among the most important directions of current GEA research. PMBGAs replace traditional variation operators of GEAs by learning and sampling a probabilistic model of promising solutions. The paper describes two advanced PMBGAs: the Bayesian optimization algorithm (BOA), and the hierarchical BOA (hBOA). The paper argues that BOA and hBOA can solve an important class of nearly decomposable and hierarchical problems in a quadratic or subquadratic number of function evaluations with respect to the number of decision variables.
---
paper_title: Efficient and Accurate Parallel Genetic Algorithms

paper_content:

Preface. Acknowledgments. 1. Introduction. 2. The Gambler's Ruin and Population Sizing. 3. Master-Slave Parallel GAs. 4. Bounding Cases of GAs With Multiple Demes. 5. Markov Chain Models of Multiple Demes. 6. Migration Rates and Optimal Topologies. 7. Migration and Selection Pressure. 8. Fine-Grained and Hierarchical Parallel GAs. 9. Summary, Extensions, and Conclusions. References. Index.
---
paper_title: Design of Parallel Estimation of Distribution Algorithms

paper_content:

A long-lasting water-based paint having an exceptional resistance to both chemical and mechanical damage comprises a combination of acrylic resins as pigment binders. Flaked highly corrosion-resistant stainless steel, finely ground mica flakes, calcium carbonate and a small amount of zinc oxide are included in the pigment. The paint is prepared by adding at least approximately 60% of the acrylic resin into the paint after all of the pigment, substantially reducing the amount of air entrapped in the paint during mixing.
---
paper_title: Evaluation-relaxation schemes for genetic and evolutionary algorithms

paper_content:

Genetic and evolutionary algorithms have been increasingly applied to solve complex, large scale search problems with mixed success. Competent genetic algorithms have been proposed to solve hard problems quickly, reliably and accurately. They have rendered problems that were difficult to solve by the earlier GAs to be solvable, requiring only a subquadratic number of function evaluations. To facilitate solving large-scale complex problems, and to further enhance the performance of competent GAs, various efficiency-enhancement techniques have been developed. This study investigates one such class of efficiency-enhancement technique called evaluation relaxation. Evaluation-relaxation schemes replace a high-cost, low-error fitness function with a lowcost, high-error fitness function. The error in fitness functions comes in two flavors: Bias and variance. The presence of bias and variance in fitness functions is considered in isolation and strategies for increasing efficiency in both cases are developed. Specifically, approaches for choosing between two fitness functions with either differing variance or differing bias values have been developed. This thesis also investigates fitness inheritance as an evaluationrelaxation scheme. In fitness inheritance, the fitness values of some individuals are inherited from their parents rather than through a costly evaluation function, thereby reducing the total function-evaluation cost. Simple facetwise models have been derived to capture the dynamics in each case and have been verified with simple but illustrating empirical results. These models are also used to develop analytical framework to tune algorithm parameters to obtain maximum speed-up.
---
paper_title: Efficiency Enhancement of Genetic Algorithms via Building-Block-Wise Fitness Estimation

paper_content:

This paper studies fitness inheritance as an efficiency enhancement technique for a class of competent genetic algorithms called estimation distribution algorithms. Probabilistic models of important sub-solutions are developed to estimate the fitness of a proportion of individuals in the population, thereby avoiding computationally expensive function evaluations. The effect of fitness inheritance on the convergence time and population sizing are modeled and the speed-up obtained through inheritance is predicted. The results show that a fitness-inheritance mechanism which utilizes information on building-block fitnesses provides significant efficiency enhancement. For additively separable problems, fitness inheritance reduces the number of function evaluations to about half and yields a speed-up of about 1.75-2.25.
---
paper_title: Don’t Evaluate, Inherit

paper_content:

This paper studies fitness inheritance as an efficiency enhancement technique for genetic and evolutionary algorithms. Convergence and population-sizing models are derived and compared with experimental results. These models are optimized for greatest speed-up and the optimal inheritance proportion to obtain such a speed-up is derived. Results on OneMax problems show that when the inheritance effects are considered in the population-sizing model, the number of function evaluations are reduced by 20% with the use of fitness inheritance. Results indicate that for a fixed population size, the number of function evaluations can be reduced by 70% using a simple fitness inheritance technique.
---
paper_title: Efficient Genetic Algorithms Using Discretization Scheduling

paper_content:

In many applications of genetic algorithms, there is a tradeoff between speed and accuracy in fitness evaluations when evaluations use numerical methods with varying discretization. In these types of applications, the cost and accuracy vary from discretization errors when implicit or explicit quadrature is used to estimate the function evaluations. This paper examines discretization scheduling, or how to vary the discretization within the genetic algorithm in order to use the least amount of computation time for a solution of a desired quality. The effectiveness of discretization scheduling can be determined by comparing its computation time to the computation time of a GA using a constant discretization. There are three ingredients for the discretization scheduling: population sizing, estimated time for each function evaluation and predicted convergence time analysis. Idealized one- and two-dimensional experiments and an inverse groundwater application illustrate the computational savings to be achieved from using discretization scheduling.
---
paper_title: A Maximum Entropy Approach to Sampling in EDA – The Single Connected Case

paper_content:

The success of evolutionary algorithms, in particular Factorized Distribution Algorithms (FDA), for many pattern recognition tasks heavily depends on our ability to reduce the number of function evaluations.
---
paper_title: Designing Competent Mutation Operators via Probabilistic Model Building of Neighborhoods

paper_content:

This paper presents a competent selectomutative genetic algorithm (GA), that adapts linkage and solves hard problems quickly, reliably, and accurately. A probabilistic model building process is used to automatically identify key building blocks (BBs) of the search problem. The mutation operator uses the probabilistic model of linkage groups to find the best among competing building blocks. The competent selectomutative GA successfully solves additively separable problems of bounded difficulty, requiring only subquadratic number of function evaluations. The results show that for additively separable problems the probabilistic model building BB-wise mutation scales as \({\mathcal{O}}(2^km^{1.5})\), and requires \({\mathcal{O}}(\sqrt{k}\log m)\) less function evaluations than its selectorecombinative counterpart, confirming theoretical results reported elsewhere [1].
---
paper_title: Loopy Substructural Local Search for the Bayesian Optimization Algorithm

paper_content:

This paper presents a local search method for the Bayesian optimization algorithm (BOA) based on the concepts of substructural neighborhoods and loopy belief propagation. The probabilistic model of BOA, which automatically identifies important problem substructures, is used to define the topology of the neighborhoods explored in local search. On the other hand, belief propagation in graphical models is employed to find the most suitable configuration of conflicting substructures. The results show that performing loopy substructural local search (SLS) in BOA can dramatically reduce the number of generations necessary to converge to optimal solutions and thus provides substantial speedups.
---
paper_title: The effectiveness of mutation operation in the case of Estimation of Distribution Algorithms

paper_content:

The Estimation of Distribution Algorithms are a class of evolutionary algorithms which adopt probabilistic models to reproduce individuals in the next generation, instead of conventional crossover and mutation operators. In this paper, mutation operators are incorporated into Estimation of Distribution Algorithms in order to maintain the diversities in EDA populations. Two kinds of mutation operators are examined: a bitwise mutation operator and a mutation operator taking account into the probabilistic model. In experiments, we do not only compare the proposed methods with conventional EDAs on a few fitness functions but also analyze sampled probabilistic models by using KL-divergence. The experimental results shown in this paper elucidate that the mutation operator taking account into the probabilistic model improve the search ability of EDAs.
---
paper_title: Searching for Ground States of Ising Spin Glasses with Hierarchical BOA and Cluster Exact Approximation

paper_content:

Summary. This chapter applies the hierarchical Bayesian optimization algorithm (hBOA) to the problem of finding ground states of Ising spin glasses with ±J and Gaussian couplings in two and three dimensions. The performance of hBOA is compared to that of the simple genetic algorithm (GA) and the univariate marginal distribution algorithm (UMDA). The performance of all tested algorithms is improved by incorporating a deterministic hill climber based on single-bit flips. The results show that hBOA significantly outperforms GA and UMDA on a broad spectrum of spin glass instances. Cluster exact approximation (CEA) is then described and incorporated into hBOA and GA to improve their efficiency. The results show that CEA enables all tested algorithms to solve larger spin glass instances and that hBOA significantly outperforms other compared algorithms even in this case.
---
paper_title: A parallel framework for loopy belief propagation

paper_content:

There are many innovative proposals introduced in the literature under the evolutionary computation field, from which estimation of distribution algorithms (EDAs) is one of them. Their main characteristic is the use of probabilistic models to represent the (in) dependencies between the variables of a concrete problem. Such probabilistic models have also been applied to the theoretical analysis of EDAs, providing a platform for the implementation of other optimization methods that can be incorporated into the EDA framework. Some of these methods, typically used for probabilistic inference, are belief propagation algorithms. In this paper we present a parallel approach for one of these inference-based algorithms, the loopy belief propagation algorithm for factor graphs. Our parallel implementation was designed to provide an algorithm that can be executed in clusters of computers or multiprocessors in order to reduce the total execution time. In addition, this framework was also designed as a flexible tool where many parameters, such as scheduling rules or stopping criteria, can be adjusted according to the requirements of each particular experiment and problem.
---
paper_title: The Factorized Distribution Algorithm and the Minimum Relative Entropy Principle

paper_content:

We assume that the function to be optimized is additively decomposed (ADF). Then the interaction graph $G_{ADF}$ can be used to compute exact or approximate factorizations. For many practical problems only approximate factorizations lead to efficient optimization algorithms. The relation between the approximation used by the FDA algorithm and the minimum relative entropy principle is discussed. A new algorithm is presented, derived from the Bethe-Kikuchi approach in statistical physics. It minimizes the relative entropy to a Boltzmann distribution with fixed $eta$. We shortly compare different factorizations and algorithms within the FDA software. We use 2-d Ising spin glass problems and Kaufman's n-k function as examples.
---
paper_title: Verification of the theory of genetic and evolutionary continuation

paper_content:

A few cycles of an input signal are correlated, or compared, with a few cycles of the input signal received at a previous interval and the interval is varied when correlation, or a positive comparison, has been obtained with the apparatus providing an output or detection signal after a predetermined number of correlations have occurred.
---
paper_title: Let's Get Ready to Rumble: Crossover Versus Mutation Head to Head

paper_content:

This paper analyzes the relative advantages between crossover and mutation on a class of deterministic and stochastic additively separable problems. This study assumes that the recombination and mutation operators have the knowledge of the building blocks (BBs) and effectively exchange or search among competing BBs. Facetwise models of convergence time and population sizing have been used to determine the scalability of each algorithm. The analysis shows that for additively separable deterministic problems, the BB-wise mutation is more efficient than crossover, while the crossover outperforms the mutation on additively separable problems perturbed with additive Gaussian noise. The results show that the speed-up of using BB-wise mutation on deterministic problems is \({\mathcal{O}}(\sqrt{k}\log m)\), where k is the BB size, and m is the number of BBs. Likewise, the speed-up of using crossover on stochastic problems with fixed noise variance is \({\mathcal{O}}(m\sqrt{k}/\log m)\).
---
paper_title: Using Time Efficiently: Genetic-Evolutionary Algorithms and the Continuation Problem

paper_content:

This paper develops a macro-level theory of efficient time utilization for genetic and evolutionary algorithms. Building on population sizing results that estimate the critical relationship between solution quality and time, the paper considers the tradeoff between large populations that converge in a single convergence epoch and smaller populations with multiple epochs. Two models suggest a link between the salience structure of a problem and the appropriate population-time configuration for best efficiency.
---
paper_title: Evolutionary optimization and the estimation of search distributions with applications to graph bipartitioning

paper_content:

Abstract We present a theory of population based optimization methods using approximations of search distributions. We prove convergence of the search distribution to the global optima for the factorized distribution algorithm (FDA) if the search distribution is a Boltzmann distribution and the size of the population is large enough. Convergence is defined in a strong sense––the global optima are attractors of a dynamical system describing mathematically the algorithm. We investigate an adaptive annealing schedule and show its similarity to truncation selection. The inverse temperature β is changed inversely proportionally to the standard deviation of the population. We extend FDA by using a Bayesian hyper-parameter. The hyper-parameter is related to mutation in evolutionary algorithms. We derive an upper bound on the hyper-parameter to ensure that FDA still generates the optima with high probability. We discuss the relation of the FDA approach to methods used in statistical physics to approximate a Boltzmann distribution and to belief propagation in probabilistic reasoning. In the last part are sparsely connected. Our empirical results are as good or even better than any other method used for this problem.
---
paper_title: Incorporating a priori Knowledge in Probabilistic-Model Based Optimization

paper_content:

This invention provides heat curable compositions comprising a high viscosity, peroxide curable polydiorganosiloxane, a relatively low viscosity liquid diorganoalkenylsiloxy endblocked polydiorganosiloxane, a reinforcing filler and an effective amount of a vinyl specific organic peroxide. The tensile and recovery properties of the cured elastomer are optimized when the concentration of diorganoalkenylsiloxy groups on the liquid polydiorganosiloxane relative to the concentration of repeating units in the peroxide curable polydiorganosiloxane is within specified limits.
---
paper_title: Hierarchical Bayesian optimization algorithm: toward a new generation of evolutionary algorithms

paper_content:

Over the last few decades, genetic and evolutionary algorithms (GEAs) have been successfully applied to many problems of business, engineering, and science. This paper discusses probabilistic model-building genetic algorithms (PMBGAs), which are among the most important directions of current GEA research. PMBGAs replace traditional variation operators of GEAs by learning and sampling a probabilistic model of promising solutions. The paper describes two advanced PMBGAs: the Bayesian optimization algorithm (BOA), and the hierarchical BOA (hBOA). The paper argues that BOA and hBOA can solve an important class of nearly decomposable and hierarchical problems in a quadratic or subquadratic number of function evaluations with respect to the number of decision variables.
---
paper_title: Using Previous Models to Bias Structural Learning in the Hierarchical BOA

paper_content:

Estimation of distribution algorithms (EDAs) are stochastic optimization techniques that explore the space of potential solutions by building and sampling explicit probabilistic models of promising candidate solutions. While the primary goal of applying EDAs is to discover the global optimum or at least its accurate approximation, besides this, any EDA provides us with a sequence of probabilistic models, which in most cases hold a great deal of information about the problem. Although using problem-specific knowledge has been shown to significantly improve performance of EDAs and other evolutionary algorithms, this readily available source of problem-specific information has been practically ignored by the EDA community. This paper takes the first step toward the use of probabilistic models obtained by EDAs to speed up the solution of similar problems in the future. More specifically, we propose two approaches to biasing model building in the hierarchical Bayesian optimization algorithm (hBOA) based on knowledge automatically learned from previous hBOA runs on similar problems. We show that the proposed methods lead to substantial speedups and argue that the methods should work well in other applications that require solving a large number of problems with similar structure.
---
paper_title: A problem - knowledge based evolutionary algorithm KBOA for hypergraph partitioning

paper_content:

A sintered titanium carbide tool steel composition is provided comprising by weight about 15% to 40% primary grains of titanium carbide dispersed through a steel matrix making up the balance, the composition of said steel matrix consisting essentially by weight of about 3% to 7% chromium, about 2% to 6% molybdenum, about 2% to 8% nickel, about 0.2% to 0.6% carbon and the balance essentially iron.
---
paper_title: Convergence Theory and Applications of the Factorized Distribution Algorithm

paper_content:

The paper investigates the optimization of additively decomposable functions (ADF) by a new evolutionary algorithm called Factorized Distribution Algorithm (FDA). FDA is based on a factorization of the distribution to generate search points. First separable ADFs are considered. These are mapped to generalized linear functions with metavariables defined for multiple alleles. The mapping transforms FDA into an Univariate Marginal Frequency Algorithm (UMDA). For UMDA the exact equation for the response to selection is.computed under the assumption of proportionate selection. For truncation selection an approximate equation for the time to convergence is used, derived from an analysis of the OneMax function. FDA is also numerically investigated for non separable functions. The time to convergence is very similar to separable ADFs. FDA outpe1iorms the genetic algorithm with recombination of strings by far.
---
paper_title: The gambler's ruin problem, genetic algorithms, and the sizing of populations

paper_content:

The paper presents a model for predicting the convergence quality of genetic algorithms. The model incorporates previous knowledge about decision making in genetic algorithms and the initial supply of building blocks in a novel way. The result is an equation that accurately predicts the quality of the solution found by a GA using a given population size. Adjustments for different selection intensities are considered and computational experiments demonstrate the effectiveness of the model.
---
paper_title: On The Supply Of Building Blocks

paper_content:

This study addresses the issue of building-block supply in the initial population. Facetwise models for supply of a single building block as well as for supply of all schemata in a partition have been developed. An estimate for the population size required to ensure the presence of all raw building blocks has been derived using these facetwise models. The facetwise models and the population-sizing estimate are verified with computational results.
---
paper_title: Population sizing for entropy-based model building in discrete estimation of distribution algorithms

paper_content:

This paper proposes a population-sizing model for entropy-based model building in discrete estimation of distribution algorithms. Specifically, the population size required for building an accurate model is investigated. The effect of selection pressure on population sizing is also preliminarily incorporated. The proposed model indicates that the population size required for building an accurate model scales as Θ(m log m), where m is the number of substructures of the given problem and is proportional to the problem size. Experiments are conducted to verify the derivations, and the results agree with the proposed model.
---
paper_title: Genetic Algorithms, Noise, and the Sizing of Populations

paper_content:

This paper considers the effect of stochasticity on the quality of convergence of genetic algorithms (GAs). In many problems, the variance of building-block fitness or so-called collateral noise is the major source of variance, and a population-sizing equation is derived to ensure that average signal-to-collateral-noise ratios are favorable to the discrimination of the best building blocks required to solve a problem of bounded deception. The sizing relation is modified to permit the inclusion of other sources of stochasticity, such as the noise of selection, the noise of genetic operators, and the explicit noise or nondeterminism of the objective function. In a test suite of five functions, the sizing relation proves to be a conservative predictor of average correct convergence, as long as all major sources of noise are considered in the sizing calculation. These results suggest how the sizing equation may be viewed as a coarse delineation of a boundary between what a physicist might call two distinct phases of GA behavior. At low population sizes the GA makes many errors of decision, and the quality of convergence is largely left to the vagaries of chance or the serial fixup of flawed results through mutation or other serial injection of diversity. At large population sizes, GAs can reliably discriminate between good and bad building blocks, and parallel processing and recombination of building blocks lead to quick solution of even difficult deceptive problems. Additionally, the paper outlines a number of extensions to this work, including the development of more refined models of the relation between generational average error and ultimate convergence quality, the development of online methods for sizing populations via the estimation of populations via the estimation of population-sizing parameters, and the investigation of populationsizing in the context of niching and other schemes designed for use in problems with high cardinality solution sets. The paper also discusses how these results may one day lead to rigorous proofs of convergence for recombinative G As operating on problems of bounded description.
---
paper_title: Scalability of the Bayesian optimization algorithm

paper_content:

To solve a wide range of different problems, the research in black-box optimization faces several important challenges. One of the most important challenges is the design of methods capable of automatic discovery and exploitation of problem regularities to ensure efficient and reliable search for the optimum. This paper discusses the Bayesian optimization algorithm (BOA), which uses Bayesian networks to model promising solutions and sample new candidate solutions. Using Bayesian networks in combination with population-based genetic and evolutionary search allows BOA to discover and exploit regularities in the form of a problem decomposition. The paper analyzes the applicability of the methods for learning Bayesian networks in the context of genetic and evolutionary search and concludes that the combination of the two approaches yields robust, efficient, and accurate search.
---
paper_title: Enhancing the Performance of Maximum–Likelihood Gaussian EDAs Using Anticipated Mean Shift

paper_content:

Many Estimation---of---Distribution Algorithms use maximum-likelihood (ML) estimates. For discrete variables this has met with great success. For continuous variables the use of ML estimates for the normal distribution does not directly lead to successful optimization in most landscapes. It was previously found that an important reason for this is the premature shrinking of the variance at an exponential rate. Remedies were subsequently successfully formulated (i.e. Adaptive Variance Scaling (AVS) and Standard---Deviation Ratio triggering (SDR)). Here we focus on a second source of inefficiency that is not removed by existing remedies. We then provide a simple, but effective technique called Anticipated Mean Shift (AMS) that removes this inefficiency.
---
paper_title: Drift and Scaling in Estimation of Distribution Algorithms

paper_content:

This paper considers a phenomenon in Estimation of Distribution Algorithms (EDA) analogous to drift in population genetic dynamics. Finite population sampling in selection results in fluctuations which get reinforced when the probability model is updated. As a consequence, any probability model which can generate only a single set of values with probability 1 can be an attractive fixed point of the algorithm. To avoid this, parameters of the algorithm must scale with the system size in strongly problemdependent ways, or the algorithm must be modified. This phenomenon is shown to hold for general EDAs as a consequence of the lack of ergodicity and irreducibility of the Markov chain on the state of probability models. It is illustrated in the case of UMDA, in which it is shown that the global optimum is only found if the population size is sufficiently large. For the needle-in-a haystack problem, the population size must scale as the square-root of the size of the search space. For the one-max problem, the population size must scale as the square-root of the problem size.
---
paper_title: iBOA: The Incremental Bayesian Optimization Algorithm

paper_content:

This paper proposes the incremental Bayesian optimization algorithm (iBOA), which modifies standard BOA by removing the population of solutions and using incremental updates of the Bayesian network. iBOA is shown to be able to learn and exploit unrestricted Bayesian networks using incremental techniques for updating both the structure as well as the parameters of the probabilistic model. This represents an important step toward the design of competent incremental estimation of distribution algorithms that can solve difficult nearly decomposable problems scalably and reliably.
---
paper_title: Space Complexity of Estimation of Distribution Algorithms

paper_content:

In this paper, we investigate the space complexity of the Estimation of Distribution Algorithms (EDAs), a class of sampling-based variants of the genetic algorithm. By analyzing the nature of EDAs, we identify criteria that characterize the space complexity of two typical implementation schemes of EDAs, the factorized distribution algorithm and Bayesian network-based algorithms. Using random additive functions as the prototype, we prove that the space complexity of the factorized distribution algorithm and Bayesian network-based algorithms is exponential in the problem size even if the optimization problem has a very sparse interaction structure.
---
paper_title: Model Accuracy in the Bayesian Optimization Algorithm

paper_content:

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.
---
paper_title: Spurious dependencies and EDA scalability

paper_content:

Numerous studies have shown that advanced estimation of distribution algorithms (EDAs) often discover spurious (unnecessary) dependencies. Nonetheless, only little prior work exists that would study the effects of spurious dependencies on EDA performance. This paper examines the effects of spurious dependencies on the performance and scalability of EDAs with the main focus on EDAs with marginal product models and the onemax problem. A theoretical model is proposed to analyze the effects of spurious dependencies on the population sizing in EDAs and the theory is verified with experiments. The effects of spurious dependencies on the number of generations are studied empirically. The effects of replacement strategies on the performance of EDAs with spurious linkage are also investigated.
---
paper_title: Analyzing Probabilistic Models in Hierarchical BOA

paper_content:

The hierarchical Bayesian optimization algorithm (hBOA) can solve nearly decomposable and hierarchical problems of bounded difficulty in a robust and scalable manner by building and sampling probabilistic models of promising solutions. This paper analyzes probabilistic models in hBOA on four important classes of test problems: concatenated traps, random additively decomposable problems, hierarchical traps and two-dimensional Ising spin glasses with periodic boundary conditions. We argue that although the probabilistic models in hBOA can encode complex probability distributions, analyzing these models is relatively straightforward and the results of such analyses may provide practitioners with useful information about their problems. The results show that the probabilistic models in hBOA closely correspond to the structure of the underlying optimization problem, the models do not change significantly in consequent iterations of BOA, and creating adequate probabilistic models by hand is not straightforward even with complete knowledge of the optimization problem.
---

Title: An Introduction and Survey of Estimation of Distribution Algorithms

Section 1: Introduction
Description 1: This section provides an overview of Estimation of Distribution Algorithms (EDAs) and their applications.

Section 2: Estimation of Distribution Algorithms
Description 2: This section explains the basic concepts of EDAs and how they work.

Section 3: General EDA Procedure
Description 3: This section outlines the general procedure for implementing EDAs, including algorithm steps and important concepts.

Section 4: Solving Onemax with a Simple EDA
Description 4: This section illustrates the basic EDA procedure using the onemax problem as an example.

Section 5: EDA Overview
Description 5: This section provides a broad overview of different types of EDAs, categorized by the type of distributions they encode.

Section 6: Discrete Variables
Description 6: This section covers EDAs that work on fixed-length strings of a finite cardinality, including different models that capture interactions between variables.

Section 7: Permutation EDAs
Description 7: This section discusses EDAs designed for problems where candidate solutions are represented by permutations, such as the traveling salesman problem.

Section 8: Real-Valued Vectors
Description 8: This section addresses EDAs applicable to optimization problems represented by real-valued vectors and their approaches, including direct representation.

Section 9: EDA-GP
Description 9: This section reviews EDAs designed for genetic programming (GP), focusing on challenges and successful implementations.

Section 10: Multi-Objective EDAs
Description 10: This section discusses EDAs developed for solving multi-objective optimization problems and methods for finding Pareto optimal solutions.

Section 11: Related Algorithms
Description 11: This section compares EDAs with other closely related stochastic optimization algorithms and techniques.

Section 12: Advantages and Disadvantages of Using EDAs
Description 12: This section reviews the main advantages and disadvantages of using EDAs compared to other metaheuristics.

Section 13: Efficiency Enhancement Techniques for EDAs
Description 13: This section outlines various techniques to enhance efficiency in EDAs, including parallelization, hybridization, and evaluation relaxation.

Section 14: EDA Theory
Description 14: This section covers theoretical aspects of EDAs, including convergence proofs, population sizing, diversity loss, memory complexity, and model accuracy.

Section 15: Additional Information
Description 15: This section provides pointers to additional sources of information on EDAs, including software, journals, and conferences.

Section 16: Summary and Conclusions
Description 16: This section summarizes the capabilities and strengths of EDAs and concludes with the potential of these algorithms in solving complex optimization problems.