# EEG Feature Extraction Using Genetic Programming for the Classification of Mental States
## 3 Proposed Enhanced System
### Augmented Feature Extraction with Genetic Programming: \({}^{+}\)Fegp
Figure 6: Block diagram for the proposed Augmented Feature Extraction with Genetic Programming (\({}^{+}\)FEGP). 2. **New genetic operators**. Because of the manner in which individuals are represented, it is necessary to introduce new search operators. For any of these operators, the root node is avoided during the operation to preserve the representation. 1. Inter-crossover. This is a crossover performed between subtrees belonging to different individuals, which produces two offspring. The selection for the crossover points is based on a local fitness measure (discussed in detail later), which allows the best subtrees to interchange genetic material. This is visualized in Figure 8. 2. Intra-crossover. For a given individual, genetic material can be swapped within the same individual using this operator, depicted in Figure 9. The rationale behind this is that genetic material from one feature might help the evolution of another within the same individual, improving the overall fitness. The subtree selection is performed randomly, choosing the crossover points from different subtrees. This operator generates two offspring. Figure 8: \({}^{+}\)FEGP inter-crossover, swapping subtrees between different individuals. F1\({}_{i}\) is the local fitness; the crossover points are chosen from the subtrees with \(max(\mathrm{F1})\). Figure 7: \({}^{+}\)FEGP individual representation. Feature removal mutation. Similarly, a deletion operator is needed to reduce the new feature space. The subtree to be removed is selected randomly. This operator can only be used if \(r>1\). 3. **Terminal selection during population initialization. ** In a canonical GP, the initial trees are built by randomly choosing a function or terminal from the available sets in an iterative fashion. This selection process is commonly referred to as sampling with replacement, which could lead to some variables not being chosen as terminal elements in the initial population; the probability of this happening will increase when the number of input features is large. If this is the case, then the initial generations will lack proper exploration of the search space, particularly in the terminal elements, which may lead the search toward local optima. A simple mechanism to avoid this is to enforce that every variable is chosen at least one time as a terminal element in a GP individual. This can be achieved by performing a sampling without replacement of the input features in the terminal set of the GP search. When a terminal is randomly selected, then it is excluded on the subsequent terminal selection steps until all available terminals have been chosen; then, the procedure is repeated by making all terminals available to the tree generation algorithm, such as full, grow, or Ramped Half and Half. 4. **Genetic operator selection. ** In canonical GP, operators are chosen at each generation with a user-defined probability. The probability of choosing each operator is usually static throughout the search. In the work by [PERSON] and [PERSON] [60], their operator probabilities are changed at each generation by rewarding or penalizing operators according with their success at producing good offspring (offspring with high fitness). After an initial preliminary experimentation, we propose functions that modify the operator probabilities based on the work of [PERSON] and [PERSON]. Based on [60], three operator probabilities (intra-crossover: \(p_{IntrC}\), inter-individual feature crossover: \(p_{InterF}\), and subtree mutation: \(p_{M}\)) are given by a common dynamic behavior, with the following characteristics: They are periodic, the variation range is rather small, and they are stationary. For simplicity, this condition was replaced by a constant value; in early experimentation, the system behaved almost identically to the algorithm by [60]. The other three operators (inter-crossover: \(p_{InterC}\), feature insertion mutation: \(p_{K^{+}}\), and feature removal mutation: \(p_{K^{-}}\)) exhibited unique dynamic behaviors using the algorithm by [60].