Even-Parity Problem

  1from deap_er import creator
  2from deap_er import tools
  3from deap_er import base
  4from deap_er import gp
  5import operator
  6import random
  7import numpy
  8
  9
 10random.seed(1234)  # disables randomization
 11
 12
 13PARITY_FANIN_M = 6
 14PARITY_SIZE_M = 2 ** PARITY_FANIN_M
 15
 16inputs: list = [None] * PARITY_SIZE_M
 17outputs: list = [None] * PARITY_SIZE_M
 18
 19
 20def fill_inputs_outputs():
 21    for i in range(PARITY_SIZE_M):
 22        inputs[i] = [None] * PARITY_FANIN_M
 23        value = i
 24        dividor = PARITY_SIZE_M
 25        parity = 1
 26        for j in range(PARITY_FANIN_M):
 27            dividor /= 2
 28            if value >= dividor:
 29                inputs[i][j] = 1
 30                parity = int(not parity)
 31                value -= dividor
 32            else:
 33                inputs[i][j] = 0
 34        outputs[i] = parity
 35
 36
 37def evaluate(individual, toolbox):
 38    func = toolbox.compile(expr=individual)
 39    result = sum(func(*in_) == out for in_, out in zip(inputs, outputs))
 40    return result,  # The comma is essential here.
 41
 42
 43def setup():
 44    pset = gp.PrimitiveSet("MAIN", PARITY_FANIN_M, "IN")
 45    pset.add_primitive(operator.and_, 2)
 46    pset.add_primitive(operator.or_, 2)
 47    pset.add_primitive(operator.xor, 2)
 48    pset.add_primitive(operator.not_, 1)
 49    pset.add_terminal(1)
 50    pset.add_terminal(0)
 51
 52    creator.create("FitnessMax", base.Fitness, weights=(1.0,))
 53    creator.create("Individual", gp.PrimitiveTree, fitness=creator.FitnessMax)
 54
 55    toolbox = base.Toolbox()
 56    toolbox.register("expr", gp.gen_full, prim_set=pset, min_depth=3, max_depth=5)
 57    toolbox.register("individual", tools.init_iterate, creator.Individual, toolbox.expr)
 58    toolbox.register("population", tools.init_repeat, list, toolbox.individual)
 59    toolbox.register("compile", gp.compile_tree, prim_set=pset)
 60    toolbox.register("evaluate", evaluate, toolbox=toolbox)
 61    toolbox.register("select", tools.sel_tournament, contestants=3)
 62    toolbox.register("mate", gp.cx_one_point)
 63    toolbox.register("expr_mut", gp.gen_grow, min_depth=0, max_depth=2)
 64    toolbox.register("mutate", gp.mut_uniform, expr=toolbox.expr_mut, prim_set=pset)
 65
 66    stats = tools.Statistics(lambda ind: ind.fitness.values)
 67    stats.register("avg", numpy.mean)
 68    stats.register("std", numpy.std)
 69    stats.register("min", numpy.min)
 70    stats.register("max", numpy.max)
 71
 72    return toolbox, stats
 73
 74
 75def print_results(best_ind):
 76    if not best_ind.fitness.values == (64,):
 77        raise RuntimeError('Evolution failed to converge.')
 78    print(f'\nEvolution converged correctly.')
 79
 80
 81def main():
 82    fill_inputs_outputs()
 83    toolbox, stats = setup()
 84    pop = toolbox.population(size=300)
 85    hof = tools.HallOfFame(1)
 86    args = dict(
 87        toolbox=toolbox,
 88        population=pop,
 89        generations=40,
 90        cx_prob=0.5,
 91        mut_prob=0.1,
 92        hof=hof,
 93        stats=stats,
 94        verbose=True
 95    )
 96    tools.ea_simple(**args)
 97    print_results(hof[0])
 98
 99
100if __name__ == "__main__":
101    main()