• Citations on Research Index (Citeseer)
• Google scholar entries
• DBLP: Martin Pelikan
• Bibtex entries on Computer Science Bibliographies

2007

Claudio F. Lima, Martin Pelikan, David E. Goldberg, Fernando G. Lobo, Kumara Sastry, Mark Hauschild
Influence of Selection and Replacement Strategies on Linkage Learning in BOA

Rajiv Kalapala, Martin Pelikan and Alexander K. Hartmann
Hybrid Evolutionary Algorithms on Minimum Vertex Cover for Random Graphs

Martin Pelikan, Shigeyoshi Tsutsui, and Rajiv Kalapala
Dependency Trees, Permutations, and Quadratic Assignment Problem

Martin Pelikan and Alexander K. Hartmann
Obtaining Ground States of Ising Spin Glasses via Optimizing Bonds Instead of Spins

Mark Hauschild, Martin Pelikan, Claudio F. Lima, and Kumara Sastry
Analyzing Probabilistic Models in Hierarchical BOA on Traps and Spin Glasses

2006

Martin Pelikan
Implementation of the Dependency-Tree Estimation of Distribution Algorithm in C++

Shigeyoshi Tsutsui, Martin Pelikan and David E. Goldberg
Node Histogram vs. Edge Histogram: A Comparison of PMBGAs in Permutation Domains

Shigeyoshi Tsutsui and Martin Pelikan
Cunning Ant System: An Extension of Edge Histogram Sampling Algorithms to ACO

Lima, C. F., Pelikan, M., Sastry, K., Butz, M., Goldberg, D. E., Lobo, F. G.
Substructural neighborhoods for local search in the Bayesian optimization algorithm

Yu, T.-L., Sastry, K., Goldberg, D. E., Pelikan, M.
Population sizing for entropy-based model building in genetic algorithms

Pelikan, M., Laury, J. D., Jr.
Order or not: Does parallelization of model building in hBOA affect its scalability?

Sastry, K., Pelikan, M., Goldberg, D. E.
Analysis of ideal recombination on random decomposable problems

Pelikan, M., Sastry, K., Butz, M. V., Goldberg, D. E.
Generator and interface for random decomposable problems in C

Pelikan, M., Hartmann, A. K.
Hierarchical BOA, cluster exact approximation, and Ising spin glasses

Pelikan, M., Sastry, K., Butz, M. V., Goldberg, D. E.
Hierarchical BOA on random decomposable problems

2005

Butz, M.V., Pelikan, M., Llora, X., Goldberg, D.E.
Automated global structure extraction for effective local building block processing in XCS

Butz, M.V., Pelikan, M., Llora, X., Goldberg, D.E.
Extracted global structure makes local building block processing effective in XCS

Pelikan, M., Sastry, K., Goldberg, D.E.
Multiobjective hBOA, clustering, and scalability

Sastry, K., Pelikan, M., Goldberg, D.E.
Decomposable problems, niching, and scalability of multiobjective estimation of distribution algorithms

Ondas, R., Pelikan, M., Sastry, K.
Scalability of genetic programming and probabilistic incremental program evolution

Pelikan, M.
Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms

2004

Sastry, K., Goldberg, D.E., Pelikan, M.
Efficiency enhancement of probabilistic model building genetic algorithms

Potthast, F., Ocenasek, J., Rutishauser, D., Pelikan, M., Schlapbach, R.
Database independent detection of isotopically labeled MS/MS spectrum peptide pairs

Ocenasek, J., Pelikan, M.
Parallel mixed Bayesian optimization algorithm: A scaleup analysis

Sastry, K., Pelikan, M., Goldberg, D.E.
Efficiency enhancement of genetic algorithms via building-block-wise fitness estimation

Pelikan, M., Ocenasek, J., Trebst, S., Troyer, M., Alet, F.
Computational complexity and simulation of rare events of Ising spin glasses

Pelikan, M., Tz-Kai Lin
Parameter-less hierarchical BOA

Pelikan, M., Sastry, K.
Fitness inheritance in the Bayesian optimization algorithm

2003

S. Tsutsui, Pelikan, M., Goldberg, D.E.
Using edge histogram models to solve permutation problems with probabilistic model-building genetic algorithms

Pelikan, M., Goldberg, D.E., Ocenasek, J., Trebst, S.
Robust and scalable black-box optimization, hierarchy, and Ising spin glasses

Ocenasek, J., Schwarz, J., Pelikan, M.
Design of multithreaded estimation of distribution algorithms

Pelikan, M., Goldberg, D.E.
Hierarchical BOA solves Ising spin glasses and MAXSAT

2002

S. Tsutsui, Goldberg, D. E., Pelikan, M.
Solving sequence problems by building and sampling edge histograms

Pelikan, M.
Bayesian Optimization Algorithm: From Single Level to Hierarchy
Ph.D. Dissertation from the Dept. of Computer Science at the University of Illinois at Urbana-Champaign

Khan, N., Goldberg, D.E., Pelikan, M.
Multi-objective Bayesian optimization algorithm

2001
 

Pelikan, M., Sastry, K., Goldberg, D.E.
Evolutionary Algorithms + Graphical Models = Scalable Black-Box Optimization

Ceroni, A., Pelikan, M., Goldberg, D.E.
Convergence-time models for the simple genetic algorithm with finite population

Pelikan, M., Goldberg, D.E., Tsutsui, S.
Combining the Strengths of the Bayesian Optimization Algorithm and Adaptive Evolution Strategies

Tsutsui, S., Pelikan, M., Goldberg, D.E.
Evolutionary Algorithm Using Marginal Distribution Models in Continuous Domain

Sastry, K., Goldberg, D.E., Pelikan, M.
Don't Evaluate, Inherit

Butz, M.V., Pelikan, M.
Analyzing the Evolutionary Pressures in XCS

Pelikan, M., Goldberg, D.E.
Escaping Hierarchical Traps with Bayesian Optimization Algorithm

2000

Pelikan, M.
A C++ Implementation of the Bayesian Optimization Algorithm with Decision Graphs

Pelikan, M., Goldberg, D.E., Sastry, K.
Bayesian Optimization Algorithm, Decision Graphs, and Occam's Razor

Pelikan, M., Goldberg, D.E.
Genetic Algorithms, Clustering, and the Breaking of Symmetry

Pelikan, M., Goldberg, D.E.
Research on the Bayesian Optimization Algorithm

Pelikan, M., Goldberg, D.E.
Hierarchical Problem Solving by the Bayesian Optimization Algorithm

Pelikan, M., Goldberg, D.E., Cantú-Paz, E.
Bayesian Optimization Algorithm, Population Sizing, and Time to Convergence

1999

Pelikan, M., Goldberg, D.E., Lobo, F.
A Survey of Optimization by Building and Using Probabilistic Models

Pelikan, M., Lobo, F.
Parameter-less Genetic Algorithm: A Worst-case Time and Space Complexity Analysis

Pelikan, M.
A Simple Implementation of the Bayesian Optimization Algorithm (BOA) in C++ (version 1.0)

Pelikan, M., Goldberg, D. E., Cantú-Paz, E.
BOA: The Bayesian Optimization Algorithm

Pelikan, M., Muehlenbein, H.
The Bivariate Marginal Distribution Algorithm

