Quantum Artificial Bee Colony Algorithm for Knapsack Problem

Abstract:

The traditional quantum evolutionary algorithm takes a long time to converge and can be easy trap into local optima. In order to overcome and accelerate the speed of the convergence, a new quantum evolutionary algorithm is proposed in the paper. The proposed new algorithm named discrete quantum bee colony algorithm incorporate the basic idea of the artificial bee colony algorithm. The initial population can be initialized randomly using quantum encoded and the population can be formed by there parts and every subpopulation can evolve cooperatively. In the end, the individual will rated according to the multi-granularity mechanism and also rated according to the evolution condition. Simulation results of knapsack problems show that the proposed algorithm performs better than other algorithm.

• Periodical: Advanced Materials Research (Volumes 605-607)
• Pages: 1722-1728
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.605-607.1722
• Online since: December 2012
• Authors: Zhen Liu, Yun An Hu
• Keywords: Chaotic, Knapsack Problem, Quantum-Inspired Evolutionary Algorithm

References

[1] K. H. Han and J. H. Kim．"Quantum-inspired evolutionary algorithm for a class of combinatorial optimization", IEEE Transactions on Evolutionary Computation, Vol.6(2002), pp.580-593

DOI: 10.1109/tevc.2002.804320

[2] S. F. Zhao, G. Z. Xu, T. F. Tao and L. Liang．"-coded chaotic quantum-inspired genetic algorithm for training of fuzzy neural networks[J]．Computers and Mathematics with Applications, Vol.57(2009), pp.2009-2015

DOI: 10.1016/j.camwa.2008.10.048

[3] H. L. Xing, X. Liu, X. Jin and Y. F. Ji．"A multi-granularity evolution based quantum genetic algorithm for QoS multicast routing problem in WDM networks[J]．Computer Communications, Vol.32(2009), pp.386-393

DOI: 10.1016/j.comcom.2008.11.009

[4] Karaboga D, Bastrk B．"On the performance of artificial bee colony (ABC) algorithm", Applied Soft Computing, Vol.8(2008), pp.687-697．

DOI: 10.1016/j.asoc.2007.05.007

[5] Dervis Karaboga, Bahriye Akay．"A modified artificial bee colony (ABC) algorithm for constrained optimization problems", Applied Soft Computing, Vol.11(2011), p.3021–3031．

DOI: 10.1016/j.asoc.2010.12.001

[6] Bilal Alatas．"Chaotic bee colony algorithms for global numerical optimization", Expert Systems with Applications, Vol.37(2010), pp.5682-5687．

DOI: 10.1016/j.eswa.2010.02.042

[7] W. P. Ding, J. D. Wang, Z. J. Guan．"Efficient rough attribute reduction based on quantum frog-leaping co-evolution", ACTA ELECTRONICA SINICA, Vol.39(2011): pp.2597-2603（In Chinese）．

[8] L. C. Jiao, Y. Y. Li, M. G. Gong．"Quantum-inspired immune clonal algorithm for global optimization", IEEE Transactions on System, Man and Cybernetics, Part B, Vol.38(2008): pp.1234-1253．

DOI: 10.1109/tsmcb.2008.927271

[9] Li P C, Song K P, Yang E L．"Phase encoded-based quantum ant optimization", Systems Engineering–Theory & Practice, Vol.31(2011): pp.1565-1570（In Chinese）．

[10] Xiong W Q, Wei P．"Binary ant colony evolutionary algorithm", ACTA AUTOMATICA SINICA, Vol.33(2007): pp.259-264（In Chinese）．

DOI: 10.1360/aas-007-0259

[11] Hu G, Xiong W Q, Zhang X, et al．"Binary ant colony algorithm with controllable bias search", Control Theory & Applications, Vol.28(2011): pp.1071-1080（In Chinese）．