Brain Computer Interface using Genetic Algorithm with modified Genome and Phenotype Structures

Introduction

The human brain is the most evolved organ of most intelligent and evolved species (human) on earth. The brain is the origin of attention, actions, memory, cognition, perception, emotions, beliefs, telepathy and intuitions in the human body. The fact that the brain utilizes electrical signals for its functioning, was discovered by R. Canton (Caton, 1875) in 1875. Thereafter, Hans Berger (Berger, 1929), for the first time, measured the electrical activity of the human brain and named it as Electroencephalogram (EEG).

The present research work reports new applications of intelligent techniques for signal processing of EEG signals from human subjects. Corresponding to every thought, intention or action, there is a place in the brain where electrical activity along with chemical reactions happens and the action is initiated by communication through neurons.   The electrical activity of neurons in the human brain can be monitored by available modern techniques such as Magnetic Resonance Imaging (MRI), Electroencephalograms (EEG), Positron Emission Tomography (PET), functional Magnetic Resonance Imaging (fMRI), Electrocorticography (ECoG), etc. EEG being a versatile measurement of neural electrical activity in the human brain, so it can be used to study complex dynamics of the brain, paving the way to a diagnosis of various brain disorders and brain-machine interface applications.

The technological means devised for communication between the brain and a computing device is named as Brain-Computer Interface (BCI). The research on BCI began as early as in the 1970s (Vidal, 1973, 1977), but due to lack of fast computing machines, research in this area didn't progress for a long time. During the 1990s (Pfurtscheller & Lopes, 1999), research in this area picked some momentum and with the turning of the millennium, the transistor density in microprocessors increasing with Moore's Law gave fervent speed to computing machines and thereby fueled the research in BCIs. In BCI, the brain signals corresponding to certain activity are accessed through some technological means like EEG and manipulated and decoded by computational methods which can give the command to some actuator, so that the action in the thought of the subject can be translated into mechanical action by the use of machines having intelligence. These interfacing systems can be extremely helpful to the patients severally impaired due to some accident or neuro-motor diseases, whose sensory-motor system is not working and who are not able to perform normal motor actions initiated in their brains. The present paper proposes an optimal feature and channel selection scheme for motor imagery classification corresponding to limb movements in the human body. A synergetic approach employing Support Vector Machine (SVM), Wavelet Packet Transform (WPT), and Genetic Algorithms (GAs) are employed for the optimization problem addressed in this paper.  In the proposed scheme, the wavelet packet transform is used for the selection of sensory-motor frequency band and feature extraction. The number of channels and features are selected simultaneously by GA. SVM acts as part of the objective function for GA. The dataset-1 of BCI competition-IV (Publicly available), is utilized for the present research work. This paper presents a unique feature extraction mechanism using wavelet packet transform and approximate entropy. The EEG signals are decomposed at the 8th level using WPD, the coefficients are extracted and approximate entropy is computed at selected nodes of the 8th level decomposition to give feature vector. The nodes are selected corresponding to the sensory-motor frequency band. This feature extraction is carried out for all electrodes (channels). The simultaneous selection of relevant channels along with the relevant feature from the selected channels is carried out by using Genetic Algorithms. The three-dimensional structure of the population of GA is the first time proposed in the present paper. The cross-over operator is also modified for the kind of population under consideration. The results obtained Motor imagery classification outperform the previously reported results in the literature (Park et al., 2013).

Literature Review 

The genesis of BCI lies in the roots of the discovery of electrical currents in the brain (Caton, 1875) and measurements of these currents (Berger, 1929) in human subjects. The groundbreaking research work of Wilder Graves Penfield (Eccles & Feindel, 1978) for the discovery of the motor cortex was a seed for modern BCI systems. Vidal J.J in 1973, coined the term "Brain-Computer Interface" (Vidal, 1973), and further proposed classification of evoked responses/ event-related potentials in human EEG (Vidal, 1977). The publication by Vidal (Vidal, 1977) is the known first peer-reviewed publication in the field of BCI. Vidal is known as the inventor of BCI.  For a long time, due to the unavailability of fast computing processors, the research in BCI did not have any progress. With the turning of millennium and increasing speeds of computers, the research in BCI saw a spur in reporting of publications.

