Genetic Algorithms

Genetic algorithms are derived from biological themes associated with DNA. A series of genotypes are generated, which are random strings of ones and zeros. The group of them constitute a population. To get from random strings to solving a problem, there needs to be a mechanism, similar to transcription, which maps the unique combination of ones and zeros to a process which solves the problem. This is called a fitness function.

The fitness function takes the ones and zeros, and implements a solution. By calculating a fitness function for each genotype, the quality of the solution that a genotype encodes is determined. Some solutions are going to be better than others. The fitness selection process selects some of the best genotypes and combines features from pairs of those, some are mutated slightly by changing a 1 to 0 or vice versa, and the worst are replaced. This cycle is referred to as a generation. This cycle is then repeated. Over time, the solutions that are closer to solving the problem become more common. Eventually, the problem is sufficiently solved and the process completes. The particular flavor of genetic algorithms/programming used is a technique called grammatical evolution.

Grammatical evolution uses a grammar in a Backus-Naur form, which defines variables and statements, using the genotype as selector of the form. The met hod is particularly useful because it can produce syntactically correct programs, and enables a great deal of control over output from modest changes to fixed sets of statements to a wildly unconstrained profusion of code.

Implementation

This implementation of grammatical evolution in Python:

• Supports wrapping of the genotype while mapping
• Can extend the genotype length while wrapping, allowing more nuanced crossovers and mutations
• Supports runtime mapping of variables. The program is not simply predefined and run, but can continue to pull random but reproducible variables and functions during runtime.
• There are a number of fitness selection options, such as Elite, Tournaments, Fitness Proportionate, and Linear Ranking.
• Mutations can be applied once per genotype, or apply a low mutation probability per genotype bit.
• Crossovers have a choice of one or two children.