Genetic Algorithms for Engineering
Machine learning is the topic of the hour; so in an attempt to stay relevant I thought I’d join in and share some of my own experience. Genetic algorithms are a ‘learning’ approach that can be used to find the optimum from a problem where there are millions of potential solutions, without having to test them all.
The Life of a GA.
The metaphor is fairly simple, if not incredibly brutal:
Day One: Encoding
It all begins when an uncaring God decides to define a creature chromosome. This chromosome can take many forms, but at its simplest it’s a series of on-off switches representing various states (furriness, pointed ears, fangs, etc.). This is called the encoding stage; the form of the solution is defined.
Day Two: Genesis
Happy with the creature definition, our God randomly creates a large(ish) population of the critters, each with a different chromosome, and puts them in a pen for safe keeping. This is the seed that will be used to start the ball rolling. These individuals (or creatures, in our case) are unlikely to be the solution we were looking for; but that doesn’t matter; they are cheap to create.
Day Three: The Hunger Games
Next, our lovable individuals are all tested against a number of qualifiers (marketability, tendency to turn evil if fed after midnight, etc.) and branded with a score. This is the fitness test, it allows us to rank our current population to find out which are beginning to show the qualities we are looking for in our optimised solution.
Day Four: Rapture
We unleash the velociraptors; only the fittest survive. There’s blood everywhere, and only a small percentage of our population remain- those with the highest fitness ranking. If you believe in nature, these poor, frightened, critters are our best hope to find our solution. Their unfit peers were just taking up memory, representing dead ends on our journey to perfection.
Day Five: The Percy Sledge Chapter
Here’s where it gets weird. We begin to play matchmaker for the remaining traumatised and bewildered creations. But because we don’t want our populace to become so homogeneous that it misses other viable options (becomes trained too early); we blast the new offspring with radiation- randomly mutating their chromosomes. This adds entropy, without which the algorithm can become ‘fixated’ on the first slightly rewarding condition and miss something better.
Day Six: Episode Five
The cycle begins again, ad infinitum (well, almost)- pitting mutant children against their own parents and even grandparents, each successive population is tested, culled and bred. The rules of evolution are clear; the desired (most successful) attributes will start to propagate, and (without variations in the fitness tests), our population will become trained on producing offspring more and more apt at surviving.
Day Seven: The Black Sabbath
Finally the rate of improvement begins to dwindle, and a pair of hands reach out from the sky and pluck out the fittest of the fittest; the creature with the highest ranking- our optimum solution. Looking down at the awed faces of its family and comrades- it is the first to see the bombs drop. Afterwards our perfect creature sits alone on the ledge of the pit- the sole survivor of a brutal algorithm. And the answer our God was looking for.
In Civil Engineering
Genetic algorithms are at their best when they are finding the ‘best’ of a vast array of potential solutions, and where there is a clear relationship between changes in attributes and the fitness of the resulting individual. Although the above example is cruel, our creatures are actually fairly lucky- had we set out on a brute force approach (literally trying every permutation) we would have had to slaughter millions of them. By creating small samples and combining the attributes of the fittest, we are likely to converge on the best solution after a few tens of generations.
In civil and structural engineering this approach lends itself to goal seeking and optimisation. For example, in calibrating a material model you can apply a genetic algorithm to converge on the properties that match the test data. Similarly, there is the opportunity to use them to find the optimum design for a given set of rules.
In my (limited) experience, I would suggest
- Keep your encoding as simple as possible. The clearer the relationship between chromosome change and fitness, the faster you’ll converge on a solution.
- Your fitness function has to be quick to evaluate. If you find yourself talking about doing a finite element analysis, for example, you need to simplify.
- Breeding and mutation can be calibrated, but you’ll get the best solutions if the way you combine your chromosomes ‘persists’ what was best in the parents. A common pitfall, for example, is separating two inter-related attributes so that the resulting ‘positive’ is lost.
If you’re intrigued and fancy giving them a go, I would recommend taking a look at DEAP, which is a Python library that provides the mathematical base of the Genetic Algorithm approach; ‘all’ you need to do is provide a way of encoding and measuring the fitness of your problem/solution.
Welcome to the future!