# Local Crossover: A New Genetic Operator for Grammatical Evolution
## 2 Materials and Methods  
### Basics of the Grammatical Evolution Method  
Grammatical Evolution considers chromosomes as a set of production rules in the provided BNF grammar. BNF grammar is usually denoted as a set \(G=(N,T,S,P)\) with the following assumptions:  
* \(N\) defines the set of non-terminal symbols.
* \(T\) is a set that contains the terminal symbols.
* \(S\) is a non-terminal symbol that corresponds to the start symbol of the grammar.
* \(P\) is the set of the rules used during production. These rules are in the form \(A\to a\) or \(A\to aB,\ A,B\in N,\ a\in T\). In the Grammatical Evolution procedure, a sequence number is assigned to every production rule.  
The grammar used for the rule machine learning method is outlined in Figure 1 and the corresponding grammar for the neural network construction technique is displayed in Figure 2.  
<S>::= <ifexpr> value=expr> else value=<expr> (0) <ifexpr>::= if(<bexpr>) value=<expr> (0) |<ifexpr> else if(<bexpr>) value=<expr> (1) <bexpr>::=expr> <rop> <expr> (0) |<bexpr> <bop> <bexpr> (1) <rop>::= > (0) |>= (1) |< (2) |<= (3) |= (4) |!= (5) <bop>::= & (0) | | (1) <expr> ::= (<expr> <op> <expr>) (0) | <func> (<expr> ) (1) |<term> (2) <op> ::= + (0) | - (1) | * (2) | / (3) <func> ::= sin (0) | cos (1) |exp (2) |log (3) <term>::=<xlist> (0) |<dlist>.<dlist> (1) <xlist>::=x1 (0) | x2 (1)........ | xD (D-1) <dlist>::=<digit> (0) | <digit><dlist> (1) <digit> ::= 0 (0)| 1 (1) | 2 (2)| 3 (3) | 4 (4)| 5 (5) | 6 (6)| 7 (7) | 8 (8)| 9 (9)  
Figure 1: The BNF grammar used in the method that constructs rules using the Grammatical Evolution procedure.  
The notation \(<\) > is used to enclose non-terminal symbols. The numbers at the end of the production rules represent the sequence number of each rule. The parameter \(d\) is the dimension of the used dataset (number of features). Grammatical Evolution produces valid expressions by starting from the starting symbol \(S\) and by following the production rules. The method selects the following production rules according to the following scheme:  
* The next element denoted as \(V\) from the chromosome to be processed is retrieved.
* The next production rule is selected according to the formula. \[\text{Rule}=V\text{ mod NR}\] (1) where the value NR represents the total number of production rules for the under processing non-terminal symbol.  
For a dataset with three features \((x_{1},x_{2},x_{3})\), the following possible expression could be created for the case of the rule method:  
\[\text{if}(x_{1}>2+\sin(x_{3}))\text{value}=1+\cos(x_{2})\text{ else value}=1+x_{1}\]  
The terminal symbol value is used to denote the final outcome of the rule method. For the same case, the following constructed neural network could be created:  
\[\text{NNC}(x)=2.45\text{sig}(1.9x_{1}+3.11x_{3}+2.5)+5.9\text{sig}(10.8x_{2}+6.25)\]  
This grammar of Figure 2 is able to produce artificial neural networks using this form:  
\[N\big{(}\overrightarrow{x},\overrightarrow{p}\big{)}=\sum_{i=1}^{H}p_{(n+2) i-(n+1)}\sigma\Bigg{(}\sum_{j=1}^{n}x_{j}p_{(n+2)i-(n+1)+j}+p_{(n+2)i}\Bigg{)} \tag{2}\]  
The vector \(\overrightarrow{x}\) indicates the input vector and the vector \(\overrightarrow{p}\) stands for the parameter set of the neural network. The integer constant \(H\) denotes the number of weights or processing units. These networks have one processing level, but the grammar could be easily extended to produce neural networks of additional levels. The function \(\text{sig}(x)\) used in the previous example denotes the sigmoid function given by  
\[\text{sig}(x)=\frac{1}{1+\exp(-x)} \tag{3}\]  
Figure 2: The BNG grammar for the procedure of creating artificial neural networks with Grammatical Evolution.  
used in the majority of cases of neural networks. Of course, the Grammatical Evolution procedure can construct neural networks with different activation functions or neural networks that use a mix of activation functions.