Title: A lower-bound result on the power of a genetic algorithm
Author: Kihong Park, Computer Science Dept., Boston University
Date: October 12, 1994
Abstract:
This paper presents a lower-bound result on the computational power of
a genetic algorithm in the context of combinatorial optimization. We describe
a new genetic algorithm, the merged genetic algorithm, and prove that
for the class of monotonic functions, the algorithm finds the optimal solution,
and does so with an exponential convergence rate. The analysis pertains to the
ideal behavior of the algorithm where the main task reduces to showing
convergence of probability distributions over the search space of combinatorial
structures to the optimal one. We take exponential convergence to be indicative
of efficient solvability for the sample-bounded algorithm, although a sampling
theory is needed to better relate the limit behavior to actual behavior. The
paper concludes with a discussion of some immediate problems that lie ahead.