Pattern Mining with Evolutionary Algorithms by Sebastián Ventura & José María Luna

Author:Sebastián Ventura & José María Luna
Language: eng
Format: epub
Publisher: Springer International Publishing, Cham

It is common in the GP literature to represent expressions in a Polish notation also known as prefix notation, so the expression for adding the numbers 3 and 8 is written as (+ 3 8) rather than (3  +  8). This notation often makes it easier to analyse the relationship between (sub)expressions and their corresponding (sub)trees. Considering the sample individual illustrated in Fig. 5.1, the prefix notation is given by the expression (min (+ (∗ 4 x) y) (∗ (∗ x x) 2)). It should be noted that the performance of the GP trees will obviously depend on the way in which GP trees are implemented. In some environments, tree-based representations may be too memory-inefficient since they require the storage and management of numerous pointers (from node to node of the tree structure). Besides, in cases where individuals are represented as prefix notations, brackets might become redundant and trees may be simpler.

Focusing on the generation of individuals, it is a stochastic procedure like in other EAs found in the literature. Many authors have considered different approaches to obtain random individuals in GP [31], and two of the first methodologies in this regard are known as full and grow methods. In both methods a maximum predefined depth is used, so no extremely large trees can be generated. The depth of a specific node within the tree is defined as the number of nodes needed to be traversed to reach it (starting from the root node, whose depth is 0). Similarly, the depth of a tree is defined as the largest depth that can be found in it by considering its leaves or terminal symbols. Considering the sample individual shown in Fig. 5.1, the depth of the tree is 3, whereas the depth of the node that represents the sum function (+) is 1.

The full method generates trees having leaves which are at the same depth. In this method, nodes are taken at random from the set of functions until the maximum tree depth is reached and, at this point, only terminal nodes can be chosen. Notice that the fact that all the leaves have the same depth does not necessarily imply that all the generated trees have the same shape. In fact, it only happens if all the functions have an equal arity, also known as the number of subtrees. Figure 5.2 illustrates the process in which a full tree of depth 2 is created. The full tree represents the function min(4 + y,  x ∗ 7), and all the functions have an arity of 2.

Fig. 5.2Example of the construction of a sample full tree having maximum depth 2

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.