Title :
An evolutionary algorithm for magic squares
Author :
Xie, Tao ; Kang, Lishan
Author_Institution :
Coll. of Comput. Sci., Nat. Univ. of Defense Technol., Changsha, China
Abstract :
Magic square construction is a complex and hard permutation problem of recreational combinatorics with a long history. Not only does the complexity consist in that the number of magic squares increases rapidly with the order of magic square, but also in that the percentage of magic squares in the possible permutation of the first n2 natural numbers decreases with the order. Based on the two-phase construction conjecture, we propose an improved evolutionary algorithm for magic square construction. Mutation operators are specially designed so that the mutation domain can be located and the mutation probabilities adjusted adaptively, which include the number pair permutations, the row permutations and column permutations. In addition, some heuristics-based local permutations, like the row/column local rectification and the local diagonal rectification, are used to complement the stochastic mechanism. Computational results show that, the two-phase construction conjecture is computationally effective, and the improved evolutionary algorithm is highly efficient for magic square construction.
Keywords :
combinatorial mathematics; evolutionary computation; probability; stochastic processes; column permutation; diagonal rectification; evolutionary algorithm; heuristics-based local permutation; magic square construction; mutation operator; number pair permutation; probability; recreational combinatorics; row permutation; row/column local rectification; stochastic mechanism; two-phase construction conjecture; Combinatorial mathematics; Computer science; Educational institutions; Evolutionary computation; Genetic mutations; History; Humans; Rivers; Software engineering; Stochastic processes;
Conference_Titel :
Evolutionary Computation, 2003. CEC '03. The 2003 Congress on
Print_ISBN :
0-7803-7804-0
DOI :
10.1109/CEC.2003.1299763