Genetic algorithms: novel models and fitness -based adaptive disruption strategies

Abstract

Genetic Algorithms are robust search and optimization methods that have emerged to be effective for a variety of real-world problems. They are stochastic, iterative techniques based on a population of evolving solutions, and draw inspiration from principles of natural evolution and natural genetics. The research described in this thesis contributes to both the theoretical and practical aspects of Genetic Algorithms. The primary goal of this thesis is to develop mathematical models of Genetic Algorithms (GAs), that enable us to simulate their dynamics. Two novel models based on different mathematical characterizations have been presented. The first model, which we refer to as the populationary model, is based on populations that are distributed Binomially over the strings in the population. We develop the properties of these Binomially Distributed Populations (BDPs) for objective functions called functions of unitation, and we characterize the effects of crossover and mutation by decomposing the population into BDPs. The fundamental property of BDPs is that uniform crossover and mutation conserve the Binomial distribution of strings in the populations. Based on these ideas, we develop a GA-simulator, called GASIM, for functions of unitation. GASIM, with a time complexity of O(P) (where P is the string length), presents a considerable improvement over previous approaches that have exponential time complexities. Next, we generalize this populationary model to objective functions called functions of unitation variables, which cover all objective functions defined over binary strings. We extend the notion of BDPs to Generalized Binomially Distributed Populations (GBDPs), and demonstrate that the properties of BDPs generalize to GBDPs. We demonstrate the validity of the generalized model by implementing a GA-simulator for functions of two unitation variables - GASIM 2. The correctness of simulation results obtained from GASIM and GASIM 2 is verified by comparing them with those obtained from actual GA runs. The second model that we consider is to realize a cost-effective approach of simulating GA dynamics. We extend the Schema Theorem to relate the number of Schema instances of generations that are not consecutive. For this purpose, we introduce the notions of fitness moments. We show that the fitness moments of the population in any generation can be exactly predicted from those of the initial population, when considering the effects of selection alone. For modelling the effects of crossover and mutation, we consider realistic approximations for the fitness moments of the disrupted strings. We demonstrate the efficacy of this approach by comparing the predicted fitnesses with those obtained from actual GA runs. The highlight of this approach is the low time complexity of simulation: O(G²), where G is the number of generations for which the GA dynamics has to be simulated. Fitness moments also present a general analysis technique for GAs, and we demonstrate the utility of fitness moments by presenting an analysis of a novel fitness-based controlled disruption strategy in GAs. A second aspect of the work presented in the thesis is the development of two efficient GA variants - the Controlled Disruption Genetic Algorithm (CDGA) and the Adaptive Genetic Algorithm (AGA) - based on the fitness-based controlled disruption strategy. These variants incorporate a fitness-based disruption strategy to simultaneously improve the explorative and exploitative capacities of the GA. The efficacy of CDGA and AGA is demonstrated by comparing their performance with Holland’s GA on standard test functions. AGA, which incorporates fitness-based adaptive crossover and mutation probabilities, is studied in detail. The Schema theorem is rederived for AGA, and the robustness of AGA over a spectrum of multimodal functions is demonstrated. The application of AGA in two real-world problems - Test Generation for detecting faults in VLSI circuits and in optimizing Neural Network weights - is discussed, and the utility of AGA as an efficient search technique is established.