My intention with this article is to give an intuitive and non-technical introduction to the field of evolutionary algorithms, particularly with regards to optimisation.
If I get you interested, I think you’re ready to go down the rabbit hole and simulate evolution on your own computer. If not … well, I’m sure we can still be friends.
Survival of the fittest
According to Charles Darwin, the great evolutionary biologist, the human race owes its existence to the phenomenon of survival of the fittest. And being the fittest doesn’t necessarily mean the biggest physical presence.
Once in high school, my lunchbox was targeted by swooping eagles, and I was reduced to a hapless onlooker. The eagle, though smaller in form, was fitter than me because it could take my lunch and fly away – it knew I couldn’t chase it.
As harsh as it sounds, look around you and you will see many examples of the rule of the jungle – the fitter survive while the rest gradually vanish.
The research area, now broadly referred to as Evolutionary Algorithms, simulates this behaviour on a computer to find the fittest solutions to a number of different classes of problems in science, engineering and economics.
The area in which this area is perhaps most widely used is known as “optimisation”.
Optimisation is everywhere
Your high school maths teacher probably told you the shortest way to go from point A to point B was along the straight line joining A and B. Your mum told you that you should always get the right amount of sleep.
And, if you have lived on your own for any length of time, you’ll be familiar with the ever-increasing cost of living versus the constant income – you always strive to minimise the expenditures, while ensuring you are not malnourished.
Whenever you undertake an activity that seeks to minimise or maximise a well-defined quantity such as distance or the vague notion of the right amount of sleep, you are optimising.
Look around you right now and you’ll see optimisation in play – your Coke can is shaped like that for a reason, a water droplet is spherical for a reason, you wash all your dishes together in the dishwasher for a reason.
Each of these strives to save on something: volume of material of the Coke can, and energy and water, respectively, in the above cases.
So we can safely say optimisation is the act of minimising or maximising a quantity. But that definition misses an important detail: there is always a notion of subject to, or satisfying some conditions.
You must get the right amount of sleep, but you also must do your studies and go for your music lessons. Such conditions, which you also have to adhere to, are known as “constraints”. Optimisation with constraints is then collectively termed “constrained optimisation”.
After constraints comes the notion of “multi-objective optimisation”. You’ll usually have more than one thing to worry about (you must keep your supervisor happy with your work and keep yourself happy and also ensure that you are working on your other projects). In many cases these multiple objectives can be in conflict.
Evolutionary algorithms and optimisation
Imagine your local walking group has arranged a weekend trip for its members and one of the activities is a hill climbing exercise. The problem assigned to your group leader is to identify who among you will reach the hill in the shortest time.
There are two approaches he or she could take to complete this task: ask only one of you to climb up the hill at a time and measure the time needed, or ask all of you to run all at once and see who reaches first.
That second method is known as the “population approach” of solving optimisation problems – and that’s how evolutionary algorithms work. The “population” of solutions are evolved over a number of iterations, with only the fittest solutions making it to the next.
This is analogous to the champion girl from your school making to the next round which was contested among champions from other schools in your state, then your country, and finally winning among all the countries.
Or, in our above scenario, finding who in the walking group reaches the hill top fastest, who would then be denoted as the fittest.
In engineering, optimisation needs are faced at almost every step, so it’s not surprising evolutionary algorithms have been successful in that domain.
Design optimisation of scramjets
At the Multi-disciplinary Design Optimisation Group at the University of New South Wales, my colleagues and I are involved in the design optimisation of scramjets, as part of the SCRAMSPACE program. In this, we’re working with colleagues from the University of Queensland.
Our evolutionary algorithms-based optimisation procedures have been successfully used to obtain the optimal configuration of various components of a scramjet.
Some of these have quite technical names, that in themselves would require quite a bit of explanation but, if you want, you can get a feel for the kind of work we do, and its applications for scramjets, by clicking here.
There are, at the risk of sounding over-zealous, no limits to the application of evolutionary algorithms.
Has this whetted your appetite? Have you learnt something new today?
If so, I’m glad. May the force be with you!