Top > JACIII > Experimental Study on Pair Swap Strategy in Quantum-Inspired E ...

single-jc.php

JACIII Vol.13 No.2 pp. 97-108
doi: 10.20965/jaciii.2009.p0097
(2009)

Paper:

Views over last 60 days: 539

Experimental Study on Pair Swap Strategy in Quantum-Inspired Evolutionary Algorithm

Takahiro Imabeppu, Shigeru Nakayama, and Satoshi Ono

Department of Information and Computer Science, Faculty of Engineering, Kagoshima University, 1-21-40 Korimoto, Kagoshima 890-0065, Japan

Received:
December 25, 2007
Accepted:
September 17, 2008
Published:
March 20, 2009
Creative Commons License
Keywords:
quantum-inspired evolutionary algorithm, pair swap, migration, 0-1 knapsack problem
Abstract
Quantum-Inspired Evolutionary Algorithm (QEA), a type of stochastic algorithm for solving combinatorial optimization problems, is evolutionary computation using quantum bits and superposition states in quantum computation. Although coarse-grained parallel, QEA has many parameters that must be adjusted manually. The simpler algorithm, Quantum-inspired Evolutionary Computation with Pair Swap operator (QEAPS), the authors propose involves just one population and a simple genetic operation exchanging best solution information between two individuals chosen randomly, instead of the migration operation used in QEA, and thereby fewer parameters to be adjusted. The authors found in experiments that QEAPS finds highly qualified solutions, is more robust against constraint handling, and has a higher search performance of thanks to diversified best solution information.
Cite this article as:
T. Imabeppu, S. Nakayama, and S. Ono, “Experimental Study on Pair Swap Strategy in Quantum-Inspired Evolutionary Algorithm,” J. Adv. Comput. Intell. Intell. Inform., Vol.13 No.2, pp. 97-108, 2009.
Data files:
References
  1. [1] D. Deutsch, “Quantum Theory, the Church-Turing Principle, and the Universal Quantum Computer,” Proc. Royal Society of London Ser. A, Vol.A400, pp. 97-117, 1985.
  2. [2] M. A. Nielsen and I. L. Chuang, “Quantum Computation and Quantum Information,” Cambridge Univ. press, New York, 2000.
  3. [3] D. M. Lucas, A. Ramos, J. P. Home, M. J. McDonnell, S. Nakayama, J.-P. Stacey, S. C. Webster, D. N. Stacey, and A. M. Steane, “Isotope-selective photoionization for calcium ion trapping,” Physical Review A, Vol.69, No.012711, 2004.
  4. [4] S. Nakayama, “Consideration on the Square Root Gates of Quantum Logic Gates,” Trans. of Japan Society for Computational Engineering and Science, Vol.7, pp. 77-82, 2005.
  5. [5] A. Narayanan and M. Moore, “Quantum-inspired Genetic Algorithms,” Proc. IEEE Int. Conf. Evolutionary Computation, pp. 61-66, 1996.
  6. [6] S. Nakayama, I. Iimura, M. Matsuo, and M. Maezono, “Consideration on Interference Crossover Method in Genetic Algorithm,” IPSJ Journal, Vol.48, No.8, pp. 2625-2635, 2006.
  7. [7] S. Nakayama, I. Iimura, and T. Ito, “Consideration on Quantum Interference Crossover Method in Immune Algorithm,” The IEICE Trans. on Information and Systems, Vol.J88-D-I, No.12, pp. 1795-1799, 2005.
  8. [8] S. Nakayama, M. Maezono, and S. Ono, “Proposal of Helical Crossover Strategy in Genetic Programming,” Trans. of the Institute of Systems, Control and Information Engineers, Vol.19, No.6, pp. 262-264, 2006.
  9. [9] S. Nakayama, I. Iimura, T. Ito, and S. Ono, “Proposal of Mixed Interference Crossover Method in Immune Algorithm,” The IEICE Trans. on Information and Systems, Vol.J89-D, No.6, pp. 1449-1456, 2006.
  10. [10] K.-H. Han and J.-H. Kim, “Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization,” IEEE Trans. Evolutionary Computation, Vol.6, No.6, pp. 580-593, 2002.
  11. [11] K.-H. Han and J.-H. Kim, “On Setting the Parameters of Quantum-inspired Evolutionary Algorithm for Practical Applications,” in Proc. 2003 Congress on Evolutionary Computation, IEEE Press, pp. 178-184, 2003.
  12. [12] D. E. Goldberg, “Genetic Algorithms in Search, Optimization, and Machine Learning,” Addison-Wesley, 1989.
  13. [13] K. Mori, M. Tsukiyama, and T. Fukuda, “Application of an immune algorithm to multi-optimization problems,” IEEJ Trans. on Electronics, Information and Systems, Vol.117-C, No.5, pp. 593-598, 1997.
  14. [14] J. Koza, “Genetic Programming: On the Programming of Computers by Means of Natural Selection,” MIT Press, 1992.
  15. [15] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by Simulated Annealing,” Science, Vol.220, No.4598, pp. 45-54, 1983.
  16. [16] R. Tanese, “Distributed Genetic Algorithm,” Proc. 3rd Int. Conf. on Genetic Algorithms, pp. 434-439, 1989.
  17. [17] T. Starkweather, D. Whitley, and K. Mathias, “Optimization Using Distributed Genetic Algorithms,” Parallel Problem Solving from Nature, Springer-Verlag, pp. 176-185, 1990.
  18. [18] T. C. Velding, “The Distributed Genetic Algorithm Revisited,” Proc. 6th Int. Conf. on Genetic Algorithms, pp. 114-121, 1995.
  19. [19] I. Iimura, K. Matsuoka, and S. Nakayama, “Consideration on Islands' Distance Strategy in a Genetic Local Search based on One-Dimensional Torus Type Island Model,” IEEJ Trans. on Electronics, Information and Systems, Vol.125-C, No.1, pp. 84-92, 2005.
  20. [20] K. Mizuno, S. Nishihara, H. Kanoh, and I. Kishi, “Population migration: a meta-heuristics for stochastic approaches to constraint satisfaction problems,” Informatica, Vol.25, No.3, pp. 421-429, 2001.
  21. [21] L. J. Eshelman and J. D. Schaffer, “Preventing premature convergence in genetic algorithms by preventing incest,” Proc. Fourth Int. Conf. on Genetic Algorithms, pp. 115-122, 1991.
  22. [22] Y. Leung, Y. Gao, and Z. B. Xu, “Degree of population diversity-a perspective on premature convergence in genetic algorithms and its markov chain analysis,” IEEE Trans. on Neural Networks, Vol.8, No.5, pp. 1165-1176, September 1997.
  23. [23] S. Nakayama, T. Imabeppu, S. Ono, and I. Iimura, “Consideration on Pair Swap Strategy in Quantum-Inspired Evolutionary Algorithm,” The IEICE Trans. on Information and Systems, Vol.J89-D, No.9, pp. 2134-2139, 2006.
  24. [24] S. Nakayama, T. Imabeppu, and S. Ono, “Pair Swap Strategy in Quantum-Inspired Evolutionary Algorithm,” Proc. Genetic and Evolutionary Computation Conf. (GECCO2006), Late-Breaking Papers Session, 2006.
  25. [25] S. Martello and P. Toth, “Knapsack Problems – Algorithms and Computer Implementations,” John Wiley and Sons Ltd., 1990.
  26. [26] S. Martello, D. Pisinger, and P. Toth, “Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem,” Management Science, Vol.45, pp. 414-424, 1999.
  27. [27] S. Martello, D. Pisinger, and P. Toth, “New trends in exact algorithm for the 0-1 knapsack problem,” European Journal of Operational Research, Vol.123, pp. 325-332, 2000.
  28. [28] D. H. Ackley, “A Connectionist Machine for Genetic Hillclimbing,” Kluwer Academic Publishers, 1987.
  29. [29] J. M. Varanelli and J. P. Cohoon, “Population-Oriented Simulated Annealing: A Genetic/Thermo-dynamic Hybrid Approach to Optimization,” Proc. of the Sixth Int. Conf. on Genetic Algorithms, pp. 174-181, 1995.
  30. [30] K.-H. Han and J.-H. Kim, “On the Analysis of the Quantum-inspired Evolutionary Algorithm with a Single Individual,” Proc. IEEE Congress on Evolutionary Computation, pp. 9172-9179, 2006.
  31. [31] C. A. Brizuela and N. Sannomiya, “A Diversity Study in Genetic Algorithms for Job Shop Scheduling Problems,” Proc. Genetic and Evolutionary Computation Conf. (GECCO99), pp. 75-82, 1999.

Creative Commons License  This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Apr. 22, 2024