多路复用器 3-8 问题

多路复用器问题是另一个广泛使用的遗传编程问题。基本上，它训练一个程序来重现电子 `多路复用器 <http://en.wikipedia.org/wiki/Multiplexer>`_（mux）的行为。通常使用3-8多路复用器（3个地址输入，从A0到A2，以及8个数据输入，从D0到D7），但实际上可以使用任何大小的多路复用器。

这个问题首先由 Koza 定义（参见 参考）。

使用的基本集合

原始集合几乎与 Parity 中使用的集合相同。从 operator 导入的三个布尔运算符（与、或和非），以及一个特定的 if-then-else 原始运算符，根据第一个参数的值返回第二个或第三个参数。

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)

像往常一样，我们也添加了两个终端，一个布尔值 true 和一个布尔值 false。

评估函数

为了加快评估速度，输入/输出对的计算在启动时完成，而不是在每次评估调用时进行。这种预计算还允许通过更改 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]

之后，评估函数变得简单，因为我们既有输入也有输出值。适应度则是2048个案例中正确预测输出的数量（对于一个3-8多路复用器）。

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

完整的 examples/gp/multiplexer。

参考

John R. Koza, “遗传编程I：通过自然选择对计算机进行编程”, MIT Press, 1992, 第170-187页.