Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (20): 48-50.DOI: 10.3778/j.issn.1002-8331.2008.20.014

• 理论研究 • Previous Articles     Next Articles

Hybrid quantum algorithm and its application in flow shop problem

FU Jia-qi,YE Chun-ming,XIE Jin-hua   

  1. College of Business,University of Shanghai for Science and Technology,Shanghai 200093,China
  • Received:2007-10-09 Revised:2007-12-07 Online:2008-07-11 Published:2008-07-11
  • Contact: FU Jia-qi

混合量子算法及其在flow shop问题中的应用

傅家旗,叶春明,谢金华   

  1. 上海理工大学 管理学院,上海 200093
  • 通讯作者: 傅家旗

Abstract: Quantum Evolutionary Algorithm(QEA) is a distinctive type of algorithm for optimization currently,and the theoretical basis of QEA is quantum computation.The algorithm takes advantage of intervention and parallelism of quantum bit thoroughly,which enables QEA to solve combinatorial optimization problems.While solving scheduling problems,QEA has defects that it converges slowly and doesn’t use other immature individual.Hybrid Quantum Algorithm(HQA) is formed and it sucks Particle Swarm Optimization algorithm(PSO) and evolutionary computation into QEA.Classical flow shop problem is employed to test the algorithm,and the result shows that the hybrid algorithm overcomes the defects of QEA and it has universality to solve scheduling problems.

Key words: Quantum Evolutionary Algorithm(QEA), quantum bit, Particle Swarm Optimization algorithm(PSO), Hybrid Quantum Algorithm(HQA)

摘要: 量子进化算法(QEA)是目前较为独特的优化算法,它的理论基础是量子计算。算法充分借鉴了量子比特的干涉性、并行性,使得QEA求解组合优化问题具备了可行性。由于在求解排序问题中,算法本身存在收敛慢,没有利用其它未成熟个体等缺陷,将微粒群算法(PSO)及进化计算思想融入QEA中,构成了混合量子算法(HQA)。采用flow shop经典问题对算法进行了测试,结果证明混合算法克服了QEA的缺陷,对于求解排序问题具有一定的普适性。

关键词: 量子进化算法, 量子比特, 微粒群算法, 混合量子算法