“Were Dinosaurs just a local Max ?” – A Genetic Algorithms intro

There are many theories about the disappearing of dinosaurs: meteors, diseases, global warning, global cooling, global mid-temperature, lack of TV and Radio or even Reptile Phobia.
Another theory is that maybe they weren’t just the right stuff. Great ADN, but not top material. And maybe Artificial Intelligence could explain it:
There a nice type of AI that goes by the name of Genetic Algorithms, which grabs the essences of live and evolution and imitates nature prevail of the fittest.

by ksbuehler

Genetic Algorithms are a stochastic algorithm (something that when ran twice on the same premises may give different results) that evolves a gene population to a maximum fitness. In mathmatical terms (if this is by any change a better way to try to explain it) it’s a nice search technique that changes the arguments of a function so they give the highest result, being the function result the fitness of those arguments and being those arguments the representation of an individual in our universe.

So, if we, ok, mr. Charles Darwin got it right and the Genetic Algorithms search technique translates it correctly, it is possible that Dinosaurs where just a local maximum of the real world fitness function result spectrum and the gene population just got away from it after spent much time around it trying to search the global maximum.

The next important questions are:
What if we are a local maximum too ?.. will we try the manipulate live fitness function?.. aren’t we already?.. probably, but like a local maximum, we’ll just mess it up and be gone like the big lizards.

Another possible scenario is: what if there is really a global maximum and nature evolution gets there, every creature on the planet would be almost the same, than, wouldn’t the dye of boredom.. doom by bore.. would that just be a paradox, if the premium specie would not be fit to live, or does this mean that they will just be very bore and patient creatures.. hmm.. maybe some people I know are already more evolved

This is mostly non-sense, but the only thing that matters .. is.. can computer science and algorithms start to explain life and human / species behavior, history and future ?

Only time an evolution will tell…

But, here is the real post.. an introduction of..

Genetic Algorithms

by colm.mcmullan

Genetic Algorithms are a fine search algorithm that start with an initial populations, chooses just some of the fittest individuals, reproduce them creating fitter population and goes on and on till you stop it and get a quite fit population. You can then that the best individual of that generation (iteration) and use him.

In real live

Imagine that you want to know what is the most efficient way of driving your car to work so you spend less gas (it is really expensive !! nowadays), you can have lots and lots of ways of driving, accelerate more, accelerate less, go slo, go fast, use different types of tires, go one way, go the other, let the engine working and getting hotter for a while, start driving right away, put the weight on the back, put it on the front, and on and on…
So, our genes ADN will be an array of possible values for each of this type of variable. Each individual would be a trial, a going to the office with a certain set of values and conditions (a ADN sequence) and our population would be a set of trials or a series of days going to work in a different way.
Ok, so what we would do is to create a first random population, this is, take note on a sheet of different possible ways to go to work by car (going slowly or not, etc) and see how much gas we spend with which of those configurations.

The gas spending is really our fitness function, being the less you spend the fittest the individual and it’s genes are.
Then, after the set is all done, you select only some of them, not just the top, but the ones that took less gas, would be choosen with most probability. This is so that you don’t narrow down your possibilities to soon and get stuck with dinosaurs but instead keep your options still open.

With the selected individuals (set of car and driving configurations), mostly the top cream of the generation, make them reproduce and mutate and create a new generation. By reproduce I mean, take two configurations and cut parts of each other and create a new one, just like mixing a song. By mutate, I mean, some genes – variables or aspects of the configuration – just change them to something else not taking in account any off the parents.

Only selecting some of best elements of the population and recombine them, you pretty much end up with a fitter population.. hopefully.
So, instead of testing all of you driving configurations, that could be exponential regarding the number of possible variables, waiting perhaps 5 or 6 years in trials. You could use genetic algorithms and do more guided trials; and after some generations, you probably will have a great contender to most efficient way to drive to work. The planet would thank!

In most cases, these algorithms are used in complex problems where you don’t have a linear or simple fitness function with a big list of genes (variables). As you can see, it’s very handy to safe some time and still get sub-optimal solutions

