You are here

Genetic Algorithm- mating method

I noticed in your genetic algorithm example here on the site, that just after mating the best 1/4 with any of the best 1/2, you overwrite that same best 1/2 with the children produced.

// The new generation is in the matingPopulation area
// move them to the correct area for sort.
for ( int i=0;i<matingPopulationSize;i++ ) {
chromosomes[i] = chromosomes[i+matingPopulationSize];
chromosomes[i].calculateCost(cities);
}

your explaination is:

The newly created children are moved to the bottom 50% of the population. This effectively kills the lower 50% of organisms that are not well suited.

for ( int i=0;i<matingPopulationSize;i++ ) {
chromosomes[i] = chromosomes[i+matingPopulationSize];
chromosomes[i].calculateCost(cities);
}

but what the code does (at least as I understand it) is produce new children in the bottom 50%, then overwrite the parents, effectively cloning the children.

I implemented your code, minus the overwriting section, and the parents are preserved, then sorted with the new kids. I noticed something interesting though, when the parents are preserved, the algorithm is actually much less effective and seems to get caught at local maxima.

I was wondering if you'd share your thoughts on this? Was overwriting the parents intended, or just a fortunate slip that somehow increases effectiveness? Also, why is this more effective? That is the part that has me most baffled.

Thanks,

Neural Network Forums: 
jeffheaton's picture

That example is from the first edition of the book:

http://www.heatonresearch.com/articles/8/page4.html

I did change this method in the 2nd edition. And Encog uses something very similar, though more extensible, to the 2nd edition.

Here is how it works in the first edition.

Say you have 1000 chromosomes. The first 250 are mated with the first 500. This produces 500 offspring. They are stored in the lower 500 locations, while the mating takes place. Then I copy the bottom 500 to the first, and sort only the first 500. At this point we have two copies of the children, one in the lower 500 and the new copy in the first 500. So each generation dies, and only the children remain. This is not the best way to do it, but it does work.

A better method is to let the children replace the lower 500 and then NOT replace the top. Then parents can remain if they are better suited than the children. This is how the 2nd edition works. If you want to modify the 1st edition code to do this, just do the following:

// Mate the chromosomes in the favoured population
// with all in the mating population
for ( int i=0;i<favoredPopulationSize;i++ ) {
Chromosome cmother = chromosomes[i];
// Select partner from the mating population
int father = (int) ( 0.999999*Math.random()*(double)matingPopulationSize);
Chromosome cfather = chromosomes[father];

mutated += cmother.mate(cfather,chromosomes[ioffset],chromosomes[ioffset+1]);
chromosomes[ioffset].calculateCost(cities);
chromosomes[ioffset+1].calculateCost(cities);
ioffset += 2;
}

// The new generation is in the matingPopulation area
// move them to the correct area for sort.
/* for ( int i=0;i<matingPopulationSize;i++ ) {
chromosomes[i] = chromosomes[i+matingPopulationSize];
chromosomes[i].calculateCost(cities);
}
*/

// Now sort the new mating population
Chromosome.sortChromosomes(chromosomes,chromosomes.length);

The key changes are, make sure the first loop calculates the cost for the children. Comment out the copy. Then finally, make sure the entire population is sorted.

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer