
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Convergence of the Simple Genetic Algorithm to the Twobit Problems
Yoshikane TAKAHASHI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E77A
No.5
pp.868880 Publication Date: 1994/05/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: PAPER Category: Algorithms, Data Structures and Computational Complexity Keyword: biological systems, genetic algorithm, optimization problems, twobit problems, difference equation system, convergence, reproduction, crossover,
Full Text: PDF>>
Summary:
We develop a convergence theory of the simple genetic algorithm (SGA) for twobit 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.

