基于模拟退火的蚁群算法求解Job-Shop问题  

APPLICATION OF ANT COLONY OPTIMIZATION BASED ON SIMULATED ANNEALING TO JOG-SHOP PROBLEM

作　　者：张晓婧[1] 高慧敏[1] 

机构地区：[1]太原科技大学计算机科学与技术学院,山西太原030024

出　　处：《计算机应用与软件》2008年第5期77-79,共3页Computer Applications and Software

基　　金：山西省自然科学基金项目资助(20041048)。

摘　　要：引用蚁群算法来解决Job-Shop问题(简称JSP),但是由于蚁群算法本身的原理和Job-Shop问题之间的差异性,使得用基本的蚁群算法来解决Job-Shop问题存在一些缺陷。从蚁群算法的改进入手,采用了不同策略的信息素更新方法,并采用模拟退火算法对搜索到的解进行处理,不仅加快了算法的收敛速度,而且能收敛到更好的解,最后用实例对算法的有效性进行了验证。Ant colony optimization method is applied to solve Job-Shop problem（JSP）. But due to the discrepancy between the theory of ant colony optimization and the Job-Shop problem, there are some disadvantages to solve Job-Shop problem singly by basic ant colony optimization. The ant colony algorithm is improved. A method for pheromone updating of different policies is presented, and the simulated annealing algorithm is adopted. The converage speed is accelerated, and good value is achieved. Finally, the validity of the algorithm is verified with practice.

关 键 词：Job—Shop问题 蚁群算法 模拟退火算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O224[自动化与计算机技术—计算机科学与技术]