The Improved Hybrid Genetic Algorithm Based On Clustering

There are a large number of optimal and adaptive problems in the research aboutmodern scientific theory and practice. The general methods of calculation can’t solvelarge-scale multi-modal optimal problems. Genetic algorithm is a kind of adaptiveglobal optimal probabilistic searching algorithm that simulates the biological geneticevolutionary process. It exerts genetic operations such as selection, crossover andmutation to each generation’s population in terms of probability, which makes thepopulation evolve gradually to the state including or closing to the optimal solution,so it is an effective algorithm for solving all kinds of complex optimal problems.The balance between premature convergence and convergence rate is the focusof the research of genetic algorithm. It is the key how to effectively balance theabove conflict for improving the algorithm’s performance on the complexmulti-modal optimal problems. The main reason of premature convergence is theloss of population’s diversity caused by the close inbreeding among good individualsat early evolution. In order to solve these problems, this paper integrates clusteringmethod such as K-means clustering, hierarchical clustering, minimum spanning treeclustering and the thoughts of optimal representative with genetic algorithmsuccessively, and puts forward the corresponding improved genetic algorithms. Andon the basis, this paper integrates local search and orthogonal experiments with theimproved genetic algorithms and proposes a hybrid population differentiationgenetic algorithm, and evaluates and validates the new method’s effectiveness on thehigh-dimensional, complex and multimodal optimal problems. The main researchesof this paper are as follows:(1) To solve the problem of premature convergence, this paper presents animproved genetic algorithm based on clustering (CGA) after researching andimplementing some existing clustering algorithms and some improved geneticalgorithms. CGA can restrain the premature convergence effectively by dividing thepopulation into different sub populations with the clustering and prohibiting thegenetic operation between the similar individuals in the same sub population.Through theoretical analysis, this paper indicates that CGA can overcome theineffective crossover operation better than the standard genetic algorithm (SGA).(2) Aiming at the lower convergence rate of CGA caused by the inhibition ofpremature convergence, this paper puts forward an optimal representative improvedgenetic algorithm based on clustering (OCGA) based on CGA. Instead of the selected individual, the new method selects the optimal individual in the same subpopulation to attend the crossover operation, and accelerates the searching efficiencyof the algorithm.(3) This paper implements different CGAs and OCGAs with K-meansclustering, hierarchical clustering, minimum spanning tree clustering, and conductsthe related contrastive numerical experiments on the Benchmark functionoptimization problems. The experimental results show, compared with SGA, CGAand OCGA could restrain the premature convergence phenomenon to a certain extent,and OCGA algorithm could accelerate the searching efficiency.(4) This paper proposes a hybrid population differentiation genetic algorithm(HPDGA) based on OCGA. The new algorithm puts forward a Direction-BasedSimplex Crossover that is suitable for the local search, which can directionallyproduce a number of better offspring based on the parents’ fitness. And accompaniedwith the Direction-Based Simplex Crossover, this paper proposes an adaptivestrategy for local search, which uses different local operators according to thenumber of sub populations and the number of individuals in the sub population toaccelerate the evolution.(5) This paper conducts the contrastive numerical experiments about HPDGAon14high dimensional Benchmark function optimization problems, and the resultsindicate that the performance of new algorithm is significantly better than a varietyof existing comparative algorithms.