Digital Evolutionary Convergence?

[Doc Toe]

RE : Evolving the following circuit with Built-In Self-Test: RD53 (96 gates).

For this run, are the islands converging (and getting stuck) on a particular unsatisfactory(??) solution?

Doc Toe

[Stephen_B]

Looks like the population is inbred at the moment. In GA this is generally considered a bad thing since other good solutions are lost. You'd like to see local maxima preserved.

[michaelgarvie]

This was quite a key point actually. The optimised algorithm running since 2 months back has no noise in the evaluation for these combinational benchmarks. This means the evaluation always returns the same (accurate) fitness value. WHen this is combined with elitism (always keeping the fittest individuals into the next generation) then the top fitness will never go down and you may be more likely to get stuck at local optima.

To avoid this I've removed elitism so now there's a (small) chance of loosing the fittest individual which means the GA can - if you like - rollback and try other approaches if one of them gets stuck. Also I've put migration probability right down to 1/100 so genetic diversity is kept high. Lets see how this run goes!

[Stephen_B]

I'm sure that this has been done before, but I was wondering if it might be a good idea to keep a master list of elites. To be a member, you'd have to have good fitness and be genetically unrelated.

To test for unrelatedness, assuming a binary representation for individuals, you could bitwise-OR their genome and count the number of ones. If the number of ones is above some threshhold, count them as unrelated. If they are related, keep the best one, otherwise add them to the list.

You could choose to reintroduce individuals on this list that have gone extinct periodically.

Stephen

[michaelgarvie]

I guess what you're aiming at with your bitwise-OR metric is Hamming distance. I have heard of people doing this before and have done it myself manually at times. With some luck the new setup will sort itself out on its own.