Designing Multiplexers!

One problem used to test methods in AI is the multiplexer problem. It has been used as an example to test the ability of different methods such as decision trees, genetic programming, neural networks, and gene expression programming to correctly classify inputs. The idea is that for some k > 0 we want to design a multiplexer with k address lines and 2^k data lines, and we want the multiplexer's output to be the data line selected by the address lines. The way this has been done with GP and GEP is to have these methods evolve a boolean expression with all k+2^k variables, one for each input, whose result should match the correct data line input.

The fitness in this case can just be how many test cases the function/multiplexer works correctly for. In John Koza's work he used how many it misclassified instead, and then produced a scaling function to normalize the fitness' and make sure they could be used in roulette wheel selection. I'm going the simpler route and just finding how many cases (and you do try every possible case for every individual every generation) each solution gets correct. I am free to minimize or maximize with RGEP, and scaling would have absolutely no effect since the scaling function will be either isotone or antitone- either way tournament selection will only compare ordering not size.

I'm going to try this problem as a test for RGEP to show that it can evolve more then just functions, which is what most of my tests are doing. I plan on trying different size multiplexers, probably 3, 7, and 11 sized because that is what Koza tried in one of his works on GP. I want to also try doing decision tree evolution in RGEP for some variety, and it would be pretty simple to evolve a decision tree for this problem. I think it might even be easier then the boolean function approach as a completely correct tree could be very short.

I will try to post about decision trees when I get that far.