Research On Intelligent Computation Of Magic Square Problem

Based on the theory of the digital magic square lock, this thesis focuses on two problems: one is to search some fast construction algorithms for random magic squares, and the other is to search some algorithms to sovle the unfinished magic square with low rank.According to the demand of construction randomness and based on the idea of searching magic squares in the solution space, constructing a magic square with rank n in a computational way can be considered as a search procedure in a space with possible permutations of n~2 consecutive natural numbers, and hence transformed to an ordinary problem of combinatorial optimization, which can be figured out by the evolutional strategies. To improve the computational efficiency, the search order in the magic square, which is regarded as a multi-objective problem, has been studied and then three different magic square construction algorithms with different evolution orders are proposed; One is a hybrid type that evolves firstly in row, then in column and finally in diagonal asynchronously. Because heuristics is applied to the construction procedure, this algorithm can satisfy magic sum of each row, column and two main diagonals in a short time by means of the unitary zero setting operator as well as the binary zero setting operator. Experiments show that the hybrid evolutional algorithm is far more efficient than other two algorithms including evolving in row, column and diagonal simultaneously and evolving firstly in row and column and then in diagonal.To solve the unfinished magic square problem, the difficulties and obstacles in magic square can be exploited when systematic property and computational complexity are concerned. Starting with some established combinatorial algorithms related to the unfinished magic square problem, the combinatorial algorithm based on enumerating method is put forward, and an improved dynamic combinatorial algorithm is given. However, the combinatorial algorithm based on enumerating method is not capable of figuring out those massive problems, owing to that the enumerating method cannot solve the combinatorial explosion. Thus the intelligent optimization algorithm is brought forward to settle the unfinished magic square. Moreover, some methods and organizational structures are proposed to acquire the heuristic knowledge. Finally, based on the idea that an unfinished magic square problem can be solved as a Pareto optimum set, a novel clustering approach based on machine learning and statistic combination is proposed, and a hybrid optimization algorithmic framework combined with some intelligent algorithms is given, such as a Tabu search method and an immune algorithm.