# Multiplexer 3-8 Problem¶

The multiplexer problem is another extensively used GP problem. Basically, it trains a program to reproduce the behavior of an electronic multiplexer (mux). Usually, a 3-8 multiplexer is used (3 address entries, from A0 to A2, and 8 data entries, from D0 to D7), but virtually any size of multiplexer can be used.

This problem was first defined by Koza (see Reference).

## Primitives set used¶

The primitive set is almost the same as the set used in Parity. Three Boolean operators (and, or and not), imported from operator, and a specific if-then-else primitive, which return either its second or third argument depending on the value of the first one.

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


As usual, we also add two terminals, a Boolean true and a Boolean false.

## Evaluation function¶

To speed up the evaluation, the computation of the input/output pairs is done at start up, instead of at each evaluation call. This pre-computation also allows to easily tune the multiplexer size, by changing the value of MUX_SELECT_LINES.

MUX_SELECT_LINES = 3
MUX_IN_LINES = 2 ** MUX_SELECT_LINES
MUX_TOTAL_LINES = MUX_SELECT_LINES + MUX_IN_LINES

# input : [A0 A1 A2 D0 D1 D2 D3 D4 D5 D6 D7] for a 8-3 mux
inputs = [ * MUX_TOTAL_LINES for i in range(2 ** MUX_TOTAL_LINES)]
outputs = [None] * (2 ** MUX_TOTAL_LINES)

for i in range(2 ** MUX_TOTAL_LINES):
value = i
divisor = 2 ** MUX_TOTAL_LINES
# Fill the input bits
for j in range(MUX_TOTAL_LINES):
divisor /= 2
if value >= divisor:
inputs[i][j] = 1
value -= divisor

# Determine the corresponding output
indexOutput = MUX_SELECT_LINES
for j, k in enumerate(inputs[i][:MUX_SELECT_LINES]):
indexOutput += k * 2**j
outputs[i] = inputs[i][indexOutput]


After that, the evaluation function is trivial, as we have both inputs and output values. The fitness is then the number of well predicted outputs over the 2048 cases (for a 3-8 multiplexer).

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


The complete examples/gp/multiplexer.

## Reference¶

John R. Koza, “Genetic Programming I: On the Programming of Computers by Means of Natural Selection”, MIT Press, 1992, pages 170-187.