The Application Of Evolutionary Computation In Combination Optimization & Data Mining

Evolutionary Computation is a type of model which uses computer to simulate the evolutionary process of nature, especially the process of biological evolution, to solve the complex problems. Due to its intelligent properties such as self-organizing, self-learning and self-adaptation, and some advantages such as simple, common, robust, suitable for parallel processing, evolutionary computation is widely used in combinatorial optimization, data mining, optimization and other areas.For the past few years, the theory of evolutionary computation gradually enriches and improves. In this paper, two types of classical combinatorial optimization problems TSP and SAT problem are studied based on evolutionary computation. New algorithms are designed to solve these two types of NP-hard problem. In addition, This paper also discuss the application of evolutionary computation in the field of data mining to search classification rules and in the area of satellite communications to solve dynamic channel allocation and optimization problem. By proposing some new ideas, new strategy, the new evolutionary algorithms solve these two problems effectively, thus demonstrating the powerful capabilities of evolutionary computation in searching and optimization area.On the TSP problem, an improved algorithm is proposed to accelerate the convergence of the Guo-Tao algorithm (GT) by design new evolution operators, and by increasing some control strategy. Based on the new algorithm a distributed evolutionary algorithm is proposed to solve the lager-scale size of TSP problem. Also another parallel mechanism on evolutionary algorithms is raised and analysis. Numerical experiments show that the Improved GT algorithm can effectively solve small and medium-scale size of TSP problem. Experiments also show that distributed evolutionary algorithm can solve large-scale size of TSP problem.On the SAT problem, by introducing a personification strategy to evolutionary algorithm and by improving designing of crossover operator and mutation operator, an improved evolutionary algorithm (SAT-IEA) is proposed to solve SAT problem. The new algorithm not only has the properties of global convergence, and also the properties of parallelism and inheritance. Numerical experiments show that for random-examples and part of the SATLIB test examples, new algorithm is clearly superior to the general evolutionary algorithm in computing speed and success rate. A fast algorithm named Solar is compared with the new algorithm.On the classification problem in data mining, to improve original gene expression programming algorithms, a new evolutionary algorithm is proposed by designing new fitness function, optimizing initialization population, add new evolutionary operator and use new selection strategy. Numerical experiments show that the new algorithm can be used in classification rules mining, and its accuracy is better than traditional methods.On dynamic channel allocation problem, a mathematical model of "China 36 cell" satellite dynamic channel allocation problem is extracted. Via the theoretical analysis of the model, the paper proves that such problems can be transformed into graph coloring problem. It pointed out a new direction for the solving of such problems. Against "China 36 cell" satellite dynamic channel allocation problem, three strategies are raised. They are evolutionary algorithms, configure algorithm and hybrid algorithm which is a combination of the previous two algorithms. Numerical experiments are done on "China 36 cell" dynamic channel allocation problem, and the result show that the hybrid algorithm performs better.