Convergence of the Simple Genetic Algorithm to the Two-bit Problems

Yoshikane TAKAHASHI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E77-A   No.5   pp.868-880
Publication Date: 1994/05/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms, Data Structures and Computational Complexity
biological systems,  genetic algorithm,  optimization problems,  two-bit problems,  difference equation system,  convergence,  reproduction,  crossover,  

Full Text: PDF>>
Buy this Article

We develop a convergence theory of the simple genetic algorithm (SGA) for two-bit problems (Type I TBP and Type II TBP). SGA consists of two operations, reproduction and crossover. These are imitations of selection and recombination in biological systems. TBP is the simplest optimization problem that is devised with an intention to deceive SGA into deviating from the maximum point. It has been believed that, empirically, SGA can deviate from the maximum point for Type II while it always converges to the maximum point for Type I. Our convergence theory is a first mathematical achievement to ensure that the belief is true. Specifically, we demonstrate the following. (a) SGA always converges to the maximum point for Type I, starting from any initial point. (b) SGA converges either to the maximum or second maximum point for Type II, depending upon its initial points. Regarding Type II, we furthermore elucidate a typical sufficient initial condition under which SGA converges either to the maximum or second maximum point. Consequently, our convergence theory establishes a solid foundation for more general GA convergence theory that is in its initial stage of research. Moreover, it can bring powerful analytical techniques back to the research of original biological systems.