1998

Pelikan, M., Goldberg, D. E., Cantú-Paz, E.
Linkage Problem, Distribution Estimation, and Bayesian Networks

Pelikan, M., Muehlenbein, H.
Marginal Distributions in Evolutionary Algorithms

1996

Kvasnicka, V., Pospichal, J., Pelikan, M.
Read's Linear Codes and Evolutionary Computation Over Populations of Rooted Trees

Kvasnicka, V., Pospichal, J., Pelikan, M.
Stochastic Simulation of Multiagent Models

Kvasnicka, V., Pospichal, J., Pelikan, M.
Hill Climbing with Learning (An Abstraction of Genetic Algorithm)
 
 

Abstract
The Bayesian optimization algorithm (BOA) uses Bayesian networks to learn linkages between the decision variables of an optimization problem. This paper studies the influence of different selection and replacement methods on the accuracy of linkage learning in BOA. Results on concatenated m-k deceptive trap functions show that the model accuracy depends on a large extent on the choice of selection method and to a lesser extent on the replacement strategy used. Specifically, it is shown that linkage learning in BOA is more accurate with truncation selection than with tournament selection. The choice of replacement strategy is important when tournament selection is used, but it is not relevant when using truncation selection. On the other hand, if performance is our main concern, tournament selection and restricted tournament replacement should be preferred. These results aim to provide practitioners with useful information about the best way to tune BOA with respect to structural model accuracy and overall performance.

Reference
Claudio F. Lima, Martin Pelikan, David E. Goldberg, Fernando G. Lobo, Kumara Sastry, and Mark Hauschild (2007). Influence of Selection and Replacement Strategies on Linkage Learning in BOA. MEDAL Report No. 2007005, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri in St. Louis, MO.

Download preprint as PDF

Abstract
This paper analyzes the hierarchical Bayesian optimization algorithm (hBOA) on minimum vertex cover for standard classes of random graphs and transformed SAT instances. The performance of hBOA is compared with that of the branch-and-bound problem solver (BB), the simple genetic algorithm (GA) and the parallel simulated annealing (PSA). The results indicate that BB is significantly outperformed by all the other tested methods, which is expected as BB is a complete search algorithm and minimum vertex cover is an NP-complete problem. The best performance is achieved by hBOA; nonetheless, the performance differences between hBOA and other evolutionary algorithms are relatively small, indicating that mutation-based search and recombination-based search lead to similar performance on the tested classes of minimum vertex cover problems.

Reference
Rajiv Kalapala, Martin Pelikan and Alexander K. Hartmann (2007). Hybrid Evolutionary Algorithms on Minimum Vertex Cover for Random Graphs. MEDAL Report No. 2007004, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri in St. Louis, MO.

Download preprint as PDF

Abstract
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.

Reference
Martin Pelikan, Shigeyoshi Tsutsui, and Rajiv Kalapala (2007). Dependency Trees, Permutations, and Quadratic Assignment Problem. MEDAL Report No. 2007003, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri in St. Louis, MO.

Download preprint as PDF

Abstract
Frustrated Ising spin glasses represent a rich class of challenging optimization problems that share many features with other complex, highly multimodal optimization and combinatorial problems. This paper shows that transforming candidate solutions to an alternative representation that is strongly tied to the energy function simplifies the exploration of the space of potential spin configurations and that it significantly improves performance of evolutionary algorithms with simple variation operators on Ising spin glasses. The proposed techniques are incorporated into the simple genetic algorithm, the univariate marginal distribution algorithm, and the hierarchical Bayesian optimization algorithm.

Reference
Martin Pelikan and Alexander K. Hartmann (2007). Obtaining Ground States of Ising Spin Glasses via Optimizing Bonds Instead of Spins. MEDAL Report No. 2007002, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri in St. Louis, MO.

Download preprint as PDF

Abstract
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 two common test problems: concatenated traps and 2D Ising spin glasses with periodic boundary conditions. We argue that although Bayesian networks with local structures can encode complex probability distributions, analyzing these models in hBOA 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 subsequent iterations of BOA, and creating adequate probabilistic models by hand is not straightforward even with complete knowledge of the optimization problem.

Reference
Mark Hauschild, Martin Pelikan, Claudio F. Lima, and Kumara Sastry (2007). Analyzing Probabilistic Models in Hierarchical BOA on Traps and Spin Glasses. MEDAL Report No. 2007001, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri in St. Louis, MO.

Download preprint as PDF

Abstract
This technical report describes how to download, compile and use the C++ source code of the dependency-tree estimation of distribution algorithm, which uses dependency trees to model promising solutions and sample the new ones. Candidate solutions are represented by fixed-length strings with a finite number of values in each string position (the code is not restricted to binary strings). The report also describes how to modify the code to solve new optimization problems. Additional documentation can be found in the provided software package, which includes a detailed documentation in PDF, HTML, and LaTeX formats.

Reference
Martin Pelikan (2006). Implementation of the Dependency-Tree Estimation of Distribution Algorithm in C++. MEDAL Report No. 2006010, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri in St. Louis, MO.

Download preprint as PDF

Abstract
Previous papers have proposed an algorithm called the edge histogram sampling algorithm (EHBSA) that models the relative relation between two nodes (edge) of permutation strings of a population within the PMBGA framework for permutation domains. This paper proposes another histogram based model we call the node histogram sampling algorithm (NHBSA). The NHBSA models node frequencies at each absolute position in strings of a population. Sampling methods are similar to that of EHBSA. Performance of NHBSA is compared with that of EHBSA using two types of permutation problems: the FSSP and the quadratic assignment problem (QAP). The results showed that the NHBSA works better than the EHBSA on these problems.

Reference
Shigeyoshi Tsutsui, Martin Pelikan, and David E. Goldberg (2006). Node Histogram vs. Edge Histogram: A Comparison of PMBGAs in Permutation Domains. MEDAL Report No. 2006009, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri in St. Louis, MO.

Download preprint as PDF

Abstract
In this paper, we propose a variant of an ACO algorithm called the cunning Ant System (cAS). In cAS, each ant generates a solution by borrowing a part of a solution which was generated in previous iterations, instead of generating the solution entirely from pheromone density. Thus we named it, cunning ant. This cunning action reduces premature stagnation and exhibits good performance in the search. The experimental results showed cAS worked very well on the TSP and it may be one of the most promising ACO algorithms.

Reference
Shigeyoshi Tsutsui and Martin Pelikan (2006). Cunning Ant System: An Extension of Edge Histogram Sampling Algorithms to ACO. MEDAL Report No. 2006008, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri in St. Louis, MO.

Download preprint as PDF

Abstract
It has been shown that model building in the hierarchical Bayesian optimization algorithm (hBOA) can be efficiently parallelized by randomly generating an ancestral ordering of the nodes of the network prior to learning the network structure and allowing only dependencies consistent with the generated ordering. However, it has not been thoroughly shown that this approach to restricting probabilistic models does not affect scalability of hBOA on important classes of problems. This paper demonstrates that although the use of a random ancestral ordering restricts the structure of considered models to allow efficient parallelization of model building, its effects on hBOA performance and scalability are negligible.

