Intelligent recombination using genotypic learning in a collective learning genetic algorithm

Standard genetic algorithms have difficulty finding optimal solutions to combinatorial optimization problems when the problem representation results in interdependent bits that are not proximally located on the chromosome. The objective of this research was to design and test an approach to genetic algorithms that employs genotypic learning to do intelligent recombination, in an effort to partially address this problem.; This research introduces a new Collective Learning Genetic Algorithm (CLGA) which applies Collective Learning Systems Theory to do intelligent recombination based on a cooperative exchange of knowledge between interacting chromosomes. Each individual in the population observes a unique set of features in the chromosomes with which it interacts in order to explicitly estimate the average fitnesses of schemata in the population, and to use that information to guide recombination. Stages of evolution are still controlled by a global algorithm, but much of the control in the CLGA is distributed among chromosomes that are individually responsible for recombination, mutation and selection. The primary research hypothesis of this work is that the CLGA is capable of effectively and efficiently finding high quality solutions to combinatorial optimization problems over a large range of epistasis.; The effects of various operating parameters on CLGA performance were investigated to provide insight into CLGA behavior. Performance was found to be independent of the size of features observed, indicating that the CLGA's success is not due to explicit linkage learning. Intelligent recombination was found to behave similar to more standard recombination operators on low epistasis problems, but more similar to mutation on high epistasis problems. This was attributed to the fact that decisions in the CLGA are based on the consistency of information provided by the environment. When epistasis is high, the variance of decisions is high, causing the CLGA to behave more randomly; when epistasis is low, decisions are more informed causing the CLGA to behave more intelligently. The result is a form of adaptive implicit mutation.; The major contributions of this work are the introduction of a new paradigm for implementing genetic algorithms, and the confirmation of the utility of genotypic learning as a mechanism for adapting recombination to the degree of problem epistasis.