Adaptation on Rugged Landscapes Generated by Local Interactions of Neighboring Genes

Fitness landscapes were constructed by creating phenotypes through 20 iterations of an elementary cellular automaton (CA), with the genotype determining initial state of the CA and bitwise conformity of the CA after iteration to a specified target string determining fitness. Landscapes were classified by the rule class of the CA rule which generated them (Li-Packard classification) and by several global measures of the landscape itself. A genetic algorithm (GA) simulated adaptation on these landscapes. Landscapes generated by Class 3 (locally chaotic) CA rules had very infrequent local optima and were easy for GAs to adapt on. This suggests that bounded chaos--in which small changes in the genotype produce substantial but contained changes in the phenotype or fitness function--is a characteristic of GA representation which increases search effectiveness. Class 4 (chaotic) rules were most difficult for all GAs, and were more difficult for GAs which used crossover and mutation than for those using mutation only. Landscapes with low correlation lengths (a global measure) were the most difficult, and highly uncorrelated landscapes were more difficult for crossover GAs than for mutation-only GAs. These results suggest that crossover often reduces GA performance on low-correlation and chaotic fitness functions. Mean hill-climbing walk length to a peak is closely tied to GA performance: nearly all difficult landscapes were those with mean walk length near 1.