So, what is a genetic algorithm?

To herein be found my ongoing, annotated, plausibly correct description of a genetic algorithm…

A genetic algorithm is a process that models the biological process of evolution by natural selection: organisms that manage to successfully breed before they shuffle off this mortal coil being considered tip-top. Those that don’t not really being considered at all.

Of course the selection in simulated evolution is much more directed and focused towards an end goal (especially for optimisation experiments such as the case of minimal sorting networks), but there are also open-ended GAs where initial rules are set and evolution falls out naturally as a result without an end goal in mind.

The mainstay of genetic algorithms are the following stages:

  • Initialisation: Create the initial population. This could be a single individual or many large groups of distinct species.
  • Then, in a continuous loop
    • Calculate fitness: Work out the fitness of all the members of the population (or all the new ones at least).
    • Breed: Produce the next generation of the population.
      • Choose parent(s) for the new offspring. You can have one or two or three or more.
      • Create a new offspring from the combined genetic code of those parent(s). If each child has only one parent, then this is a clone of that parent, else you’ll have to do some crossover of the parents’ genes
      • Give each offspring a number of mutations. A good rule of thumb is one mutation per child, though you can try any number.
    • Cull: remove the excess members of the population down to some population size you’ve decided upon.
    • Terminate?: Decide whether you want to stop. Do you have success criteria? Do you have a maximum number of generations to run the experiment or a maximum amount of time? Will you stop when it looks like there are no new improvements to be had? Do you just think that it’s now good enough?

Some GA’s have used huge populations, two parents with crossover and no mutations. Others use only a single parent, no crossover and a single mutation per child. Without mutation your population isn’t going to improve beyond a few generations. If you’re relying on multiple simultaneous mutations to jump out of local minima, then you’re likely to be waiting a very long time. For my own experiments I tend to go with a single parent, a single mutation per child and lots of wandering through the fitness landscape. The framework, however, should be able to handle whichever parameters the user wants.

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s