# 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`.

    N = 30

The main function includes the setting of some parameters, namely the number of increasing population restarts and the initial sigma value. Then, the instantiation of the `Toolbox` is done in the main function because it will change with the restarts. Next are initialized the `HallOfFame`, The `statistics` and the list of `Logbook` objects, one for each restart.

    creator.create("Individual", list, fitness=creator.FitnessMin)

    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", numpy.mean)
        stats.register("std", numpy.std)
        stats.register("min", numpy.min)
        stats.register("max", numpy.max)

        logbooks = list()

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)

            logbooks.append(tools.Logbook())
            logbooks[-1].header = "gen", "evals", "restart", "regime", "std", "min", "avg", "max"

            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

                halloffame.update(population)
                record = stats.compile(population)
                logbooks[-1].record(gen=t, evals=lambda_, restart=i, regime=regime, **record)
                if verbose:
                    print(logbooks[-1].stream)

                # 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

                mins.append(record["min"])
                if (len(mins) == mins.maxlen) and max(mins) - min(mins) < 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

                # Need to transfor strategy.diagD[-1]**2 from pyp/numpy.float64 to python
                # float to avoid OverflowError
                if strategy.sigma / sigma > float(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 occurred
                    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)):
            stop_causes = [k for k, v in conditions.items() if v]
            print("Stopped because of condition%s %s" % ((":" if len(stop_causes) == 1 else "s:"), ",".join(stop_causes)))
            i += 1

Some variables have been omitted for clarity, refer to the complete example for more details examples/es/cma_bipop.py.

[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