Evolution of a Magic Square - Problem Info
The goal is to find a true magic square. That is the number from 1 to n^2 (n!=2) are
to be arranged within a n*n grid, in such a way that the all sums of all rows,
all sums of all columns and both sums of the diagonals yield the same value S.
chromosome (genotype representation)
// 4x4 magic square
double object_parameters[] = { 1 ,2 ,3 ,4,
5 ,6 ,7 ,8,
9 ,10,11,12,
13,14,15,16 };
double strategy_parameters[] = { 2,2,2,2,
2,2,2,2,
2,2,2,2,
2,2,2,2};
A problem_specific mutation-operator is used. It is based on swapping
object-parameters: For each chromosome to be 'mutated' the following process
is repeated X times (where X is the strategy_parameters value): A single object parameter is randomly chosen from the n^2 object-parameters. This object parameter is swapped with a second one. The second object parameter is (again) randomly chosen from the n^2 object-parameters, using the restriction that its value must be within a range of +- the first parameters strategy-parameter.
All strategy_parameters are equal. The strategy parameters are adapted. With equal probability they are increased by 1, decreased by 1 or kept as they are.
example:
let all startegy-parameters have a value of 2; => 2 swap-operations
1. swap
let the first selected object-parameter be number 6;
look for second object-parameter within range 4..8={4,5,6,7,8};
let the second selected object-parameter be number 7;
=> swap 6 and 7
2. swap
let the first selected object-parameter be number 16;
look for second object-parameter within range 14..18={14,15,16,17,18};
let the second selected object-parameter be number 15;
=> swap 16 and 15
Note that using recombination with this example will produce 'illegal' magic
squares and should NOT be used (see below: effect of crossover in GA-version) !
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)
applet parameters
- param name="n" value="4"
evolve a n*n magic square
10x10 magic square
