# Constructing Features Using a Hybrid Genetic Algorithm
## 2 Method Description
### The Usage of Grammatical Evolution  
Grammatical evolution is an evolutionary procedure whereby the chromosomes represent production rules from a BNF (Backus-Naur form) grammar [58], which is very often used to describe the syntax of programming languages, document formats, etc. These grammars are defined as the set \(G=(N,T,S,P)\) where:  
* \(N\) is the set of non-terminal symbols, which produce a series of terminal symbols through production rules.
* \(T\) is the set of terminal symbols.
* \(S\) is a non-terminal symbol which is also called the start symbol.
* \(P\) is a set of production rules in the form \(A\to a\) or \(A\to aB,\ A,B\in N,\ a\in T\).  
The production procedure starts from the start symbol of the BNF grammar and iteratively produces programs by replacing non-terminal symbols with the right hand of the production rules that will be selected according to the value of each element in the chromosome. In the proposed method, the BNF grammar of Figure 1 was used to create a new feature from the initial features. The symbols that are in \(<>\) are considered non-terminal symbols. The parameter N denotes the number of original features. Typically, a chromosome \(x\) in grammatical evolution is expressed as a series of binary values 0 or 1. In the current work, in order to simplify the mapping procedure and to increase the speed of the algorithm, every element of each chromosome is considered an integer in a predefined range. In our case, the range \([0,255]\) was used but of course, this could be easily changed.  
Take, for example, the chromosome \(x=[9,8,6,4,16,10,17,23,8,14]\) and \(N=3\). The valid expression \(f(x)=x_{2}+\cos(x_{3})\) is created using a series of production steps shown in Table 1. An expression is considered valid if it only contains terminal symbols. Each number in the parentheses stands for the sequence number of the production rule. Hence, the process to produce \(N_{f}\) features from the original is as follows:  
1. Every chromosome \(Z\) is split into \(N_{f}\) parts. Each part \(g_{i}\) will be used to construct a feature.
2. For every part \(g_{i}\) construct a feature \(t_{i}\) using the grammar given in Figure 1.
3. Create a mapping function: \[G(\overrightarrow{x},Z)=\left(t_{1}(\overrightarrow{x},Z),t_{2}( \overrightarrow{x},Z),\ldots,t_{N_{f}}(\overrightarrow{x},Z)\right)\] (6) where \(\overrightarrow{x}\) is a pattern from the original set and \(Z\) is the chromosome.  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**String** & **Chromosome** & **Operation** \\ \hline \(<\)expr\(>\) & 9,8,6,4,16,10,17,23,8,14 & 9 \(\mod\)\(3=0\) \\ \hline (\(<\)expr\(>\)\(<\)op\(>\)\(<\)expr\(>\)) & 8,6,4,16,10,17,23,8,14 & 8 \(\mod\)\(3=2\) \\ \hline (\(<\)terminal\(>\)\(<\)op\(>\)\(<\)expr\(>\)) & 6,4,16,10,17,23,8,14 & 6 \(\mod\)\(2=0\) \\ \hline (\(<\)xlist\(>\)\(<\)op\(>\)\(<\)expr\(>\)) & 4,16,10,17,23,8,14 & 4 \(\mod\)\(3=1\) \\ \hline (\(\chi\)2\(<\)op\(>\)\(<\)expr\(>\)) & 16,10,17,23,8,14 & 16 \(\mod\)\(4=0\) \\ \hline (\(\chi\)2 \(+\)\(<\)expr\(>\)) & 10,17,23,8,14 & 10 \(\mod\)\(3=1\) \\ \hline (\(\chi\)2 \(+\)\(<\)func\(>\)(\(<\)expr\(>\))) & 17,23,8,14 & 17 \(\mod\)\(4=1\) \\ \hline (\(\chi\)2 \(+\)\(<\)(\(<\)expr\(>\))) & 23,8,14 & 23 \(\mod\)\(2=1\) \\ \hline (\(\chi\)2 \(+\)\(<\)(terminal\(>\))) & 8,14 & 8 \(\mod\)\(2=0\) \\ \hline (\(\chi\)2 \(+\)\(<\)xlist\(>\))) & 14 & 14 \(\mod\)\(3=2\) \\ \hline (\(\chi\)2 \(+\)\(\cos(\chi\)3)) & & \\ \hline \hline \end{tabular}
\end{table}
Table 1: Steps to produce a valid expression from the BNF grammar.  
S::=expr> (0) <expr> ::= (<expr> <op> <expr>) (0) | <func> ( <expr> ) (1) | <terminal> (2) <op> ::= + (0) | - (1) | * (2) | / (3) <func> ::= sin (0) | cos (1) |exp (2) |log (3) <terminal>::=<list> (0) |<digitlist>.<digitlist> (1) <xlist>::=x1 (0) | x2 (1)........ | xN (N) <digitlist>::=<digit> (0) | <digit><digit> (1) | <digit><digit> (2) <digit> ::= 0 (0) | 1 (1) | 2 (2) | 3 (3) | 4 (4) | 5 (5) | 6 (6) | 7 (7) | 8 (8) | 9 (9)