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 \(2^6 = 64\) 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.compile(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 examples/%sgp/parity.
Reference¶
John R. Koza, “Genetic Programming II: Automatic Discovery of Reusable Programs”, MIT Press, 1994, pages 157-199.