Reference
Claudio F. Lima, Martin Pelikan, Kumara Sastry, Martin Butz, David E. Goldberg, and Fernando G. Lobo (2006). Substructural neighborhoods for local search in the Bayesian optimization algorithm. MEDAL Report No. 2006007, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri in St. Louis, MO.

Download preprint as PDF

Abstract
This paper presents a population-sizing model for the entropy-based model building in genetic algorithms. Specifically, the population size required for building an accurate model is investigated. The effect of the selection pressure on population sizing is also incorporated. The proposed model indicates that the population size required for building an accurate model scales as O(mlog m), where m is the number of substructures and proportional to the problem size. Experiments are conducted to verify the derivations, and the results agree with the proposed model.

Reference
Tian-Li Yu, Kumara Sastry, David E. Goldberg, and Martin Pelikan (2006). Population Sizing for Entropy-based Model Building in Genetic Algorithms. MEDAL Report No. 2006006, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri in St. Louis, MO.

Download preprint as PDF

Abstract
It has been shown that model building in the hierarchical Bayesian optimization algorithm (hBOA) can be efficiently parallelized by randomly generating an ancestral ordering of the nodes of the network prior to learning the network structure and allowing only dependencies consistent with the generated ordering. However, it has not been thoroughly shown that this approach to restricting probabilistic models does not affect scalability of hBOA on important classes of problems. This paper demonstrates that although the use of a random ancestral ordering restricts the structure of considered models to allow efficient parallelization of model building, its effects on hBOA performance and scalability are negligible.

Reference
Pelikan, M., Laury, J. D., Jr. (2006). Order or Not: Does Parallelization of Model Building in hBOA Affect Its Scalability?. MEDAL Report No. 2006005, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri in St. Louis, MO.

Download preprint as PDF

Abstract
This paper analyzes the behavior of a selectorecombinative genetic algorithm (GA) with an ideal crossover on a class of random additively decomposable problems (rADPs). Specifically, additively decomposable problems of order k whose subsolution fitnesses are sampled from the standard uniform distribution U[0,1] are analyzed. The scalability of the selectorecombinative GA is investigated for 10,000 rADP instances. The validity of facetwise models in bounding the population size, run duration, and the number of function evaluations required to successfully solve the problems is also verified. Finally, rADP instances that are easiest and most difficult are also investigated.

Reference
Sastry, K., Pelikan, M., Goldberg, D. E. (2006). Analysis of ideal recombination on random decomposable problems. MEDAL Report No. 2006004, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri in St. Louis, MO.

Download preprint as PDF

Abstract
This technical report describes how to download, compile and use the C source code of the generator of random additively decomposable functions and the functions that enable the use of the generated instances in any standard optimization algorithm.

Reference
Pelikan, M., Sastry, K., Butz, M. V., Goldberg, D. E. (2006). Generator and interface for random decomposable problems in C. MEDAL Report No. 2006003, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri in St. Louis, MO.

Download preprint as PDF

Abstract
This paper analyzes the hierarchical Bayesian optimization algorithm (hBOA) on the problem of finding ground states of Ising spin glasses with $\pm J$ 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 and cluster exact approximation (CEA). The results show that hBOA significantly outperforms GA and UMDA on a broad spectrum of spin-glass instances and that CEA enables all tested algorithms to solve larger spin-glass instances. Using advanced hybrid methods created by combining competent genetic and evolutionary algorithms with advanced local searchers thus proves advantageous in this challenging class of problems.

Reference
Pelikan, M., Hartmann, A. K. (2006). Hierarchical BOA, cluster exact approximation, and Ising spin glasses. MEDAL Report No. 2006002, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri in St. Louis, MO.

Download preprint as PDF

Abstract
The hierarchical Bayesian optimization algorithm (hBOA) can solve nearly decomposable and hierarchical problems scalably and reliably. This paper describes a class of random additively decomposable problems with and without interactions between the subproblems and tests hBOA on a large number of random instances of the proposed class of problems. The performance of hBOA is compared to that of the simple genetic algorithm with standard crossover and mutation operators, the univariate marginal distribution algorithm, and the hill climbing with bit-flip mutation. The results confirm that hBOA achieves quadratic or subquadratic performance on the proposed class of random decomposable problems and that it significantly outperforms all other methods included in the comparison. The results also show that low-order polynomial scalability is retained even when only a small percentage of hardest problems are considered and that hBOA is a robust algorithm because its performance does not change much across the entire spectrum of random problem instances of the same structure. The proposed class of decomposable problems can be used to test other optimization algorithms that address nearly decomposable problems.

Reference
Pelikan, M., Sastry, K., Butz, M. V., Goldberg, D. E. (2006). Hierarchical BOA on random decomposable problems. MEDAL Report No. 2006001, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri in St. Louis, MO.

Download preprint as PDF

Abstract
This paper describes and analyzes sporadic model building, which can be used to enhance the efficiency of the hierarchical Bayesian optimization algorithm (hBOA) and other estimation of distribution algorithms (EDAs). With sporadic model building, the structure of the probabilistic model is updated once every few iterations (generations), whereas in the remaining iterations only model parameters (conditional and marginal probabilities) are updated. Since the time complexity of updating model parameters is much lower than the time complexity of learning the model structure, sporadic model building decreases the overall time complexity of model building. The paper shows that for boundedly difficult nearly decomposable and hierarchical optimization problems, sporadic model building leads to a significant model-building speedup that decreases the asymptotic time complexity of model building in hBOA by a factor of O(n^0.26) to O(n^0.65), where n is the problem size. On the other hand, sporadic model building also increases the number of evaluations until convergence; nonetheless, for decomposable problems, the evaluation slowdown is insignificant compared to the gains in the asymptotic complexity of model building.

Reference
Pelikan, M., Sastry, K., Goldberg, D. E. (2005). Sporadic model building for efficiency enhancement of hBOA. IlliGAL Report No. 2005026, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, IL.

Download preprint as compressed PS or PDF

Abstract
Learning Classifier Systems (LCSs), such as XCS and other accuracy-based classifier systems, evolve distributed problem solutions represented by a population of rules. During evolution, features are specialized, propagated, and recombined to provide increasingly accurate subsolutions. Recently, it was shown that, like in conventional genetic algorithms (GAs), some problems require the processing of subsets of features as opposed to individual features to find the problem solution efficiently. In such problems, standard variation operators of genetic and evolutionary algorithms used in LCSs suffer from potential disruption of groups of interacting features, resulting in poor performance. This paper introduces two competent crossover operators to XCS by incorporating techniques derived from competent GAs: the extended compact GA (ECGA) and the Bayesian optimization algorithm (BOA). Instead of simple crossover operators such as uniform crossover or one-point crossover, here a probabilistic model of the global population is built and sampled to generate offspring classifiers locally. The distinction between the global and local problem structure is an additional challenge since the local problem structure may differ from the global structure. Two offspring generation methods are introduced and evaluated. The results show that it is possible to achieve performance similar to that of informed crossover operators, which are specifically designed to provide ideal exploration on tested problems. Thus, by detecting dependency structures online, we create the first competent LCSs, XCS/ECGA and XCS/BOA, that are able to identify and propagate lower-level dependency structures effectively without any information about these structures given in advance.

