A Step Forward in Studying the Compact Genetic Algorithm

One of the most famous optimization procedures for combinatorial optimization is the Genetic Algorithm (GA). By maintaining a population of solutions, the GA can be viewed as implicitly modeling of the solutions seen in the search process. In the standard GA, new solutions are generated by applying randomized recombination operators on two or more high-quality individuals of the current population (Goldberg, 1989). These recombination operators, such as one-point, two-point or uniform crossover, randomly select non-overlapping subsets of two "parent" solutions to form "children" solutions. By using a crossover operator that preserves groups of parameters from parents to children, the GA attempts to capture dependencies between the parameters implicitly. The poor behavior of genetic algorithms in some problems, sometimes attributed to designed operators, has led to the development of other types of algorithms. The Probabilistic Model Building Genetic Algorithms (PMBGAs) or Estimation of Distribution Algorithms (EDAs) are a class of algorithms which has been developed recently to preserve the building blocks (Larranaga and Lozano, 2001). The principal concept in this new technique is to prevent the disruption of partial solutions contained in a solution by building a probabilistic model.