用带蚁群搜索的多种群遗传算法求解作业车间调度问题

A Multi-population Genetic Algorithm with Ant Search for Job Shop Scheduling Problems

结合遗传算法和蚁群算法的优点,提出一种带蚁群搜索的多种群遗传算法.多个种群各自遗传进化,用蚁群搜索得到的解替代各种群中的较劣个体,增加种群的多样性,提高种群的质量;根据各种群最优个体设定初始信息素,大大缩短信息素的累积过程,加快蚁群搜索的速度.利用算法对典型作业车间调度问题进行求解,仿真计算结果表明,该算法是有效的.*

By integrating the advantages of both genetic algorithm and ant colony algorithm, this paper presents a multi-population genetic algorithm with ant search. In this algorithm, populations evolve independently, and worse chromosomes of each population are replaced by solutions obtained from ant search, so as to increase the diversity and improve the quality of populations. By setting the initial pheromone trail based on the best chromosomes of each population, the accumulation process of pheromone trail is greatly shortened, and the searching speed of ants is quickened. This algorithm has been used to solve a benchmark job shop scheduling problem. Simulation result shows that the algorithm is effective.