Solving The Magic Square Problem Using Selection Hyper-heuristics

Selection hyper-heuristics are high-level optimisation strategies the aim of which is to increase the generality of optimisation solvers. These have recently attracted substantial attention and effort from researchers in numerous areas including, but not limited to, operational research, artificial intelligence, engineering and computer science. A Magic Square is a matrix of nxn dimension, which includes all the numbers in $\{$1, 2, $\ldots, n^{2}\}$ such that the sum of each row, column and main diagonal is equal. With large values of n, it’s shown that finding the optimal configuration is hard. This is defined as a minimisation problem that aims to optimise a measure of error that describes how far a given configuration is from being a magic square. In this study, we present the results of testing twenty hyper-heuristics on various instances of the magic square problem. The empirical results reveal that hyper-heuristics that utilise a reinforcement learning selection method outperform all other hyper-heuristics in this study. In particular, with the increase in the complexity of the problem, a hyper-heuristic utilising simulated annealing as solution acceptance method in addition to the reinforcement learning proves to be promising.