Sorting out Creationism

I told you there's no end to tweaking a Genetic Algorithm. As it is, the program is not very powerful; it cannot find minimal networks of width 7:

% ./ganet -width 7 -pool 100 -seed 11
Searching for a 7-network of size 16 and depth 6 (fitness = 34.00000)
      1 act =  3.00%, avg = 8.66667, max = 10.00000 (39/24)
      2 act =  4.00%, avg = 9.25000, max = 11.00000 (38/23)
      3 act =  6.00%, avg = 9.00000, max = 13.00000 (36/21)
     10 act = 21.00%, avg = 8.95238, max = 14.00000 (35/25)
     21 act = 48.00%, avg = 10.60417, max = 16.00000 (33/21)
     32 act = 53.00%, avg = 11.16981, max = 17.00000 (32/20)
     45 act = 53.00%, avg = 14.47170, max = 18.00000 (31/20)
     46 act = 54.00%, avg = 14.68519, max = 20.00000 (29/18)
     53 act = 61.00%, avg = 15.31148, max = 21.00000 (28/20)
     62 act = 65.00%, avg = 17.21538, max = 23.00000 (26/16)
     77 act = 70.00%, avg = 20.44286, max = 24.00000 (25/14)
     78 act = 69.00%, avg = 21.08696, max = 26.00000 (23/14)
     84 act = 66.00%, avg = 22.22727, max = 27.00000 (22/11)
     91 act = 77.00%, avg = 23.89610, max = 28.00000 (21/10)
     92 act = 74.00%, avg = 23.98649, max = 29.00000 (20/11)
     97 act = 75.00%, avg = 25.33333, max = 30.00000 (19/10)
    111 act = 82.00%, avg = 27.89024, max = 31.00000 (18/10)
    137 act = 84.00%, avg = 30.30952, max = 32.00000 (17/10)
^CInterrupted.

0:2;2:4,3:5;3:6;4:6,1:5,0:3;3:4,1:2;2:3;3:5,0:1;3:4,1:2,5:6;4:5,2:3
Solution in 13781 rounds with fitness 32.000000
Found a 7-network of size 17 and depth 9

There are a number of things that can be changed, beyond the command-line parameters. Mind you, these are important, especially the pool size: too large a pool, and evaluation will spend all your patience; too little, and the population gets stuck on a local maximum. Beyond that, it's code intervention time.

The first weak spot is the fitness evaluation function. My original intent was to give absolute priority to network size, and then to network depth; in other words, fitness(s, d) < fitness(s′, d′)   ⇔   s < s′  ∨  s = s′ ∧ d < d′. This is restrictive, because a reduction in depth may trigger a further reduction in size. A more graded fitness measure rewards reductions both in size and depth, even if that means that your GA spends a little more optimizing the latter.

let target_fitness (size, depth) =
  let size, depth = float size, float depth in
  let overhead = size +. depth /. size in
  overhead /. (overhead -. 1.)

The idea is to compute a penalty score comprised of a whole point per size, and a fraction of a size per level, so that a worst-case O(n²) network is not as bad as a great (n + 1)-level sorter, preserving monotonicity. Since in this program, a fitter individual has a greater score, and individuals that sort, I use inversion to change the overhead into a fitness value. As you can see, this value is the nearer to one the larger the network is:

# Array.map (fun (s,_,d) -> target_fitness (s,d)) known_best_bounds ;;
- : float array =
[|nan; nan; 2.; 1.33333333333333326; 1.21739130434782616;
  1.11688311688311681; 1.08759124087591252; 1.06504065040650397;
  1.05459770114942519; 1.04118616144975284; 1.03540903540903551;
  1.02921535893155269; 1.02617449664429539; 1.02262443438914019;
  1.01992966002344665; 1.01812884428617667; 1.01690617075232459|]

(the first two positions make no sense, and are only sentinels). With that change, the GA progresses a bit further:

% ./ganet -width 7 -pool 100 -seed 11
Searching for a 7-network of size 16 and depth 6 (fitness = 1.06504)
      1 act =  3.00%, avg = 1.02506, max = 1.02590 (39/24)
      2 act =  4.00%, avg = 1.02545, max = 1.02659 (38/23)
