Even-Parity Problem

Parity is one of the classical GP problems. The goal is to find a program that produces the value of the Boolean even parity given n independent Boolean inputs. Usually, 6 Boolean inputs are used (Parity-6), and the goal is to match the good parity bit value for each of the

System Message: WARNING/2 (2^6 = 64)

latex exited with error [stdout] This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013/TeX Live for SUSE Linux) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2011/06/27> Babel <3.9f> and hyphenation patterns for 78 languages loaded. (/usr/share/texmf/tex/latex/base/article.cls Document Class: article 2007/10/19 v1.4h Standard LaTeX document class (/usr/share/texmf/tex/latex/base/size12.clo)) (/usr/share/texmf/tex/latex/base/inputenc.sty ! LaTeX Error: File `utf8x.def’ not found. Type X to quit or <RETURN> to proceed, or enter new name. (Default extension: def) Enter file name: ! Emergency stop. <read *> l.131 \endinput ^^M No pages of output. Transcript written on math.log.
possible entries. The problem can be made harder by increasing the number of inputs (in the DEAP implementation, this number can easily be tuned, as it is fixed by a constant named PARITY_FANIN_M).

For more information about this problem, see Reference.

Primitives set used

Parity uses standard Boolean operators as primitives, available in the Python operator module :

pset = gp.PrimitiveSet("MAIN", PARITY_FANIN_M, "IN")
pset.addPrimitive(operator.and_, 2)
pset.addPrimitive(operator.or_, 2)
pset.addPrimitive(operator.xor, 2)
pset.addPrimitive(operator.not_, 1)
pset.addTerminal(1)
pset.addTerminal(0)

In addition to the n inputs, we add two constant terminals, one at 0, one at 1.

Note

As Python is a dynamic typed language, you can mix Boolean operators and integers without any issue.

Evaluation function

In this implementation, the fitness of a Parity individual is simply the number of successful cases. Thus, the fitness is maximized, and the maximum value is 64 in the case of a 6 inputs problems.

def evalParity(individual):
    func = toolbox.lambdify(expr=individual)
    return sum(func(*in_) == out for in_, out in zip(inputs, outputs)),

inputs and outputs are two pre-generated lists, to speedup the evaluation, mapping a given input vector to the good output bit. The Python sum() function works on booleans (false is interpreted as 0 and true as 1), so the evaluation function boils down to sum the number of successful tests : the higher this sum, the better the individual.

Conclusion

The other parts of the program are mostly the same as the Symbolic Regression algorithm.

The complete example: [source code]

Reference

John R. Koza, “Genetic Programming II: Automatic Discovery of Reusable Programs”, MIT Press, 1994, pages 157-199.