Genetic algorithm sounds like terminology from a B-rated sci-fi movie. Just what is a genetic algorithm? Is it human? Is it a computer? Is it alive? Is it the mutant offspring from some defunct Government experiment? All of these questions, and more, will be answered within the pages of this paper. The adventure will begin with a trip back in time to the roots of genetic algorithms. From there, the journey will press on to the inventor, or the father of genetic algorithms, Dr. John H. Holland at the University of Michigan. Finally, moving forward in time, covering a span of over twenty years from the inception of the genetic algorithm to its present day representations and applications, the terminology and concepts behind these algorithms will be explored.
"God . . . created a number of possibilities in case some of
His prototypes failed-that is the meaning of evolution."
Graham Greene (1904-91), British novelist.
Mr. Visconti, in Travels With My Aunt, pt. 2, ch. 7 (1969).
Nature - it is all around us. We see it everyday, and we are even a part of it. It is so simple, but yet, so complex and over thousands of years, it has changed to adapt to its environment. This process of change is called evolution. It is not a process that we are overtly aware of, however, we are products of it. It can be said that the process of evolution is a process of adaptation. Adaptation is the part of evolution that has captivated computer scientists since the beginning of the computer age. Back in the 1960's the process of adaptation intrigued John Holland. This intrigue led him to study it formally. He believed that somehow this process, or the mechanisms of this process, could be captured in a computer. He proceeded to develop ways to do just that.
Between the 60's and 70's, Dr. Holland, along with his students and colleagues, laid the foundation for an area of artificial intelligence (AI) research that is now called genetic algorithms. Genetic algorithms are not a separate discipline under AI research, but are considered part of evolutionary computation. The field of evolutionary computation is mainly made up of evolution strategies, evolutionary programming and genetic algorithms. Research in this field is based on "the idea that evolution could be used as an optimization tool for engineering problems."  The common thread in all evolutionary systems is the belief that it is possible "to evolve a population of candidate solutions to a given problem, using operators inspired by natural genetic variation and natural selection."  John Holland's original intent was not to design algorithms that solve specific problems, as was the mindset of the day, but instead to study the process of adaptation.
In nature, natural selection occurs partly through the functions of crossover, inversion, and mutation, which will be defined later. Natural selection also occurs through reproduction and death. One of the basic ideas...