Evolutionary Informatics

Genetic Algorithms and Irreduciblity

Eytan H. Suchard Email: Eytan_il [at] netvision [dot] com

Abstract

Genetic Algorithms are a good method of optimization if the target function to be optimized conforms to some important properties. The most importantof a is that the sought for solution can be approached by cumulative mutations such that the Markov chain which models the intermediate genes has a probability that doesn't tend to zero as the gene grows. In other words each improvement of the gene — set of 0s and 1s — follows from a reasonable edit distance — minimum number of bits that change between two genes — and the overall probability of these mutations does not vanish. If for reaching an improvement, the edit distance is too big then GAs are not useful even after millions of generations and huge populations of millions of individuals. If on the other hand the probability of a chain of desired mutations tends to zero as the chain grows then also the GA fails. There are target functions that can be approached by cumulative mutations but yet, statistically defy GAs. This short paper represents a relatively simple target function that its minimization can be achieved stepwise by small cumulative mutations but yet GAs fail to converge to the right solution in ordinary GAs.

[ PDF | CODE ]