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
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.
simple:
integer representation of parameter = corresponding number in magic square;
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)