Reference
Butz, M.V., Pelikan, M., Llora, X., Goldberg, D.E. (2005). Automated global structure extraction for effective local building block processing in XCS. IlliGAL Report No. 2005011, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, IL.

Download preprint as compressed PS or PDF

Abstract
Learning Classifier Systems (LCSs), such as the accuracy-based XCS system, evolve distributed problem solutions represented by a population of rules. Recently, it was shown that decomposable problems may require effective processing of feature subsets as opposed to individual features, which cannot be generally assured with standard crossover operators. Although a number of competent crossover operators capable of effective identification and processing of arbitrary subsets of variables or string positions were proposed for genetic and evolutionary algorithms, none of these operators were incorporated into LCSs. This paper introduces two competent crossover operators to XCS by incorporating techniques from competent genetic algorithms (GAs): the extended compact GA (ECGA) and the Bayesian optimization algorithm (BOA). Instead of applying standard crossover operators, here a probabilistic model of the global population is built and sampled to generate offspring classifiers locally. Two offspring generation methods are introduced and evaluated. Results indicate that the performance of the proposed learning classifier systems XCS/ECGA and XCS/BOA is similar to that of XCS with informed crossover operators that is given all information about problem structure on input and exploits this knowledge using problem-specific crossover operators.

Reference
Butz, M.V., Pelikan, M., Llora, X., Goldberg, D.E. (2005). Extracted global structure makes local building block processing effective in XCS. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2005), pp. 655-662. Also IlliGAL Report No. 2005010.

Download preprint as compressed PS or PDF

Abstract
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 sizedportion 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.

Reference
Pelikan, M., Sastry, K., Goldberg, D.E. (2005). Multiobjective hBOA, clustering, and scalability. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2005), pp. 663-670. Also IlliGAL Report No. 2005005.

Download preprint as compressed PS or PDF

Preprint arXiv:cs.NE/0502034

Abstract
The paper analyzes the scalability of multiobjective estimation of distribution algorithms (MOEDAs) on a class of boundedly-difficult additively-separable multiobjective optimization problems. The paper illustrates that even if the linkage is correctly identified, massive multimodality of the search problems can easily overwhelm the nicher and lead to exponential scale-up. Facetwise models are subsequently used to propose a growth rate of the number of differing substructures between the two objectives to avoid the niching method from being overwhelmed and lead to polynomial scalability of MOEDAs.

Reference
Sastry, K., Pelikan, M., Goldberg, D.E. (2005). Decomposable problems, niching, and scalability of multiobjective estimation of distribution algorithms. Proceedings of the IEEE Conference on Evolutionary Computation (CEC-2005). Also IlliGAL Report No. 2005004.

Download compressed PS or PDF

Preprint arXiv:cs.NE/0502057

Abstract
This paper discusses scalability of standard genetic programming (GP) and the probabilistic incremental program evolution (PIPE). To investigate the need for both effective mixing and linkage learning, two test problems are considered: ORDER problem, which is rather easy for any recombination-based GP, and TRAP or the deceptive trap problem, which requires the algorithm to learn interactions among subsets of terminals. The scalability results show that both GP and PIPE scale up polynomially with problem size on the simple ORDER problem, but they both scale up exponentially on the deceptive problem. This indicates that while standard recombination is sufficient when no interactions need to be considered, for some problems linkage learning is necessary. These results are in agreement with the lessons learned in the domain of binary-string genetic algorithms (GAs). Furthermore, the paper investigates the effects of introducing unnecessary and irrelevant primitives on the performance of GP and PIPE.

Reference
Ondas, R., Pelikan, M., Sastry, K. (2005). Scalability of genetic programming and probabilistic incremental program evolution.

Preprint arXiv:cs.NE/0502029

About the book
This book provides a framework for the design of competent optimization techniques by combining advanced evolutionary algorithms with state-of-the-art machine learning techniques. The primary focus of the book is on two algorithms that replace traditional variation operators of evolutionary algorithms, by learning and sampling Bayesian networks: the Bayesian optimization algorithm (BOA) and the hierarchical BOA (hBOA). They provide a scalable solution to a broad class of problems. The book provides an overview of evolutionary algorithms that use probabilistic models to guide their search, motivates and describes BOA and hBOA in a way accessible to a wide audience, and presents numerous results confirming that they are revolutionary approaches to black-box optimization.

Reference
Pelikan, M. (2005). Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms. Springer.

The book can be ordered from Springer here

Abstract
This paper presents two different efficiency-enhancement techniques for probabilistic model building genetic algorithms. The first technique proposes the use of a mutation operator which performs local search in the sub-solution neighborhood identified through the probabilistic model. The second technique proposes building and using an internal probabilistic model of the fitness along with the probabilistic model of variable interactions. The fitness values of some offspring are estimated using the probabilistic model, thereby avoiding computationally expensive function evaluations. The scalability of the aforementioned techniques are analyzed using facetwise models for convergence time and population sizing. The speed-up obtained by each of the methods is predicted and verified with empirical results. The results show that for additively separable problems the competent mutation operator requires O(k 0.5 logm)--where k is the building-block size, and m is the number of building blocks--less function evaluations than its selectorecombinative counterpart. The results also show that the use of an internal probabilistic fitness model reduces the required number of function evaluations to as low as 1-10% and yields a speed-up of 2--50.

Reference
Sastry, K., Goldberg, D.E., Pelikan, M. (2004). Efficiency Enhancement of of Probabilistic Model Building Genetic Algorithms. IlliGAL Report No. 2004020, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, IL.

Download compressed PS or PDF

Preprint arXiv:cs.NE/0405062

Abstract
Mass spectrometry data generated in differential profiling of complex protein samples are classically exploited using database searches. In addition, quantitative profiling is performed by various methods, one of them using isotopically coded affinity tags, where one typically uses a light and a heavy tag. Here, we present a new algorithm, ICATcher, which detects pairs of light/heavy peptide MS/MS spectra independent of sequence databases. We also give a framework on how to organize spectrum pairs into links, clusters, and hyperclusters. The method can be used for de novo sequencing and detection of posttranslational modifications. ICATcher is distributed as open source software.

Reference
Potthast, F., Ocenasek, J., Rutishauser, D., Pelikan, M., Schlapbach, R. (2005). Database Independent Detection of Isotopically Labeled MS/MS Spectrum Peptide Pairs. Journal of Chromatography B, 817 (2), pp. 225-230.

Abstract
Estimation of Distribution Algorithms have been proposed as a new paradigm for evolutionary optimization. This paper focuses on the parallelization of Estimation of Distribution Algorithms. More specifically, the paper discusses how to predict performance of parallel Mixed Bayesian Optimization Algorithm (MBOA) that is based on parallel construction of Bayesian networks with decision trees. We determine the time complexity of parallel Mixed Bayesian Optimization Algorithm and compare this complexity with experimental results obtained by solving the spin glass optimization problem. The empirical results fit well the theoretical time complexity, so the scalability and efficiency of parallel Mixed Bayesian Optimization Algorithm for unknown instances of spin glass benchmarks can be predicted. Furthermore, we derive the guidelines that can be used to design effective parallel Estimation of Distribution Algorithms with the speedup proportional to the number of variables in the problem.