The Event-Related Potential (ERP) being phase-locked and Event-Related Synchronization (ERS)/Desynchronization (ERD) being non- phase-locked, are different responses of the human nervous system. The results of time and space quantification of ERD/ERS, for several movement experiments, is presented in (Pfurtscheller & Lopes, 1999).

 Fast and reliable classification of EEG patterns is necessary for the development of BCI systems. The hand movement imagination in EEG recordings is prevalent from contra- & ipsilateral central areas of the brain. The estimation of spatial filters by common spatial pattern along with weighted importance of electrodes for classification used as special feature resulted in classification accuracies for hand movement imagery for three subjects as 90.8%, 92.7%, and 99.7% (Ramoser et al., 2000).

The EEG in primary sensorimotor areas is affected by motor imagery in a similar way as in the real movement of the concerned organ of the body. The band power or adaptive autoregressive parameters extracted used as features and input to a linear discrimination analysis and neural networks-based classification system resulted in effective control of a hand prosthesis by a tetraplegic patient (Pfurtscheller & Neuper, 2001). An exhaustive review of BCI and motor imagery classification is presented in (Wolpaw et al., 2002).  Different functional states of the brain are depicted in terms of short-term spectral transformations structure of EEG in (Fingelkurts et al., 2003). The training of a subject for reliably and voluntarily producing changes in his/her EEG as per different motor imagery tasks is a critical issue for the success of BCI systems (Curran & Stokes, 2003). 

The past few decades have seen an upsurge in developing new techniques for man-to-machine communication. The EEG or ECoG signals recorded from the subject and fed to an intelligent system can prove to be an effective orthosis or word processing software of some effective mechanism for patients suffering from Locked-in Syndrome (LIS). Six datasets including training (labeled) and test (unlabeled) sets in the documented format are provided by Four laboratories engaged in EEG-based BCI across the globe (Blankertz et al., 2004).

An algorithm using Fisher discriminate analysis and Common spatial subspace decomposition with features obtained from Bereitschafts potential and event-related desynchronization gave 84% classification accuracy using the "BCI Competition 2003" test set (Y. Wang et al., 2004). 

BBCI - the Berlin Brain-Computer Interface presented by Blankertz Benjamin et al. (Blankertz et al., 2006), deals with the translation of brain signals from movements/ intentions into control commands by using an advanced machine learning algorithm. This technique is different from the conventional techniques in terms of training time, which extends up to 50-100 hrs., for conventional techniques. The subject training requirement for BBCI is minimal. The new Hex-o-Spell text entry system speeds communication up to 6–8 letters per minute, is presented in (Blankertz et al., 2006). The computational challenges for non-invasive brain-computer interfaces are addressed in (Popescu et al., 2008). A review of signal preprocessing and classification for mental state monitoring and EEG-based BCI applications has been presented (Klaus-Robert Muller, Tangermann et al., 2008).

The spatial filter optimized using Common Spatial Pattern (CSP) algorithm for EEG/ MEG (Magnetoencephalogram) BCI is reported in (Moritz & Buss, 2008), which faces two shortcomings, the first in terms of classification error and second in terms of CSP being extended to multiclass classification with heuristics. The Information-Theoretic Feature Extraction (ITFE) along with Joint Approximate Diagonalization (JAD) was proposed to address these issues (Moritz & Buss, 2008).   The mean classification accuracy is increased by 23.4% with a new scheme tested with dataset IIIa of BCI competition III. Subject-specific feature extraction and Motor Imagery classification technique based upon subject-specific discriminative Filter Bank with common spatial pattern algorithm reported (Thomas et al., 2009) to reduce error rates by 8.9% and 17.42% for dataset IIb of BCI competition IV and dataset IVa of BCI competition III respectively.

In (Naeem et al., 2009), the preprocessing with PCA has not been found suitable in a small set of components for retaining motor imagery information. The 6 ICA components selected by visual inspection resulted in a 61.9% classification rate while the full range of 22 components has resulted in 63.9%. A variance criterion for automatic selection of ICA components has selected 8 components and has given a 63.1% classification rate. Selection of electrodes from mid-central and centroparietal regions of the brain and, by using CSPs and infomax also has resulted in good classification accuracy for motor imagery detection.  

