Information Technology Reference
In-Depth Information
and, consequently, very difficult to solve using this approach. So, a good alter-
native consists of trying to discover some kind of pattern in these functions
and then use this information to design all the functions we need. Let's see
how this works for the odd-parity functions.
We have already designed the most parsimonious solution to the XOR
function using the function set F = {AND, OR, NOT} in the section Boolean
Logic (see Table 4.9). As you can see by its expression below, it requires a
total of eight nodes:
A
O
N
a
b
A
a
b
Now we could try and use this solution as a UDF to solve the next odd-
parity function (the odd-3-parity function) in order to find out if there is some
kind of pattern in their structure that we could exploit. As you can see in
Table 4.15, the inclusion of this function as a UDF in the function set is
responsible for a considerable increase in performance (notice that, in the
absence of the UDF, not only the number of generations is 10 times higher
but also the success rate is considerably lower). And this happens every time
a lower order odd-parity function is used as a UDF to design a higher order
function (compare Tables 4.14 and 4.15). And this most probably means that
there is a pattern we can explore to design good parsimonious solutions to
any parity function. Let's then see if we can find this pattern.
In order to do so, it helps a lot to be able to find the most parsimonious
expressions so that all the unnecessary bits would disappear and the underly-
ing order becomes clearly visible. For that an evolutionary strategy similar
to the one used in section 4.3.2, Universal Logical Systems, is used. Thus, a
flexible head length is chosen to allow an efficient evolution without restric-
tions regarding program size, and then, after a perfect solution has been found,
a fitness function with parsimony pressure is applied in order to trim the
perfect solution. The results of such an analysis are shown in Figure 4.9.
And as you can see in Figure 4.9, the pattern is perfectly clear and very
simple, providing a simple and efficient way of designing any parity func-
tion one wishes for using just NOTs, ANDs, and ORs gates.