The algorithm

So, let’s look at the algorithm and its several parts.

ADN

First step is to code your genes ADN. Each gene is a variable of your problem; in our example, the number of minutes you waited with the engine on before start driving is one of those. An ADN can be made of many types of variables, for instance, some could be real numbers (like the number of minutes) while others can be binary (like stating if the baggage was on the front or on the back), or any other type (enumeration, float, etc..). To simplify, on most problems, the Genes have the same type, but it is perfectly normal to use different gene types on one ADN.

Initial Population

After you decided how an individual is made of, you have to create an initial population. The size of the population, the bigger it is, the longer it will take to get new generations (unless you have a great parallel computing setup), but a small population could take ages to get any decent results or any diversity. To decide the population size, just use your instinct, it’s usually a great tool!

Remember that the initial population has to be random. Every individual has to be created from random genes (respecting the genes types and restrictions, of course). This is so that you get a good diversity and don’t pre-orientate the solution, which could doom you to settle, once again, with dinosaurs.

Nevertheless, one advice is that you create your initial with some pre-constraints, creating only “productive” elements. But do this only for a number of elements you can create as being “productive” and do it completely random for the others. Productive means that they may use values that might not be the soluction, but at lease could be a valid solution. For instance, if you know that the car can’t have an speed average if it doesn’t heat up a bit first, select firstly random genes that don’t mix high velocity and cool engine. This can give you a head start and won’t compromise your diversity.

Fitness Function

The fitness function is basically a function that takes a gene as argument and gives the fitness of that gene ADN. It’s something you can run and return an result regarding the ranking of your variables. In our car case, the function is the travel to work with the car configuration and the result is the cost of the gas spent.

Be sure to have a quick function, as it will be ran many many times. hmm.. also be sure that this function really represents the fitness in your problem, as the algorithm tries to optimize this function. If the function is poor you will have poor results. Imagine if in our example, the function was just the time you took to office.. that would probably not work, because you would end up with a great way to get fast to work, but at a possible greater cost.

Natural Selection

Run the fitness function to the entire population. Now, choose about half of the best ones. Not the best half though. Why? Because that would compromise the diversity (you never thought that diversity was that good?.. it is! even on the mathmatical level.. ) and you would end up with the same faces all the time and does could be sad faces

So, how to choose ? You have to have some kind of stochastic process, so that you guaranty that the decision is flexible and changes always. Two of the most known processes are the roulette wheel selection and the tournament selection. I prefer to use the first one, but they are very similar in the way that fitter elements have more probably of reproduction but a good fitness isn’t a secure ticket.
On roulette wheel, each element has the same number of bullets as the fitness, this is, if the fitness function gave a result of 6, we will have 6 bullets in the gun with his name. The number of bullets in the “gun” is the total of of the several fitness results. At the end, you start rolling the revolver chamber and shooting some bullets. After each shot you take out all the bullets of that element and select him for reproduction.. you do this until you have enough guys to create a new generation.

Next Generation

As I told before, you can create new elements using to major operators: crossover or mutation.
With crossover, you get two genes together, select parts of each and create a new one. On mutation, you just get a ADN gene or more and change it to a another value.

You can also create you own Operators that can be based on one or several elements and genes. One possible choice is to create an operator that combines two elements but only compatible gene values (like in our speed vs cooling example).

Finish Line

There isn’t any finish line unless you didn’t compromise the diversity and the next generation is exactly the same as the one before.
One could have several good ways of stopping the search. One is to see if the fittest element is fitter than a pre-written value. Another is to check if the differences between this generation and the previous are smaller than a percentage limit. Or.. you could just set a number of iterations that you think is fair and go with it and refine it as you go by.

Back to dinosaurs

Well, we can only hope that somewhere in a “next generation” of life, diversity will take over and go back to does guys. They sure look cool.

By the way, here is a ruby implementation of Genetic Algorithms. If you have fun with it , please send feedback!