智能混合优化策略及其在流水作业调度中的应用

Intelligent Hybrid Optimization Strategy and Its Application to Flow-Shop Scheduling

通过结合蚁群算法(ACO)的并行搜索结构和模拟退火算法(SA)的概率突跳性,提出了一种有效的混合优化策略,并将该策略应用于流水作业调度问题(FSP).在该策略中,蚁群系统的一个周游路线为模拟退火算法提供了一系列初始解,在每个退火温度上进行抽样准则检验并产生新解,然后更新信息激素;蚁群算法再利用模拟退火算法产生的新解进行并行搜索.同时,根据此策略构建并实现了针对FSP问题求解的具体混合算法.仿真结果表明,混合算法弥补了ACO易陷入局部最优和SA搜索效率较低的缺点,增强了全局搜索能力,在求解FSP调度问题的性能上也优于其他算法.

By combining the parallel searching structure of ant colony optimization (ACO) with the probabilistic jumping property of simulated annealing (SA), an effective hybrid optimization strategy was developed, and applied to flow-shop scheduling problems (FSP). In the hybrid strategy, a cycle course of the ant system can provide effective initial solutions for SA, and SA generates new solutions based on the metropolis criterion at each temperature, then the ant system updates pheromone trails and proceeds with parallel searching through reusing the new solutions from SA. Meanwhile, the hybrid algorithm for flow-shop scheduling problems is created and realized on the basis of the hybrid strategy. With some benchmark FSP problems, the simulation results show that the method compensates the deficiency of ACO that is easy to be run into local optimum and SA that has lower efficiency, and strengthens the global search ability. Compared with other algorithms for solving FSP, the proposed method has better performance.