Problem Solving with Darwin

Genetic Algorithms are a way of solving problems by mimicking the same processes mother nature uses. They use the same combination of selection, recombination and mutation to evolve a solution to a problem.
[AI Junkie Genetic Algorithm Tutorial]

Claudia Schiffer has still not shown herself. I'm beginning to believe that the Law of Attraction is nothing but a farce. They certainly had me fooled, but as George Bush once said: "There's an old saying in Tennessee — I know it's in Texas, probably in Tennessee — that says: Fool me once, shame on — shame on you. Fool me — you can't get fooled again." Something about the shoe being on the other foot in your mouth now.


George Bush. Living proof that mutation is random and we're definitely not intelligently designed.

If the Law of Attraction is not a good problem solving strategy - and that's a big if, I mean the Law of Attraction seems so plausible, especially when you critically evaluate its claims - then what is? This depends largely on the kind of problems you want to solve.

What kind of problems can you solve with the Law of Attraction?

I'm convinced that the Law of Attraction is not a solution, but a symptom of far greater problems bubbling below the surface. Regardless, most people who employ the Law of Attraction wrestle with questions posed by an existential crisis, unrequited love, dashed dreams, shattered hopes, a quarter-life crisis, a mid-life crisis or the ponies they didn't get for Christmas. While ponies posing questions, or a grown man wrestling with a pony might be amusing to some (especially those who produce or purchase snuff films), humorous charades are not part of the solution I had in mind.

These problems have some of the following characteristics in common:

• The search space is incredibly large, clearly misunderstood or overwhelmingly complex.


• It is difficult to employ expert knowledge to narrow the search space. Dr Phil is not going to help beyond asking you how you feel about it.


• A mathematical analysis is unavailable. Q: What should I study? A: 42. Doesn't make sense, does it?


• More traditional search methods for solutions to the problems have failed.

Fortunately, mother nature has already solved problems of this kind for millions of years. Darwin described some of her methods accurately and the field of computer science took his description and encoded it as a simple algorithm that helps to solve problems of this nature.

A Genetic Algorithm in Pseudocode

1. Generate an initial population.


2. Determine the fitness of each candidate in the population.


3. Wash, rinse and repeat these steps until a sufficient solution is found:
   
   1. Select the candidates with the highest rating for reproduction.
   
   
   2. Breed a new generation through crossover and mutation.
   
   
   3. Discard the worst ranking members of the population.
   
   

That might seem like Geek to you, and in fact it is. Rest assured, I will help cast light on the subject by giving you a walkthrough illustrating how you can use mother nature's own problem solving algorithm to solve your problems. Not all your problems. That rash is not going to go away with this. Sorry.

A Walkthrough to Illustrate Problem Solving with Darwin

Given a perplexing problem: What should you study?

1. Generate an initial population. In this instance, you can write down a list of fields you have ever considered in your life. If you can't think of twenty, get a brochure from a tertiary institute and randomly write down a list of courses from it. You can pick any number, but don't make the initial number too small.


2. Determine the fitness of each candidate in the population. The way you determine the fitness of each course is up to you. It is however important to attach a numerical value to each course. You can give each course a rating on a scale of one to ten, for instance.


3. Repeat these steps until you have only one item left on your list:
   
   1. Select the candidates with the highest rating for reproduction. This means you pick all the ones closest to ten for breeding.
   
   
   2. Breed a new generation through crossover and mutation. Crossover means you take properties of one course and combine it with properties of another course and see if there is such a course in the brochure. You'd rather take that course than the other two and give it a higher rating (plus one, unless it is already ten, then its rating just stays at ten).
      
      Mutation means you alter a course slightly. Suggest you had biochemistry as a course. Now you slightly alter it to become anatomy and physiology. Of course, this is subjective. If you'd still prefer to rather do biochemistry than anatomy and physiology, then rather keep biochemistry and discard the mutation. That's one advantage you have over mother nature: you can design your population intelligently.
      
      How do you choose when to mutate and when to crossover? This is also subjective. You could mutate every third course on your list, unless it is one you already feel strongly attached to, then just mutate the one immediately after it. You could crossover every item divisible by four and its immediate predecessor. You could decide to only mutate one round, and only crossover the next round. You can be as random as you like - it works for mother nature - but don't alter your population too much during each round. Mother nature doesn't condone bootstrapping.
   
   
   3. Discard the worst ranking members of the population. In our example, just delete one item from the list after each round. If you arrive at a scenario where all the lowest ranking items have a similar number, pick the course you like the least and delete it. If you can't decide, flip a coin.
   
   

Does This Really Work?

Surprisingly, yes it does. The list of applications for genetic algorithms on Wikipedia contains among others:

• Training artificial neural networks when pre-classified training examples are not readily obtainable


• Scheduling applications, including job-shop scheduling.


• Selection of optimal mathematical model to describe biological systems.


• Plant floor layout.


• Optimisation of data compression systems, for example using wavelets.


• Linguistic analysis.


• Electronic circuit design.


• Container loading optimization.


• Automated design of sophisticated trading systems in the financial sector.


• Automated design of industrial equipment.

Some Useful Links

• A field guide to Genetic Programming. A free e-book for the real geeks.


• Genetic Algorithms. A very broad introduction to the discipline.


• The Wikipedia page on Genetic Algorithms.