A Motor Imagery training system for neurofeedback-based BCI is proposed in (Hwang et al., 2009). The real-time brain activation maps on the cortex are shown to subjects in this system. A total of ten healthy subjects, out of whom five are trained for the system while the other five are not trained, have taken part in the experiment. The trained group of participants has successfully performed the motor imagery task and activated their motor cortex without moving their limbs. This system is demonstrated as an effective training tool for motor imagery tasks in BCI.

In (Shahid et al., 2010), the authors propose a scheme for the extraction of nonlinear features, which uses higher-order statistics. This technique, the bispectrum reports the performance of the system in terms of mutual information, classification accuracy, and Cohen's kappa depicting to give better power spectrum based BCI.

Kaushik Majumdar et al. (Majumdar, 2011) present a survey on soft computing techniques for pattern data mining /recognition from EEG signals. The computational intelligence techniques such as neural statistical discrimination, networks, evolutionary computation, fuzzy logic, and Bayesian inference, have been used for pattern recognition from EEG recorded from human subjects. The dimensionality of EEG data has increased due to the availability of high-density EEG recording systems at an affordable cost. Soft computing techniques are gaining attention for the processing of high-dimensional data. The survey concluded that the Bayesian approaches and the Artificial Neural Network (ANN) based approaches emerged as more advantageous over other soft computing techniques for MI-based BCI.  The Ref. (Wei & Wang, 2011) a scheme based upon Binary Multi-Objective Particle Swarm Optimization (BMOPSO) is proposed to address the channel selection and classification problem for motor imagery tasks for a BCI.

The selection of channels in BCI using EEG is necessary because it removes irrelevant and noisy channels and thereby improves the system performance and increases user convenience by the use of a lesser number of channels. A scheme using Sparse Common Spatial Pattern (SCSP) algorithm for channel selection from human EEG for BCI is presented in (Arvaneh et al., 2011). This algorithm has been proposed as an optimization problem, to remove irrelevant and noisy channels,  the number of channels minimized while classification accuracy improved. The classification accuracy improved by 10% with an optimized number of channels, over the case when three electrodes, Cz, C3 and C4 were used.  datasets IVa of BCI competition III and IIa of BCI competition IV were used for the experiments.

In Ref. (Tam et al., 2011), a BCI system based upon Support Vector Machine Recursive Feature Elimination (SVM-RFE) and Fisher’s criterion is developed to find a minimal number of electrodes for chronic stroke patients, to operate an assistive device with more than 90% accuracy.

The authors of (J. Yang et al., 2012) demonstrate the effectiveness of their proposed scheme based upon the Genetic Neural Mathematics Method (GNMM) to perform effective channel selections/reductions, thereby reducing the difficulty of data collection and improving the discriminatory power of classifier. Two datasets have been used in this work, the first is ECoG data from BCI competition III while the second a recording of 960 trials with 32-channel, 256 Hz EEG where participants asked to execute a left or right-hand button-press in response to stimuli pointing left or right arrow. Out of 32, Six channels selected, and the response correctness classification accuracy achieved is 86% and 82% for the actual hand response classification.

The scheme proposed in (Y. Yang et al., 2012) uses Time-frequency Discrimination Factor (TFDF) to extract discriminative ERD features for BCI data classification.  This approach gives better classification results (mean kappa coefficient = 0.62), with only two bipolar channels. Andrew Jackson, et al. (Jackson & Zimmerman, 2012), presented a review and summarized the therapeutic effects that may be achieved by closing the loop between the nervous system and electronic devices.

A scheme, to classify different Motor Imagery (MI) patterns using coefficients of Joint Regression (JR) model and spectral powers at two specific frequencies is presented in  (Hu et al., 2012), achieved classification accuracies of  90% and 80% on training and test data respectively for data of one subject from BCI 2003 Data set III. Wang Deng et al. (D. Wang et al., 2012), also use dataset 2a of BCI competition IV, presented, the overall four-class kappa values between 0.41 and 0.80.

