The task of the 11bit boolean multiplexer is to decode a 3bit binary address (000, 001, 010, 011, 100, 101, 110, 111) and return the value of the corresponding data register
(d_{0}, d_{1}, d_{2}, d_{3}, d_{4},
d_{5}, d_{6}, d_{7}). Thus, the boolean 11multiplexer is a function of 11 arguments: three,
a_{0} to a_{2}, determine the address, and eight, d_{0} to
d_{7}, determine the answer. As GEP uses singlecharacter chromosomes,
T = {a, b, c, 1, 2, 3, 4, 5, 6, 7, 8} which correspond, respectively, to
{a_{0}, a_{1}, a_{2}, d_{0}, d_{1},
d_{2}, d_{3}, d_{4}, d_{5}, d_{6},
d_{7}}.
There are 2^{11} = 2048 possible combinations for the 11 arguments of the boolean 11multiplexer function. For this problem a random sampling of the 2048 combinations was used each generation as the fitness cases for evaluating fitness. The fitness cases were assembled by address, and for each address a subset of 20 random combinations was used each generation. Therefore, a total of 160 random fitness cases were used each generation as the adaptation environment. In this case, the fitness of a program is the number of fitness cases for which the boolean value returned is correct, plus a bonus of 180 fitness points for each subset of combinations solved correctly as a whole. Therefore, a total of 200 fitness points was attributed for each correctly decoded address, being the maximum fitness 1600. The idea was to make the algorithm decode one address at a time. And, in fact, the individuals learn to decode first one address, then another, until the last one (see
Figure 17).
To solve this problem, multigenic chromosomes composed of 27 genes were used, each gene consisting of only one terminal. Thus, no functions were used to generate the chromosomes, although the subETs were posttranslationally linked by IF.
The parameters used per run are shown in Table
2, column 5. The first correct solution in this experiment was found in generation 390 of run 1 (the characters are linked 3 by 3, forming an ET with depth 4, composed of 40 nodes, the first 14 nodes being IFs, and the remaining nodes, the chromosome characters; see Kexpression
(3.12) and Figure
5):
012345678901234567890123456
3652bb5bbba4c87c43bcca62a51
which is a universal solution for the 11multiplexer. Figure
17 shows the progression of average fitness of the population and the fitness of the best individual for run 1 of the experiment summarized in
Table 2, column 5.
As shown in the fifth column of Table 2, GEP solves the 11multiplexer with a success rate of 0.57. It is worth noting that GP could not solve the 11multiplexer with a population size 500 for 51 generations
[18], and could only solve it using 4,000 individuals
[9].
Figure 17. Progression of average fitness of the population and the fitness of the best individual for run 1 of the experiment summarized in
Table 2, column 5 (11multiplexer).
