Advances in Artificial Intelligence: Resit Assignment

The Boolean multiplexer is a well-known benchmark classification problem in machine learning. The problems are defined for binary strings of length l = k + 2^k. The first k bits index into the remaining 2^k data bits, returning the value of the indexed data bit which would appear at output Z. A correct classification results in a fitness increment of 1.

E.g., as above, for k=2, an input 110001 (S₀S₁ABCD) followed by a response of 1 would result in a correct classification because the first two bits are the index address corresponding to the binary encoded number 3 and the value at address line 3 is 1.

Write a report on your attempts to solve the multiplexer problem of size k=2 as effectively as possible using any form of evolutionary intelligence covered in the course, building upon your own genetic algorithm code developed in the lab sessions. Clearly describe the encoding used for the induction, show example runs and solutions found, together with explanations of how they work. The system should be trained by presenting each of the possible 2^l input strings and recording the number of correct classifications. Generally, more marks will be given to the effective use of more sophisticated approaches; other extensions could include larger multiplexers. Include a research section at the beginning of the report which briefly discusses classification in data mining and how evolutionary computing techniques have been used for such problems.