Search code examples
algorithmevolutionary-algorithm

How is reproduce processing in (μ,λ) evolution strategy algorithm?

In the (μ,λ) adaptive type evolution strategy algorithm, in my realization, the process is:

  1. I have μ individuals, and generate λ offspring from these population
  2. In λ individuals, do mutation for the mutation strength, then mutate the candidate solutions. After mutation, evaluate fitness for all λ individuals.
  3. Selection: rank all λ individuals by fitness, select the best μ individuals as next generation's population. Go back to 1. if criteria haven't reached.

In 1. , I generate offspring from μ individuals. When I see the paper

http://www.cs.bham.ac.uk/~pxt/NIL/es.pdf

http://ieeexplore.ieee.org/document/5596676/

if seems that I could get offspring by cloning from μ individuals and create offspring.

But how could I do this in detail? Should I just clone the μ individuals with a constant, and get offspring by λ = proportion * μ ?

But in this way, in the mutation phase, won't I get several same result after mutation? And during the selection phase, I thought I may get same individuals for the same fitness value.

How could I create the λ offspring exactly?

Solution

  • Should I just clone the μ individuals with a constant, and get offspring by λ = proportion * μ ?

    Yes, start with proportion == 2. And you will get several time similar individual. Make sure to only duplicate the n bests (n < μ / (3 * proportion) ) individuals. Because you will have to forget/destroy the n worsts individuals.

    in the mutation phase, won't I get several same result after mutation?

    Maybe your error is in the cloning step. You must do a complet copy not just a clone; a real copy of every bit, not just a copy of a pointer. Becarefull, many clone function do not copy inner-referenced objects. Here the word clone, is just a comparison to biologie.

    if your individuals are array of integer, then you should have an array of array of integer. Then cloning the individual of index i, into another individual of index j, must be done in a way similar as :

    for(k = 0; k < individuals[i].length; k++)
    individuals[j][k] = individuals[i][k];

    The second step of the algorithm will force individuals to evolve, in a random way. So if a combination is encode by more than one individual, then it will have greater chances to evolve. So individuals must not share memory, to make sure diversity will prevail.

    The ieee document can't be open, it requiere to pay for it.

    How could I create the λ offspring exactly?

    sort individuals by fitness from best to worst.
for( i = 0 ; i < n ; i++) // **n** best
     copy data of individuals[i] into individuals[individuals.length-i] // replace a worst one, by the copy of a good one.

    This step should be done in constant memory. No freeing(delete), no mallocing(new).