Improvement Of Differential Evolution Algorithm And Its Application In K-means Clustering Algorithm

Differential evolution algorithm (Differential Evolution Algorithm, referred to DE), which is proposed by Rainer Storn and Kenneth Price to solve the Chebyshev polynomial as a branch of evolutionary algorithms by 1995. DE algorithm has a lot of advantages, such as:the convergence is good, the model is simple, the control parameters are less and it is easy to be implemented. Because of these advantages, DE algorithm has been paid more and more attention. DE algorithm has strong global search ability, which can make the algorithm unaffected by the nature of the problem. It can effectively solve complex optimization problems, and it is increasingly being applied in sloving practical problems.Although DE algorithm has many advantages, but there are also disadvantages, such as:DE algorithm is easy to fall into local optimum, there will be stagnation, it has slow convergence speed and even unconvergence. Therefore, this thesis improves the standard DE algorithm from the two aspects of initial population quality optimization and evolutionary strategy:using chaotic search method and and reverse learning method to optimize the initial population. This thesis proposes a two-stage strategy of mutation and crossover, and in the end this thesis uses five benchmark functions to test the improved algorithm, the results show that the improved DE algorithm have shown the better optimization results and convergence speed in single modal or multimodal optimization problems, the effect of improving is significant.Clustering is an important application tool in data mining, statistical analysis, data compression and vector quantization, and K-means clustering algorithm is the most widely used. K-means clustering algorithm has a lot of shortcomings, such as:it needs to determine the K-value first; it is sensitive to the clustering center and is easy to converge to local optimum value, while DE algorithm has strong robustness for the optimization of parameters. Therefore, in order to overcome the shortcomings of K-means clustering algorithm, this thesis proposes an improved K-means clustering algorithm--KTMDE, which is based on two-stage of mutation and crossover strategy. This method combines the global convergence of DE algorithm with the efficiency of the K-means clustering algorithm, it uses the cluster center as population vector coding method, combining with the chaotic search backward learning methods for choosing kmax cluster centers as the initial population of individuals, K clustering centers are randomly selected to compose the individual vector from kmax cluster centers in every iteration procedure. In the use of TMDE algorithm to optimize the population at the same time, using K-means clustering algorithm for the new generation of the population generated by TMDE algorithm, this strategy not only can accelerate the convergence speed of K-TMDE algorithm, but also can search the best number of K and improve the quality of clustering. The results show that this algorithm can effectively optimize the K-means clustering algorithm.