The way to obtain order of magnitude speed-ups in GAs (or even better) is to understand why GAs have an asymptotic convergence rate. It was generally thought that the selection operator weakens as the population nears convergence to a single - most fit - chromosome and that this slows down the search. Others suggested that poor performing bits were hitchhiking on the backs of very strong bits and that the GA was poor at breaking such correlations once they were significantly strong. Back in 1995 I showed that it was in fact the crossover operator that was at fault.

As the population converges the probability that two parents will produce cloned offspring (i.e., identicical to the parents) increases. It is obvious that when the population has fully converged to a single string that the probability of cloning is 1. What surprises most people is that on a random population before any iterations of the GA the probability of cloning can be as high as 50%! It''s a function of the length of the string.

Clearly then, if we can avoid clones then the search will progress further. The naive approach might be to simply reject clones as they are produced and perform crossover again on the parents. Unfortunately, this doesn''t actually prevent asymptotic convergence - it merely alters its rate - as a lot of time will be spent finding and rejecting clones. You might get a factor of 2 increase in performance of the algorithm, but thats about it.

The solution then is to prevent the population from converging! But, you say, this is going against the whole point of the algorithm! And you''d be right! I don''t have the space here for a full explanation but basically you prevent the population from converging by removing individual bits (from every population member) that have already converged (over a reasonable threshold: like 95%). Chromosomes will converge from most significant bit (MSB: the bit that contributes the most to the fitness evaluation) down to the least significant bit (LSB: which contributes the least). To maintain the effectiveness of the algorithm, you stick a new bit (randomly selected) into a new position in the string such that the new position is now the least significant bit. Ie, you add as little perturbation to the string as possible while changing the information it encodes.

The bits that you pull out you ''lock'' into your solution string.

The beauty of this approach - which I called Bit Stripping - is that you can run it for as long as you like to obtain whatever level of accuracy you desire for your optimisation problem.

I did lots of tests against standardised sets of test problems and found that my GAs outperformed standard GAs over the whole suit of problems. Performance benefits varied from several orders of magnitude on uni-model problems to same order of magnitude on multimodal stochastic functions. I certainly proved that you were no worse off for employing my method and that it was fairly easy to do so.

Additionally, I re-derived Holland''s Schema Theorem to include the effects of cloning. The resulting formula was as elegant as Holland''s original and more accurately explained the asymptotic convergence rate of Holland''s 3 operator GA.

If you have any specific questions, just holler.

Timkin

quote: Original post by Timkin


I did lots of tests against standardised sets of test problems and found that my GAs outperformed standard GAs over the whole suit of problems. Performance benefits varied from several orders of magnitude on uni-model problems to same order of magnitude on multimodal stochastic functions. I certainly proved that you were no worse off for employing my method and that it was fairly easy to do so.

Additionally, I re-derived Holland''s Schema Theorem to include the effects of cloning. The resulting formula was as elegant as Holland''s original and more accurately explained the asymptotic convergence rate of Holland''s 3 operator GA.

If you have any specific questions, just holler.

Timkin

Do you have a pointer to your published paper on this?

Thanks,

Eric

quote: Original post by Geta

Do you have a pointer to your published paper on this?

On the (mis-guided) advice of my then supervisor I did not publish this work externally (only internally). This was based on the fact that two other researchers (Shraudolph & Belew) had devised a similar, but computationally more complex method that achieved similar results. In hindsight, their method was not based on the same understanding as mine and I probably could have published... maybe I still should!

Anyway, I only have hardcopies of the thesis. If you''re desperate for a copy, email me a snail-mail address and I will dispatch you a copy.

Cheers,

Tim