An improved multi-population genetic algorithm for job shop scheduling problem

摘要

This paper introduces “population migration” idea and proposes an improved multi-population genetic algorithm based on population migration, which differed from tradition multi-population genetic algorithms that only improve the crossover and mutation operator. The new algorithm provides a population adjusting strategy based on population migration to adjust the population size automatically. Firstly, the algorithm divides the initial population into some subpopulations and performs different genetic algorithms on different subpopulations. Secondly, it evaluates the favorable index of each subpopulation after some runtime. Then, it makes some chromosome moving to the subpopulation with high favorable index to continue to evolve. Finally, when the population has a phenomenon of local value, the algorithm makes the chromosome in this population diffuse to different population to search a new global best value. The new algorithm is experimented with the Muth and Thompson standard problem, and the result of the experiment shows the convergence capability and ability to solve the precocity of the new algorithm is improved sharply.