The Multivariate Extensions of Empirical Mode Decomposition (MEMD) presented in (Park et al., 2013). The direct processing via enhances the localization of the frequency information in multichannel EEG is carried out by MEMD, while Noise-Assisted-MEMD gives a highly localized time-frequency representation. The BCI Competition IV Dataset I is used for experiments and it is reported that the average classification accuracy found to be 75.5% and the best classification accuracy is 91.9 % ± 3.0, for subject ‘g’. The electrode selection is the main drawback of this work. A total of 11 electrodes from the sensorimotor region are selected for each subject. An adaptive scheme for the selection of electrodes for individual subjects is required for further improvement of classification accuracy and to make the BCI user-friendly.

The intersession non-stationarity is addressed by EEG data space adaptation (EEG-DSA) in (Arvaneh, 2013). The supervised version, and the unsupervised version of EEG-DSA using the Kullback-Leibler (KL) divergence criterion. The scheme is evaluated on BCI Competition IV data set IIa and another data set recorded from 16 subjects performing motor imagery tasks on different days. The reference (Shenoy, 2014), also uses dataset 2a of ‘BCI Competition IV’ and ‘BCI Competition III dataset Iva’, and reports the highest classification accuracy 95.18% for subject ‘ay’. This technique (Shenoy, 2014) employed a channel selection mechanism based upon priori information of the MI task and iteratively optimized the number of relevant channels to improve the classification accuracy.

In the techniques reported in (Shenoy, 2014), the channel selection scheme is not adaptive, so the computational intelligence-based techniques can prove to be effective for improving channel selection optimization. 

The inconsistencies from multiple classifiers are used to select the relevant EEG electrodes for the M.I. tasks in (H. Yang et al., 2014). The noisy channels fluctuate the classification accuracies make the basis for channel selection and the identified noisy channels are removed by this technique. A random forest (RF) classifier with feature extraction by Filter bank common spatial pattern (FBCSP) is used for classification of M.I. task from EEG in (Bentlemsan et al., 2014). The system performance is evaluated on ‘Dataset 2b’ of the ‘BCI Competition IV’.

       The authors of (Tomida & Tanaka, 2015) present a sparsity-aware data selection method from multiple trials of EEG recordings. A weighted averaging with weight coefficients for rejecting the trials is introduced. The ℓ1-minimization is used to find the weight coefficients, leading to sparse weights such that low-quality trials are allotted nearly zero-values. This method is used to estimate covariance matrices for CSP.

The long-term training effects across 10 sessions using a 2-class MI-tasks in fifteen subjects are investigated using EEG and functional near-infrared spectroscopy (fNIRS) in (Kaiser et al., 2014).

In Ref. (Baali et al., 2015), linear prediction singular value decomposition (LP-SVD) is proposed for feature extraction and resulting average accuracy as 81.38%, when tested on ‘BCI competition’ ‘IIIa data set’. In (Soman & Jayadeva, 2015), a mechanism for M.I. classification proposed which uses the combination of ‘classifiability’ for selecting the optimal frequency band and Twin Support Vector Machine (TWSVM) as a classifier, The scheme evaluated on 'dataset 2b’ of ‘BCI competition III’. The use of 'classifiability' as a mechanism for optimal selection of features is the major drawback of this approach (Soman & Jayadeva, 2015) and can be replaced with an evolutionary approach for improving the classification accuracy and long-term online training. 

In Ref. (Meng et al., 2015), a scheme has been presented for spatial-spectral features extraction from EEG using an objective function based on Bayes classification error and the mutual information between spatial-spectral MMISS features and class labels. The maximum classification accuracy 97.9% for subject ‘al’ from ‘dataset IVa’ of ‘BCI competition III’ is reported. Experiments on monkeys presented in  (Kao et al., 2015), describes the evolution of dynamics of the neural population through time.

