Efficiency enhancement techniques for probabilistic model building genetic algorithms

Funder

Organizational Unit

Publications

Dependency structure matrix, genetic algorithms, and effective recombination

Publication . Yu, Tian-Li; Goldberg, David E.; Sastry, Kumara; Lima, Claudio F.; Pelikan, Martin

In many different fields, researchers are often confronted by problems arising from complex systems. Simple heuristics or even enumeration works quite well on small and easy problems; however, to efficiently solve large and difficult problems, proper decomposition is the key. In this paper, investigating and analyzing interactions between components of complex systems shed some light on problem decomposition. By recognizing three bare-bones interactions-modularity, hierarchy, and overlap, facet-wise models arc developed to dissect and inspect problem decomposition in the context of genetic algorithms. The proposed genetic algorithm design utilizes a matrix representation of an interaction graph to analyze and explicitly decompose the problem. The results from this paper should benefit research both technically and scientifically. Technically, this paper develops an automated dependency structure matrix clustering technique and utilizes it to design a model-building genetic algorithm that learns and delivers the problem structure. Scientifically, the explicit interaction model describes the problem structure very well and helps researchers gain important insights through the explicitness of the procedure.

2009-12Journal article

Open access

Application of substructural local search in the MAXSAT problem

Publication . Gonzalez, Pedro Frazão; Lobo, Fernando

Genetic Algorithms (GAs) are stochastic optimizers usually applied to problems where the use of deterministic methods is not practical or when information about how to solve the problem is scarce. Although traditional GAs show good results in a broad range of problems, they do not take into account the dependencies that may exist among the variables of a given problem. Without respecting these links, achieving the optimum can be very hard or even impossible. Estimation of Distribution Algorithms (EDAs) are methods inspired on GAs that are able to learn the linkage between variables without providing any information about the problem structure. These methods use machine learning techniques to build a probabilistic model that captures the regularities present in the population (a set of candidate solutions for our problem). The learned model is used to generate new solutions similar to those present in the population but also with some innovation. The Substructural Local Search (SLS) is a method recently proposed that takes advantage from the model built by the EDA and performs local search in each substructure of the model, providing in the end a high quality solution. This method has shown to improve the e_ciency of the search when applied to di_erent EDAs in several arti_cial problems of bounded di_culty. In this thesis, the utility of SLS in the hierarchical Bayesian Optimization Algorithm (hBOA) (an EDA that uses Bayesian networks as probabilistic model), is investigated in the MAXSAT problem. Results show that SLS is able to improve the e_ciency of hBOA, but only on MAXSAT instances with a small number of variables. For larger instances that behavior is not observed. Additionally, the SLS execution is analyzed in order to better understand the obtained results. Finally, some observations and suggestions are exposed for an improvement of SLS.

2011Master thesis

Open access

Substructural local search in discrete estimation of distribution algorithms

Publication . Lima, Cláudio Miguel Faleiro de; Lobo, Fernando

The last decade has seen the rise and consolidation of a new trend of stochastic optimizers known as estimation of distribution algorithms (EDAs). In essence, EDAs build probabilistic models of promising solutions and sample from the corresponding probability distributions to obtain new solutions. This approach has brought a new view to evolutionary computation because, 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. This dissertation proposes the integration of substructural local search (SLS) in EDAs to speedup the convergence to optimal solutions. Substructural neighborhoods are de ned by the structure of the probabilistic models used in EDAs, generating adaptive neighborhoods capable of automatic discovery and exploitation of problem regularities. Speci cally, the thesis focuses on the extended compact genetic algorithm and the Bayesian optimization algorithm. The utility of SLS in EDAs is investigated for a number of boundedly di cult problems with modularity, overlapping, and hierarchy, while considering important aspects such as scaling and noise. The results show that SLS can substantially reduce the number of function evaluations required to solve some of these problems. More importantly, the speedups obtained can scale up to the square root of the problem size O( p `).

2009Doctoral thesis

Open access