Genetic Algorithms
While reading Emergence by Steven Johnson I came across an interesting observation:
In order to watch Darwinian evolution in action, all you need are objects that are capable of reproducing themselves imperfectly, and having some sort of resource limitation so that there is competition.
That's a small axiom to make evolution work! So I decided to test this hypothesis and went to do some research on it. And surely I soon found a whole field of AI (Artificial Intelligence) research dedicated to this approach dubbed as "Genetic Programming". After reading up on the basics I decided to put it to the test myself on the following problem:
- I defined a 10x10 matrix and plotted two paths (see diagrams below) between opposing corners of the matrix.
- The program simulates a population of x ants trying to randomly walk through the matrix only giving preference to squares that are in its genotype. When an ant visits a square defined on the path, its fitness is increased (like picking up food - you have higher chance of survival).
- Ants that visit most squares have a higher probability of passing on their genes. Initially a gene is random sequence of numbers from 1 to 100, where each number represents a preference for a square in the matrix, and the length of the gene is the length of the path. Thus, a perfect gene is the sequence of numbers that define the path through the matrix.
- Questions was: If we pick the 'fit' ants and randomly cross them with other ants (applying mutations to the genes at random). What will happen from generation to generation?
Restrictions on the problem
- Length of the genotype of each ant is the length of the path.
- Order of the genotype does not matter (to make things simpler).
- At each point the ant can move forward, back and left or right.
- The ant is restricted to a 10x10 matrix of squares. When at the edge, the ant is forced to stay in the matrix by disallowing it to walk off the edge.
- Ant does not go back to square it just came from. (So the ant does have a memory, albeit a very short one).
- Once the ant finds a square on the path its fitness is increased. But if the ant later comes back to same square, its fitness remains the same. (Once you eat the food on the path, it doesn't reappear, so overall fitness is the function of number of distinct squares discovered).
Results
It works flawlessly! And I have to say, even though you expect the result, you get an eerie feeling when you see how well it works. A population of randomly behaving ants with no regard for each other's actions becomes smarter on average with each generation. In the language of Steven Johnson, on the macro level of the population a new global behavior of intelligence emerges from a population that only makes decisions on the micro level. (Economics, Social Sciences, AI...). Got you thinking?
Interesting Observations
- Std. Deviation grows as the average fitness grows and flat-lines once the genome gets close to 'perfect'.
- Before the std. deviation flat-lines average fitness is increasing continuously (aka the population gets smarter with every generation)
- Higher population values result in higher granularity of average growth of intelligence. The population takes a longer time to reach a certain point of average fitness than a smaller population, but unlike small population it does not seem to converge as soon and can grow further overtime.
Generation #1------------------------------------------------------------ Max Fitness: 15 Min Fitness: 1 Avg. Fitness: 5.225 Std.Deviation: 2.2430796701 Generation #2------------------------------------------------------------ Max Fitness: 15 Min Fitness: 1 Avg. Fitness: 5.899 Std.Deviation: 2.2829829196 Generation #3------------------------------------------------------------ Max Fitness: 17 Min Fitness: 1 Avg. Fitness: 6.139 Std.Deviation: 2.4086262642 Generation #4------------------------------------------------------------ Max Fitness: 17 Min Fitness: 2 Avg. Fitness: 6.592 Std.Deviation: 2.5349481182
The function between population, number of moves per ant and the mutation rate is not linear. Rather, it looks like a conditional relationship where the population has to be certain size to solve a problem of size x and number of moves and mutation rate need to be adjusted to the population as well.
There is a critical mass that needs to be reached before the population can get smarter.
- Average member of the population needs to surpass a certain 'IQ' (fitness) value before the population can get smarter as a whole.
- There's a tradeoff in mutation rate. If set too high, the population can't get smart because too much variance is introduced (aka the fit are not at all guaranteed to pass on their genes). But if set too low, the population prematurely converges on a suboptimal solution.
Solutions
So did my program solve the two paths that I defined? Yep! For first path of length 19 the minimum # of generations I could get is 118 before a perfect gene was found.
Population: 2000 ants Genotype Length: 19 Mutation Rate: 40% Steps per ant per generation: 150 Generation #118 ------------------------------------------------------------ Max Fitness: 18 Min Fitness: 1 Avg. Fitness: 13.3315 Std.Deviation: 4.5968655992 ---------------------------------------- Solution Found ---------------------------------------- Solution: 91 64 72 81 82 46 74 44 45 73 37 38 54 36 8 18 28 10 9
For the second path of length 35 the minimum # of generations was 555.
Population: 5000 ants Genotype Length: 35 Mutation Rate: 40% Steps per ant per generation: 150 Generation #555 ------------------------------------------------------------ Max Fitness: 34 Min Fitness: 1 Avg. Fitness: 26.8442 Std.Deviation: 10.2330088075 ---------------------------------------- Solution Found ---------------------------------------- Solution: 27 14 13 32 21 44 84 43 81 12 31 11 26 85 33 45 72 83 55 65 75 73 15 37 16 30 48 63 49 39 10 82 20 47 29
Note: # of generations is not a good measure of performance on a sequential model, since an increase in population size will result in more time to compute the result. But if run in parallel, the results are achieved faster.
Algorithm
My program is not optimized with respect to resources/cpu cycles, I've tried to avoid any obvious resource hogs but I'm sure it can be made to run much faster. I used C#'s ArrayLists throughout the program and I'm sure some parts of my program don't need the overhead associated with them, bitstrings could prove to be much faster (but require more time to code correctly, thus I skipped that part). However, some notable parts of the algorithm are..
Fitness Proportionate Selection (Roulette Wheel Selection algorithm)
After each generation of ants gets a go at the matrix I tally up the fitness scores and assign a probability of that ant being selected as a parent based on its fitness value compared to the rest of the ants. (Hence, Pr(ant#) < 1.0 and the sum of Pr(all ants) = 1.0) This is done through a decision vector implementation where the size of the vector depends on the population size, to account for the need for higher granularity in a large population. This alg'm seems to work fine, but I'm curious if Tournament Selection would give better runtime.
Crossover
I used simple one-point crossover (reproduction) function where two parents are picked by the alg'm described above. Then, a random point in their genotype is decided on and each genotype is split into (A1,B1), (A2,B2). From here a two possibilities for a child can be formed: (A1, B2) or (A2, B1). I randomly decide on the combination, create the child and repeat until the full new population is regenerated.
Mutation
I restricted mutation to introducing new random variables only into the genotype. Alternatively I had a random case where I decide to either introduce a new value or swap phenotype values in different locations within the genotype but that didn't seem to affect the runtime too much so I switched back to the basic case. Once a genome is selected for mutation a random starting point is picked within it, and new values are generated for every subsequent mod(another random variable between 1-5) location.
Possible Improvements
- Formulate the problem in a more interesting fashion. (Ex: Instead of a continuous path, create patches of food and let ants find them, see if they develop a path between all of them)
- Instead of regenerating the population completely, maybe allow a certain top x% of the previous population's genes to continue without being regenerated.
- Allow population to grow with time, this could offset the premature convergence. (However, other variables such as number of steps and mutation rate may need to be adjusted with population growth also).
- Try different selection algorithms. (Tournament Sort)
Download Source Code and Executable - Download Source Code and Executable
Ilya Grigorik is a web ecosystem engineer, author of High Performance Browser Networking (O'Reilly), and Principal Engineer at Shopify — follow on Twitter.