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.

  • GA - interface help
  • Genetic Algorithms Theory
  • should be an applet here

     

    Chromosome (genotype representation)


    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
       [ [11010][10110][00001][10100]    // 11 13 16  5
         [01100][11100][10000][11000]    //  6  7  1  3
         [01000][00010][10010][00110]    //  2  8  9 12
         [01110][00100][11110][01010] ]  // 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.

  • drawing the chromsome (phenotype representation)

    simple: integer representation of parameter = corresponding number in magic square;

    quality function

    The magic 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)