Research On Evolutionary Clustering Algorithm And Its Expansion In Graph Space

Evolutionary computing is a global search algorithm suitable for solving complex,highdimensional and large-scale problems.By simulating the data vectors as the genotype in the organism,simulating the evolution process of the species in nature,performing operations such as crossover and mutation on the data vectors,and selecting individuals more adapted to the environment from the newly generated individuals and the original individuals as the new population,so as to continuously iteratively optimize the data,and finally find the global optimal solution.In the clustering problem,as a classic global optimization algorithm,evolutionary computing provides a powerful solution.According to the application scenarios,clustering algorithms can be divided into applications in vector space and graph space:In the vector space,this paper finds that the individual coding schemes in the evolutionary clustering algorithm have the problems of redundancy and inconsistency,which not only wastes search resources,but also disrupts the mutual learning process between individuals.In order to solve the problem of clustering redundancy,this paper proposes a method of gene sequence resorting.This method first selects the reference vector with the best current fitness,and then rearranges the coding order of the genotypes according to the distance between the genes in each individual and the reference vector.In this way,the clustering scheme represented by each individual is uniform and corresponding to each other,thereby eliminating redundancy and solving the problem of inconsistent learning between individuals in the algorithm.Combining the above methods,this paper improves two different types of clustering algorithms based on distance-based convex clustering and density-based non-convex clustering,and develops a general evolutionary clustering framework.Experiments show that this method can effectively improve the performance of the evolutionary clustering algorithm on data sets of different shapes.On the other hand,in the graph space,when using the local adjacency coding scheme,because there are connected edges between adjacent clusters in the evolutionary clustering algorithm,the process of randomly selecting adjacent edges will result in nodes that should belong to different clusters.Wrongly selected into the same category,resulting in infeasible solutions.In response to the above problems,this paper designs a line graph-based edge-closing local adjacency coding scheme.By introducing the concept of imaginary empty edges in the adjacency list,temporarily closing some edges,so as to obtain the correct local partitioning scheme.In addition,this paper designs a heuristic initialization strategy.The selection of adjacent edges is more inclined to the edges that are closer to the current edge or in a more central position in the cluster to speed up the convergence of the algorithm.Based on the above coding scheme and initialization strategy,this paper proposes a line graph-based memetic algorithm(LGMA),which uses simulated annealing algorithm and hill climbing algorithm with elite strategy on the basis of classic memetic algorithm to perform local optimization.The experimental results show that the memetic algorithm based on the line graph can effectively solve the problem of node division errors and improve the search accuracy and stability of the memetic algorithm in graph clustering.