Documentation:Tutorials:Multi-population evolution with migration

From Beagle

This section is a tutorial on how to setup a basic multi-population evolution with migration.

Principle

This section is a quick remainder about the multi-population evolution with migration. For a more deeper introduction, see ???

Some times, when using an evolutionary algorithm, using a bigger population don't bring signifiant fitness improvements. Indeed, it could be even worse ! It's possible, for a given problem, there is an optimal range for the population size. In this case, the only way to improve the results is to increase the number of generations. Well, life is not that simple with evolutionary algorithms. Your genetic representation could suffer from diversity problems. The individuals in the population could be quit the same, trapping the algorithm in a local optimimum. So increasing the number of generations would be only a ressource waste. How to bring some diversity witout enlarging the population ?

A both simple and elegant solution to adress this issue is to use multi-population evolution with migration. The population is splited in severals clusters of individuals. The selection operator works only into a given cluster, it will select only individuals of the same cluster. At each generation, a reduced number of individuals of a cluster will travel to another cluster : this is called a migration. If you have seen that a population of 50 individuals is the best for your problem but you suffer from a lack of diversity, you could use several islands of 50 individuals.

Practice

Open Beagle provide a simple mechanism to setup a multi-population evolution with migration. First of all, your code. Well, that's already done, since you don't need to code anything. Indee, you just have to put an operator called "MigrationRandomRingOp" in your XML configuration file, into the main loop set. Here it is an example of a main loop set before modification

<MainLoopSet>
  <GenerationalOp>
    <MyEvaluationOp>
      <MyGroovyMutationOp>
        <SelectTournamentOp/>
      </MyGroovyMutationOp>
    </MyEvaluationOp>

    <MyEvaluationOp>
      <MyFunkyMutationOp>
        <SelectTournamentOp/>
      </MyFunkyMutationOp>
    </MyEvaluationOp>

    <MyEvaluationOp>
      <MyCrossoverOp>
        <SelectTournamentOp/>
      </MyCrossoverOp>
    </MyEvaluationOp>

    <SelectTournamentOp/>
  </GenerationalOp>

  <StatsCalcSimpleFitnessOp/>
  <TermMaxEvalsOp/>
  <MilestoneWriteOp/>
</MainLoopSet>

After modification :

<MainLoopSet>
  <GenerationalOp>
    <MyEvaluationOp>
      <MyGroovyMutationOp>
        <SelectTournamentOp/>
      </MyGroovyMutationOp>
    </MyEvaluationOp>

    <MyEvaluationOp>
      <MyFunkyMutationOp>
        <SelectTournamentOp/>
      </MyFunkyMutationOp>
    </MyEvaluationOp>

    <MyEvaluationOp>
      <MyCrossoverOp>
        <SelectTournamentOp/>
      </MyCrossoverOp>
    </MyEvaluationOp>

    <SelectTournamentOp/>
  </GenerationalOp>

  <!-- That's the operator to add -->
  <MigrationRandomRingOp/>

  <StatsCalcSimpleFitnessOp/>
  <TermMaxEvalsOp/>
  <MilestoneWriteOp/>
</MainLoopSet>

Now, you just have to setup two registers in your configuration file : ec.mig.size and ec.pop.size If you need 10 islands of 50 individuals, with two individuals per migration :

<Entry key="ec.pop.size">50/50/50/50/50/50/50/50/50/50</Entry>
<Entry key="ec.mig.size">2</Entry>

If you need 3 islands of 100 individuals and 1 island of 10 individuals

<Entry key="ec.pop.size">100/10/100/100</Entry>

Easy, hu ?

With Distributed Beagle

Not yet documented.

That's all !