基于遗传和禁忌搜索混合算法的预制生产调度的研究

Research on Precast Production Scheduling Based on Genetic and Tabu Searching Hybrid Algorithm

摘要:

遗传算法是一种全局搜索能力较强的元启发式算法,可通过不断进化种群得到最优或近优解；但是遗传算法的局部搜索能力较差,容易发生早熟收敛问题。因此为了克服遗传算法早熟收敛的问题,考虑到禁忌搜索算法的局部搜索能力较强的优势,提出了一种遗传和禁忌搜索的混合算法解决预制生产流水车间的提前和拖期惩罚问题。该混合算法是在遗传算法每次迭代后,通过禁忌搜索改进当前种群中的最好染色体,并替换种群中适应度值最差的染色体。经实验测试表明,所提出的混合算法的性能更优,更容易得到全局最优解或近优解。

Abstract:

Genetic algorithm (GA) is a meta-heuristic algorithm with strong global search ability, which can obtain the optimal or near-optimal solution by continuously evolving population; however, the local search ability of GA is poor, so it is easy to occur the problem of premature convergence. Therefore, in order to overcome the problem of premature convergence of GA, considering the advantage of local search ability of tabu search (TS) algorithm, a hybrid algorithm of genetic and tabu search (GA_TS) is proposed to solve the problem of earliness and tardiness penalty in precast production flow shop. The hybrid algorithm is to improve the best chromosomes in the current population by TS after each iteration of the GA, and replace the chromosome with the worst fitness value in the population. The experimental results show that the proposed GA_TS algorithm has better performance and can obtain global optimal solution or near-optimal solution.