Sunday, August 28, 2011

Genetic Algorithms.

The hominoids evolved from a common ancestor.  Source.


I have been thinking a lot about genetic algorithms lately.  The idea was introduced to me here, where I lost many an hour watching cars evolve to fit different tracks.  I later saw it being used in the lab where I did my honours thesis, with a peer attempting to design better fuel cells.  Perhaps I shall start with an explanation of what exactly these genetic algorithms (GAs) are.

A GA seeks to mimic the natural evolution that we see in our day-to-day life on Earth.  Take for example how we humans reproduce.  We are produced via sexual reproduction, we get half our chromosomes from our mother and the other half from our father, called "crossover" in terms of genetics and GAs.  After random mutations (which GAs also utilise), we are essentially a genetic experiment.  We have a fairly high success rate currently due to the societies we have built, but in earlier eras survival was not necessarily the virtual guarantee it is now.  Should the organism survive to procreate, it is largely considered a success.  The better the individual, the better the chance of this success.  Therefore, with increasing number of generations, the "good" traits we inherit from chromosomes should come to predominate in the larger population, since ideally those individuals with "bad" traits are less likely to succeed and procreate.

Life, in our case, is the equivalent of a "fitness function" for GAs.  Life determines fitness of individuals by killing off or making the less successful crossovers less likely to breed.  In terms of computers, the fitness will be evaluated based on what the scientist wants to accomplish with the algorithm.  The boxcar example above evaluates the fitness of cars based on how far they get on a given track, and how fast they do it.  A selection process then chooses breeding pairs to create the next generation (with the most successful individuals very likely to reproduce).  Naturally, crossovers of fit individuals does not guarantee fit offspring, but it becomes increasingly likely as the population will "converge" to a solution for a given problem.

Sunlight.  You'll understand if you read the next paragraph.  Source.

By now, my dear reader, you must be wondering what on Earth can be accomplished with a GA.  The answer, really, is whatever you want it to.  A video of a TED talk by Bill Gross was my inspiration for this post.  Bill Gross decided that he wanted to design a solar energy solution using mirrors and Stirling Engines, and he used a GA to do it.  He designed the computer to utilise chromosomes based on mirror pieces in three dimensional space (presumably with random placement and orientation), and with enough time, the GA gave what it felt to be the best solution based on the fitness function used (it sought to maximise the hours of sunlight the device would be useful for).  I highly recommend watching the video, at least so that one can view the results, which are truly remarkable.

The strength of GAs is that, so long as they utilise a good fitness function, they can come up with solutions a human engineer might never come up with.  Perhaps we as humans would think of these solutions with enough time, but we are creatures of habit.  Computers, given enough degrees of freedom, can come up with truly remarkable solutions without the bias towards existing solutions that we humans may exhibit.  These solutions often represent the convergence of an entire population within the computer to one design.  It is just as we humans have come to where we are today through genetics and evolution.

Arguably the most fascinating aspect of GAs is that we are not exactly certain why they work.  There exists no theorem or mathematical proof which would explain why a GA would ever be a good solution.  Additionally, the solutions generated by GAs often catch scientists off-guard.  They look strange and new to us, but must be a good solution, as they have already been tested under the constraints of the fitness function.  Bill Gross, too, was surprised to see what his GA had developed, and like other scientists, had no idea how it had come to such a conclusion.  The only reason we have to think GAs will work is the large GA experiment we see around us, commonly known as life.

As a result of all of this, I have found myself wondering where else GAs could improve our lives.  I also think I could utilise a GA to select a fantasy hockey pool team, a thought that titillates me to no end.  I'm not sure I've done the best job of explaining GAs here, but I hope I've piqued your interest enough that you will do some reading of your own.  It's truly wonderful stuff.