Recent approaches towards the classification of events from EEG signatures include ‘Robust Support Matrix Machine(RSMM)’, for data of a single trial EEG (Zheng et al., 2018), covert verb reading in motor imagery paradigm (Zhang et al., 2018), hybrid BCI combining M.I and P300 potentials for driving wheelchair (Yu et al., 2017), bilinear regularized locality preserving (BRLP) and extreme learning machine based BCI (Xie et al., 2018), Kullback-Leibler divergence based feature selection (J. Wang et al., 2018), ‘common spatial pattern’ algorithm-based feature extraction and a fusion of ‘fuzzy’ ‘standard additive model’ with ‘particle swarm optimization’ (Nguyen et al., 2018), Spiking Neural Models (Salazar-Varas & Vazquez, 2018), convolutional neural network (CNN) architecture for M.I. classification (Sakhavi et al., 2018), android feedback-based BCI training system (Penaloza et al., 2018), ‘feature weighting and regularization’ (FWR) method using all ‘Common Spatial Pattern’ features to minimize information loss (Mishuhina & Jiang, 2018), and Dealing uncertainty in motor imagery classification with ‘type-2 fuzzy logic system’ (Herman et al., 2017). The study and analysis of these recent approaches paved the way for the present proposed approach for motor imagery classification with optimal channel selection.

Methodology

This section proposes a novel motor imagery classification and channel selection scheme. This scheme is based upon ‘wavelet packet decomposition’, ‘approximate entropy’, ‘support vector machine’ and ‘Genetic Algorithms’. This section describes the implementation details of different tools and technologies used. The scheme starts with the selection of data, processing of this data with wavelet packet decomposition for selection of sensory-motor frequency bands and giving wavelet coefficients for feature computation followed by channel and feature selection by GA with SVM acting as the objective function.

Data Selection

The ‘data set I’ of ‘BCI Competition IV’ (Blankertz et al., 2007) is taken for training and testing of the proposed scheme. The data corresponds to EEG signals measured from 59 EEG electrode positions. Out of these 59 electrodes, some of the electrodes carry data that are more correlated to the intended motor imagery. Each subject chose 2 motor imagery tasks amongst the following three (movement of):  right hand, left hand, and foot (both feet). The subjects performed a total of 200 trials and in each trial; the subject imagined one of the two possible tasks for 4 seconds. It is specified that the subject 'a' chose left hand and foot, subject 'b' chose left hand and foot (both feet) and right hand, subject 'f' chose left hand and subject 'g' chose left and right hands (Park et al., 2013).

Table 1. The sizes of datasets for different subjects for Dataset 1 of BCI Competition IV

The 100 Hz down-sampled data is taken for the present work. The data is provided for all the subjects (BCI Competition IV, 2008). The sizes of data for different subjects are shown in Table1. The mark information (in the folder 'mrk' in data provided in .mat format) is provided for the starting point of each trial in a data set, which is used to prepare data segments for all the trials. The 200 segments for each subject are extracted as the data is provided for 200 trials with mark information.

Wavelet Packet Decomposition Sensorimotor Frequency Band Selection and Feature Extraction

The wavelet packet decomposition at the 8th level is used to decompose each EEG segment (data corresponding to each trial) for the subjects under consideration. After decomposition, 256 coefficients are obtained. The wavelet spectrum (via wpspectrum command in Matlab) is used to find the wavelet coefficients corresponding to the sensorimotor frequency band (i.e., 8-32Hz). A total of 124 coefficients (out of a total of 256 coefficients) corresponding to this frequency band are selected for each EEG segment.

For one subject, a total of 200 trials resulted in 124×59×200 number of coefficients for further feature extraction. Approximate entropy (Pincus et al., 1991) is computed for each WPD coefficient at each selected node (total 124 nodes selected in the desired spectrum) for all the 59 channels, to compute the feature vector. This feature vector forms the search space for GA to search the optimal channels and relevant features for optimizing the classification accuracy among two motor imagery tasks. 

The Genetic Representation

A binary-coded GA is employed for the proposed application. We conjectured and devised a novel 3-dimensional genetic representation of the population employed for the G.A. In this representation, instead of a single string, a chromosome is represented by a two-dimensional structure with each column of chromosome representing the feature vector (total 124 features) for a particular channel (total 59 channels corresponding to each column).

