摘要
提出了一种基于操作方式进行编码和解码的量子遗传算法,并将其用于求解一种典型的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.
出处
《机械与电子》
2008年第4期6-10,共5页
Machinery & Electronics
基金
江苏省教育厅自然科学基金项目(06KJB510040)
关键词
量子遗传算法
JOB-SHOP调度
组合优化
quantum genetic algorithm
Job- Shop scheduling
combinational optimization
