An evolutionary algorithm for magic squares

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 n² 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.