Fig. 1 (a) and (b) represent the two-dimensional chromosome structures. In Fig 1 (a), the allele value represents the feature number n belonging to channel number m. Fig.1 (b) represents the binary allele values randomly initiated by a coin flip (a subroutine is coded in Matlab for coin flip). A chromosome comprises 59 × 124 matrix of binary alleles (either a 0 or 1) as shown in Fig.1 (b).

The complete population is a three-dimensional structure containing binary allele values in each chromosome, as shown in Fig. 2. In the three-dimensional population, the allele  belongs to chromosome ‘r’ with ‘n’ and ‘m’ as explained above.  The first row of each chromosome is used to present the selection or rejection of the particular channel. In the front page (i.e. 59×10 matrix), the presence of '1' implies the corresponding channel is selected while the presence of '0' corresponds to rejection of the corresponding channel. In the same way, the presence of '1' corresponds to selection and '0' corresponds to rejection of the corresponding feature in subsequent pages. The selected features of only the selected channels will participate in the classification process during computation of the classification rate to serve as fitness value for the corresponding chromosome.

The rationale for the 2-d representation of chromosome: The advantage that accrues from 2- dimensional representation of a chromosome is that not only the features are optimally selected but also the relevant electrodes are simultaneously selected optimally by the GA.

Fig 1. Structure of two dimensional       Fig 2. Three dimensional structure of population

Chromosome

The Genetic Operators

The canonical GA contains selection, cross-over and mutation operators. In the proposed scheme, the initial three-dimensional binary population is generated randomly, i.e., with coin flip subroutine. The Roulette Wheel Selection is used as the selection mechanism. A novel modified cross-over is implemented for the three-dimensional representation of the binary population, which is explained in this section. The mutation is a simple random (but dictated by the probability of mutation) bit flip for binary representation of allele values. The description of initialization of the GA population and different operators is explained below:

Initialization of Population

A binary population is initialized using coin flip subroutine; the outcome of head corresponds to '1' and tail to '0'. The size of the population is 59×10×124 (59 rows, 10 columns and 124 pages) as shown in Fig. 2 depicts the representation of the population. The population size '10' is selected on the rationale that according to the theory of large numbers; '10' is considered the smallest large number.

Computing Fitness

SVM is employed for computation of classification rate corresponding to each chromosome, which forms a part of fitness value. In the front page of population, the channel (electrode) positions corresponding to '1' are selected and further the features corresponding to '1'

(out of total 124 features per electrode) in all the pages corresponding to the selected channel are taken for the computation of classification rate. One row with corresponding pages in the 'r’ dimension forms a chromosome (size 59×124,  with n=1 to 59, m= 1 to 124 and r=1 forms the first chromosome of the population). The fitness is computed for all chromosomes (10) in the population. A feature vector is formed by fetching all the selected feature values for 200 trials for a subject and these features are presented for training and testing of the SVM gives part of fitness values, using ten-fold cross-validation. Fitness is computed for all the chromosomes (10) in the population. The fitness value of the chromosome is given by:           

              (6.1)

Where, FV = Fitness Value, C = Classification accuracy (computed by SVM),

 E   = Number of electrodes (Channels), F = Number of Features

w1 and w2 = weighting factors

The typical values for w1= 0.002 and w2=0.001 are taken in the present application.

The rationale for the choice of fitness function: All the channels for which EEG data is recorded are not relevant (even some of them are quite far away from the neural activation region corresponding to the motor imagery activity under consideration). So, the selection of relevant channels is an important aspect of designing an effective MI classification system. The number of channels is to be reduced and only the relevant channels to be selected, so, the number of channels with a weighting factor is subtracted. Also, all the features corresponding to a selected channel are not relevant for classification, so to minimize the number of features the corresponding number with a weighting factor is deduced from fitness value. The values of the weighting factor are chosen primarily to make their values below 1 (because the max value for classification rate is 1 here (i.e., 100%)) and secondly to give more weight to classification rate the values are tuned. Further, the tuning of weighting factors is another open area of research we recommend.

Selection

Roulette Wheel Selection (RWS) is employed in the present implementation.

Cross-Over