⟨…22 lines deleted…⟩
    160 act = 73.00%, avg = 1.04722, max = 1.05751 (18/ 7)
    189 act = 85.00%, avg = 1.05599, max = 1.06093 (17/ 7)
^CInterrupted.

0:6,2:5,3:4;2:3,4:6,0:1;5:6,0:2,1:3;1:2,3:5;3:4;2:3,4:5;5:6,1:2,3:4
Solution in 47744 rounds with fitness 1.060932
Found a 7-network of size 17 and depth 7

But not enough to reach the target fitness. Some other idea is needed, and it is to actually respect the definition of Microbial Tournament laid out by Inman Harvey. His method matches up individuals a pair at a time, not the entire population at once. This requires more iterations, but each one involves a single mating, so the efficiency of doing pair-at-a-time tournaments is mostly the same. First, I need a way to draw a pair of individuals at random, uniformly form the population. The twist is that I must not pit an individual against itself:

let random_disjoint_pair n =
  let i = Random.int n in
  let j = Random.int (pred n) in
  if i > j then (i, j) else (i, succ j)

To draw a random disjoint pair 0 ≤ i ≠ j < n with uniform probabilities, it's best to treat the problem as if it were an urn drawing without replacement. In contrast to the generation of ordered pairs, this makes it easy to select both members of such a non-diagonal pair with exactly uniform probabilities: select 0 ≤ i < n with uniform probability 1/n. This leaves n - 1 possibilities for j: draw it from the set 0 ≤ j < n - 1 with uniform probability 1/(n - 1). If j ≥ i, bump j up by one to simulate the "hole" left behind by the drawing of i. With that, the tournament proceeds not in block, but pair by pair:

let tournament fitness p =
  let iter = ref 0
  and last = ref 0. in
  Sys.catch_break true;
  begin try while p.best.score < fitness do
    (* Only this line changes! *)
    microbial_tournament p (random_disjoint_pair !pool_size);
    incr iter;
    if 1. <= p.best.score && !last < p.best.score then begin
      let (s, d) = count_genes p.best.genes in
      last := p.best.score;
      let sum, act = Array.fold_left (fun (s, n as p) g ->
        if g.score < 1. then p else (s +. g.score, succ n))
        (0., 0) p.pool in
      Printf.fprintf stderr "%7d act = %5.2f%%, avg = %7.5f, max = %7.5f (%2d/%2d)\n"
        !iter
        (100. *. float act /. float !pool_size)
        (sum /. float act)
        !last
        s d;
      flush stderr
    end
  done with Sys.Break -> prerr_endline "Interrupted.\n" end;

That's it, just one line. Let's try it:

% ./ganet -width 7 -pool 100 -seed 11
Searching for a 7-network of size 16 and depth 6 (fitness = 1.06504)
      1 act =  3.00%, avg = 1.02506, max = 1.02590 (39/24)
    174 act =  7.00%, avg = 1.02528, max = 1.02727 (37/25)
⟨…30 lines deleted…⟩
  11019 act = 82.00%, avg = 1.05993, max = 1.06478 (16/ 7)
 171081 act = 86.00%, avg = 1.06386, max = 1.06504 (16/ 6)
4:6,2:5,1:3;3:6,1:4,0:2;2:3,0:1,5:6;1:2,4:5;3:5,2:4;3:4,1:2,5:6
Solution in 171081 rounds with fitness 1.065041
Found a 7-network of size 16 and depth 6

Success! It takes a while to shave off the last level, but it does. Note how the percent of active individuals (that is, those that actually sort) climb up as the fitness of the best network approaches the target. The downside of this is that the fact that the GA found a network at all is somewhat of a fluke; smaller or larger pools still make finding a minimal network a hit-and-miss proposition. The last level is the hardest, which is an indication that there is a local minimum that is hard to break out of. For instance, for a smaller pool I had to also change the seed in order to find a solution:

% ./ganet -width 7 -pool 49 -seed 12
Searching for a 7-network of size 16 and depth 6 (fitness = 1.06504)
      1 act =  8.16%, avg = 1.02612, max = 1.02799 (36/26)
     55 act = 14.29%, avg = 1.02624, max = 1.02804 (36/24)
