ON MODELING GENETIC ALGORITHMS FOR FUNCTIONS OF UNITATION

We discuss a novel model for analyzing the working of Genetic Algorith ms (GA's), when the objective function is a function of unitation. The model is exact (not approximate), and is valid for infinite populatio ns, Functions of unitation depend only on the number of 1's in any str ing, Hence, we only need to model the variations in the distribution o f strings with respect to the number of 1's in the strings, We introdu ce the notion of a Binomial Distributed Population (BDP) as the buildi ng block of our model, and we show that the effect of uniform crossove r on BDP's is to generate two other BDP's, We demonstrate that a popul ation with any general distribution may be decomposed into several BDP 's, We also show that a general multipoint crossover may be considered as a composition of several uniform crossovers, Based on these result s, the effects of mutation and crossover on the distribution of string s have been characterized, and the model has been defined, GASIM - a G enetic Algorithm Simulator for functions of unitation - has been imple mented based on the model, and the exactness of the results obtained f rom GASIM has been verified using actual Genetic Algorithm runs, The t ime complexity of the GA simulator derived from the model is O(l(3)) ( where l is the string length), a significant improvement over previous models with exponential time complexities, As an application of GASIM , we have analyzed the effect of crossover rate on deception in trap f unctions, a class of deceptive functions of unitation, We have obtaine d interesting results - we are led to believe that increasing values o f pc, the crossover rate, increase the probability of the GA convergin g to the local optimum of the trap function.