Urgent help needed for simple genetic Program

The problem that I have to solve is the following

Implement a genetic programming algorithm and use it to solve the \6-multiplexer" problem (Koza 1992). In this problem there are six Boolean-valued terminals, a0; a1; d0; d1; d2; d3, and four functions, AND, OR, NOT, IF. The fi rst three functions are the usual logical operators, taking two, two, and one argument respectively, and the IF function takes three arguments. (IF X Y Z) evaluates its fir rst argument X. If X is true, the second argument Y is evaluated; otherwise the third argument Z is evaluated. The problem is to fi nd a program that will return the value of the d terminal that is addressed by the two a terminals. E.g., if a0 = 0 and a1 = 1, the address is 01 and the answer is the value of d1. Likewise, if a0 = 1 and a1 = 1, the address is 11 and the answer is the value of d3. The fitness of a program should be the fraction of correct answers over all 64 possible tness cases (i.e., values of the six terminals).

I understand the problem but I have no idea how to implement this in MATLAB. First of all, how would I generate random candidate solutions? I can't use a matrix because you cannot put OR and AND and IF functions in a matrix. Somehow I need to create different trees that I can save. I really do not even know how to start. Can this even be done in MATLAB?

Thanks,

Alex

Answer 1

[Walter Roberson]

You mean like d = [d0 d1 d2 d3], then d(a0*2+a1+1) ?

You cannot use a matrix formulation of the problem, because it would be completely valid for a genetically generated program to be something like

IF((AND(A0,OR(A1,A1)),NOT(NOT(NOT(AND(A0,A0)))))), NOT(AND(A0,A1)))

which is clearly not encodeable in a single matrix. (I dunno, maybe as a series of matrices multiplied and added together... though you would need subtraction too in order to code the NOT.)

I haven't been able to tell what your intended output is...