Reference
Pelikan, M., Ocenasek, J. (2004). Parallel mixed Bayesian optimization algorithm: A scaleup analysis. Optimization by Building and Using Probabilistic Models 2004 (OBUPM-2004), Seatttle, WA.

Download compressed PS or PDF

Preprint arXiv:cs.NE/0406007

Abstract
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.

Reference
Sastry, K., Pelikan, M., Goldberg, D.E. (2004). Efficiency Enhancement of Genetic Algorithms via Building-Block-Wise Fitness Estimation. IlliGAL Report No. 2004010, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, IL.

Download compressed PS or PDF

Preprint arXiv:cs.NE/0405065

Abstract
We discuss the computational complexity of random 2D Ising spin glasses, which represent an interesting class of constraint satisfaction problems for black box optimization. Two extremal cases are considered: (1) the +/- J spin glass, and (2) the Gaussian spin glass. We also study a smooth transition between these two extremal cases. The computational complexity of all studied spin glass systems is found to be dominated by rare events of extremely hard spin glass samples. We show that complexity of all studied spin glass systems is closely related to Frechet extremal value distribution. In a hybrid algorithm that combines the hierarchical Bayesian optimization algorithm (hBOA) with a deterministic bit-flip hill climber, the number of steps performed by both the global searcher (hBOA) and the local searcher follow Frechet distributions. Nonetheless, unlike in methods based purely on local search, the parameters of these distributions confirm good scalability of hBOA with local search. We further argue that standard performance measures for optimization algorithms---such as the average number of evaluations until convergence---can be misleading. Finally, our results indicate that for highly multimodal constraint satisfaction problems, such as Ising spin glasses, recombination-based search can provide qualitatively better results than mutation-based search.

Reference
Pelikan, M., Ocenasek, J., Trebst, S., Troyer, M., Alet, F. (2004). Computational complexity and simulation of rare events of Ising spin glasses. Genetic and Evolutionary Computation Conference 2004 (GECCO-2004), Springer-Verlag, pp. 36-47.

Preprint arXiv:cs.NE/0402030

Abstract
The parameter-less hierarchical Bayesian optimization algorithm (hBOA) enables the use of hBOA without the need for tuning parameters for solving each problem instance. There are three crucial parameters in hBOA: (1) the selection pressure, (2) the window size for restricted tournaments, and (3) the population size. Although both the selection pressure and the window size influence hBOA performance, performance should remain low-order polynomial with standard choices of these two parameters. However, there is no standard population size that would work for all problems of interest and the population size must thus be eliminated in a different way. To eliminate the population size, the parameter-less hBOA adopts the population-sizing technique of the parameter-less genetic algorithm. Based on the existing theory, the parameter-less hBOA should be able to solve nearly decomposable and hierarchical problems in quadratic or subquadratic number of function evaluations without the need for setting any parameters whatsoever. A number of experiments are presented to verify scalability of the parameter-less hBOA.

Reference
Pelikan, M., Tz-Kai Lin (2004). Parameter-less hierarchical BOA. Genetic and Evolutionary Computation Conference 2004 (GECCO-2004), Springer-Verlag, pp. 24-35.

Preprint arXiv:cs.NE/0402031

Abstract
This paper describes how fitness inheritance can be used to estimate fitness for a proportion of newly sampled candidate solutions in the Bayesian optimization algorithm (BOA). The goal of estimating fitness for some candidate solutions is to reduce the number of fitness evaluations for problems where fitness evaluation is expensive. Bayesian networks used in BOA to model promising solutions and generate the new ones are extended to allow not only for modeling and sampling candidate solutions, but also for estimating their fitness. The results indicate that fitness inheritance is a promising concept in BOA, because population-sizing requirements for building appropriate models of promising solutions lead to good fitness estimates even if only a small proportion of candidate solutions is evaluated using the actual fitness function. This can lead to a reduction of the number of actual fitness evaluations by a factor of 30 or more.

Reference
Martin Pelikan, & Kumara Sastry (2004). Fitness inheritance in the Bayesian optimization algorithm. Genetic and Evolutionary Computation Conference 2004 (GECCO-2004), Springer-Verlag, pp. 48-59.
Also published as IlliGAL Report No. 2004009, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL.

BibTeX

Download compressed PS (2004009.ps.Z)

Preprint arXiv:cs.NE/0402032

Abstract
Recently, there has been a growing interest in probabilistic model-building genetic algorithms (PMBGAs), which replace traditional variation operators of genetic and evolutionary algorithms by building and sampling a probabilistic model of promising solutions. In this paper we propose a PMBGA that uses edge histogram based sampling algorithms (EHBSAs) to solve problems with candidate solutions represented by permutations. Two sampling algorithmsthe sampling without template (EHBSA/WO) and the sampling with template (EHBSA/WT)are presented. The proposed algorithms are tested on several instances of the traveling salesman problem (TSP). The results show that EHBSA/WT works fairly well even with a small population size on all tested problem instances and that it outperforms popular two-parent recombination operators for permutations and other PMBGAs for permutation problems. Combining EHBSA with a simple local heuristic for solving TSP called 2-OPT improves the performance of the algorithm, enabling efficient solution to problems of hundreds of cities. Nonetheless, unlike most other TSP solvers, EHBSA is not limited to solving TSP instances, but it can be applied to any problem defined on permutations.

Reference
Shigeyoshi Tsutsui, Martin Pelikan, & David E. Goldberg (2003). Using edge histogram models to solve permutation problems with probabilistic model-building genetic algorithms . Submitted for publication. Also IlliGAL Report No. 2003022.

BibTeX

Download compressed PS (2003022.ps.Z)

Abstract
One of the most important challenges in computational optimization is the design of advanced black-box optimization techniques that would enable automated, robust, and scalable solution to challenging optimization problems. This paper describes an advanced black-box optimizer---the hierarchical Bayesian optimization algorithm (hBOA)---that combines techniques of genetic and evolutionary computation, machine learning, and statistics to create a widely applicable tool for solving real-world optimization problems. The paper motivates hBOA, describes its basic procedure, and provides an in-depth empirical analysis of hBOA on the class of random 2D and 3D Ising spin glass problems. The results on Ising spin glasses indicate that even without much problem-specific knowledge, hBOA can provide competitive or better results than techniques specialized in solving the particular problem or class of problems. Furthermore, hBOA can solve a large class of nearly decomposable and hierarchical problems for which there exists no other scalable solution.

Reference
Martin Pelikan, David E. Goldberg, Jiri Ocenasek, & Simon Trebst (2003). Robust and scalable black-box optimization, hierarchy, and Ising spin glasses. Submitted for publication. Also IlliGAL Report No. 2003019.

BibTeX

Download compressed PS (2003019.ps.Z)

Abstract
Estimation of Distribution Algorithms (EDAs) use a probabilistic model of promising solutions found so far to obtain new candidate solutions of an optimization problem. This paper focuses on the design of parallel EDAs. More specifically, the paper describes a method for parallel construction of Bayesian networks with local structures in form of decision trees in the Mixed Bayesian Optimization Algorithm. The proposed Multithreaded Mixed Bayesian Optimization Algorithm (MMBOA) is intended for implementation on a cluster of workstations that communicate by Message Passing Interface (MPI). Communication latencies between workstations are eliminated by multithreaded processing, so in each workstation the high-priority model-building thread, which is communication demanding, can be overlapped by low-priority model sampling thread when necessary. High performance of MMBOA is verified via simulation in TRANSIM tool.

