Genetic Algorithms And Evolutionary Learning .*;
Simple Function Example 4
This one is a significant improvement over Example 2 and Example 3, but includes several new options and more code improvements. As before, it's a simple genetic algorithm that generates combinations of five numbers and four operators with results that aim toward a target number.
Three new methods of selection are included: Roulette Wheel, Stochastic Universal Sampling, and Truncation Selection. The General Random method is still available.
Roulette Wheel Selection:
The individuals are mapped to contiguous segments of a line, such that each individual's segment is proportional to its fitness. A random number is generated and the individual whose segment spans the random number is selected. The process is repeated until the desired number of individuals is obtained. This technique is analogous to a roulette wheel with each slice proportional in size to the fitness of the individuals.
Stochastic Universal Sampling:
The individuals are mapped to contiguous segments of a line, such that each individual's segment is proportional to its fitness; exactly as in roulette-wheel selection. Here equally spaced pointers are placed over the line as many as there are individuals to be selected. The position of the first pointer is given by a randomly generated number, the rest of the pointers are equally spaced up to the end of the line.
Similar to the general random method, but only the best individuals are selected for parents. The parameter for truncation selection is the truncation threshold "Trunc". Trunc indicates the proportion of the population to be selected as parents and takes values ranging from 50%-10% (higher percentages can be used, but they tend to stagnate the population). Individuals below the truncation threshold do not produce offspring.
Here's where to choose between selection options.
Simply leave one of these functions uncommented in the GeneticAlgorithm() function.
Also included is the option to use double-crossover or single-crossover. The previous examples only used single-crossover.
In this example, no chromosomes are removed from the population. New offspring are created and the population grows exponentially. The Chromosome class is used to store data about each chromosome (i.e.; data, fitness, etc.). An instance of Visual Basic's ArrayList collection class is used for the Population array, which contains and manages all instantiated chromosome objects.
Here's where to choose between crossover options.
// SingleCrossover(ParentA, ParentB, NewChildIndex)
DoubleCrossover(ParentA, ParentB, NewChildIndex)
Simply comment out one of these function calls in the Mating() function.
Selection Probability is a new addition that is used in this example.
Note however, that Region and Age are not being used in this example. These two are just remnants of experiments I was doing along the way. At one point, I wanted to see if I could speed up the algorithm by removing some of the chromosomes that were regularly not selected for mating (e.g.; Age could signify how many epochs a particular chromosome went without mating). Region is part of another experiment I haven't quite finished yet. The Region variable would allow the algorithm to separate groups of chromosomes into regions, allow them to evolve, then mix groups together through migration.
These are the constraints of this example:
- Selection is accomplished using the General Random method, Roulette Wheel, Stochastic Universal Sampling, or Truncation Selection methods. Any one of these can be chosen by commenting and uncommenting the function calls in GeneticAlgorithm().
- The usual operator precedence rules of algebra are not used, the expressions are simply evaluated from left to right.
- The option to use either single or double crossover can be chosen by commenting or uncommenting the function calls in Mating().
- The population's starting size "StartSize" needs to be set (instead of the MaxSize used in the previous examples).
- The maximum number of offspring that can be created during each epoch, "oRate" needs to be set.
Start Size = 75, Mating Rate = 0.7, Mutation Rate = 0.001, Offspring Rate = 20, with Roulette selection and single crossover. All things considered, I personally think that general random selection is about as fair to all chromosomes as roulette. Also note that a larger start size and offspring rate will increase the chances that the algorithm will hit the target sooner.
... 100011000010101100111101100111000001 = -1 72.1739130434783% 001111100110101100101110001111000101 = 55 88.4057971014493% 001111110001101100011011011011101000 = 80 95.6521739130435% 010011100111101000011011000011000111 = 22 78.8405797101449% 011011001001101001001111000111000010 = -1 72.1739130434783% 100010110110110100101100010110110101 = 12 75.9420289855073% 000111011000110010001011000011000001 = -16 67.8260869565217% 010110110100110101001101100110110100 = 0 72.463768115942% Chromosome total = 105 Chromosome total = 82 Chromosome total = 88 Chromosome total = 82 Chromosome total = 83 Chromosome total = 109 Chromosome total = 109 Chromosome total = 81 Chromosome total = 83 Chromosome total = 92 Chromosome total = 115.5 Chromosome total = 81 Chromosome total = 89 Chromosome total = 91 Chromosome total = 114 Chromosome total = 112 Chromosome total = 81 Chromosome total = 118 Chromosome total = 116 Chromosome total = 109 Chromosome total = 88 Chromosome total = 95 Chromosome total = 108 Chromosome total = 93 Chromosome total = 98 Chromosome total = 100 Done. 010011101001110000111110001110110001 4 * 9 - 3 * 3 + 1 = 100 Completed 88 epochs. Encountered 1 mutations in 1064 offspring.