The isolation of useful subprograms/sub-functions is a related research theme in GP. However, in most studies subprograms are not reused across different problems. In [2] for instance, the hierarchical automatic function definition technique was introduced so as to facilitate the development of useful sub-functions whilst solving a problem. Machine learning was employed in [3] to analyse the internal behaviour (semantics) of GP programs so as to automatically isolate potentially useful problem specific subprograms.
SB was used in [4] to define intermediate subtasks for GP. Two GP search operator were introduced which semantically searched a library of subtrees which could be used to solve the subtasks. Similar work was carried out in [6, 7], however in these cases subtree libraries were smaller and static, and only a single tree was iteratively modified as opposed to a population of trees.
Semantic backpropagation (SB) within the context of GP is an active research topic [4, 5, 6, 7].
Consider the output array produced by the root node of a solution tree, where each element within the array corresponds to the output from one fitness case. This output array is the semantics of the root node. If the solution is perfectly correct, the output array will correspond exactly to the target output array of the problem at hand. In a programmatic style, the output array of a general node node x will be denoted as node x.outputs and the output from fitness case i will be denoted by node x.outputs[i].
Each node within a tree produces an output array, a feature which has been exploited in [3] to isolate useful subtrees. The simplest example of a tree (beyond a single node) is a triplet of nodes: a parent node node a, the left child node node b, and the right child node node c.
As a two fitness case example, suppose that a triplet is composed of a parent node node a representing the operator AND, a left child node node b representing input argument A1 = [0,1], and a right child node node c representing input argument A2 = [1,1]. The output array of the parent node is given by:
Figure 1. Function tables for the reverse operators: ANDOR
operator assigned to the parent node, as this is the operator that is reversed. And secondly, on the choices made (note the ANDexample above), at each loci, as to which of the two child output arrays contains the # value. These decisions are made by the controller component.
Using these reverse operators for SB can only ever produce a pair of output arrays which are different from the problem target outputs in two ways. Firstly, the output arrays can be a flipped (using the NOT gate on each bit) or an un-flipped versions of the problem target outputs. Secondly, some elements of the output arrays will be # elements.
Figure 2. A visual representation of the NNGS algorithm during the development of a solution tree.
A visual representation of the NNGS algorithm can be seen in Fig. 2, which shows a snapshot of a partially generated solution tree. This tree, in it’s unfinished state, is composed of: AND and OR operators, an input argument labelled A1, and two unprocessed nodes. The basic role of the NNGS algorithm is to manage growing the solution tree by passing unprocessed nodes to the controller and substituting back the generated/returned node triplet.
Algorithm 1 gives a simple and more thorough explanation of NNGS. In line 2 the output values of the solution tree root node are set to the target output values of the problem at hand. The output values of a node are used, along with the reverse operators, by the controller (line 9) to generate the output values of the returned child nodes. The controller also sets the node type (they are either operators or input arguments) of the input parent node and generated child nodes.
Nodes which have been defined by the controller as input arguments (with labels: A1, A2, A3... etc.) can not have child nodes (they are by definition leaf nodes) and are therefore
not processed further by the controller (line 6). When every branch of the tree ends in an input argument node, the algorithm halts.
Note that the controller may well generate a triplet where one or more of the child nodes require further processing. In this case the NNGS algorithm will pass these nodes back to the controller at a later stage before the algorithm ends. In effect, by using the controller component the NNGS algorithm simply writes out the solution tree.
Given an unprocessed node, the controller generates two child nodes and their output arrays using one of the four reverse operators. It also sets the operator type of the parent node to correspond with the chosen reverse operator that is used.
The ultimate goal of the controller is to assign an input argument to each generated child node. For example, suppose that the controller generates a child node with an output array node b.outputs = [0,1,1,#] and that an input argument is given by A1 = [0,1,1,0]. In this case, node b can be assigned (can represent) the input argument A1 because [0,1,1,#] = [0,1,1,0]. The algorithm halts once each leaf node has been assigned an input argument.
Before giving a detailed description of the proof-of-concept controller, there are a few important general points to stress: Firstly, the entire decision making process is deterministic. Secondly, the decision making process is greedy (the perceived best move is taken at each opportunity). Thirdly, the controller does not know the location of the input node within the solution tree. The controller has priori knowledge of the input argument arrays, the operators, and the reverse operators only. Furthermore, the controller, in its current state, does not memorise the results of it’s past decision making.
In this regard, when processing a node, the controller has knowledge of that node’s output array only. In this way, the controller acts locally on each node. Multiple instances of the controller could act in parallel by processing all unprocessed nodes simultaneously.
5.1 Step-by-step
This subsection will give a step-by-step run-through of the procedure undertaken by the proof-of-concept controller. Figure 3 serves as a diagrammatic aid for each major step.
5.1.1 Step 1
Given an input (parent) node node a, and for each reverse operator in Table 1, the first step taken by the controller is to generate output arrays for each of the child nodes. In the example given in step 1 of Fig. 3 only the ORreverse operator is used. The OR
reverse operator generates # values in the child output arrays due to the following property OR
. In this step, whenever the opportunity arises (regardless of the reverse operator employed), all generated # values within the child output arrays will be placed in the output array of the right child node node c. For example in the case of OR
will be used and not (#,1).
Note that the reverse operators propagate all # elements from parent to child nodes. This feature is exemplified in step 1 of Fig. 3 by the propagation of the # value at locus 4 of node a.outputs to loci 4 of both node b.outputs and node c.outputs.
5.1.2 Step 2
By this step, the controller has generated four different (in general) node b.outputs arrays, one for each reverse operator. The goal for this step is to compare each of those arrays to each of the possible input argument arrays (A1, A2... etc). As an example, in step 2 of Fig. 3 the generated node b.outputs array is compared to the A2 input argument array.
Two separate counts are made, one for the number of erroneous 0 argument values E0 and one for the number of erroneous 1 argument values E1 (highlighted in blue and red respectively in Fig. 3). Two further counts are made of the number of erroneous node b loci, for 0 and 1 input arguments values, which could have been # values (and therefore not erroneous) had the controller not specified in step 1 that all # values should be placed in the node c.outputs array whenever possible. These last two statistics will be denoted by M0 and M1 for 0 and 1 input arguments values respectively. These four statistics form an error table for each reverse operator-input argument pair.
5.1.3 Step 3
In this step, the controller sorts the error tables by a number of statistics. Note that M0 and M1
are the number of remaining erroneous 0 argument values and erroneous 1 argument values respectively if all # values were moved from the
Figure 3. Diagrammatic aid for the proof-of-concept controller.
possible. To simplify matters we note that
Each error table is ranked by (in order, all increasing): Mk , Ek, Mj
, E j, and the number of # values in node c.outputs. In a greedy fashion, the very best error table (lowest ranked) will be select for the next step (in Fig. 3 the OR-A2 error table is selected). Note that the ranked list of error tables might need to be revisited later from step 5.
5.1.4 Step 4
The error table selected in step 3 effectively serves as an instruction which details how the node b.outputs and
node c.outputs arrays should be modified. The goal of the controller is to move the minimum number of # values from the node c.outputs array to the node b.outputs array such as to satisfy the error count for either 1’s or 0’s in one of the input arguments. In the example given in Fig. 3, two # values in node c.outputs are swapped with 1’s in node b.outputs.
5.1.5 Step 5
In this step, the algorithm checks that the generated
node b.outputs and node c.outputs arrays do not exactly equal either the parent node node a or the grand parent node node p (if it exists). If this check fails, the algorithm reverts back to step 3 and chooses the next best error table.
5.1.6 Step 6
The final step of the algorithm is to appropriately set the operator type of node a given the final reverse operator that was used. In this step the algorithm also checks whether either (or both) of the child nodes can represent input arguments given their generated output arrays.
The Boolean function synthesis benchmarks solved in this paper are standard benchmarks within GP research [2, 3, 4, 6]. They are namely: the comparator 6bits and 8bits (CmpXX), majority 6bits and 8bits (MajXX), multiplexer 6bits and 11bits (MuxXX), and even-parity 6bits, 8bit, 9bits, and 10bits (ParXX).
Their definitions are succinctly given in [3]:
“For an v-bit comparator Cmp v, a program is required to return true if the v/2 least significant input bits encode a number that is smaller than the number represented by the v/2 most significant bits. In case of the majority Maj v problems, true should be returned if more that half of the input variables are true. For the multiplexer Mul v, the state of the addressed input should be returned (6-bit multiplexer uses two inputs to address the remaining four inputs, 11-bit multiplexer uses
three inputs to address the remaining eight inputs). In the parity Par v problems, true should be returned only for an odd number of true inputs.”
The even-parity benchmark is often reported as the most difficult benchmark [2].
The results are given in Table 1 and show that the NNGS algorithm finds solutions quicker than all other algorithms on all benchmarks with the exception of the ILTI algorithm on the Mux11 benchmark. A significant improvement in run time was found for the Par08 benchmark.
The solution sizes produced by the NNGS algorithm are always larger than those found by the BP4A and ILTI algorithms with the exception of the Cmp06 results. The RDO scheme and ILTI algorithm both relay on traversing large tree libraries which make dealing with large bit problems very computationally intensive. As such, these methods do not scale well in comparison to the NNGS algorithm.
It is a clear that NNGS is weakest on the Mux11 benchmark. In this case a very large solution tree was found which consisted of 12,373 nodes. The multiplexer benchmark is significantly different from the other benchmarks by the fact that only four input arguments are significant to any single fitness case: the three addressing bits and the addressed bit. Perhaps this was the reason why the chosen methodology implemented in the controller resulted with poor results in this case.
There are two possible branches of future research which stem from this work, the first centres around meta-GP. As a deterministic set of rules, the proof-of-concept controller is eminently suited to be encoded and evolved as part of a metaGP system. The difficulty in this case will be in appropriately choosing the set of operators which would be made available to the population of controller programs.
The second avenue of research which stems from this work involves encoding the current proof-of-concept controller within the weights of a neural network (NN). This can be achieved through supervised learning in the first instance by producing training sets in the form of node triplets using the current controller. A training set would consist of randomly generated output arrays and the proof-of-concept controller generated child output arrays. In this way, the actual Boolean problem solutions do not need to be found before training.
As part of the task of find a better controller, the weights of the NN could be evolved using genetic algorithms (GA), similar to the method employed by [8]. The fitness of a NN weight set would correspond to the solution sizes obtained by the NNGS algorithm when employing the NN as a controller: the smaller the solutions, the better the weight set fitness. Using the proof-of-concept controller in this way would ensure
Table 1. Results for the NNGS algorithm when tested on the Boolean benchmarks, perfect solution were obtained for each run. BP4A columns are the results of the best performing algorithm from [3] (* indicates that not all runs found perfect solution). The RDOp column is taken from the best performing (in terms of fitness) scheme in [4] (note that in this case, average success rates and average run times were not given).
that the GA population would have a reasonably working individual within the initial population.
A NN may also serve as a reasonable candidate controller for extending the NNGS algorithm to continuous symbolic regression problems. In this case, the input arguments of the problem would also form part of the NN’s input pattern.
I wish to thank Marc Schoenauer for interesting discussions and excellent supervision during my masters internship at INRIA, Paris, France where this work was conducted.
[1] Koza, John R. Genetic programming: on the programming of computers by means of natural selection. Vol. 1. MIT press, 1992.
[2] Koza, John R. ”Hierarchical Automatic Function Defini-tion in Genetic Programming.” FOGA. 1992.
[3] Krawiec, Krzysztof, and Una-May O’Reilly. ”Behavioral programming: a broader and more detailed take on semantic GP.” Proceedings of the 2014 conference on Genetic and evolutionary computation. ACM, 2014.
[4] Pawlak, T., Bartosz Wieloch, and Krzysztof Krawiec. ”Semantic backpropagation for designing search operators in genetic programming.” (2014): 1-1.
[5] Krawiec, Krzysztof, and Tomasz Pawlak. ”Approximating geometric crossover by semantic backpropagation.” Proceedings of the 15th annual conference on Genetic and evolutionary computation. ACM, 2013.
[6] Ffrancon, Robyn and Marc Schoenauer. ”Memetic Semantic Genetic Programming.” In Proceedings of the 2015 conference on Genetic and evolutionary computation. ACM, 2015 (in print).