ES - diversity over generations

[Sam N]

In Inspyred's implementation of Evolution Strategy (ES object), I find that many of the population members (100 population size) over many generations tend to resemble each other, perhaps too much. The average population fitness tends to rise towards the best, with the worst fitness following too. Eventually, the worst fitness catches up close to the average, but then worse/average fitness stay flat for many generations. Is there a way to increase diversity to allow similar levels of exploration even at higher generations? Increasing mutation rate might help but does the mutation rate decay with increasing generations in Inspyred's ES? Thanks for any suggestions. Sam

[Mark Coletti]

It is normal behavior for an evolutionary algorithm to converge to a homogenous population.  If you're worried about finding multiple minima or maxima, the typical solution is just to do multiple restarts and reruns, which is advisable anyway since EAs are inherently stochastic.  I recommend doing at least five separate runs, though ideally about 30 would be statistically significant.  That may admittedly not be feasible if the evaluation times are significantly lengthy.

If you really want to include diversity management in your EA, there are a few approaches to try:

• Go with Bill Spears' tag bits whereby parents can only undergo crossover if they have the same tags [1]; since an ES uses real-values, you may be able to emulate this with a real-value "tag" field and only allow crossover with parents that have tags within a certain distance of one another.
• Use some other form of sub-populations, such as island models
• Turn this into a multi-objective problem. Add a new, second objective that is some form of diversity measure, and maximize that.  Coming up with a sensible diversity measure may be problematic, but the literature has some different approaches to try.  E.g., [2]

Cheers,

Mark Coletti

[1] Spears, William M. "Simple subpopulation schemes." Proceedings of the Evolutionary Programming Conference. Vol. 3. River Edge, NJ: World Scientific, 1994.

[2] Toffolo, A., & Benini, E. (2003). Genetic diversity as an objective in multi-objective evolutionary algorithms. Evolutionary computation, 11(2), 151-167.

On Fri, Aug 27, 2021 at 2:44 PM Sam N <sam...@gmail.com> wrote:

In Inspyred's implementation of Evolution Strategy (ES object), I find that many of the population members (100 population size) over many generations tend to resemble each other, perhaps too much. The average population fitness tends to rise towards the best, with the worst fitness following too. Eventually, the worst fitness catches up close to the average, but then worse/average fitness stay flat for many generations. Is there a way to increase diversity to allow similar levels of exploration even at higher generations? Increasing mutation rate might help but does the mutation rate decay with increasing generations in Inspyred's ES? Thanks for any suggestions. Sam

--
You received this message because you are subscribed to the Google Groups "Inspyred" group.
To unsubscribe from this group and stop receiving emails from it, send an email to inspyred+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/inspyred/f974822e-29ce-46df-b1ac-9f8e60280cf5n%40googlegroups.com.

--

mcol...@gmail.com

[Aaron Garrett]

I apologize for not seeing this sooner. Somehow it was funneled to spam.

Just to add to Mark's highly informative answer, there is a crowding replacement operator in the library that you might look at: https://aarongarrett.github.io/inspyred/reference.html#inspyred.ec.replacers.crowding_replacement

--
Aaron Garrett

To view this discussion on the web visit https://groups.google.com/d/msgid/inspyred/CAHpqhBM_SyMUWT%3DKAntDgrzp6BUz4v4izSz51joCOD0rN2u6OQ%40mail.gmail.com.