eaMuPlusLambda/ES is worse than eaSimple/SGA

[Freakwill]

I have tried many examples, showing that eaMuPlusLambda/ES is worse than eaSimple/SGA in performance. That is disappointed.

import array
import numpy as np
from deap import base, creator, tools, algorithms

creator.create("FitnessMin", base.Fitness, weights=(-1,))

creator.create("Individual", array.array, typecode="d", fitness=creator.FitnessMin)
creator.create("Strategy", array.array, typecode="d")
toolbox = base.Toolbox()
toolbox.register("gene", np.random.random)
toolbox.register("individual", tools.initRepeat, creator.Individual,
                 toolbox.gene, n=IND_SIZE)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=0.1, indpb=0.1)
toolbox.register("select", tools.selTournament, tournsize=3)

from deap import benchmarks

toolbox.register("evaluate", benchmarks.ackley)

IND_SIZE=30
MIN_VALUE = 0
MAX_VALUE = 1
MIN_STRATEGY = 0.2
MAX_STRATEGY = 5

# Individual generator
def generateES(size, imin, imax, smin, smax):
    ind = creator.Individual(np.random.uniform(imin, imax, size))
    ind.strategy = creator.Strategy(np.random.uniform(smin, smax, size))
    return ind

def checkStrategy(minstrategy):
    def decorator(func):
        def wrappper(*args, **kargs):
            children = func(*args, **kargs)
            for child in children:
                for i, s in enumerate(child.strategy):
                    if s < minstrategy:
                        child.strategy[i] = minstrategy
            return children
        return wrappper
    return decorator

toolbox1 = base.Toolbox()
toolbox1.register("individual", generateES,
    IND_SIZE, MIN_VALUE, MAX_VALUE, MIN_STRATEGY, MAX_STRATEGY)
toolbox1.register("population", tools.initRepeat, list, toolbox1.individual)
toolbox1.register("mate", tools.cxESBlend, alpha=0.1)
toolbox1.register("mutate", tools.mutESLogNormal, c=1.0, indpb=0.03)
toolbox1.register("select", tools.selTournament, tournsize=3)
toolbox1.register("evaluate", benchmarks.ackley)
toolbox1.decorate("mate", checkStrategy(MIN_STRATEGY))
toolbox1.decorate("mutate", checkStrategy(MIN_STRATEGY))

import time

logbook_dict = {'eaSimple':[], 'eaMuCommaLambda':[], 'eaMuPlusLambda':[]}
time_dict = {'eaSimple':[], 'eaMuCommaLambda':[], 'eaMuPlusLambda':[]}
ngen = 1000
for _ in range(1):
    stats = tools.Statistics(key=lambda ind: ind.fitness.values)
    stats.register("min", np.min)

    time1 = time.perf_counter()
    pop = toolbox.population(n=50)
    _, logbook = algorithms.eaSimple(pop, toolbox=toolbox, cxpb=0.75, mutpb=0.15, ngen=ngen, stats=stats, verbose=False)
    time2 = time.perf_counter()
    logbook_dict['eaSimple'].append(logbook)
    time_dict['eaSimple'].append(time2 - time1)

    time1 = time.perf_counter()
    popc = toolbox1.population(n=50)
    _, logbook = algorithms.eaMuPlusLambda(popc, toolbox1, mu=40, lambda_=60, cxpb=0.3, mutpb=0.7, ngen=ngen, stats=stats, verbose=False)
    time2 = time.perf_counter()
    time_dict['eaMuPlusLambda'].append(time2 - time1)
    logbook_dict['eaMuPlusLambda'].append(logbook)

VGA = 'eaMuPlusLambda'
import matplotlib.pyplot as plt
fig, ax = plt.subplots()

gen = np.arange(ngen+1)
fmins = np.row_stack([logbook.select("min") for logbook in logbook_dict['eaSimple']]).mean(axis=0)
line1 = ax.plot(gen, fmins, "r-", label="Minimum Fitness(SGA)")

fmins = np.row_stack([logbook.select("min") for logbook in logbook_dict['eaMuPlusLambda']]).mean(axis=0)
line2 = ax.plot(gen, fmins, "b-", label=f"Minimum Fitness({VGA})")

t = np.mean(time_dict['eaMuPlusLambda']) / np.mean(time_dict['eaSimple'])
gent= [k * t for k in gen if k * t<=ngen]
line2t = ax.plot(gent, fmins[:len(gent)], "g-.", label=f"Minimum Fitness({VGA})/Time")

ax.set_xlabel("Generation / Time")
ax.set_ylabel("Fitness")

lns = line1 + line2 + line2t
labs = [l.get_label() for l in lns]
ax.legend(lns, labs)

plt.show()

[fmder]

Thanks for this study, I never benchmarked the algorithms like that. AFAIK, they should be roughly equivalent offering different trade-offs between exploration and exploitation.

My first guess is that the simple algorithm uses more exploration as in a single generation individuals can be mated and mutated, while in the (µ + λ) algorithm individual can only be mated or mutated.

My second guess is your parameters, in the simple algorithm you use 75% crossover and 15% mutation, while in the (µ + λ) algorithm you use 30% crossover and 70% mutation.

[Freakwill]

crossover

Thank you for your guesses. I think, more important is the time costed in the final analysis, whatever how much exploration is took. To change the parameters of (µ + λ) algorithm could not make it better than SGA, I think. And the original ES algorithm, there is no crossover (This is the reason why I turn up mutpb).

[bjuergens]

this is interesting, I am using a modified eaMuPlusLambda to train neural networks for motion control and atari-game-playing. eaMuPlusLambda seems to perform well for me. I haven't tried eaSimple.

Could it be, that the evaluation in your example is not "difficult enough" to benefit from mupluslambda? e.g. for problems with an non deterministic evaluation function?

I guess, that eaSimple behaves basically like a MuCommaLambda. And in my experiments I have observed very bad performance when I drop the parent generation from the population.