Example for evolutionary regression with local search via evolution strategies

Example demonstrating the use of Cartesian genetic programming for a regression task that involves numeric constants. Local search via evolution strategies is used to determine numeric leaf values of the graph.

# The docopt str is added explicitly to ensure compatibility with
# sphinx-gallery.
docopt_str = """
  Usage:
    example_local_search_evolution_strategies.py [--max-generations=<N>]

  Options:
    -h --help
    --max-generations=<N>  Maximum number of generations [default: 500]

"""

import functools

import matplotlib.pyplot as plt
import numpy as np
import scipy.constants
from docopt import docopt

import cgp

args = docopt(docopt_str)

We first define the target function. Note that this function contains numeric values which are initially not available as constants to the search.

def f_target(x):
    return np.e * x ** 2 + 1.0 + np.pi

Then we define the objective function for the evolution. It consists of an inner objective which accepts a NumPy-compatible function as its first argument and returns the mean-squared error between the expression represented by a given individual and the target function evaluated on a set of random points. This inner objective is used by the local search to determine appropriate values for Parameter node and the actual objective function to update the fitness of the individual.

def inner_objective(ind, seed):
    """Return a loss for the numpy-compatible function f. Used for
    calculating the fitness of each individual and for the local
    search of numeric leaf values.

    """

    f = ind.to_numpy()
    rng = np.random.RandomState(seed)
    batch_size = 500
    x = rng.uniform(-5, 5, size=batch_size)
    y = f(x)
    return -np.mean((f_target(x) - y) ** 2)


def objective(individual, seed):
    """Objective function of the regression task."""

    if not individual.fitness_is_None():
        return individual

    individual.fitness = inner_objective(individual, seed)

    return individual

Next, we define the parameters for the population, the genome of individuals, the evolutionary algorithm, and the local search.

population_params = {"n_parents": 1, "seed": 818821}

genome_params = {
    "n_inputs": 1,
    "n_outputs": 1,
    "n_columns": 36,
    "n_rows": 1,
    "levels_back": None,
    "primitives": (cgp.Add, cgp.Sub, cgp.Mul, cgp.Parameter),
}

ea_params = {
    "n_offsprings": 4,
    "mutation_rate": 0.05,
    "tournament_size": 1,
    "n_processes": 1,
    "k_local_search": 2,
}

evolve_params = {"max_generations": int(args["--max-generations"]), "termination_fitness": 0.0}

# restrict the number of steps in the local search; since parameter
# values are propagated from parents to offsprings, parameter values
# may be iteratively improved across generations despite the small
# number of steps per generation
local_search_params = {"max_steps": 5}

We then create a Population instance and instantiate the local search and evolutionary algorithm.

pop = cgp.Population(**population_params, genome_params=genome_params)

# define the function for local search; an instance of the
# EvolutionStrategies can be called with an individual as an argument
# for which the local search is performed
local_search = cgp.local_search.EvolutionStrategies(
    objective=functools.partial(inner_objective, seed=population_params["seed"] + 1),
    seed=population_params["seed"] + 2,
    **local_search_params,
)

ea = cgp.ea.MuPlusLambda(**ea_params, local_search=local_search)

We define a recording callback closure for bookkeeping of the progression of the evolution.

history = {}
history["champion"] = []
history["fitness_parents"] = []


def recording_callback(pop):
    history["champion"].append(pop.champion)
    history["fitness_parents"].append(pop.fitness_parents())


obj = functools.partial(objective, seed=population_params["seed"] + 1)

Finally, we call the evolve method to perform the evolutionary search.

cgp.evolve(pop, obj, ea, **evolve_params, print_progress=True, callback=recording_callback)

Out:

