bool_fool.py

"""Use genetic programming to reverse-engineer a truth table."""

import random
import inspect
import string
from multiprocessing import Process, Value
from deap import creator, base, tools, gp

# 110 Automata
# truth_table = [
#     ((True, True, True), False),
#     ((True, True, False), True),
#     ((True, False, True), True),
#     ((True, False, False), False),
#     ((False, True, True), True),
#     ((False, True, False), True),
#     ((False, False, True), True),
#     ((False, False, False), False)
# ]
# NAND(XNOR(C, B), IMPLIES(B, A))

operators = {
    "AND": lambda x, y: x and y,
    "OR": lambda x, y: x or y,
    "XOR": lambda x, y: x != y,
    "NOT": lambda x: not x,
    "NOR": lambda x, y: not (x or y),
    "NAND": lambda x, y: not (x and y),
    "XNOR": lambda x, y: x == y,
    "IMPLIES": lambda x, y: (not x) or y
}


def setup_pset(size):
    """Set up our primitive set."""
    pset = gp.PrimitiveSet("main", size)

    for name, func in operators.items():
        pset.addPrimitive(func, len(inspect.getargspec(func).args), name=name)

    # Create a dict of the form:
    # {
    #     "ARG0": "A",
    #     "ARG1": "B",
    #     ...
    # }
    new_args = {
        "ARG{}".format(i): x
        for i, x in enumerate(string.ascii_uppercase[0:size])
    }
    pset.renameArguments(**new_args)

    return pset


def setup_toolbox(pset):
    """Set up the GP toolbox."""
    creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
    creator.create("Individual", gp.PrimitiveTree, fitness=creator.FitnessMin, pset=pset)

    toolbox = base.Toolbox()
    toolbox.register("expr", gp.genFull, pset=pset, min_=1, max_=7)
    toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.expr)

    return toolbox


def scoring(pset, truth_table, ind):
    """Score an individual."""
    func = gp.compile(ind, pset)
    correct = sum([func(*args) == out for args, out in truth_table])
    total = len(truth_table)
    return correct / total


def random_score(pset, toolbox, truth_table, min_complexity):
    """Evolve an ideal expression tree."""
    ind = toolbox.individual()
    score = scoring(pset, truth_table, ind)
    complexity = sum([isinstance(x, gp.Primitive) for x in ind])

    if complexity < min_complexity.value and score == 1.0:
        min_complexity.value = complexity
        print(complexity)
        print(str(ind))

    return complexity


def spin(pset, toolbox, truth_table, min_complexity):
    """Keep on running them tests."""
    while True:
        random_score(pset, toolbox, truth_table, min_complexity)


def rand_bool():
    """Return either True or False, stochastically."""
    return bool(random.randint(0, 1))


def int_as_bools(i, size):
    """Convert an integer into a tuple of True and False."""
    bin_string = "{0:0{1}b}".format(i, size)
    return tuple([bool(int(x)) for x in bin_string])


def rand_truth_table(size):
    """Generate a random truth table for a function of :size: inputs."""
    return [(int_as_bools(x, size), rand_bool()) for x in range(0, 2 ** size)]


def print_table(truth_table):
    """Pretty print a truth table."""
    for args, out in truth_table:
        print("{} -> {}".format(",".join([str(x) for x in args]), out))


def main():
    """Main driver."""
    size = 4
    min_complexity = Value('i', 1000)
    truth_table = rand_truth_table(size)
    pset = setup_pset(size)
    toolbox = setup_toolbox(pset)
    processes = []

    print_table(truth_table)

    for _ in range(0, 4):
        p = Process(target=spin, args=(pset, toolbox, truth_table, min_complexity))
        p.start()
        processes.append(p)

    try:
        for x in range(0, 4):
            processes[x].join()
    except KeyboardInterrupt:
        for x in range(0, 4):
            processes[x].terminate()


if __name__ == "__main__":
    main()

This doesn't actually use GP. It's random search.