摘要
车间作业调度问题是一个典型的NP-hard问题。分析了蚂蚁算法和遗传算法的特点,就遗传算子、交叉概率和变异概率上对传统遗传算法进行了改进;同时为了加速蚂蚁的搜索效率、减少迭代次数,重构了传统蚂蚁算法的下一个结点选择策略、信息素的局部更新策略,并将改进后的两个算法进行混合求车间作业调度的最优解。试验表明,算法的改进和混合提高了搜索效率及搜索结果的准确性。
The job shop scheduling problem is a classic NP-hard problem. In this paper, we analyses the characteristic of ant algorithm and genetic algorithm. The traditional genetic algorithm is improved in genetic arithmetic operators and cross probability. We reconstructed next crunodes choosing strategy of traditional ant algorithm and ameliorated the strategy of local information updating in order to accelerate the search efficiency of ant algorithm and reduce the iterative time; We mix the improved genetic algorithm with the improved ant algorithm to get the best outcome of job shop scheduling problem. The experiment indicates that the improved and mixed algorithm improves the efficiency of searching and veracity of result.
出处
《软件导刊》
2006年第12期70-72,共3页
Software Guide
关键词
遗传算法
蚂蚁算法
蚂蚁遗传混合算法
车间作业调度
genetic algorithm
ant algorithm
ant algorithm genetic algorithm
job shop scheduling problem