[2/500] max fitness: -6.881744583806576
[3/500] max fitness: -4.239318139952327
[4/500] max fitness: -4.239318139952327
[5/500] max fitness: -4.239318139952327
[6/500] max fitness: -4.2376957679343406
[7/500] max fitness: -4.175395171937035
[8/500] max fitness: -4.0843059447257115
[9/500] max fitness: -4.0843059447257115
[10/500] max fitness: -4.0843059447257115
[11/500] max fitness: -4.0843059447257115
[12/500] max fitness: -4.0843059447257115
[13/500] max fitness: -4.020180611862108
[14/500] max fitness: -3.987534685393779
[15/500] max fitness: -3.987534685393779
[16/500] max fitness: -3.982115911323054
[17/500] max fitness: -3.982115911323054
[18/500] max fitness: -3.982115911323054
[19/500] max fitness: -3.982115911323054
[20/500] max fitness: -3.982115911323054
[21/500] max fitness: -3.982115911323054
[22/500] max fitness: -3.982115911323054
[23/500] max fitness: -3.982115911323054
[24/500] max fitness: -3.982115911323054
[25/500] max fitness: -3.9783604395665826
[26/500] max fitness: -3.9783604395665826
[27/500] max fitness: -3.975963080498914
[28/500] max fitness: -3.9750413898704484
[29/500] max fitness: -3.9750413898704484
[30/500] max fitness: -3.974868290993899
[31/500] max fitness: -3.974868290993899
[32/500] max fitness: -3.85342666502812
[33/500] max fitness: -3.840948237271232
[34/500] max fitness: -3.829865951473381
[35/500] max fitness: -3.818854139942691
[36/500] max fitness: -3.8079393011551694
[37/500] max fitness: -3.7975692305038242
[38/500] max fitness: -3.787213475511162
[39/500] max fitness: -3.777223610695676
[40/500] max fitness: -3.766680768725331
[41/500] max fitness: -3.756839938976412
[42/500] max fitness: -3.747036064090625
[43/500] max fitness: -3.737381219897841
[44/500] max fitness: -3.7277175758131427
[45/500] max fitness: -3.717793730125041
[46/500] max fitness: -3.708016854400642
[47/500] max fitness: -3.6982601042564305
[48/500] max fitness: -3.688439543144267
[49/500] max fitness: -3.6788614880092063
[50/500] max fitness: -3.669222551648229
[51/500] max fitness: -3.6598265812526587
[52/500] max fitness: -3.650306313723362
[53/500] max fitness: -3.6405507370383074
[54/500] max fitness: -3.631311431721749
[55/500] max fitness: -3.622171681144139
[56/500] max fitness: -3.6129228307197043
[57/500] max fitness: -3.603532773075208
[58/500] max fitness: -3.594538835130544
[59/500] max fitness: -3.586006858898131
[60/500] max fitness: -3.577134500980999
[61/500] max fitness: -3.5681746010612367
[62/500] max fitness: -3.5589700921389666
[63/500] max fitness: -3.549600907592355
[64/500] max fitness: -3.5401113788503706
[65/500] max fitness: -3.5310973427172017
[66/500] max fitness: -3.5225028551289825
[67/500] max fitness: -3.5135724845686473
[68/500] max fitness: -3.504486214365747
[69/500] max fitness: -2.5814693162841014
[70/500] max fitness: -1.798765523939992
[71/500] max fitness: -1.1925933685462708
[72/500] max fitness: -0.44130265714672784
[73/500] max fitness: -0.020641384104450395
[74/500] max fitness: -0.0034663029647299206
[75/500] max fitness: -0.0005979864681252498
[76/500] max fitness: -0.00010324056328251351
[77/500] max fitness: -2.6186226050626374e-05
[78/500] max fitness: -5.921426996423762e-06
[79/500] max fitness: -1.1824540864575155e-06
[80/500] max fitness: -5.070027011077923e-08
[81/500] max fitness: -5.070027011077923e-08
[82/500] max fitness: -3.078209891681923e-08
[83/500] max fitness: -3.078209891681923e-08
[84/500] max fitness: -3.078209891681923e-08
[85/500] max fitness: -4.929644402485364e-09
[86/500] max fitness: -4.929644402485364e-09
[87/500] max fitness: -4.929644402485364e-09
[88/500] max fitness: -4.929644402485364e-09
[89/500] max fitness: -4.929644402485364e-09
[90/500] max fitness: -4.929644402485364e-09
[91/500] max fitness: -4.929644402485364e-09
[92/500] max fitness: -4.929644402485364e-09
[93/500] max fitness: -4.30848985793525e-09
[94/500] max fitness: -3.6749018276108156e-09
[95/500] max fitness: -2.9841780186794337e-09
[96/500] max fitness: -2.9841780186794337e-09
[97/500] max fitness: -2.9351615812390943e-09
[98/500] max fitness: -2.93075211976597e-09
[99/500] max fitness: -2.93075211976597e-09
[100/500] max fitness: -2.7351892061894353e-09
[101/500] max fitness: -2.7351892061894353e-09
[102/500] max fitness: -2.7351892061894353e-09
[103/500] max fitness: -2.7351892061894353e-09
[104/500] max fitness: -2.6617300319014235e-09
[105/500] max fitness: -2.6617300319014235e-09
[106/500] max fitness: -2.6617300319014235e-09
[107/500] max fitness: -2.6617300319014235e-09
[108/500] max fitness: -2.6617300319014235e-09
[109/500] max fitness: -2.6617300319014235e-09
[110/500] max fitness: -2.6580956920261464e-09
[111/500] max fitness: -2.6580956920261464e-09
[112/500] max fitness: -2.6580956920261464e-09
[113/500] max fitness: -2.6580956920261464e-09
[114/500] max fitness: -2.6580956920261464e-09
[115/500] max fitness: -2.6580956920261464e-09
[116/500] max fitness: -2.6580956920261464e-09
[117/500] max fitness: -2.6576550322519943e-09
[118/500] max fitness: -2.6576550322519943e-09
[119/500] max fitness: -2.6576550322519943e-09
[120/500] max fitness: -2.6576550322519943e-09
[121/500] max fitness: -2.6576550322519943e-09
[122/500] max fitness: -2.657636629725745e-09
[123/500] max fitness: -2.657636629725745e-09
[124/500] max fitness: -2.6576253172100185e-09
[125/500] max fitness: -2.6576253172100185e-09
[126/500] max fitness: -2.6576253172100185e-09
[127/500] max fitness: -2.6576253172100185e-09
[128/500] max fitness: -2.6576253172100185e-09
[129/500] max fitness: -2.6576253172100185e-09
[130/500] max fitness: -2.6576164997562943e-09
[131/500] max fitness: -2.6576164997562943e-09
[132/500] max fitness: -2.6576164997562943e-09
[133/500] max fitness: -2.6576164997562943e-09
[134/500] max fitness: -2.6576164997562943e-09
[135/500] max fitness: -2.6541571293983925e-09
[136/500] max fitness: -2.6400979702486384e-09
[137/500] max fitness: -2.6067651992255644e-09
[138/500] max fitness: -2.528749678874879e-09
[139/500] max fitness: -2.353336721564865e-09
[140/500] max fitness: -1.9980557885494574e-09
[141/500] max fitness: -1.5205501545528233e-09
[142/500] max fitness: -1.472070164033228e-09
[143/500] max fitness: -1.4019798683029157e-09
[144/500] max fitness: -1.282764124910066e-09
[145/500] max fitness: -1.1341527722339276e-09
[146/500] max fitness: -9.61042589977955e-10
[147/500] max fitness: -7.578954444223847e-10
[148/500] max fitness: -5.577680973949372e-10
[149/500] max fitness: -3.8029804289412244e-10
[150/500] max fitness: -2.375868784809527e-10
[151/500] max fitness: -1.290325442051286e-10
[152/500] max fitness: -4.339237606313096e-11

