Genetic Algorithms.., A Primer

It is Charles Darwin’s 200th birthday. So I guess there must be loads of posts on GA, strewn across the Internet. Genetic Algorithms are special to me because they are the prime reason why I am doing whatever it is that I am doing.

This post is a light intro to Genetic Algorithms, sans its terms. Genetic Algorithms are delightfully simple. GA is an approximation algorithm, that is, they are used in situations where either the optimal solution is unnecessary or the complexity of the problem does not permit it. Sometimes, the Genetic Algorithm may produce the most optimal result also. Since examples are the best way to learn an algorithm, here’s the example problem we are to solve.

Balancing moments

Balancing moments

Given to you is a configuration of balances as shown in the figure. The problem is to balance the configuration by adding weights on either side. You are provided with 10 weights measuring 1,2,3……10 kg each. Each weight is to be used exactly once. Thanks to GreatBG for this puzzle. His puzzles are always most entertaining. This can roughly be equated to the traveling salesperson problem. In the problem, the salesperson is to visit all cities (and comeback ), in such a sequence so as to minimize the total distance covered. The most naive solution is to try all possible sequences and see which one gives the minimum cost. For a map of n cities, that comes to n! combinations. A similar approach would work in our case also, but then, when the map or the number of weights is larger, the technique, takes so much more time. A more professional approach would be ruffle up your knowledge of elementary physics and reduce the problem to a set of linear equations and then solve them. Naaa.

Genetic Algorithms

My code, in C++, is here. Here’s the pseudo-code, sourced from wikipedia

  1. Choose initial population
  2. Evaluate the fitness of each individual in the population
  3. Repeat until termination: (time limit or sufficient fitness achieved)
    1. Select best-ranking individuals to reproduce
    2. Breed new generation through crossover and/or mutation (genetic operations) and give birth to offspring
    3. Evaluate the individual fitnesses of the offspring
    4. Replace worst ranked part of population with offspring

Initializing the Population

The algorithm maintains a set of solutions. Not optimal solutions, just solutions. For example, in the case of the TSP, it may be a set of random ordering of the cities. In our problem, a set of random configuration of weights. In the program, I maintain the configuration as a string, where the weight alloted to each slot is represented by a character, with ‘A’ being 1, ‘B’ being 2 and so on. The weights are added bottom to top and left to right. One point to be noted here is that all solutions in the set must stick to the constraints of the problem. No city must be re-visited, no weight can be added twice.

Evaluating the Population

This is the key part of the algorithm. Once a way is found to evaluate each member of the ‘population’, the problem is half complete already. In our case, the “fitness” will be based on the resultant moment in the system. Therefore, best solution will have 0 fitness, the resultant moment in the system would be zero.

Until the required precision is obtained, or a maximum limit on the number of iterations is reached, we continue by doing the following opertions.

Crossover

This is where we actually begin to understand why it is called Genetic Algorithms in the first place. According to Darwin’s thery of Natural Selection, the best members of the population mate to produce better offsprings. Similarly, in our algorithms, the best solutions found so far mate with each other to (hopefully) produce a better solution. In code, this translates as the merging of substrings from different members, chosen from among the best solutions found so far. Point to be noted is that if done improperly, this could result in an offspring, that is not even a valid member of the population. It might violate the problems’ constraints. In TSP, and in this case, the same city/weight might get listed again, which cannot be allowed. So we use a special crossover method called, Partially Matched Crossover(PMX in code) which is beyond the scope of a primer.

Mutation

Some members of the population are randomly chosen to be mutated. Mutation is a process by which the offsprings get a trait that is inherited neither from the father nor the mother.While translating into code, this simply means swapping two characters within the string. You can choose more complex mutation techniques if desired. Again, the problem constraints must be satisfied. Mutation is required mainly to increase the variety of solutions in the population. Variety is very important.

Natural Selection and Elitism

Once these operations are done on the parents, a new generation of solutions are born. To make sure that the best solution in this generation is atleast as good as the best one in the previous generation, we introduce “elitism”. Normally, all the individuals in the previous generation are replaced by the members from the newer generation. But by having a non zero elitism value, a small portion of the best solutions from the previous generation survive on in the next generation.

Going by the paradigm of survival of the fittest, we now select the best solutions from the both the generations and these form the actual next generation. (My code is slightly varied. It does not use natural selection, the members of the younger generation simply replace all but the elite members of the elder population)

Local Maxima

Genetic Algorithms suffer from the problem that it might converge to a non-optimal solution. Consider that we are looking for the solution that is at the top of a mountain. It is possible that the population end up on an elevated hill, far away form the mountain. This is possible if the various values are not tuned properly. The algorithm will not get out of this situation by itself. the best way to go in this kind of a scenario is to simply start again.

People, Blogs, Conferences and Applications

