Binomially distributed populations for modelling GAs

We discuss a novel model for analyzing the working of genetic algorithms, when the objective function is a function of unitation. The model is exact (not approximate), and is valid for infinite populations. We introduce the notion of a binomially distributed population (BDP) as the building block of our model, and we show that the effect of uniform crossover on BDPs is to generate two other BDPs. We demonstrate that a population with any general distribution may be decomposed into several BDPs. We also show that a general multipoint crossover may be considered as a composition of several uniform crossovers. Based on these results, the effects of mutation and crossover on the distribution of strings have been characterized, and the model has been defined. The time complexity of the algorithm derived from the model is $O(\int^3)$ (where $\int$ is the problem size), a significant improvement over previous models with exponential time complexities, GASIM-a Genetic Algorithm Simulator for functions of unitation-has been implemented, and the exactness of the results obtained from GASIM has been verified from actual genetic algorithm run