After finishing the evolution, we plot the result and log the final evolved expression.

width = 9.0
fig = plt.figure(figsize=(width, width / scipy.constants.golden))

ax_fitness = fig.add_subplot(121)
ax_fitness.set_xlabel("Generation")
ax_fitness.set_ylabel("Fitness")
ax_fitness.set_yscale("symlog")

ax_function = fig.add_subplot(122)
ax_function.set_ylabel(r"$f(x)$")
ax_function.set_xlabel(r"$x$")


print(f"Final expression {pop.champion.to_sympy()} with fitness {pop.champion.fitness}")

history_fitness = np.array(history["fitness_parents"])
ax_fitness.plot(np.max(history_fitness, axis=1), label="Champion")
ax_fitness.plot(np.mean(history_fitness, axis=1), label="Population mean")

x = np.linspace(-5.0, 5, 100).reshape(-1, 1)
f = pop.champion.to_func()
y = [f(xi) for xi in x]
ax_function.plot(x, f_target(x), lw=2, label="Target")
ax_function.plot(x, y, lw=1, label="Target", marker="x")

plt.savefig("example_local_search_evolution_strategies.pdf", dpi=300)

Out:

Final expression 2.7182809739095278*x_0**2 + 4.141600810360232 with fitness -4.339237606313096e-11