The 11-multiplexer problem is an extended version of the 6-multiplexer with 2³=8 addresses (000, 001, 010, 011, 100, 101, 110, 111) and 8 data registers (d₀ to d₇). Thus, the Boolean 11-multiplexer is a function of 11 activities {a₀,a₁,a₂,d₀,d₁,d₂, d₃,d₄,d₅,d₆,d₇} which correspond respectively to the elements of the terminal set {a,b,c,1,2,3,4,5,6,7,8}. In this case there are 2¹¹=2048 possible combinations for the 11 arguments of the Boolean 11-multiplexer function. For this problem a random sampling of the 2048 combinations (160) was used as the fitness cases for evaluating fitness.

Notes: I- if (x,y,z) function: if x is 1, the second argument is evaluated, otherwise the third argument is evaluated.

Conclusion:
It's worth noticing that GP could not solve the 11-multiplexer with population size 500 for 51 generations [1], and could only solve it using 4,000 individuals although Koza [2] didn't mention the success rate.

Download the executable

Bibliography:
1. O'Reilly, U-M, and F. Oppacher (1996). A comparative analysis of GP. Chapter 2 of Advances in Genetic Programming 2, ed. P. J. Angeline and K. E. Kinnear, MIT Press.
2. Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: MIT Press.

Back

***