Skip to content

Instantly share code, notes, and snippets.

Last active Jan 22, 2021
What would you like to do?
Knuth Problem (described in section 3.2 of the 3rd edition of the book "Artificial Intelligence: A Modern Approach", p. 73) with Tree-based Genetic Programming
# You need to have graphviz installed
# if you want to plot the trees (commented for now).
# It doesn't seem to find the right solution.
# The best solution seems to be: floor(sqrt(float(sqrt(4)))),
# which produces 1, so it has a fitness of 4.
import math
import operator
import random
import sys
# import matplotlib.pyplot as plt
# import networkx as nx
import numpy as np
from deap import algorithms, base, creator, tools
from deap import gp
# from networkx.drawing.nx_agraph import graphviz_layout
NoneType = type(None)
# def plot_expression(expr):
# nodes, edges, labels = gp.graph(expr)
# g = nx.Graph()
# g.add_nodes_from(nodes)
# g.add_edges_from(edges)
# pos = graphviz_layout(g, prog="dot")
# nx.draw_networkx_nodes(g, pos)
# nx.draw_networkx_edges(g, pos)
# nx.draw_networkx_labels(g, pos, labels)
def fact(x):
return float(math.factorial(x))
def identity(x):
return x
primitive_set = gp.PrimitiveSetTyped("f", [int], float)
primitive_set.addPrimitive(math.floor, [float], float)
primitive_set.addPrimitive(math.sqrt, [float], float)
primitive_set.addPrimitive(abs, [float], float)
primitive_set.addPrimitive(abs, [int], int)
primitive_set.addPrimitive(fact, [int], float)
primitive_set.addPrimitive(identity, [int], int, name="int")
primitive_set.addPrimitive(identity, [float], float, name="float")
primitive_set.addTerminal(4, int)
primitive_set.addTerminal(4, float)
# Define new classes, whose objects can later be initialized and used.
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", gp.PrimitiveTree, fitness=creator.FitnessMax)
# Create the toolbox.
toolbox = base.Toolbox()
# Define function that can later be called during the evolution process.
toolbox.register("tree_initializer", gp.genFull, pset=primitive_set,
min_=1, max_=5)
toolbox.register("individual", tools.initIterate, creator.Individual,
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
toolbox.register("compile", gp.compile, pset=primitive_set)
def evaluate(individual):
func = toolbox.compile(expr=individual)
# plot_expression(individual)
diff = 5 - func(4)
return diff,
toolbox.register("evaluate", evaluate)
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("mate", gp.cxOnePoint)
toolbox.register("expr_mut", gp.genFull, min_=0, max_=3)
toolbox.register("mutate", gp.mutUniform, expr=toolbox.expr_mut,
toolbox.decorate("mate", gp.staticLimit(key=operator.attrgetter("height"),
toolbox.decorate("mutate", gp.staticLimit(key=operator.attrgetter("height"),
def main():
seed = random.randrange(sys.maxsize)
# 2543404381583366948
print("Seed =", seed)
pop = toolbox.population(n=100)
hof = tools.HallOfFame(1)
stats_fit = tools.Statistics(lambda ind:
stats_size = tools.Statistics(len)
mstats = tools.MultiStatistics(fitness=stats_fit, size=stats_size)
mstats.register("avg", np.mean)
pop, log = algorithms.eaSimple(pop, toolbox, 0.8, 0.2, 100, stats=mstats,
halloffame=hof, verbose=True)
# print log
return pop, log, hof
if __name__ == "__main__":
pop, log, hof = main()
print("Best individual =", hof[0])
print("Fitness =", hof[0].fitness)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment