Adaptive Genetic Algorithm with Mutation and Crossover Matrices

Nga L. Law, Kwok Yip Szeto

A matrix formulation for an adaptive genetic algorithm is developed using mutation matrix and crossover matrix. Selection, mutation, and crossover are all parameter-free in the sense that the problem at a particular stage of evolution will choose the parameters automatically. This time dependent selection process was first developed in MOGA (mutation only genetic algorithm) and now is extended to include crossover. The remaining parameters needed are population size and chromosome length. The adaptive behavior is based on locus statistics and fitness ranking of chromosomes. In crossover, two methods are introduced: Long Hamming Distance Crossover (LHDC) and Short Hamming Distance Crossover (SHDC). LHDC emphasizes exploration of solution space. SHDC emphasizes exploitation of local search process. The one-dimensional random coupling Ising Spin Glass problem, which is similar to a knapsack problem, is used as a benchmark test for the comparison of various realizations of the adaptive genetic algorithms. Our results show that LHDC is better than SHDC, but both are superior to MOGA, which has been shown to be better than many traditional methods.