Reference
Jiri Ocenasek, Josef Schwarz, & Martin Pelikan (2003). Design of multithreaded estimation of distribution algorithms. Genetic and Evolutionary Computation Conference 2003 (GECCO-2003), Springer-Verlag, pp. 1247-1258.

BibTeX

For download options, click here.

Abstract
Theoretical and empirical evidence exists that the hierarchical Bayesian optimization algorithm (hBOA) can solve challenging hierarchical problems and anything easier. This paper applies hBOA to two important classes of real-world problems: Ising spin-glass systems and maximum satisfiability (MAXSAT). The paper shows how easy it is to apply hBOA to real-world optimization problems---in most cases hBOA can be applied without any prior problem analysis, it can acquire enough problem-specific knowledge automatically. The results indicate that hBOA is capable of solving enormously difficult problems that cannot be solved by other optimizers and still provide competitive or better performance than problem-specific approaches on other problems. The results thus confirm that hBOA is a practical, robust, and scalable technique for solving challenging real-world problems.

Reference
Martin Pelikan & David E. Goldberg (2003). Hierarchical BOA solves Ising spin glasses and MAXSAT. Genetic and Evolutionary Computation Conference 2003 (GECCO-2003), Springer-Verlag, pp. 1271-1282. Also IlliGAL Report No. 2003001.

BibTeX

For download options, click here.

Solving sequence problems by building and sampling edge histograms

Shigeyoshi Tsutsui, David E. Goldberg, and Martin Pelikan

Abstract
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.

Reference
Shigeyoshi Tsutsui, David E. Goldberg, & Martin Pelikan (2002). Solving sequence problems by building and sampling edge histograms. IlliGAL Report No. 2002024, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL.

BibTeX

Download compressed PS (2002024.ps.Z)

Abstract
There are four primary goals of this dissertation. First, design a competent optimization algorithm capable of learning and exploiting appropriate problem decomposition by sampling and evaluating candidate solutions. Second, extend the proposed algorithm to enable the use of hierarchical decomposition as opposed to decomposition on only a single level. Third, design a class of difficult hierarchical problems that can be used to test the algorithms that attempt to exploit hierarchical decomposition. Fourth, test the developed algorithms on the designed class of problems and several real-world applications.

The dissertation proposes the Bayesian optimization algorithm (BOA), which uses Bayesian networks to model the promising solutions found so far and sample new candidate solutions. BOA is theoretically and empirically shown to be capable of both learning a proper decomposition of the problem and exploiting the learned decomposition to ensure robust and scalable search for the optimum across a wide range of problems. The dissertation then identifies important features that must be incorporated into the basic BOA to solve problems that are not decomposable on a single level, but that can still be solved by decomposition over multiple levels of difficulty. Hierarchical BOA extends BOA by incorporating those features for robust and scalable optimization of hierarchically decomposable problems. A class of problems called hierarchical traps is then proposed to test the ability of optimizers to learn and exploit hierarchical decomposition. Hierarchical BOA passes the test and is shown to solve hierarchical traps and other hierarchical problems in a scalable manner. Finally, the dissertation applies hierarchical BOA to two important classes of problems of statistical physics and artificial intelligence---Ising spin-glass systems and maximum satisfiability. Experiments show that even without requiring any prior problem-specific knowledge about the structure of the problem at hand or its properties, hierarchical BOA is capable of achieving comparable or better performance than other state-of-the-art methods specializing in solving the examined classes of problems.

Reference
Martin Pelikan (2002). Bayesian optimization algorithm: From single level to hierarchy. Ph.D. thesis, University of Illinois at Urbana-Champaign, Urbana, IL. Also IlliGAL Report No. 2002023.

BibTeX
Not available for download.

Multi-objective Bayesian Optimization Algorithm

Nazan Khan, David E. Goldberg, Martin Pelikan

Abstract
This paper proposes a competent multi-objective genetic algorithm called the multi-objective Bayesian optimization algorithm (mBOA). mBOA incorporates the selection method of the non-dominated sorting genetic algorithm-II (NSGA-II) into the Bayesian optimization algorithm (BOA). The proposed algorithm has been tested on an array of test functions which incorporate deception and loose-linkage and the results are compared to those of NSGA-II. Results indicate that mBOA outperforms NSGA-II on large loosely linked deceptive problems.

Reference
Nazan Khan, David E. Goldberg, & Martin Pelikan (2002). Multi-objective Bayesian Optimization Algorithm. IlliGAL Report No. 2002009, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL.

BibTeX

Download compressed PS (2002009.ps.Z)

Abstract
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 automatically discovering the regularities in the problem and utilizing these to ensure efficient and reliable search. This paper discusses the Bayesian optimization algorithm that uses Bayesian networks to model promising solutions and guide exploration of the search space. Using Bayesian networks in combination with population-based genetic and evolutionary search allows the algorithm to discover and utilize regularities in the form of a problem decomposition. The paper analyzes the applicability of the methods for learning Bayesian networks in context of genetic and evolutionary search and concludes that the combination of the two approaches yields a robust, efficient, and accurate search.

Reference
Martin Pelikan, Kumara Sastry, & David E. Goldberg (2001). Evolutionary Algorithms + Graphical Models = Scalable Black-Box Optimization. IlliGAL Report No. 2001029, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL.

BibTeX

Download compressed PS (2001029.ps.Z)

Abstract
This paper presents various convergence models for the simple genetic algorithm (SGA) in the case of finite population. A piecewise convergence-time model is derived using ideas from two existing convergence models. The factors affecting the convergence with small population are explained and used to construct a correct model of the variance in fitness for the OneMax problem. This knowledge is included in the existing asymptotic model to derive the embedded convergence-time model. The model is extended to a different environment and modified to include an unexpected behavior that makes the SGA converge solely by genetic drift.

Reference
Alessio Ceroni, Martin Pelikan, & David E. Goldberg (2001). Convergence-time models for the simple genetic algorithm with finite population. IlliGAL Report No. 2001028, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL.

BibTeX

Download compressed PS (2001028.ps.Z)

Abstract
A method which combines competent genetic algorithms working in discrete domains with adaptive evolution strategies working in continuous domains is described. Discretization is used to transform solution between the two domains. Experiments with Bayesian optimization algorithm, sigma-self-adaptive mutation, and three different discretization methods are presented. The results suggest that the algorithm scales up well on all tested problems.

Reference
Martin Pelikan, David E. Goldberg, & Shigeyoshi Tsutsui (2001). Combining the Strengths of the Bayesian Optimization Algorithm and Adaptive Evolution Strategies. IlliGAL Report No. 2001023, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL.

BibTeX

Download compressed PS (2001023.ps.Z)

Abstract
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.

Reference
Shigeyoshi Tsutsui, Martin Pelikan, & David E. Goldberg (2001). Evolutionary Algorithm Using Marginal Histogram Models in Continuous Domain. IlliGAL Report No. 2001019, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL.

Published in GECCO-2001 Workshop Proceedings, San Francisco, CA. Pages 230-233.

BibTeX