⟨…27 lines deleted…⟩
   6852 act = 87.76%, avg = 1.06048, max = 1.06478 (16/ 7)
 106973 act = 87.76%, avg = 1.06390, max = 1.06504 (16/ 6)
2:5,0:6,1:3;3:5,1:4,0:2;2:4,0:1,5:6;3:5,1:2;2:3,4:5;5:6,3:4,1:2
Solution in 106973 rounds with fitness 1.065041
Found a 7-network of size 16 and depth 6

The time to hone into a 16-step solution was quicker, but the time needed to reduce the depth took another order of magnitude like before. A smaller yet pool shows an interesting fact: if the entire population is made of proper sorters, it will be difficult to find in the gene pool a variation that would lead to a smaller sorter. Note how the fraction of active networks remains high throughout:

% ./ganet -width 7 -pool 10 -seed 1
Searching for a 7-network of size 16 and depth 6 (fitness = 1.06504)
     46 act =  10.00%, avg = 1.02519, max = 1.02519 (40/28)
     57 act =  30.00%, avg = 1.02519, max = 1.02520 (40/27)
⟨…22 lines deleted…⟩
   1416 act = 100.00%, avg = 1.04621, max = 1.04651 (22/11)
   1551 act = 100.00%, avg = 1.04672, max = 1.04872 (21/11)
   1936 act =  80.00%, avg = 1.04874, max = 1.05115 (20/11)
   2376 act = 100.00%, avg = 1.05139, max = 1.05382 (19/11)
   2458 act =  90.00%, avg = 1.05384, max = 1.05398 (19/10)
   2569 act =  80.00%, avg = 1.05402, max = 1.05714 (18/ 9)
   2585 act = 100.00%, avg = 1.05528, max = 1.05751 (18/ 7)
 110511 act = 100.00%, avg = 1.05749, max = 1.06071 (17/ 8)
 257925 act =  70.00%, avg = 1.06126, max = 1.06452 (16/ 8)
 673211 act = 100.00%, avg = 1.06167, max = 1.06478 (16/ 7)
3081061 act =  70.00%, avg = 1.06370, max = 1.06504 (16/ 6)
0:1,2:4,5:6;4:6,2:5,1:3;1:2,0:5,3:6;0:1,3:5,2:4;3:4,1:2;2:3,4:5
Solution in 3081061 rounds with fitness 1.065041
Found a 7-network of size 16 and depth 6

Which indicates that the smaller the pool the larger should be the mutation probability, but this entails a danger of the algorithm devolving into a pure random search. Notwithstanding that, the genetic probabilities crossover_rate and mutation_rate should be run-time-settable parameters. In fact, even the selection of a random seed is harder than it should be: most of the time I want to explore different pool sizes but I'd rather not think of random seeds to give the program.

Now, with all those changes selecting values for the parameters is a random search of itself; however, the value act is a good indicator of the population health, ironically enough:

% ./ganet -w 7 -p 100 -s 0 -m 0.03 -x 0.8
Random seed: 774730236
Searching for a 7-network of size 16 and depth 6 (fitness = 1.06504)
      1 act =   2%, avg = 1.02430, max = 1.02460 (41/27)
     20 act =   3%, avg = 1.02506, max = 1.02657 (38/24)
⟨…30 lines deleted…⟩
   5570 act =  66%, avg = 1.05069, max = 1.06050 (17/ 9)
   6333 act =  66%, avg = 1.05344, max = 1.06071 (17/ 8)
  16773 act =  65%, avg = 1.05829, max = 1.06093 (17/ 7)
 143494 act =  68%, avg = 1.05764, max = 1.06115 (17/ 6)
 146242 act =  66%, avg = 1.05825, max = 1.06504 (16/ 6)
1:5,4:6,2:3;0:4,1:2,3:6;2:4,0:1,3:5;4:5,1:3;4:6,2:3;3:4,1:2,5:6
Solution in 146242 rounds with fitness 1.065041
Found a 7-network of size 16 and depth 6

(this is with a modified version that makes all parameters settable through command line options). It is evident that, with the high churn rate implied by a mutation rate of 3% even with a high rate of copying of 80%, the search proceeds rather quickly by minimizing depth before length. In a sense, it is necessary to intervene heavily in the design of a GA experiment if it is to have even a modest chance of success.