Genetic algorithms, what are they…?

If you have ever written a computer program, they you should know what an algorithm is: basically, a very detailed step-by-step description on how to solve a particular problem. At its core, programming really is about designing and implementing algorithms, algorithms that use the vocabulary of your favorite computer language to manipulate data, address locations or various libraries or API’s, such as those for I/O and IPC.

If you have never written a computer program, then you can think of algorithms as the recipes for cooking that you can find in any cookbook: again, a step-by-step description to create a “solution” (tasty dish) for a problem (you being hungry). The recipe (“algorithm”) tells you what steps to take to solve the problem, i.e. the “how“.

The point I want to make here is that in order for a programmer to make the computer to solve a problem – any type of problem – the programmer has to come up with an algorithm that in minute detail exactly describes how the computer should go about to solve the problem – the computer does not possess any kind of intelligence or creativity that would enable it to by itself figure out how to solve the problem.  Basically, the job of a programmer is to provide the mapping from the “what”, i.e. the problem to be solved, to the “how”, i.e. the exact sequence of steps the computer needs to take to perform the task at hand.

So, the above is the way we have been solving tasks using computers since the dawn of computing: programmers entering exact sequences of commands into the computer, commands that tell the computer exactly what to do, step-by-step.

Genetic algorithms (GA’s) operate in a fundamentally different way: while “traditional” algorithms rely exclusively on the programmer’s intelligence and ability to come up with an algorithm that does the trick, genetic algorithms rely solely upon evolution!  Genetic algorithms are not invented/discovered/created/implemented by a smart programmer, genetic algorithms evolve, much by “trial & error”, from previous generations of themselves.  In essence, a successful genetic algorithm – i.e. an algorithm “designed” by evolution, that is capable of successfully solving a specific problem – is the result of thousands of generations of predecessor algorithms that used trial & error to figure out better and better ways to solve the problem at hand.  A genetic algorithm uses Darwinian/evolution theory concepts such as DNA, mating, mutation and survival of the fittest to evolve a solution to a problem.

So, when working on a genetic solution to a computer program, the programmer’s job is not to come up with the algorithm that will solve the problem.  That’s the job of the GA evolution. Instead, the programmer’s job is to create a simulation environment where the “experiment”,  aiming at finding the optimal (or good-enough) algorithm,  can take place, i.e. where the evolution can run. Perhaps the most challenging task when working on genetic algorithms is to define the “fitness function”, i.e  the function that the simulation environment uses to evaluate the performance or fitness of each generation of the evolving algorithm: basically, it is the job of the fitness function to decide which characteristics (“DNA sequences”) are successful, and which are not.  The (relatively) successful algorithms from a given generation are allowed to survive and mate with other successful algorithms to create the next generation, while the less successful variants are eliminated.

To continue with the cooking analogy: if you’d apply the GA approach for cooking, you’d hire hundreds or thousands of  completely imbecile and ignorant “chefs”, and let them go about in which ever way they’d can to implement a first generation of dish for you. These initial generation “chef’s” don’t have to know anything about cooking, just let them try whatever they want. Almost all of them will fail miserably, and most likely no one will produce anything you’d want to have on your plate. Still, your job is to be the judge, i.e. the fitness function: at the end of the lifetime of the initial generation of chefs, your job is to evaluate their performance, and to select the “best” chefs, allowing them to reproduce. You’d also throw in some random mutations among the survivors. Then, let the next generation do their best, and so on. While you’d end up with piles of non-edible dishes for the first few hundred generations, eventually, after a few thousand generations,  you’d most likely be presented a dish that would reward you with three stars in Guide Michelin!  The problem with this approach in the real – non virtual – world is that few of us are willing to wait a few thousand generations to see the results, but in the virtual world of computers this type of evolution can be run in an hour or two.

GA’s are today successfully used in many domains, from aerodynamics to logistics to finance to games and movies, particularly when addressing problems that are hard if not impossible to solve with the traditional programming approach described at the top of this post.

An good introduction to GA’s can be found in Melanie Mitchell’s excellent book, “Complexity – a guided tour“, and I’ve written an example implementation to the GA problem described in Melanie’s book, and placed the code under open source licence on Github.  You are welcome to give it a go.  The README-file describes the problem and how to build and execute the program.

Advertisements

About swdevperestroika

High tech industry veteran, avid hacker reluctantly transformed to mgmt consultant.
This entry was posted in development, software and tagged , , , , , . Bookmark the permalink.

3 Responses to Genetic algorithms, what are they…?

  1. Here’s a great TED video showing what GA’s can do. http://www.ted.com/talks/torsten_reil_studies_biology_to_make_animation.html

    and this was 9 years ago.

  2. Pingback: Computer Scientists discover nature’s tendency to produce modular systems | systems-software-development-perestroika

  3. Pingback: Dynamic non-linear systems | systems-software-development-perestroika

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s