Paper:

# 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

*J. Adv. Comput. Intell. Intell. Inform.*, Vol.13 No.2, pp. 97-108, 2009.

- [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] M. A. Nielsen and I. L. Chuang, “Quantum Computation and Quantum Information,” Cambridge Univ. press, New York, 2000.
- [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] 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] A. Narayanan and M. Moore, “Quantum-inspired Genetic Algorithms,” Proc. IEEE Int. Conf. Evolutionary Computation, pp. 61-66, 1996.
- [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] 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] 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] 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] 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] 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] D. E. Goldberg, “Genetic Algorithms in Search, Optimization, and Machine Learning,” Addison-Wesley, 1989.
- [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] J. Koza, “Genetic Programming: On the Programming of Computers by Means of Natural Selection,” MIT Press, 1992.
- [15] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by Simulated Annealing,” Science, Vol.220, No.4598, pp. 45-54, 1983.
- [16] R. Tanese, “Distributed Genetic Algorithm,” Proc. 3rd Int. Conf. on Genetic Algorithms, pp. 434-439, 1989.
- [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] T. C. Velding, “The Distributed Genetic Algorithm Revisited,” Proc. 6th Int. Conf. on Genetic Algorithms, pp. 114-121, 1995.
- [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] 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] 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] 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] 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] 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] S. Martello and P. Toth, “Knapsack Problems – Algorithms and Computer Implementations,” John Wiley and Sons Ltd., 1990.
- [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] 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] D. H. Ackley, “A Connectionist Machine for Genetic Hillclimbing,” Kluwer Academic Publishers, 1987.
- [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] 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] 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.

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