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:
- The origin of evolutionary computing
- The theoretical foundation of genetic algorithms
- Advantages and limitations of genetic algorithms
From a practical perspective, you will learn how to:
- Apply genetic algorithms to leverage technical analysis of market price and volume movement to predict future returns
- Evaluate or estimate the search space
- Encode solutions in the binary format using either hierarchical or flat addressing
- Tune some of the genetic operators
- Create and evaluate fitness functions
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:
- P-problems (or P decision problems): For these problems, the resolution on a deterministic Turing machine (computer) takes a deterministic polynomial time.
- NP problems: These problems can be resolved in a polynomial time on nondeterministic machines.
- NP-complete problems: These are NP-hard problems that are reduced to NP problems for which the solution takes a deterministic polynomial time. These types of problems may be difficult to solve but their solutions can be validated.
- NP-hard problems: These problems have solutions that may not be found in polynomial time.
The categorization of NP problems using computational complexity
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.