Minimal example for evolutionary regression using hurdles

Example demonstrating the use of Cartesian genetic programming for a simple regression task where we use hurdles to implement early stopping for low-performing invididuals.

Hurdles are implemented by introducing multiple objectives, here two, which are sequentially evaluated. Only those individuals with fitness in the upper 50th percentile on the first objective are evaluated on the second objective.

References:

• Real, E., Liang, C., So, D., & Le, Q. (2020, November). AutoML-zero: evolving machine learning algorithms from scratch. In International Conference on Machine Learning (pp. 8007-8019). PMLR.

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

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

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 a target function.

def f_target(x):
    return x ** 2 + 1.0

Then we define two objective functions for the evolution. They use the mean-squared error between the output of the expression represented by a given individual and the target function evaluated on a set of random points. The first objective uses only few samples (100) to get a fast estimate how well an individual performs. The second objective uses may samples (99900) to determine the fitness precisely.

def objective_one(individual):

    if not individual.fitness_is_None():
        return individual

    n_function_evaluations = 100000

    np.random.seed(1234)
    values = np.random.uniform(-4, 4, n_function_evaluations)

    f = individual.to_func()
    loss = 0
    for x in values[:100]:
        # the callable returned from `to_func` accepts and returns
        # lists; accordingly we need to pack the argument and unpack
        # the return value
        y = f(x)
        loss += (f_target(x) - y) ** 2

    individual.fitness = -loss / n_function_evaluations

    return individual


def objective_two(individual):

    if not individual.fitness_is_None():
        return individual

    n_function_evaluations = 100000

    np.random.seed(1234)
    values = np.random.uniform(-4, 4, n_function_evaluations)

    f = individual.to_func()
    loss = 0
    for x in values[100:]:
        # the callable returned from `to_func` accepts and returns
        # lists; accordingly we need to pack the argument and unpack
        # the return value
        y = f(x)
        loss += (f_target(x) - y) ** 2

    individual.fitness = -loss / n_function_evaluations

    return individual

Next, we set up the evolutionary search. We first define the parameters for the population, the genome of individuals, and the evolutionary algorithm.

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

genome_params = {
    "n_inputs": 1,
    "n_outputs": 1,
    "n_columns": 12,
    "n_rows": 1,
    "levels_back": 5,
    "primitives": (cgp.Add, cgp.Sub, cgp.Mul, cgp.ConstantFloat),
}

We define the upper percentile of individuals which are evaluated on the (n+1)th objective by a list of numbers between 0 and 1.

ea_params = {
    "n_offsprings": 4,
    "mutation_rate": 0.03,
    "n_processes": 1,
    "hurdle_percentile": [0.5, 0.0],
}

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

We create a population that will be evolved

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

and an instance of the (mu + lambda) evolutionary algorithm

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

We define a callback for recording of fitness over generations

history = {}
history["fitness_champion"] = []


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

and finally perform the evolution

cgp.evolve(
    pop,
    [objective_one, objective_two],
    ea,
    **evolve_params,
    print_progress=True,
    callback=recording_callback
)

Out:

