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 = [[0] * 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.lambdify(expr=individual)
    return sum(func(*in_) == out for in_, out in zip(inputs, outputs)),

The complete example: [source code]

Reference

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