The novel modified cross-over scheme implemented is shown in Fig.3 and Fig.4. The value of the probability of cross-over is chosen as 0.8 in conformity with that made use of by most researchers (Srinivas & Patnaik, 1994). The cross-over site is also selected by a random process which gives a number that decides the cross-over site. One point cross over is performed two times on pair of parents in a single iteration on two-dimensional chromosomes as shown in Fig.3.  The selected chromosome pairs (parents) first undergo one point cross-over on the front page. The part of the chromosome to be exchanged is copied as a whole and not the first page only. For example, if the cross-over site is 3, then the two chosen chromosomes are dissected after 3rd allele, thus the dissected parts dimensions (1×3×124) and (1×56×124). Then, the first part (size 1×3×124) of the first chromosome is concatenated with the second part (size 1×56×124) of the second chromosome to form the child chromosome of size (1×59×124). The remaining parts of the two chromosomes are similarly concatenated to form the second child chromosome. So, it can be stated that the first one-point cross-over is carried out along the second dimension of the population throughout the population. Once this process is over, the cross over along y dimension is carried out. The cross-over is carried out in such a way that the strings exchanging the genetic material belong to the same electrodes. The size of each of the chromosomes participating is 1×59×124 each. The process is explained by taking an example of two chromosomes probabilistically (probability of cross over allowed for cross-over) selected for cross-over. The random cross-over site chosen is, say 35, thus the two parts of each of the chromosome have sizes (1×59×35) and (1×59×89) respectively. The first part having a size (1×59×35) of chromosome 1 is concatenated with the second part of the chromosome 2 to form child 1 (size1×59×124) chromosome and the remaining parts of the parent chromosomes are similarly concatenated to form the child 2 (size 1×59×124). Fig 4 depicts the process of two-dimensional cross-over on a smaller sized two-dimensional chromosome.

Mutation

The value of the probability of mutation  is chosen 0.003 in conformity with value prevalent in most research papers on GA applications. The algorithm for mutation is applied to all the allele positions in the population and where ever mutation is allowed probabilistically by the probability of mutation, the corresponding bit is flipped from ‘1’ to ‘0’ and vice-versa.

Fig. 3: Cross-over on pair of two-                           Fig. 4 The modified cross-over for 2- dimensional chromosomes                                             dimensional chromosomes (m×n)

Stopping Criterion

The stagnation of average fitness is taken as the stopping criterion. The variation in average fitness is monitored and if it is below 0.5% for successive 5 runs, then the GA is stopping from further evolution.

Proposed Genetic Algorithms Based Motor Imagery Classification and Channel Minimization Scheme

The proposed scheme is implemented in Matlab and trained and tested using data of different subjects from dataset 1 of BCI competition IV. The scheme started with extracting EEG segments for all trials (200 trials per subject available) for different subjects. The features are extracted as explained in section III.

For the proposed GA based scheme (WP-GA-SVM), a total of 59×124=7316 number of features are extracted for all channels and all WPD coefficients. This feature space forms the search space for GA. The GA is coded as explained in the implementation details in the previous section. The scheme is trained and tested for four subjects 'a', 'b', 'f' and 'g'. The schemes using dataset 1 of BCI competition IV presented in the literature (Park et al., 2013) (Tomida & Tanaka, 2015) have also presented results for subjects 'a', 'b', 'f' and 'g'. The flow chart for the proposed GA based scheme is depicted in Fig.5 and explained as the algorithm given below.

Fig. 5. Proposed GA based scheme for channel selection and motor imagery classification

Algorithm:

1. Read data for subjects ‘a’, ‘b’, ‘f’ and ‘g’.
2. Extract EEG segments (one segment for one trial) for all electrodes (for all subjects) according to mark information available in the description of the dataset.
3. Perform wavelet packet decomposition on every EEG segment.
4. Select wavelet packet coefficients corresponding to the sensorimotor frequency band, i.e., 8-32 Hz (total of 124 coefficients selected).
5. Compute approximate entropy for each WPD coefficient (compute feature vector for all 200 trials for all the subjects).
6. Initialize binary population for GA (matrix of size 59×10×124).
7. Compute the classification rate for each chromosome by training and testing with the feature vector for all trials available and then compute fitness for each chromosome of the population (using Objective).
8. Perform the Roulette Wheel Selection.
9. Perform cross-over
10. Perform mutation.
11. Compute fitness (as in step 7)
12. Check the stopping criterion (stagnation in the improvement of average fitness: the variation in fitness have less than 0.5 % of average fitness in successive 5 iterations)