[2/300] max fitness: -84.24595774757668
[3/300] max fitness: -62.89903747153193
[4/300] max fitness: -62.89903747153193
[5/300] max fitness: -62.89903747153193
[6/300] max fitness: -51.22588427381885
[7/300] max fitness: -51.22588427381885
[8/300] max fitness: -51.22588427381885
[9/300] max fitness: -51.22588427381885
[10/300] max fitness: -51.22588427381885
[11/300] max fitness: -51.22588427381885
[12/300] max fitness: -51.22588427381885
[13/300] max fitness: -51.22588427381885
[14/300] max fitness: -51.22588427381885
[15/300] max fitness: -51.22588427381885
[16/300] max fitness: -51.22588427381885
[17/300] max fitness: -51.22588427381885
[18/300] max fitness: -51.22588427381885
[19/300] max fitness: -51.22588427381885
[20/300] max fitness: -51.22588427381885
[21/300] max fitness: -51.22588427381885
[22/300] max fitness: -51.22588427381885
[23/300] max fitness: -51.22588427381885
[24/300] max fitness: -51.22588427381885
[25/300] max fitness: -51.22588427381885
[26/300] max fitness: -51.22588427381885
[27/300] max fitness: -51.22588427381885
[28/300] max fitness: -51.22588427381885
[29/300] max fitness: -51.22588427381885
[30/300] max fitness: -51.22588427381885
[31/300] max fitness: -51.22588427381885
[32/300] max fitness: -51.22588427381885
[33/300] max fitness: -51.22588427381885
[34/300] max fitness: -51.22588427381885
[35/300] max fitness: -51.22588427381885
[36/300] max fitness: -51.22588427381885
[37/300] max fitness: -51.22588427381885
[38/300] max fitness: -51.22588427381885
[39/300] max fitness: -51.22588427381885
[40/300] max fitness: -51.22588427381885
[41/300] max fitness: -51.22588427381885
[42/300] max fitness: -51.22588427381885
[43/300] max fitness: -51.22588427381885
[44/300] max fitness: -51.22588427381885
[45/300] max fitness: -51.22588427381885
[46/300] max fitness: -51.22588427381885
[47/300] max fitness: -51.22588427381885
[48/300] max fitness: -51.22588427381885
[49/300] max fitness: -51.22588427381885
[50/300] max fitness: -51.22588427381885
[51/300] max fitness: -51.22588427381885
[52/300] max fitness: -51.22588427381885
[53/300] max fitness: -51.22588427381885
[54/300] max fitness: -51.22588427381885
[55/300] max fitness: -51.22588427381885
[56/300] max fitness: -51.22588427381885
[57/300] max fitness: -51.22588427381885
[58/300] max fitness: -51.22588427381885
[59/300] max fitness: -51.22588427381885
[60/300] max fitness: -51.22588427381885
[61/300] max fitness: -51.22588427381885
[62/300] max fitness: -51.22588427381885
[63/300] max fitness: -51.22588427381885
[64/300] max fitness: -51.22588427381885
[65/300] max fitness: -51.22588427381885
[66/300] max fitness: -51.22588427381885
[67/300] max fitness: -51.22588427381885
[68/300] max fitness: -51.22588427381885
[69/300] max fitness: -51.22588427381885
[70/300] max fitness: -51.22588427381885
[71/300] max fitness: -51.22588427381885
[72/300] max fitness: -51.22588427381885
[73/300] max fitness: -51.22588427381885
[74/300] max fitness: -51.22588427381885
[75/300] max fitness: -51.22588427381885
[76/300] max fitness: -51.22588427381885
[77/300] max fitness: -51.22588427381885
[78/300] max fitness: -51.22588427381885
[79/300] max fitness: -51.22588427381885
[80/300] max fitness: -51.22588427381885
[81/300] max fitness: -51.22588427381885
[82/300] max fitness: -51.22588427381885
[83/300] max fitness: -51.22588427381885
[84/300] max fitness: -51.22588427381885
[85/300] max fitness: -51.22588427381885
[86/300] max fitness: -51.22588427381885
[87/300] max fitness: -41.552731076106
[88/300] max fitness: -1.0
[89/300] max fitness: -1.0
[90/300] max fitness: -1.0
[91/300] max fitness: -1.0
[92/300] max fitness: -1.0
[93/300] max fitness: -1.0
[94/300] max fitness: -1.0
[95/300] max fitness: -1.0
[96/300] max fitness: -1.0
[97/300] max fitness: -1.0
[98/300] max fitness: -1.0
[99/300] max fitness: -1.0
[100/300] max fitness: -1.0
[101/300] max fitness: -1.0
[102/300] max fitness: -1.0
[103/300] max fitness: -1.0
[104/300] max fitness: -1.0
[105/300] max fitness: -1.0
[106/300] max fitness: -1.0
[107/300] max fitness: -1.0
[108/300] max fitness: -1.0
[109/300] max fitness: -1.0
[110/300] max fitness: -1.0
[111/300] max fitness: -1.0
[112/300] max fitness: -1.0
[113/300] max fitness: -1.0
[114/300] max fitness: -1.0
[115/300] max fitness: -1.0
[116/300] max fitness: -1.0
[117/300] max fitness: -1.0
[118/300] max fitness: -1.0
[119/300] max fitness: -1.0
[120/300] max fitness: -1.0
[121/300] max fitness: -1.0
[122/300] max fitness: -1.0
[123/300] max fitness: -1.0
[124/300] max fitness: -1.0
[125/300] max fitness: -1.0
[126/300] max fitness: -1.0
[127/300] max fitness: -1.0
[128/300] max fitness: -1.0
[129/300] max fitness: -1.0
[130/300] max fitness: -1.0
[131/300] max fitness: -1.0
[132/300] max fitness: -1.0
[133/300] max fitness: -1.0
[134/300] max fitness: -1.0
[135/300] max fitness: -1.0
[136/300] max fitness: -1.0
[137/300] max fitness: -1.0
[138/300] max fitness: -1.0
[139/300] max fitness: -1.0
[140/300] max fitness: -1.0
[141/300] max fitness: -1.0
[142/300] max fitness: -1.0
[143/300] max fitness: -1.0
[144/300] max fitness: -1.0
[145/300] max fitness: -1.0
[146/300] max fitness: -1.0
[147/300] max fitness: -1.0
[148/300] max fitness: -1.0
[149/300] max fitness: -1.0
[150/300] max fitness: -1.0
[151/300] max fitness: -1.0
[152/300] max fitness: -1.0
[153/300] max fitness: -1.0
[154/300] max fitness: -1.0
[155/300] max fitness: -1.0
[156/300] max fitness: -1.0
[157/300] max fitness: -1.0
[158/300] max fitness: -1.0
[159/300] max fitness: -1.0
[160/300] max fitness: -1.0
[161/300] max fitness: -1.0
[162/300] max fitness: -1.0
[163/300] max fitness: -1.0
[164/300] max fitness: -1.0
[165/300] max fitness: -1.0
[166/300] max fitness: -1.0
[167/300] max fitness: -1.0
[168/300] max fitness: -1.0
[169/300] max fitness: -1.0
[170/300] max fitness: -1.0
[171/300] max fitness: -1.0
[172/300] max fitness: -1.0
[173/300] max fitness: -1.0
[174/300] max fitness: -1.0
[175/300] max fitness: -1.0
[176/300] max fitness: -1.0
[177/300] max fitness: -1.0
[178/300] max fitness: -1.0
[179/300] max fitness: -1.0
[180/300] max fitness: -1.0
[181/300] max fitness: -1.0
[182/300] max fitness: -1.0
[183/300] max fitness: -1.0
[184/300] max fitness: -1.0
[185/300] max fitness: -1.0
[186/300] max fitness: -1.0
[187/300] max fitness: -1.0
[188/300] max fitness: -1.0
[189/300] max fitness: -1.0
[190/300] max fitness: -1.0
[191/300] max fitness: -1.0
[192/300] max fitness: -1.0
[193/300] max fitness: -1.0
[194/300] max fitness: -1.0
[195/300] max fitness: -1.0
[196/300] max fitness: -1.0
[197/300] max fitness: -1.0
[198/300] max fitness: -1.0
[199/300] max fitness: -1.0
[200/300] max fitness: -1.0
[201/300] max fitness: -1.0
[202/300] max fitness: -1.0
[203/300] max fitness: -1.0
[204/300] max fitness: -1.0
[205/300] max fitness: -1.0
[206/300] max fitness: -1.0
[207/300] max fitness: -1.0
[208/300] max fitness: -1.0
[209/300] max fitness: -1.0
[210/300] max fitness: -1.0
[211/300] max fitness: -1.0
[212/300] max fitness: -1.0
[213/300] max fitness: -1.0
[214/300] max fitness: -1.0
[215/300] max fitness: -1.0
[216/300] max fitness: -1.0
[217/300] max fitness: -1.0
[218/300] max fitness: -1.0
[219/300] max fitness: -1.0
[220/300] max fitness: -1.0
[221/300] max fitness: -1.0
[222/300] max fitness: -1.0
[223/300] max fitness: -1.0
[224/300] max fitness: -1.0
[225/300] max fitness: -1.0
[226/300] max fitness: -1.0
[227/300] max fitness: -1.0
[228/300] max fitness: -1.0
[229/300] max fitness: -1.0
[230/300] max fitness: -1.0
[231/300] max fitness: -1.0
[232/300] max fitness: -1.0
[233/300] max fitness: -1.0
[234/300] max fitness: -1.1749097107135445e-33

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

width = 9.0
fig, axes = plt.subplots(1, 2, figsize=(width, width / scipy.constants.golden))

ax_fitness, ax_function = axes[0], axes[1]
ax_fitness.set_xlabel("Generation")
ax_fitness.set_ylabel("Fitness")

ax_fitness.plot(history["fitness_champion"], label="Champion")

ax_fitness.set_yscale("symlog")
ax_fitness.set_ylim(-1.0e2, 0.1)
ax_fitness.axhline(0.0, color="0.7")

f = pop.champion.to_func()
x = np.linspace(-5.0, 5.0, 20)
y = [f(x_i) for x_i in x]
y_target = [f_target(x_i) for x_i in x]

ax_function.plot(x, y_target, lw=2, alpha=0.5, label="Target")
ax_function.plot(x, y, "x", label="Champion")
ax_function.legend()
ax_function.set_ylabel(r"$f(x)$")
ax_function.set_xlabel(r"$x$")

fig.savefig("example_minimal.pdf", dpi=300)