This chapter introduces the concept of evolutionary computing. Algorithms derived from the theory of evolution are particularly efficient in solving large combinatorial or NP problems. Evolutionary computing has been pioneered by John Holland [10:1] and David Goldberg [10:2]. Their findings should be of interest to anyone eager to learn about the foundation of genetic algorithms (GA) and artificial life.
This chapter covers the following topics:
From a practical perspective, you will learn how to:
The theory of evolution, enunciated by Charles Darwin, describes the morphological adaptation of living organisms [10:3].
The Darwinian process consists of optimizing the morphology of organisms to adapt to the harshest environments—hydrodynamic optimization for fishes, aerodynamic for birds, or stealth skills for predators. The following diagram shows a gene:
The population of organisms varies over time. The number of individuals within a population changes, sometimes dramatically. These variations are usually associated with the abundance or lack of predators and prey as well as the changing environment. Only the fittest organisms within the population can survive over time by adapting quickly to sudden changes in living environments and new constraints.
NP stands for nondeterministic polynomial time. The NP problems' concept relates to the theory of computation and more precisely, time and space complexity. The categories of NP problems are as follows:
Problems such as the traveling salesman, floor shop scheduling, the computation of a graph K-minimum spanning tree, map coloring, or cyclic ordering have a search execution time that is a nondeterministic polynomial, ranging from n! to 2n for a population of n elements [10:4].
NP problems cannot always be solved using analytical methods because of the computation overhead—even in the case of a model, it relies on differentiable functions. Genetic algorithms were invented by John Holland in the 1970s, and they derived their properties from the theory of evolution of Darwin to tackle NP and NP-complete problems.
A living organism consists of cells that contain identical chromosomes. Chromosomes are strands of DNA and serve as a model for the whole organism. A chromosome consists of genes that are blocks of DNA and encode a specific protein.
Recombination (or crossover) is the first stage of reproduction. Genes from parents generate the whole new chromosome (offspring) that can be mutated. During mutation, one or more elements, also known as individual bases of the DNA strand or chromosomes, are changed. These changes are mainly caused by errors that occur when the genes from parents are being passed on to their offspring. The success of an organism in its life measures its fitness [10:5].
Genetic algorithms use reproduction to evolve a population of possible solutions to a problem.