The Research And Application Of A Multi-Population Hybrid Genetic Algorithm Based On Similarity Crowding

Genetic algorithm is a simulate the process of biological genetic evolution global probability search method which based on the Darwin’s theory of biological evolution and Mendel’s theory of genetic variation. It has characteristics such as broad applicability, strong global search capability, strong robustness. So, it has been widely applied in function optimization, portfolio optimization, production scheduling, machine learning and other fields. But, as we all know, there are two defects in the genetic algorithm which are poor local search ability and premature convergence. Aiming at the problems of genetic algorithms, this paper focuses on improving the local search ability of algorithm and maintain the diversity of the population to improved genetic algorithm. A multi-population hybrid genetic algorithm based on similarity crowding was proposed. The algorithm set up a plurality of sub-populations and one elitist preserved population evolution structure on macro, and introduced simulated annealing algorithm into sub-populations to construct reasonable structure of hybrid framework, used to improve the local search ability. On the micro aspects, used similarity evaluation standards when individuals exchange between sub-populations, according to certain methods to calculate the similarity between the exchange- individual and the individuals in the target population. Take a certain way to determine whether similar between individuals. And then implementation crowding replacement operation for maintain populations diversity, used to improve premature convergence. At last, six function optimization experiments and the comparison of optimization results are adopted to verify the effectiveness and superiority of the new algorithm.Traveling salesman problem is a combination optimization problem which has abroad application background and important theoretical value. It is an important research topic of computer scientists and managers since it has been proposed. Because of its own optimization capabilities, genetic algorithm have been widely used in solving the traveling salesman problem. And to solve the traveling salesman problem, are often used to evaluate performance of improved genetic algorithm. So the improved multi-population genetic algorithm proposed in this paper is applied to solve TSP problem up. In order to meet the TSP problem, adjustment the coding, parameter settings, genetic operations of the improved algorithm which proposed in this paper. Finally, by solving results of five data sets which provided by TSPLIB standard database, verify the effectiveness and practicality of the algorithm.