Learning gene linkage to efficiently solve problems of bounded difficulty using genetic algorithms.

Abstract

The complicated nature of modern scientific endeavors often times requires the employment of black-box optimization. For the past twenty years, the simple genetic algorithm (sGA) has proven to be a fertile inspiration for such techniques. Yet, many attempts to improve or adapt the sGA remain disconnected with its prevailing theory. This theory suggests that the sGA works by propagating building blocks--highly fit similarities in the structure of its solutions--and that it can fail by not recombining these building blocks in one optimal solution. The most successful of previous attempts to facilitate building block recombination have strayed far from the operation of the sGA, resulting in techniques that are difficult to use and implement. This dissertation presents an approach to solving the recombination problem without straying too far from the spirit of the sGA. By learning linkage, which brings the genes that constitute a building block closer together, this approach retains the sGA's operations of crossover and selection. However, this linkage-learning genetic algorithm (LLGA) can only be successful by controlling the forces of selection. It does this by shedding the deterministic mapping present in the sGA between chromosomes and solutions. The resulting algorithm is shown through both theoretical time complexity analysis and experimental verification to efficiently solve a large class of problems that are difficult for the sGA.