/ simple genetic algorithm

/ genetic search
G:{[t;p;m]Z::();E["",t;p;m]t(p,#t)_draw#t}

/ iterate over generations
E:{[t;p;m;a]while[~4:a:N[t;p;m]a;];a}

/ next generation
N:{[t;p;m;a]
 if[t _in a;:t]         / return match
 f:F[t]a                / fitness
 \*-1#Z,:(+/f)%#f       / average fitness (record, emit)
 j:(-1,_.5*p)#p _draw-p / mating pairs
 b:M[m;?t]''a[&K[p]f]j  / breeding population
 c:(#*j)_draw#t         / cross-over points
 ,/(H'[c-#t;c]). b}     / cross-over each pair

/ fitness
F:{[t;a](#t)%t L/:a}

/ levenshtein distance
L:{(#y)+*-1#{&\z,(1+1_ x)&(-1_ x)-y}/[&1+#y;x=\:y;1+!#x]}

/ survivals
K:{[p;d]
 k:{(@[x;i;+;n];y[i]-n:()_draw/:1+y i:&y>0)}
 *{p>+/*x}(k .)/(&#e;@[e;(#q)_draw-#e;+;q:(p-+/e:_ p*d%+/d)#1])}

/ crossover
H:{[a;b;x;y]((a#x),b#y;(a#y),b#x)}

/ mutation
M:{[m;u;a]
 i:&~(#a)_draw m
 v:u _dv/:a i
 j:(#i)_draw -1+#u
 @[a;i;:;v@'j]}

G["match this string";1000;10000]

\

/ genetic search
G:{[t;s;m;p;l]Z::();E[P D t;I P D s;m;p;l](p;l)_draw 2}

/ iterate over generations
E:{[t;s;m;p;l;a]while[~4:a:N[t;s;m;p;l]a;];a}

/ next generation
N:{[t;s;m;p;l;a]
 r:s{S::m;I_[x]y}/:a            / evaluate all 
 if[~#i:&~@:'r;:()]             / no terminations
 a@:i;r@:i                      / discard non-terminations
 if[t _in r;:C a r?t]           / return match
 f:F[t]r                        / fitness
 \*-1#Z,:(+/f)%#f               / average fitness (record, emit)
 m:(-1,_.5*p)#p _draw-p         / mating pairs
 b:a[&K[p]f]m                   / breeding population
 c:(#*m)_draw l                 / cross-over points
 ,/(H'[c-l;c]). b}              / cross-over each pair

/ fitness
F:{[t;r](#t)%(5:t)L/:5::'r}

/ levenshtein distance
L:{(#y)+*-1#{&\z,(1+1_ x)&(-1_ x)-y}/[&1+#y;x=\:y;1+!#x]}

/ survivals
K:{[p;d]
 k:{(@[x;i;+;n];y[i]-n:()_draw/:1+y i:&y>0)}
 *{p>+/*x}(k .)/(&#e;@[e;(#q)_draw-#e;+;q:(p-+/e:_ p*d%+/d)#1])}

/ crossover
H:{[a;b;x;y]((a#x),b#y;(a#y),b#x)}

/ mutation
M:{}

/ G["[1][0]";"[0][1]";100;1000;138]
/ G["[[0]]";"[0]";100;1000;10]
/ G["[0][1]";"[10]";100;1000;16]