|
|
|
| Evolutionary Algorithm for Magic Squares |
| XIE Tao1, ZHAO Bin1, XIE DaoYu2 |
1.College of Computer, National University of Defense Technology, Changsha 410073
2.Intelligence Computations and Control Center, Hunan Evonature Science and Technology Corporation, Limited, Changsha 410013 |
|
|
|
|
Abstract Magic square construction is a complex permutation problem with a long history. The complexity not only consists of the number of magic squares that increases rapidly with the order of magic square, but also of the percentage of magic squares in the possible permutation of the first n2 natural numbers that decreases with the order. Based on the twophase construction conjecture, an improved evolutionary algorithm for magic square construction is proposed. Mutation operators are specially designed so that the mutation domain can be located and the mutation probabilities can be adjusted adaptively which include the number transpositions, the row transpositions and column transpositions. In addition, some heuristicsbased local permutations, such as the local row/column rectification and the local diagonal rectification, are used to complement the stochastic mechanism. Computational results show that the twophase construction conjecture is computationally effective, and the improved evolutionary algorithm is highly efficient for magic square construction.
|
|
Received: 23 August 2005
|
|
|
|
|
|
[1] Berlekamp E R, Convay J H, Guy R K. Winning Ways for Your Mathematical Plays. London, UK: Academic Press, 1982
[2] Madachy L S. Magic and Antimagic Squares // Madachy J S, ed. Madachy’s Mathematical Recreations. New York, USA: Dover, 1979: 85113
[3] Pinn K, Wieczerkowski C. Number of Magic Squares from Parallel Tempering Monte Carlo. International Journal of Modern Physics, 1998, 9: 541547
[4] Abe G. Unsolved Problems on Magic Squares. Discrete Mathematics, 1994, 127(1/2/3): 313
[5] Kraitchik M. Magic Squares // Kraitchik M, ed. Mathematical Recreations. New York, USA: Norton, 1942: 142192
[6] Xie Tao, Kang Lishang. An Evolutionary Algorithm for Magic Squares // Proc of the Congress on Evolutionary Computation. Canberra, Australia, 2003, Ⅱ: 906913
[7] Bck T, Hoffmeister F, Schwefel H P. A Survey of Evolution Strategies // Proc of the 4th International Conference on Genetic Algorithms. San Diego, USA, 1991: 29 |
|
|
|
2007, Vol. 20 
