The Research Of Evolutionary Algorithm And Its Application In Chemoinformatics

Increasingly large, diverse and publicly available data sets, especially in the field of the gene expression data and atomic clusters, are being generated using various high-throughput screening, chemistry technology, and sequencing technology. Gene expression data and atomic clusters are two important problems in the chemoinformatics. The reason is that, Gene expression data is a complex task in the evolution of cancer diagnoses and atomic clusters can help the researchers to research the structure of the atomic. In other aspects, these two problems have been proved to be NP-hard problems. As we know, some studies showed that NP-Hard problems are unlikely to be solved in polynomial time. Therefore, in the thesis, we use the evolutionary algorithm including biogeography based optimization and differential evolution algorithm to solve these two problems, feature selection problem and atomic clusters problem. The main results can be summarized as follows:(1) In this part, a multi-objective biogeography based optimization method is proposed to select the small subset of informative gene relevant to the classification. In the proposed algorithm, firstly, the fisher-markov selector is used to choose the 60 top gene expression data. Secondly, to make biogeography based optimization suitable for the discrete problem, binary biogeography based optimization, as called BBBO, is proposed based on a binary migration model and a binary mutation model. Then, multi-objective binary biogeography based optimization, as we called MOBBBO, is proposed by integrating the non-dominated sorting method and the crowding distance method into the BBBO framework. Finally, the MOBBBO method is used for gene selection, and support vector machine is used as the classifier with the leave-one-out cross-validation method(LOOCV). In order to show the effective and efficiency of the algorithm, the proposed algorithm is tested on ten gene expression dataset benchmarks. Experimental results demonstrate that the proposed method is better or at least comparable with previous particle swarm optimization(PSO) algorithm and support vector machine(SVM) from literature when considering the quality of the solutions obtained.(2) In this part, we introduce a multi-objective binary differential evolution method(MOBDE) to select a small subset of genes. In the proposed method, firstly, the Fisher-Markov selector is used to choose 180 top features of gene expression data. Secondly, to make differential evolution suitable for the binary problem, a novel binary mutation method is proposed to balance the exploration and exploitation ability. Thirdly, the multi-objective binary differential evolution is introduced by integrating the summation of normalized objective value for selection of individuals into the binary differential evolution algorithm. Finally, the MOBDE algorithm can select the best suitable feature, and support vector machine(SVM) is used as the classifier with the leave-one-out cross-validation method(LOOCV). In order to show the effective and efficiency of the algorithm, ten gene expression datasets is used to verify the proposed method. Comparisons demonstrate that the MOBDE algorithm is effective and efficient for the feature selection compared with other well known algorithms.(3) In this part, the proposed algorithm uses two mutation rules based on the rand and best individuals among the entire population. In order to balance the exploitation and exploration of the algorithm, two new rules are combined through a probability rule. Then, self-adaptive parameter setting is introduced as uniformly random numbers to enhance the diversity of the population based on the relative success number of the proposed two new parameters in a previous period. In other aspects, our algorithm has a very simple structure and thus it is easy to implement. To verify the performance of MDE, atomic clusters benchmark functions and 16 benchmark functions chosen from literature are employed. The results show that the proposed MDE algorithm clearly outperforms the standard differential evolution algorithm with six different parameter settings.