A Family Portrait

I succeeded in finding a minimal 8-element sorting network with 19 comparators grouped in 6 stages. For that, I needed a change in my fitness evaluation function to reflect an insight I had while preparing the last post. My original fitness evaluator was monotone first on size and then on depth, so that fitness(s, d) < fitness(s′, d′)   ⇔   s < s′  ∨  s = s′ ∧ d < d′. It is, I found experimentally, reward more shallower than shorter networks, so that fitness(s, d) < fitness(s′, d′)   ⇔   d < d′  ∨  d = d′ ∧ s < s′. For that, note that 0 < d ≤ s, so that 0 < d/s ≤ 1, or 0 ≤ 1 - d/s < 1, and so d + 1 - d/s is monotone as required. To convert a decreasing "penalty" into an increasing fitness, I use the mapping I showed the last time, x → x/(x - 1):

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

(the entire program, minus comments, is available as a paste in OCaml Forge). This means that, sometimes, in order to decrease depth a larger network would be chosen as the winner of the tournament, but that is, apparently, the key to a successful search. With that, here are some minimal networks of order up to 8:

1. Minimal network of width 3, size 3 and depth 3 (ganet -w 3 -s 2 -x 0.8 -m 0.5)
2. Minimal network of width 4, size 5 and depth 3 (ganet -w 4 -s 1 -x 0.8 -m 0.05)
3. Minimal network of width 5, size 9 and depth 5 (ganet -w 5 -s 1 -x 0.8 -m 0.05)
4. Minimal network of width 6, size 12 and depth 5 (ganet -w 6 -s 1 -x 0.8 -m 0.05)
5. Minimal network of width 7, size 16 and depth 6 (ganet -w 7 -p 100 -s 1 -x 0.8 -m 0.05)
6. Minimal network of width 8, size 19 and depth 6 (ganet -w 8 -p 640 -s 128 -x 0.9 -m 0.09)