Combining Survival of the Fittest with Genetic Algorithm?

Question

I was implementing my beloved " Genetic Algorithm ". It was pretty much obvious that the population increased by a large number after each iteration of selection , crossover and mutation . But organisms do die as well , right ? However , there is no such provision in the algorithm that we all are aware of.

So my question is , why don't we simply eliminate some of the organisms having lower fitness from the population itself (and merge the survival of the fittest theory as well ) ? Why to carry their burden and waste the resources ( memory in our case ) ?

Also , all my thinking is based on the 3 page explanation of the algorithm given in Peter Norvig's AI book , so maybe my question has already been worked on with. I need to know about these happenings .

Plus it's my first question on this platform , so community , please don't be harsh at me !

Answer 1

Genetic algorithms, by design, eliminate the weakest solutions in the set by simply not including their genes in future generations.

How Genetic Algorithms Select Who Lives and Who Dies

Abstract: imagine that the algorithm is choosing which solutions are to be chosen, combined, and mutated for the next generation. Each solution is put on a dart board, but the better solutions take up more space on the dart board, so when the algorithm throws a dart, it is more likely to hit a more fit solution. In fact, it may even hit the same solution more than once.

Once it has its' solution set from the dart board (generally same population size as your original set, but probably contains duplicates from multiple darts hitting the same solution), you take this set, and "mutate" them by randomly switching parts of the solution. You then can "mate" solutions, in a very sexy process where you take parts of random solutions in the new generations, and combine them to form a final generation set.

This process is then repeated.

What happens to the solutions whom no dart hit? It depends entirely on your language and data structures, but they are probably objects that just get garbage collected.

Actual Code

Here is some code that I wrote in processing (Java) that emulates the dart-throwing process

I'm just calling organisms ArrayLists of floats, but they can be anything

 ArrayList<Float> normalize(ArrayList<Float> inputArray){
   float sum = 0; 
   ArrayList<Float> outputArray = new ArrayList<Float>();
   for(int i = 0; i < inputArray.size(); i++){
    sum += inputArray.get(i); 
   }
   for(int i = 0; i < inputArray.size(); i++){
    outputArray.add(inputArray.get(i)/sum); 
   }
   return outputArray;
  }

ArrayList<Float> pick(ArrayList<ArrayList> parents, ArrayList<Float> fitness){
   float searchVal = random(0, 1);
   float fitTotal = 0;
   int fitIndex = 0;
   while(searchVal > fitTotal && fitIndex < fitness.size()){
    fitTotal += fitness.get(fitIndex); 
    fitIndex++;
   }
   if(fitIndex != 0){
    return parents.get(fitIndex-1); 
   }
   else{
    return parents.get(0); 
   }
  }

How it works

This code contains two methods; a normalize method and a pick method.

The normalize method takes the fitness levels of each solution, and "normalizes" this into an array where each fitness level is divided by the total. This will result in each fitness level being a percentage of the total. They will all add up to one.

The pick method will then take in this normalized array, along with the array of parent solutions (MUST BE IN THE SAME ORDER AS FITNESS LEVELS), and pick a random number 0-1, and this number will match to a specific fitness level and the algorithm will "pick" that parent to reproduce.

You will note that solutions with a larger fitness level will have a higher chance of being "picked"

This "pick" method should be repeated for every organism you want in the next generation.

EDIT

OP mentioned that they understood the dart board analogy, and was wondering if would be at all useful to wipe the bad ones off the dart board entirely. The chances of picking bad offspring are low to begin with, but manual pruning like this would work as well.

I can see this being useful in cases where there are really bad traits that you don't want a solution to have, and you want no chance of them being put into the next set.