Download compressed PS (2001019.ps.Z)

Abstract
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 also 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.

Reference
Kumara Sastry, David E. Goldberg, & Martin Pelikan (2001). Don't Evaluate, Inherit. IlliGAL Report No. 2001013, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL.

Published in GECCO-2001 Proceedings, San Francisco, CA. Pages 551-558.

BibTeX

Download compressed PS (2001013.ps.Z)

Abstract
After an increasing interest in learning classifier systems and the XCS classifier system in particular, this paper locates and analyzes the distinct evolutionary pressures in XCS. Combining several of the pressures, an equation is derived that validates the generalization hypothesis which was stated by Wilson(1995). A detailed experimental study of the equation exhibits its applicability in predicting the change in specificity in XCS as well as reveals several other specificity influences.

Reference
Martin V. Butz, & Martin Pelikan (2001). Analyzing the Evolutionary Pressures in XCS. IlliGAL Report No. 2001009, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL.

Published in GECCO-2001 Proceedings, San Francisco, CA. Pages 935-942.

BibTeX

Download compressed PS (2001009.ps.Z)

Abstract
To solve hierarchical problems, one must be able to learn the linkage, represent partial solutions efficiently, and assure effective niching. Linkage learning results in a good problem solver on a single level. Niching and efficient representation of partial solutions ensure that the algorithm maintains enough alternative solutions on each level to compose the solutions on a higher level. We combine the Bayesian optimization algorithm, which has been shown to solve problems on a single level efficiently, with a powerful niching technique based on crowding and restricted tournament selection. Decision graphs are used as local structures to encode information about the relationships among the variables in a problem. The proposed algorithm is called the hierarchical Bayesian optimization algorithm. Additionally, we propose a new class of hierarchically decomposable problems that are deceptive on each level and show that the proposed algorithm scales up subquadratically on all test problems. The proposed class of problems is called hierarchical traps. Empirical results are in agreement with our recent convergence and population sizing theory.

Reference
Martin Pelikan, & David E. Goldberg (2001). Escaping Hierarchical Traps with Competent Genetic Algorithms. IlliGAL Report No. 2001003, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL.

Published in GECCO-2001 Proceedings, San Francisco, CA. Pages 511-518.

BibTeX

Download compressed PS (2001003.ps.Z)
 
 

Abstract
The paper explains how to download, compile, and use the C++ implementation of the Bayesian optimization algorithm (BOA) with decision graphs (Pelikan, Goldberg, & Sastry, 2000). It provides the instructions for creating input files for the BOA to solve various problems with various parameter settings and for adding new test functions into the existing code. Outputs of an example experiment are discussed.

Reference
Martin Pelikan (2000). A C++ Implementation of the Bayesian Optimization Algorithm with Decision Graphs. IlliGAL Report No. 2000025, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL.

Note
The report is to be used with the implementation of the BOA with Decision Graphs in C++

BibTeX

Download compressed PS (2000025.ps.Z)

Abstract
This paper discusses the use of various scoring metrics in the Bayesian optimization algorithm (BOA) which uses Bayesian networks to model promising solutions and generate the new ones. The use of decision graphs in Bayesian networks to improve the performance of the BOA is proposed. To favor simple models, a complexity measure is incorporated into the Bayesian-Dirichlet metric for Bayesian networks with decision graphs. The presented algorithms are compared on a number of interesting problems.

Reference
Martin Pelikan, David E. Goldberg, & Kumara Sastry (2000). Bayesian Optimization Algorithm, Decision Graphs, and Bayesian Networks. IlliGAL Report No. 2000020, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL.

Published in GECCO-2001 Proceedings, San Francisco, CA. Pages 519-526.

BibTeX

Download compressed PS (2000020.ps.Z)
 
 

Abstract
This paper introduces clustering as a tool to improve the effects of recombination and incorporate niching in evolutionary algorithms. Instead of processing the entire set of parent solutions, the set is first clustered and the solutions in each of the clusters are processed separately. This alleviates the problem of symmetry which is often a major difficulty of many evolutionary algorithms in combinatorial optimization. Furthermore, it incorporates niching into genetic algorithms and, for the first time, the probabilistic model-building genetic algorithms. The dynamics and performance of the proposed method are illustrated on example problems.

Reference
Martin Pelikan, & David E. Goldberg (2000). Genetic Algorithms, Clustering, and the Breaking of Symmetry. IlliGAL Report No. 2000013, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL.

Published in PPSN VI (2000), Paris, France. Pages 385-394.

BibTeX

Download compressed PS (2000013.ps.Z)

Abstract
This paper summarizes our recent research on the Bayesian optimization algorithm (BOA) and outlines the directions our research in this area has been following. It settles the algorithm in the problem decomposition framework used often to understand the complex behavior of genetic algorithms. It provides the most important research issues to tackle and reviews our recent progress in each of these areas.

Reference
Martin Pelikan, & David E. Goldberg (2000). Research on  the Bayesian Optimization Algorithm. IlliGAL Report No. 2000010, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL.

Published in GECCO-2000 Workshop Proceedings, pages 216-219.

BibTeX

Download compressed PS (2000010.ps.Z)

Abstract
The paper discusses three major issues. First, it discusses why it makes sense to approach problems in a hierarchical fashion. It defines the class of hierarchically decomposable functions that can be used to test the algorithms that approach problems in this fashion. Finally, the Bayesian optimization algorithm (BOA) is extended in order to solve the proposed class of problems.

Reference
Martin Pelikan, & David E. Goldberg (2000). Hierarchical Problem Solving by the Bayesian Optimization Algorithm. IlliGAL Report No. 2000002, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL.

Published in GECCO-2000 Proceedings, Las Vegas, Nevada. Pages 267-274.

BibTeX

Download compressed PS (2000002.ps.Z)

Abstract
This paper analyzes convergence properties of the Bayesian optimization algorithm (BOA). It settles the BOA into the framework of problem decomposition used frequently in order to model and understand the behavior of simple genetic algorithms. The growth of the population size and the number of generations until convergence with respect to the size of a problem is theoretically analyzed. The theoretical results are supported by a number of experiments.

Reference
Martin Pelikan, David E. Goldberg, & Erick Cantú-Paz (2000). Bayesian Optimization Algorithm, Population Sizing, and Time to Convergence. IlliGAL Report No. 2000001, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL, 13 pages.

Published in GECCO-2000 Proceedings, Las Vegas, Nevada. Pages 275-282.

BibTeX

Download compressed PS (2000001.ps.Z)

Abstract
This paper 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 further 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.

Reference
Martin Pelikan, David E. Goldberg, and Fernando Lobo (1999). A Survey of Optimization by Building and Using Probabilistic Models. IlliGAL Report No.99018, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL, 11 pages.

Published in Computational Optimization and Applications, 21(1), 5-20. Kluwer Academic Publishers, 2002 (bibtex reference).

BibTeX

Download compressed PS (99018.ps.Z)

Abstract
In this paper, the worst-case analysis of the time and space complexity of the parameter-less genetic algorithm versus the genetic algorithm with an optimal population size is provided and the results of the analysis are discussed. Since the assumptions in order for the analysis to be correct are very weak, the result is applicable to a wide range of problems. Various configurations of the parameter-less genetic algorithm are considered and the results of their time and space complexity are compared.

