SPEA2Breeder loadElites is loading wrong number of elites

[camilledolle]

In this code:

        // replace old population with archive so new individuals are bred from the archive members only
        oldPopulation = state.population;
        state.population = state.population.emptyClone();

        for(int i = 0; i < newpop.subpops.size(); i++)
            {
            Subpopulation subpop = state.population.subpops.get(i);
            Subpopulation newsubpop = newpop.subpops.get(i);
            int ne = numElites(state, i);
            for(int j = 0; j < ne; j++)
                subpop.individuals.add(j, (Individual)(newsubpop.individuals.get(j).clone()));
            }
        }

The line int ne = numElites(state, i) should be replaced by something similar to what is in NSGA2Breeder: int ne = numElites[i], because calling the function re-computes the number of elites based on state.population but this one just got emptied (see first lines of code snippet). That causes ne to always be 1

[SigmaX]

Thanks, @camilledolle —I'll look into this ASAP.

[SigmaX]

Hi @camilledolle,

So, if I run SPEA2 with no elites parameter specified, I'm able to produce a case where ne always equals 0 (since SimpleBreeder's elites mechanism, which SPEA2 inherits, defaults to zero).

None of our unit tests or example apps reach a state where ne = 1, and while I see the line in SimpleBreeder.numElites() that could cause that case, I'm having troubles coming up with a configuration that exercises it.

If you did in fact observe ne = 1, could you share the parameters you used?

---

Either way: the flaw here seems to be that, unlike NSGA-II (whose archive size is always identical to the population size) SPEA2 requires the breeder.elites parameter to be set (since it has separate archive and population sizes). No warning or error is thrown when the user fails to specify this parameter.

Is this what is happening to you? Or did you encounter this issue in some other way?

[camilledolle]

Hi @SigmaX,

I am specifying breed.elite-fraction.0 = 0.1 in the config file. Actually... by reviewing the code of SimpleBreeder.numElites(), that bug might be specific to elite-fraction parameter (instead of elite). This line is causing ne = 1:

else if (eliteFrac[subpopulation] != NOT_SET)
{
  return (int) Math.max(Math.floor(state.population.subpops.get(subpopulation).individuals.size() * eliteFrac[subpopulation]), 1.0);  // AT LEAST 1 ELITE
}

Here it is re-computing based on state.population (which is empty in SPEA2Breeder.loadElites(), but if using elite parameter, the code is simply fetching the number of elites:

if (elite[subpopulation] != NOT_SET)
{
  return elite[subpopulation];
}

[SigmaX]

Fixed. elite-fraction should work with SPEA2 now if you use the latest version from GitHub.

[camilledolle]

Hi, there's another issue with this SPEA2Breeder. In SimpleBreeder.breedPopulation() line 259:

int numElites = numElites(state, x);
int length = newSubpopSize[x] - numElites;

// we will have some extra individuals.  We distribute these among the early subpopulations
int individualsPerThread = length / numThreads;  // integer division
int slop = length - numThreads * individualsPerThread;
int currentFrom = 0;

for(int y=0;y<numThreads;y++)
{
    if (slop > 0)
    {
      numinds[y][x] = individualsPerThread + 1;
      slop--;
    }
    else
      numinds[y][x] = individualsPerThread;

    from[y][x] = currentFrom;
    currentFrom += numinds[y][x];

    if (numinds[y][x] == 0)
    {
      state.output.warnOnce("More threads exist than can be used to breed some subpopulations (first example: subpopulation " + x + ")");
    }
  }
}

The first line will, again in the case where elite-fraction parameter is used, re-compute the number of elites based on state.population (which at this point only contains the elites). And therefore the numinds will contain a bigger number than needed (so the number of individuals to breed will be greater than needed and final subpopulation will contain more individuals than needed).

In NSGA2Breeder, the numElites() method is overridden, which I think would be the correct fix for SPEA2Breeder.

[SigmaX]

Reasoning through this for my own benefit:

The basic problem is that unlike most algorithms (which breed children directly from the parent population), SPEA2 and NSGA-II first extract an elitist archive, and then breed children from that archive.

We implemented this by hacking SimpleBreeder's elitism mechanism: we override the loadElites() methods to both 1) place the elites in the new population (normal), and 2) replace the parent population with the elites (unusual behavior—not what SimpleBreeder was written to expect).

When the elite-fraction parameter is used with SPEA2, this causes trouble because SimpleBreeder.numElites() tries to use the size of the parent population to compute the archive size for the next generation. But the parent population isn't the parent population anymore—our loadElites() weirdness modified it in place to contain the new archive.

NSGA-II doesn't support an elite-fraction, because its archive is hard-coded to be equal to the population size. But it does override numElites() to ensure that the size of the previous population is used for the new archive size (aside: this strikes me as excessively complicated for NSGA-II—couldn't we simplify this, since the previous population size is always double the archive size?—but that's another matter).

Taking a cue from NSGA-II, it seems we can indeed fix SPEA2's elite-fraction by overriding numElites() to remember the size of the previous population after it has been nuked.

[SigmaX]

It was a bit trickier than I thought, since SPEA2 calls numElites() inside its loadArchive() function, but this general approach worked.

SPEA2's archive size no longer grows continuously when the elite-fraction parameter is used. Thanks for reporting, @camilledolle !