Evolving a Magic Square using Genetic Algorithms
The goal is to arrange the numbers from 1 to N^2 within a NxN grid in such a way that the sum of all rows, the sum of all columns and the sums of both diagonals become equal, i.e. the goal is to find a true magic square.
The magic square is encoded using an array of n*n bitvectors each with a size of ceil(ld(n*n)).
// 4x4 magic square numbers 1..16 <-> 10000..00001 i.e. bit-order 01234 [  // 11 13 16 5  // 6 7 1 3  // 2 8 9 12  ] // 14 4 15 10
A problem-specific crossover-operator is used which could be refered to as permutation operator. The operator is unary. That is each of the two crossover partners is handled individually. If m is the number of crossover-points than the specific crossover operator simply 'swaps' m pairs of values thus producing another permutation of 1..n^2 (n × n magic square).
A repair-operator is used. If used, the mutation operator will lead to 'illegal' magic squares. That is, the magic squares contain a single number more that once or don't contain it at all. Additionally it may produce 'out of range'-values i.e. values smaller than 1 or bigger than n^2. Thus after crossover and mutation a repair operator is used to produce 'well shaped' magic squares again.
First the 'out of range'-values are detected and set to 1 if they are smaller than 1 and set to n^2 if they are bigger than n^2. Second we count how often each of the numbers from 1 to n^2 is contained in the magic square. As long as the magic square contains numbers more than once we randomly replace single occurences of these numbers with (randomly chosen) numbers that are not contained in the magic square.
simple: integer representation of parameter = corresponding number in magic square;
sum S is 0.5*n*(n^2-1). For each row, column and diagonal the squared difference
of its sum and the magic sum is added to the quality. Which results in the
chromosomes quality value.
quality=0; for each row s=get_sum( row ) quality = quality + (S-s)*(S-s) for each column s=get_sum( column ) quality = quality + (S-s)*(S-s) s=get_sum( first_diagonal ) quality = quality + (S-s)*(S-s) s=get_sum( second_diagonal ) quality = quality + (S-s)*(S-s)