If stopping criterion met then stop iterations, else go to step 8.

Results

Results of classification and optimization of the number of channels are presented in this section.  The data for all subjects are segmented as per mark information available for trials. All subjects chose any two motor imagery tasks. The data contains 200 trials comprising of 100 trials per M.I. task. The EEG segments are decomposed at the 8th level and decomposition coefficients corresponding to sensorimotor frequency band are selected for feature extraction. In the proposed WPD-GA-SVM scheme, GA is employed for the selection of relevant channels and further relevant features are extracted from the selected channels to maximize the classification accuracy. The comparison of the results of the proposed schemes with the published results (Park et al., 2013) (Tomida & Tanaka, 2015) is presented in Table 2. For subject ‘a’ accuracy is 88.9 6.9 with 10 channels, for subject ‘b’ accuracy is 79.20±5.36with 11 channels, for subject ‘f’ accuracy is 90.50±3.56 with 13 channels, and for subject ‘g’ accuracy is 92.23±3.21with 12 channels. The proposed scheme outperforms in terms of classification accuracy for subjects ‘a, b, f, g’ and in terms of number of channels for subject ‘a’ and that for subject ‘b’ is same as reported earlier in literature (Tomida & Tanaka, 2015).  The results for proposed scheme WPD-GA-SVM outperform the results reported in (Park et al., 2013) (Tomida & Tanaka, 2015) for subjects ‘a’, ‘b’, ‘g’ & ‘f’, in terms of classification accuracy. In terms of the number of channels, the proposed approach WPD-GA-SVM outperforms the results reported in (Tomida & Tanaka, 2015) for all subjects and outperforms the results reported in (Park et al., 2013) for the subject 'a' only and that for subject ‘b’ is at par with that of  (Park et al., 2013).

The proposed scheme is a significant new research contribution to evolutionary computation in terms of proposed new three-dimensional representation of binary population of GA and further modification in GA operators as per the requirement for the new representation of population. The efficacy of the proposed new scheme is evident from the results obtained for the motor imagery classification and optimization of channels for dataset I of BCI competition IV.

Table 2. Comparison of the results of the classification of the proposed techniques with techniques reported in the literature.

Note: The abbreviations in Table 2 stand for m = number of common spatial filters, BF – Butterworth Filter, CWT – Continuous Wavelet Transform, SST – Synchro-Squeezed Wavelet Transform, EMD – Empirical Mode Decomposition, EEMD – Ensemble Empirical Mode Decomposition, MEMD – Multivariate Empirical Mode Decomposition and NA-MEMD – Noise Assisted Multivariate Empirical Mode Decomposition, WPD – Wavelet Packet Decomposition, GA – Genetic Algorithm, SVM- Support Vector Machine.

Conclusion

The BCI research can assist in providing alternative means for communication and control capacities to the patients with neuro-motor disabilities. In the present paper, an effective novel scheme for motor imagery classification is presented. A new representation for binary population and a new cross-over method for GA are introduced.

The effectiveness of the scheme is apparent from results in which the proposed scheme outperformed the results of existing techniques for subjects ‘a, b, f, g’ and also in terms of selection of channels for subject ‘a’. Therefore, proposed scheme contributes a significant development in terms of new three-dimensional representation of binary population for GA as well as significant new modification to the GA operators. The efficacy of the scheme is evident from the results presented in the paper for dataset under consideration. The future course of research may include adding adaptation in GA at different levels, for the present application. A lot of research is yet to be carried out before the day will come when the patients with completely locked-in and other types of neuro-motor disabilities will use the EEG based prosthetics with ease. 

Conflict of interest

The authors declare no potential conflict of interest regarding the publication of this work. In addition, the ethical issues including plagiarism, informed consent, misconduct, data fabrication and, or falsification, double publication and, or submission, and redundancy have been completely witnessed by the authors.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article