Reference
Martin Pelikan, Fernando Lobo (1999). Parameter-less Genetic Algorithm: A Worst-case Time and Space Complexity Analysis. IlliGAL Report No. 99014,  Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL.

BibTeX

Download compressed PS (99014.ps.Z)

Abstract
The paper explains how to download, compile, and use the simple implementation of the Bayesian optimization algorithm (BOA) (Pelikan et al., 1998, 1999), version 1.0, written in C++. It provides the instructions for creating input files for the BOA to solve various problems with various parameter settings and for adding new test functions into the existing code. Outputs of an example experiment are discussed.

Reference
Martin Pelikan (1999). A Simple Implementation of the Bayesian Optimization Algorithm (BOA) in C++ (version 1.0). IlliGAL Report No. 99011, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL.

BibTeX

Download compressed PS (99011.ps.Z)

Abstract
In this paper, an algorithm based on the concepts of genetic algorithms that uses an estimation of the joint distribution of promising solutions in order to generate new candidate solutions is proposed. The proposed algorithm is called the Bayesian optimization algorithm (BOA). To estimate the distribution of promising solutions, techniques for modeling multivariate data by Bayesian networks are used. The proposed algorithm identifies, reproduces and mixes building blocks up to a specified order. It is independent of the ordering of the variables in the strings representing the solutions.  Moreover, prior information about the problem can be incorporated into the algorithm. However, the prior information is not essential. Preliminary experiments show that the BOA outperforms the simple genetic algorithm even on decomposable functions with tight building blocks as the problem size grows.
 

Reference
Martin Pelikan, David E. Goldberg, & Erick Cantú-Paz, E. (1999). BOA: The Bayesian optimization algorithm. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-99), I, 525-532. Also IlliGAL Report No. 99003.

BibTeX

Download compressed PS (boa.ps.Z)

Abstract
The paper deals with the Bivariate Marginal Distribution Algorithm (BMDA). It is an extension of the Univariate Marginal Distribution Algorithm (UMDA). The algorithm uses the dependencies of the genes in order to improve algorithms that use simple univariate marginal distributions. BMDA is a special case of the Factorization Distribution Algorithm, but without any a problem specific knowledge in the initial stage. The dependencies of the genes are 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.
 

Reference
Martin Pelikan, & Heinz Muehlenbein (1999). Advances in Soft Computing - Engineering Design and Manufacturing, 521-535.

BibTeX

Download compressed PS (bmda.ps.Z)

Abstract
In this paper, an algorithm based on the concepts of genetic algorithms that uses an estimation of the joint distribution of promising solutions in order to generate new candidate solutions is proposed. The algorithm is settled into the context of 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 proposed algorithm 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. However, the prior information is not essential. Experiments were done with additively decomposable problems. The proposed algorithm was able to solve all tested problems in linear or close to linear time with respect to the problem size without the use of any prior knowledge about the problem.
 

Reference
Martin Pelikan, David E. Goldberg, and Erick Cantú-Paz (1998). Linkage Problem, Distribution Estimation, and Bayesian Networks. IlliGAL Report No.98013, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL.

Published in Evolutionary Computation, 8(3), 311-341, 2002. (bibtex reference)

BibTeX

Download compressed PS (98013.ps.Z)

Abstract
In this paper, the description of two gene pool recombination operators is described. Both operators are based on the estimation of the distribution of the parents and its use to generate new individuals. The Univariate Marginal Distribution Algorithm (UMDA) uses simple univariate distributions. It is a perfect algorithm for linear problems. The Bivariate Marginal Distribution Algorithm (BMDA) is an extension of UMDA. In BMDA, the most important pair dependencies are taken into account. The dependencies are measured by the Pearson's chi-square statistics. The structure of a problem is being discovered during an optimization. BMDA works well for linear problems as well as for problems with interacting genes.

Reference
Martin Pelikan, & Heinz Muehlenbein (1998). Marginal Distributions in Evolutionary Algorithms. In: Proceedings of the International Conference on Genetic Algorithms Mendel '98, Brno, Czech Republic, pp. 90-95.

BibTeX

Download compressed PS (mda.ps.Z)

Abstract
A theoretical base for efficient coding of the part of evolutionary computation, mostly represented by genetic programming, is given. The efficiency of the application of this theoretical approach was already confirmed in programs for symbolic regression [Martin Pelikan, Genetic Programming, Student Case Study, 1996 (in Slovak)]. The Read's coding of rooted trees is outlined, followed by methods of reverse translation of the code into a graph (so-called parsing). Theorem for checking, whether for a given code there exists a corresponding rooted tree, is used by an algorithm for efficient generation of a correct code. Algorithm which keeps correctness of this code of tree, while handling changes and swaps of its part, is presented. Compression os the code of trees corresponding to Koza's "automatic defined functions" is formalized. All the mentioned algorithms are given in a pseodocode.

Reference
Vladimir Kvasnicka, Jiri Pospichal, & Martin Pelikan (1996).  Read's Linear Codes and Evolutionary Computation Over Populations of Rooted Trees. In: Proceedings of the International Conference on Neural Networks Intelligent Technologies '96, Kosice, Slovakia, pp. 141-154

BibTeX

An electronic version of this paper is not available.

Abstract
This paper proposes an analytic framework for the analysis of evolutionary mechanisms of agents. Population dynamics in a simplified computational ecosystem comprised of many agents is studied. The goal is a simulation and a prediction of population development of artificial agents, which are able to reproduce proportionally to the density of their population, and are removed by a constant speed. One-type-agent and two-types-agent models are investigated, with and without competition for the living space. Application of the models can range from computer science (modeling distributed genetic algorithm optimization requiring high concentration of agents for crossover, where agents can be represented by neural networks) to economy (competition of products or technologies on the market, when a more spread product has lower production costs, gets better advertisement and therefore spreads even more) or biology (modeling an epidemic of a contagious incurable disease).

Reference
Vladimir Kvasnicka, Jiri Pospichal, & Martin Pelikan (1996).  Stochastic Simulation of Multiagent Models. In: Proceedings of the International Conference on Neural Networks Intelligent Technologies '96, Kosice, Slovakia, pp. 165-184

BibTeX

An electronic version of this paper is not available.

Abstract
Hill Climbing with Learning - a simple modification of standard hill climbing algorithm by taking into account learning features. Basic concept of this approach is the so-called probability vector, its single entries determine probabilities of appearance of '1' entries in n-bit vectors. This vector is used for the random generation of n-bit vectors that form a neighbourhood. Within the neighbourhood a few best solutions are used for updating probability vector by a formal analogue of Hebbian learning rule. The process is repeated until the probability vector entries are close either to zero or to one. The resulting probability vector unambigously determines an n-bit vector which may be interpreted as an optimal solution of the given optimization task. Resemblance with genetic algorithms is discussed. Effectiveness of the proposed method is illustrated by an example of looking for global minima of a highly multimodal function.

Reference
Vladimir Kvasnicka, Martin Pelikan, & Jiri Pospichal (1996). Hill Climbing with Learning (An Abstraction of Genetic Algorithm). Neural Network World, Vol. 6, pp. 773-796

BibTeX

The paper is not available.

For another page related to this paper, click here.