Contest Analysis

• Mid-Contest Analysis, Lucio Cetto
• Final Analysis, Lucio Cetto
• Contest Evolution, Matthew Simoneau
• Contest Winners, Min Poh

Mid-Contest Analysis

Contents

Small problem with exact solution

When the size of the matrix is small, the snake algorithms do well. This is generally the case for all the small problems in the test suite.

load testsuite_sample

M=testsuite(3).map;
N=testsuite(3).n;
S = [3     3     3     4     4     1     1
     3     3     3     4     1     1     1
     3     3     4     4     1     1     1
     2     2     5     5     5     5     5
     2     2     5     5     5     5     5
     2     2     5     5     5     5     5];

mat3d(s16527(M,N),M,[0 0 200 200],0.8)
axis off; view([30 25]);
title({'''Mg3Si2O5(OH)4''';'by GreatRumpuscat'})

figure
mat3d(s16762(M,N),M,[0 0 200 200],0.8)
axis off; view([30 25]);
title('''Kristine'' by Klaas Hartmann')

figure
mat3d(s16762(M,N),M,[0 0 200 200],0.8)
axis off; view([30 25]);
title('''Kopt Kristine 1'' by MR Keenan')

figure
mat3d(s17321(M,N),M,[0 0 200 200],0.8)
axis off; view([30 25]);
title({'''yet another pattern 3a3b54 cy14''';'by christian ylamaki'})

Simple case not caught by any algorithm

This example has an exact solution that no algorithm (so far) detects.

S = [ 1 1 1 1 1 1 1 2 2 2 2 2 2
      1 1 1 1 1 1 1 2 2 2 2 2 2
      1 1 1 1 1 1 1 2 2 2 2 2 2
      1 1 1 1 1 1 1 2 2 2 2 2 2
      1 1 1 1 1 1 1 2 2 2 2 2 2
      3 3 3 3 4 4 4 2 2 2 2 2 2
      3 3 3 3 4 4 4 2 2 2 2 2 2
      3 3 3 3 4 4 4 2 2 2 2 2 2
      3 3 3 3 5 5 5 5 5 5 5 5 5
      3 3 3 3 5 5 5 5 5 5 5 5 5
      3 3 3 3 5 5 5 5 5 5 5 5 5
      3 3 3 3 5 5 5 5 5 5 5 5 5];
N = 5;
M = zeros(size(S));
for i=1:N,
    m= (S==i);
    M(m) = (pi^9)/sum(m(:));
end

figure
mat3d(S,M,[0 0 400 300],.9)
axis off; view([30 25]);
title({'Exact solution';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s16527(M,N);
mat3d(S,M,[0 0 400 300],0.95)
axis off; view([30 25]);
title({'Mg3Si2O5(OH)4';'by GreatRumpuscat';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s16762(M,N);
mat3d(S,M,[0 0 400 300],0.95)
axis off; view([30 25]);
title({'Kristine by Klaas Hartmann';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s16762(M,N);
mat3d(S,M,[0 0 400 300],0.95)
axis off; view([30 25]);
title({'Kopt Kristine 1 by MR Keenan';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s17321(M,N);
mat3d(S,M,[0 0 400 300],0.95)
axis off; view([30 25]);
title({'yet another pattern 3a3b54 cy14';'by christian ylamaki';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

s =

  307.5542

Non-convex district areas

This is similar to the last example, but with non-convex districts. A growing algorithm may find this partition, whereas the snake approach never will.

S = [ 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2
      1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 4 4 4
      5 5 5 5 4 4 1 1 1 3 3 3 3 3 2 2 4 4 4
      5 5 5 5 4 4 1 1 1 3 3 3 3 3 2 2 4 4 4
      5 5 5 5 4 4 1 1 1 3 3 3 3 3 1 1 4 4 4
      5 5 4 4 4 4 1 1 1 3 3 3 3 3 1 1 4 6 6
      5 5 4 4 4 4 1 1 1 1 1 1 1 1 1 1 4 6 6
      5 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 4 6 6
      5 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 4 6 6];
N = 6;
M = zeros(size(S));
for i=1:N,
    m= (S==i);
    M(m) = 333/sum(m(:));
end

figure
mat3d(S,M,[0 0 400 300],.9)
axis off; view([30 25]);
title({'Exact solution';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s16527(M,N);
mat3d(S,M,[0 0 400 300],0.95)
axis off; view([30 25]);
title({'Mg3Si2O5(OH)4';'by GreatRumpuscat';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s16762(M,N);
mat3d(S,M,[0 0 400 300],0.95)
axis off; view([30 25]);
title({'Kristine by Klaas Hartmann';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s16762(M,N);
mat3d(S,M,[0 0 400 300],0.95)
axis off; view([30 25]);
title({'Kopt Kristine 1 by MR Keenan';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s17321(M,N);
mat3d(S,M,[0 0 400 300],0.95)
axis off; view([30 25]);
title({'yet another pattern 3a3b54 cy14';'by christian ylamaki';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

Randomly created partition

We created an algorithm which creates random partitions. Then we populated each partition with exactly equal groups. Even though the regions are usually convex, the current algorithms have a hard time finding the optimal solution.

load example1

figure
mat3d(flipud(S),flipud(M),[0 0 400 300],.9)
axis off; view([30 25]);
title({'Exact solution';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s16527(M,N);
mat3d(flipud(S),flipud(M),[0 0 400 300],0.98)
axis off; view([30 25]);
title({'Mg3Si2O5(OH)4';'by GreatRumpuscat';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s16762(M,N);
mat3d(flipud(S),flipud(M),[0 0 400 300],0.98)
axis off; view([30 25]);
title({'Kristine by Klaas Hartmann';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s16762(M,N);
mat3d(flipud(S),flipud(M),[0 0 400 300],0.98)
axis off; view([30 25]);
title({'Kopt Kristine 1 by MR Keenan';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s17321(M,N);
mat3d(flipud(S),flipud(M),[0 0 400 300],0.98)
axis off; view([30 25]);
title({'yet another pattern 3a3b54 cy14';'by christian ylamaki';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

Published with MATLAB® 7.0