What are Genetic Algorithms?

Ä    Note: It is not necessary to read this section in order to use TradingSolutions. However, understanding the concepts used in the program can help you to get the most out of the intermediate and advanced features.

Genetic algorithms are general-purpose search algorithms based upon the principles of evolution observed in nature. Even with today’s high-powered computers, using an exhaustive search to find the optimal solution for even relatively small problems can be prohibitively expensive.

For many problems, genetic algorithms can often find good solutions (near-optimal) in around 100 generations. This can be many times faster than an exhaustive search. For example, a chromosome containing 32 binary genes would have 4,294,967,296 possible combinations (solutions) to evaluate when using an exhaustive search. If the same problem were to be solved with a genetic algorithm of population size 50, requiring 100 generations of evolution, the genetic algorithm would only need to evaluate 5000 possible solutions.

As mentioned previously, genetic algorithms are able to find optimal or near optimal solutions by using many of the principles of evolution that can be observed in nature. These include selection, crossover, and mutation. Below is an outline of how a genetic algorithm uses these principals to search for optimal solutions:

1.    Create an initial population of chromosomes. Each chromosome is made up of a collection of genes (the parameters to be optimized) and represents a complete solution to the problem at hand. The gene values are usually initialized to random values within user-specified boundaries.

2.    Evaluate each of the chromosomes in the initial population. A chromosome is evaluated by a fitness function to determine the quality of the solution. This fitness function is problem-specific and defines the genetic algorithm’s objective for the current problem.

3.    Select chromosomes that will have their information passed on to the next generation. The most common selection operator is "roulette selection". This selection operator is based upon the evolutionary principle know as "survival of the fittest", whereby a chromosome’s probability of getting selected is proportional to its fitness. Thus, the good solutions are more likely to survive.

4.    Crossover the selected chromosomes to produce new offspring chromosomes. This crossover occurs according to some user-defined probability (usually high) and results in new chromosomes having characteristics taken from both of the parent chromosomes. The most common crossover operator is "one point crossover". This crossover operator picks a random point within the chromosomes, then switches the genes of the two chromosomes at this point to produce two new offspring. If an offspring takes the best parts from each of its parents, the result will likely be a better solution.

5.    Mutate the genes of the offspring chromosomes. This mutation occurs according to some user-defined probability (usually low) and serves to introduce some variability into the gene pool. Without mutation, offspring chromosomes would be limited to only the genes available within the initial population. For real genes, one of the most common mutation operators simply adds a Gaussian distributed random value to the gene being mutated.

6.    Repeat steps 3 through 5 until a new population of chromosomes has been created. Two chromosomes are selected, crossed-over, and mutated to produce two offspring until there are enough offspring to fill a population the same size as the last population.

7.    Evaluate each of the chromosomes in the new population. Each of the chromosomes in the current population is evaluated by the fitness function, just as the initial population was evaluated in step 2.

8.    Repeat steps 3 through 7 until some termination condition has been met. This termination condition can be based simply on the number of generations or it can be based upon more complex criteria such as the population convergence, fitness convergence, etc.

After the evolution of the initial population through many generations, the chromosomes (or solutions) within the final population will generally be much better as a whole than the chromosomes within the initial population. Also, the best chromosome in the final population will generally be near optimal if the genetic algorithm was run for enough generations.

&  Continue to the next section, Using Neural Networks and Genetic Algorithms for Technical Analysis, or return to the Overview for this chapter.