Quantum and biogeography based optimization for a class of combinatorial optimization

ABSTRACT

In this paper, an algorithm named Quantum and Biogeography based Optimization(QBO) is proposed to investigate the possibility of optimization by evolving multiple Quantum Probability Models(QPMs) via evolutionary strategies inspired by the mathematics of biogeography. In QBO, each QPM modeling an area in decision space represents a habitat, the whole population of QPMs evolve as an ecosystem with multiple habitats interacting. The migration and immigration mechanisms originally presented in Biogeography Based Optimization (BBO) [1] is introduced into QBO to implement the efficient information sharing among QPMs, which enhance the evolution of probability models towards the better status that can generate more better solutions. Experimental results on classical 0/1 knapsack problems of various scale show that the mechanisms in BBO are feasible to evolve multiple QPMs, and QBO is efficient for hard optimization problem.

REFERENCES

• 1: Dan Simon, Biogeography-Based Optimization, IEEE Transaction on Evolutionary Computation, Vol.12, No.6, Dec. 2008, P702--713.
• 2: Kuk-Hyun Han and Jong-Hwan Kim, Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization, IEEE Transaction on Evolutionary Computation, Vol.6, No.6, Dec. 2002, p580--593.
• 3: Bin Li , Zhen-quan Zhuang, Genetic Algorithm Based-On the Quantum Probability Representation, Proceedings of the Third International Conference on Intelligent Data Engineering and Automated Learning, p.500-505, August 12-14, 2002
• 4: Licheng Jiao, Yangyang Li, Maoguo Gong, Xiangrong Zhang, Quantum-Inspired Immune Clonal Algorithm for Global Optimization, IEEE Transaction on Systems, Man, and Cybernetics; Part B: Cybernetics, Vol.38, No.5, Oct. 2008, p1234--1253.
• 5: Bin Li, Lixiang Tan, Yi Zou, Zhenquan Zhuang, Quantum Probability Coding Genetic Algorithm and its applications, Journal of Electronics and Information Technology, Vol.27, No.5, May 2005. p805--810. (in Chinese)
• 6: Kuk-Hyun Han and Jong-Hwan Kim, Quantum-Inspired Evolutionary Algorithms With a New Termination Criterion, He Gate, and Two-Phase Scheme, IEEE Transaction on Evolutionary Computation, Vol. 8, No. 2, April 2004, p156--169.
• 7: John G. Vlachogiannis and Kwang Y. Lee, Quantum-Inspired Evolutionary Algorithm for Real and Reactive Power Dispatch, IEEE Transactions on Power Systems, Vol.23, No.4, Nov. 2008, p1627--1636.
• 8: Wenlong Wei, Bin Li, Yi Zou, Wencong Zhang, and Zhenquan Zhuang, A Multi-objective HW-SW Co-synthesis Algorithm based on Quantum Probability Coding Genetic Algorithm, International Journal of Computational Intelligence and Applications(World Scientific) , Volume: 7, Issue: 2 (June 2008), Page 129 -- 148.
• 9: Andre V. Abs da Cruz, Marley M. B. R. Vellasco and Marco Aurelio C. Pacheco, Quantum-Inspired Evolutionary Algorithm for Numerical Optimization, 2006 IEEE Congress on Evolutionary Computation, Vancouver, BC, Canada, July 16--21, 2006, p2630--2637.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms

Keywords:
0/1 knapsack problem, biogeography based optimization, emigration, immigration, quantum inspired evolutionary algorithms