Controlling the Stopping Criteria: BI-POP CMA-ES

A variant of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) [Hansen2001] implies to control very specifically the termination criteria in the generational loop. This can be achieved by writing the algorithm partially invoking manually the generate() and update() inside a loop with specific stop criteria. In fact, the BI-POP CMA-ES [Hansen2009] has 9 different stop criteria, which are used to control the independent restarts, with different population sizes, of a standard CMA-ES.

As usual, the first thing to do is to create the types and as usual, we’ll need a minimizing fitness and an individual that is a list.

creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)

The main function includes the setting of some parameters, namely the number of increasing population restarts and the initial sigma value. Then, the instanciation of the Toolbox is done in the main function because it will change with the restarts. Next are initialized the HallOfFame and the Statistics objects.

def main(verbose=True):
    NRESTARTS = 10  # Initialization + 9 I-POP restarts
    SIGMA0 = 2.0    # 1/5th of the domain [-5 5]

    toolbox = base.Toolbox()
    toolbox.register("evaluate", benchmarks.rastrigin)

    halloffame = tools.HallOfFame(1)

    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", tools.mean)
    stats.register("std", tools.std)
    stats.register("min", min)
    stats.register("max", max)

Then the first loop controlling the restart is set up. It encapsulates the generational loop with its many stop criteria. The content of this last loop is simply the generate-update loop as presented in the deap.algorithms.eaGenerateUpdate() function.

    while i < (NRESTARTS + nsmallpopruns):

        strategy = cma.Strategy(centroid=numpy.random.uniform(-4, 4, N), sigma=sigma, lambda_=lambda_)
        toolbox.register("generate", strategy.generate, creator.Individual)
        toolbox.register("update", strategy.update)

        conditions = {"MaxIter" : False, "TolHistFun" : False, "EqualFunVals" : False,
                      "TolX" : False, "TolUpSigma" : False, "Stagnation" : False,
                      "ConditionCov" : False, "NoEffectAxis" : False, "NoEffectCoor" : False}

        while not any(conditions.values()):
            # Generate a new population
            population = toolbox.generate()
            
            # Evaluate the individuals
            fitnesses = toolbox.map(toolbox.evaluate, population)
            for ind, fit in zip(population, fitnesses):
                ind.fitness.values = fit

            # Update the strategy with the evaluated individuals
            toolbox.update(population)

            if t >= MAXITER:
                # The maximum number of iteration per CMA-ES ran
                conditions["MaxIter"] = True

            if (len(stats.min) > i and not len(stats.min[i]) < TOLHISTFUN_ITER) and \
               max(stats.min[i][-TOLHISTFUN_ITER:])[0] - min(stats.min[i][-TOLHISTFUN_ITER:])[0] < TOLHISTFUN:
                # The range of the best values is smaller than the threshold
                conditions["TolHistFun"] = True

            if t > N and sum(equalfunvalues[-N:]) / float(N) > EQUALFUNVALS:
                # In 1/3rd of the last N iterations the best and k'th best solutions are equal
                conditions["EqualFunVals"] = True

            if all(strategy.pc < TOLX) and all(numpy.sqrt(numpy.diag(strategy.C)) < TOLX):
                # All components of pc and sqrt(diag(C)) are smaller than the threshold
                conditions["TolX"] = True
            
            if strategy.sigma / sigma > strategy.diagD[-1]**2 * TOLUPSIGMA:
                # The sigma ratio is bigger than a threshold
                conditions["TolUpSigma"] = True
            
            if len(bestvalues) > STAGNATION_ITER and len(medianvalues) > STAGNATION_ITER and \
               numpy.median(bestvalues[-20:]) >= numpy.median(bestvalues[-STAGNATION_ITER:-STAGNATION_ITER + 20]) and \
               numpy.median(medianvalues[-20:]) >= numpy.median(medianvalues[-STAGNATION_ITER:-STAGNATION_ITER + 20]):
                # Stagnation occured
                conditions["Stagnation"] = True

            if strategy.cond > 10**14:
                # The condition number is bigger than a threshold
                conditions["ConditionCov"] = True

            if all(strategy.centroid == strategy.centroid + 0.1 * strategy.sigma * strategy.diagD[-NOEFFECTAXIS_INDEX] * strategy.B[-NOEFFECTAXIS_INDEX]):
                # The coordinate axis std is too low
                conditions["NoEffectAxis"] = True

            if any(strategy.centroid == strategy.centroid + 0.2 * strategy.sigma * numpy.diag(strategy.C)):
                # The main axis std has no effect
                conditions["NoEffectCoor"] = True

        i += 1

Some variables have been omited for clarity, refer to the complete example for more details [source code].

[Hansen2001]

Hansen and Ostermeier, 2001. Completely Derandomized Self-Adaptation in Evolution Strategies. Evolutionary Computation

[Hansen2009]

Hansen, 2009. Benchmarking a BI-Population CMA-ES on the BBOB-2009 Function Testbed. GECCO‘09