Genetic Algorithms: A Primer

I have meant to blog about genetic algorithms since the inception of Down to Earth. At that time, I was reading many more accounts of ID vs. evolution than I am now, and some of that discussion didn't have a complete understanding of what engineers do today. Genetic algorithms (GA) are types of computer models that incorporate processes inspired by evolutionary biology such as selection, inheritance, mutation, and recombination. Possibly the most prolific users of GAs are engineers, so as an engineer and scientist I thought I’d broach the topic.

GAs are used to find optimal solutions to complex problems, though in practice you can never be sure they find the absolute optimum instead of just a local optimum (just as in evolution). In other words, if you built a GA to find the highest peak in the world, it might not find Everest, but instead identify Mt McKinley or Mt Cook. If your objective were to find a mountaineering challenge, perhaps this error doesn’t matter. Similarly, evolution doesn’t produce the best organisms for a given environment, but rather organisms that are good enough. The factors controlling whether or not you find Everest is the set (or population) of places where you start looking, and how you look.

The initial population is usually some random set of descriptions of an individual – the genes of the DNA. If seeking the highest peak, this could simply be the lat-long location. Initial locations could therefore be Madison, Dunedin, or Lake Vostok.

How you look is where the evolutionary lessons come in. GAs go through many iterations to find the answer. In each iteration, you look at your population and measure the individuals’ fitness (subject to a prescribed rule). Then you select the next generation based on the information contained in the previous one. If you’re looking for the highest peak, fitness would equal elevation and the DNA would equal your lat-long coordinates. The next generation could be a mix of the following: (a) the half-way point between two previous locations (inheritance); (b) some previous location with a slight random difference in latitude and longitude (mutation); or (c) swap latitudes between two locations but not longitudes (recombination).

The final step in the GA is to know when to stop. If subsequent iterations produce no appreciable increase in fitness, or no increase at all, depending on yet another rule, then the iterations stop, and you have your answer. All of these steps are depicted in the flow chart above.

Now that we understand how genetic algorithms function, what are they used for? The Wikipedia entry has a long list of applications, a list that is very much incomplete. Applications that are closer to home, and Down to Earth, are the identification of optimal irrigation schedules, calibration of numerical models, and building a mechanistic understanding of the diversity of plant traits across environments. I’ll delve into these in subsequent posts.