# QFC: A Parallel Software Tool for Feature Construction, Based on Grammatical Evolution
## 2 Methods
### Grammatical Evolution  
Grammatical evolution is a biologically inspired procedure that can create artificial programs in any language. In grammatical evolution, the chromosomes enclose production rules from a BNF (Backus-Naur form) grammar [45]. These grammars are usually described as a set \(G=(N,T,S,P)\), where  
* \(N\) is the set of non-terminal symbols.
* \(T\) is the set of terminal symbols.
* \(S\) is a non-terminal symbol defined as the start symbol of the grammar.
* \(P\) is a set of production rules in the form \(A\to a\) or \(A\to aB,\ A,B\in N,\ a\in T\).  
In order for grammatical evolution to work, the original grammar is expanded by enumerating all production rules. For example, consider the modified grammar of Figure 2. The symbols that are in \(<\!>\) are considered as non-terminal symbols. The numbers in parentheses are the production sequence numbers for each non-terminal symbol. The constant N is the original number of features for the input data. In grammatical evolution, the chromosomes are expressed as vectors of integers. Every element of each chromosome denotes a production rule from the provided BNF grammar. The algorithm starts from the start symbol of the grammar and gradually produces some program string by replacing non-terminal symbols with the right hand of the selected production rule. The selection of the rule has two steps:  
* Take the next element from the chromosome and denote it as V.
* Select the next production rule according to the the scheme Rule = V mod R, where R is the number of production rules for the current non-terminal symbol. For example, consider the chromosome \[x=[9,8,6,4,16,10,17,23,8,14]\] and \[N=3\]. The steps of mapping this chromosome to the valid expression \[f(x)=x_{2}+\cos(x_{3})\]  are illustrated in Table 1.  
Initially, grammatical evolution was used in cases of learning functions [46; 47] and solving trigonometric identities [48], but then it was also applied in other fields such as automatic composition of music [49], construction of neural networks [50; 51], automatic constant creation [52], evolution of video games [53; 54], energy demand estimation [55], combinatorial optimization [56], cryptography [57], etc.  
A key advantage of the grammatical evolution is its easy adaptability to a wide range of problems, as long as the grammar of the problem and a fitness method are provided. No additional knowledge of the problem is required such as using derivatives. Furthermore, the method can be easily parallelized, since it is essentially a genetic algorithm of integer values. However, there are a number of disadvantages that must be taken into account when using the technique. In principle, in many cases a chromosome may not be able to produce a valid expression in the underlying grammar if its elements run out. In this case, wrapping an effect can be executed, but it is not always certain that this can again provide a valid solution. Moreover, another important issue is the initialization of the chromosomes of grammatical evolution. Usually the rules are very few in number and therefore, different numbers on the chromosomes may produce the same rules.  
In the next subsection, the steps of producing artificial features from the original ones are provided and discussed.  
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) <list>::=x1 (0) | x2 (1) |................ | xN (N) <digitlist>::=<digit> (0) | <digit><digit> (1) | <digit><digit><digit> (2) <digit> ::= 0 (0) | 1 (1) | 2 (2) | 3 (3) | 4 (4) | 5 (5) | 6 (6) | 7 (7) | 8 (8) | 9 (9)