The Game of Life

This is not an article on philosophy.

This is about a zero player game called, Life.

Considering its a zero – player game, who would want to play it???

Gosper's Glider

Gosper

But before that, let me just give you a brief intro on what it is and how it is played. It is what one would call in computer science terminology as a cellular automaton. Cellular automatons are studied primarily by biologists, mathematicians and Computer Scientists.

In the second year of our computer science course, we had a paper on Thoery of Computation. And “automata”

was the most uttered word in the class. The paper was complete theory and did not seem to give any scope for fun or enjoyment, unless you were a nerd, or a mathematician.

It was in Robert Kruse’s, Data Structures and Design, that I first came across Life. So here’s the deal.

The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead. Every cell interacts with its eight neighbours, which are the cells that are directly horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

1. Any live cell with fewer than two live neighbours dies, as if by loneliness.
2. Any live cell with more than three live neighbours dies, as if by overcrowding.
3. Any live cell with two or three live neighbours lives, unchanged, to the next generation.
4. Any dead cell with exactly three live neighbours comes to life.

The initial pattern constitutes the ‘seed’ of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed — births and deaths happen simultaneously, and the discrete moment at which this happens is sometimes called a tick. (In other words, each generation is a pure function of the one before.) The rules continue to be applied repeatedly to create further generations.

Simple. Very basic indeed, simulations of how Life may exist, overcrowding, loneliness, all only too familiar for us humans. Simplicity is always a defining characteristic of an automaton. So there would be starting population, and once the sequence starts, it continues, without any intervention.

I see no further point in explaining in theory about stuff that you really can enjoy once you see it for yourself. I’ll direct you here to a Java Applet at Math.comhere Somewhere in the page is a link to a Java applet. I had also seen an online Flash implementation, as an active essay, which I am unable to retrieve now. Anyway, Go ahead. Experiment. Try your own signature, and see what it results in. How about if you draw a smiley, what happens??? Chances are most likely that the population eventually dwindled into nothing or it stabilised, i.e.., split up and formed gangs, stopped interacting with other gangs, and eventually settled down.

When John Conway published his ideas in Scientific American in 1970, he had conjectured that there could not exist initial populations, that would neither die off nor stabilise. He offered $50 as prize money to anyone who could prove or disprove his conjecture. A team from MITlead by Bill Gosper won the prize. Gosper disproved Conway’s idea by developing an initial population, called the Glider Gun, which generated a glider after every 30 generations. Thats the picture at the top of the page. Eventually more and more initial populations were found that had traits similar to the Glider Gun. Many of them were more or less.., Guns. After every X generations the population would produce a unit that would fly away, and live an endless life. I have provided a link at the bottom, in case you are interested.

Glider

Glider

Gosper’s glider was a hit. So much that, this symbol called ‘Glider’, to the right was proposed to be adopted as the symbol of the hacker community. “The Hacker Community” I am referring to here is not the one that goes around busting the Internet. Any enthusiastic coder, who tweaks a software.., could be roughly called a programmer. I am obliged to give a reference here.

[ A similar, but not related concept is the Collatz Sequence. A simple rule indicating what one particular number would mutate into next. The sequence of numbers end, when you reach one. The conjecture is that from any number, on applying the rules, it always ends in the same pattern => 16-8-4-2-1 ]

It only gets more interesting. This, “Game of Life is said to be Turing Complete“. A Turing machine is essentially an infinite tape with a pointer attached to it. But, amusingly, you can do EVERYTHING using a Turing machine that you can do using a modern day computer. It may sound , a little insane perhaps, when I say that a tape can simulate a PC. I restate, this Game can simulate your PC. Look at it this way. You would believe it if I say that AND, OR and NOT gates could simulate a PC. Naturally, that’s what PCs are made of right? Maybe it would sound a little more sane or credible to say that the game can simulate all of these gates.

Hash Life

Consider implementing the Game of Life using say, Java. Most normal approach is to keep two copies of a 2D Boolean array and juggle between them as the current population. Bill Gosper also developed an algorithm for a much faster implementation of Life called Hash Life. There are various places where one could tweak the original approach, but Hash Life remains the one of the fastest algorithms known. I hear that there are only 200 or so implementations of the algorithm all over the world. Maybe one day, I could implement one on my own…

In retrospect, John Conway’s implementation was using using stones and pebbles.

A crazy Proposition

I have been recently getting more interested in Evolution, physiology and Genetic Algorithms. And I started wondering if one could evolve an initial population that would keep multiplying. It seems utterly non-sense in one sense in that the “World” is utterly chaos. How do you judge the fitness of populations? How would one implement a cross-over?? Anyway, just a crazy idea. I just wanted to put it down, in case, somebody stumbles upon it and gives me a hint.

Further Reading: