一种求解Job-Shop调度问题的量子遗传算法  

A Novel Quantum Genetic Algorithm for Job-Shop Scheduling Problem

作　　者：朱筱蓉[1] 张兴华[1] 李纬[1] 

机构地区：[1]南京工业大学自动化学院,江苏南京210009

出　　处：《机械与电子》2008年第4期6-10,共5页Machinery & Electronics

基　　金：江苏省教育厅自然科学基金项目(06KJB510040)

摘　　要：提出了一种基于操作方式进行编码和解码的量子遗传算法,并将其用于求解一种典型的NP-hard组合优化问题即Job-Shop调度问题.该算法采用量子比特方式构造染色体,增加了算法的种群多样性和计算并行性;采用量子旋转门操作实现种群进化,有效地提高了算法的收敛速度.用基准调度问题实例对该算法进行的测试结果表明:该量子遗传算法与改进的遗传算法相比较有更好的优化性能.A kind of quantum genetic algorithm with operation- based encoding and decoding is proposed for solving Job- Shop scheduling problem,a typical NP - hard combinational optimization problem. The quantum bits are used to represent the chromosomes in the algorithm, so the characteristic of population diversity and computing parallelism are improved significantly. By using quantum rotation gate to evolve population,the convergence rate of the algorithm is increased remarkably. The test results of the benchmark problem show that the quantum genetic algorithm is superior to the improved genetic algorithms.

关 键 词：量子遗传算法 JOB-SHOP调度 组合优化 

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