nx_evo_cross.nx source

1// nx_evo_cross.nx -- EVOLUTIONARY SYNTHESIS roadmap RUNG 1: CROSSOVER (X-AUT-006M). 2// 3// nx_evo_synth (006L) is a (1+lambda) ES: elite + mutants-of-the-ONE-best = a hill 4// climber that stalls in local optima (it left target 1000 at NEAR dist=15). This 5// organ is a real GENETIC ALGORITHM: a DIVERSE population, TOURNAMENT selection, and 6// ONE-POINT CROSSOVER (recombine two parents) + mutation + elitism. Crossover mixes 7// building blocks from different lineages, so the search escapes the basins that trap 8// the mutation-only climber. Same I/O + champion-materialization as 006L, so the two 9// are a head-to-head MEASURED-EXCEED pair. 10// 11// nx_evo_cross <champion_basename> <start> <target> <seed> 12// genome = EVO_L ops; pop EVO_P; gens EVO_G; tournament size EVO_T. Deterministic 13// seeded LCG. Prints FOUND/NEAR gen dist result genome; writes the DISCOVERED 14// champion organ (runtime/_hdl_build/<name>.nx) for compile+run verification. 15// 16// MEASURED-EXCEED gate (no-false-green): on a target the 006L baseline leaves NEAR 17// (e.g. 1000), this GA reaches dist=0 (FOUND) and the champion COMPILES+RUNS to the 18// target -- a measured improvement, pos vs the documented baseline NEAR. Sovereign, 19// no gcc/.sh. HONEST SCOPE: still linear op-list genomes / distance fitness; adds 20// crossover+tournament+diversity. license_tier: ORIGINAL 21import "nx_syscalls.nx" 22const EVO_MAGIC_2862933555777941757: i64 = 2862933555777941757 23const EVO_MAGIC_3037000493: i64 = 3037000493 24const EVO_MAGIC_2654435761: i64 = 2654435761 25const EVO_MAGIC_12345: i64 = 12345 26const EVO_MAGIC_1000000000: i64 = 1000000000 27const EVO_MAGIC_65536: i64 = 65536 28 29const EVO_L: i64 = 6 30const EVO_P: i64 = 64 31const EVO_G: i64 = 400 32const EVO_T: i64 = 4 // tournament size 33 34func evc_rand(state: *i64) -> i64 { 35 state[0] = state[0] * EVO_MAGIC_2862933555777941757 + EVO_MAGIC_3037000493 36 return (state[0] >> 17) & 0x3fffffff 37} 38func evc_abs(x: i64) -> i64 { if x < 0 { return 0 - x } return x } 39func evc_eval(pop: *i64, base: i64, start: i64) -> i64 { 40 var acc: i64 = start 41 var j: i64 = 0 42 while j < EVO_L { 43 let op: i64 = pop[base + j*2]; let n: i64 = pop[base + j*2 + 1] 44 if op == 0 { acc = acc + n } 45 if op == 1 { acc = acc * n } 46 if op == 2 { acc = acc - n } 47 j = j + 1 48 } 49 return acc 50} 51func evc_randfill(pop: *i64, base: i64, state: *i64) -> i64 { 52 var j: i64 = 0 53 while j < EVO_L { pop[base + j*2] = evc_rand(state) % 3; pop[base + j*2 + 1] = (evc_rand(state) % 9) + 1; j = j + 1 } 54 return 0 55} 56// tournament selection: best (min distance) of EVO_T random individuals. 57func evc_tourney(fit: *i64, state: *i64) -> i64 { 58 var bi: i64 = evc_rand(state) % EVO_P 59 var bd: i64 = fit[bi] 60 var k: i64 = 1 61 while k < EVO_T { let i: i64 = evc_rand(state) % EVO_P; if fit[i] < bd { bd = fit[i]; bi = i } k = k + 1 } 62 return bi 63} 64func evc_cat(dst: *u8, off: i64, s: *u8) -> i64 { var i: i64 = 0; while s[i] != (0 as u8) { dst[off+i] = s[i]; i = i + 1 } return off + i } 65func evc_catn(dst: *u8, off: i64, v: i64) -> i64 { 66 var o: i64 = off 67 if v < 0 { dst[o] = 45 as u8; o = o + 1; return evc_catn(dst, o, 0 - v) } 68 if v == 0 { dst[o] = 48 as u8; return o + 1 } 69 var m: i64 = v; let t: *u8 = sys_mmap(28); var k: i64 = 0 70 while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 } 71 var i: i64 = 0 72 while i < k { dst[o+i] = t[k-1-i]; i = i + 1 } 73 return o + k 74} 75func evc_p(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 } 76func evc_atoi(s: *u8) -> i64 { 77 var n: i64 = 0; var i: i64 = 0; var neg: i64 = 0 78 if s[0] == (45 as u8) { neg = 1; i = 1 } 79 while s[i] != (0 as u8) { if s[i] >= (48 as u8) { if s[i] <= (57 as u8) { n = n * 10 + ((s[i] as i64) - 48) } } i = i + 1 } 80 if neg == 1 { return 0 - n } 81 return n 82} 83 84func main(argc: i64, argv: *i64) -> i64 { 85 if argc < 5 { evc_p("usage: nx_evo_cross <champion_basename> <start> <target> <seed>\n" as *u8); return 2 } 86 let base_name: *u8 = argv[1] as *u8 87 let start: i64 = evc_atoi(argv[2] as *u8) 88 let target: i64 = evc_atoi(argv[3] as *u8) 89 let seed: i64 = evc_atoi(argv[4] as *u8) 90 91 let state: *i64 = sys_mmap(8) as *i64 92 state[0] = seed * EVO_MAGIC_2654435761 + EVO_MAGIC_12345 93 94 let glen: i64 = EVO_L * 2 95 let pop: *i64 = sys_mmap(EVO_P * glen * 8) as *i64 96 let nxt: *i64 = sys_mmap(EVO_P * glen * 8) as *i64 97 let fit: *i64 = sys_mmap(EVO_P * 8) as *i64 98 let best: *i64 = sys_mmap(glen * 8) as *i64 99 100 var p: i64 = 0 101 while p < EVO_P { evc_randfill(pop, p * glen, state); p = p + 1 } 102 103 var best_dist: i64 = EVO_MAGIC_1000000000 104 var best_gen: i64 = 0 - 1 105 var best_res: i64 = 0 106 var found: i64 = 0 107 var g: i64 = 0 108 while g < EVO_G { 109 // evaluate 110 var gbest_d: i64 = EVO_MAGIC_1000000000; var gbest_p: i64 = 0 111 p = 0 112 while p < EVO_P { 113 let r: i64 = evc_eval(pop, p * glen, start) 114 let d: i64 = evc_abs(r - target) 115 fit[p] = d 116 if d < gbest_d { gbest_d = d; gbest_p = p } 117 p = p + 1 118 } 119 if gbest_d < best_dist { 120 best_dist = gbest_d 121 var j: i64 = 0 122 while j < glen { best[j] = pop[gbest_p * glen + j]; j = j + 1 } 123 best_gen = g; best_res = evc_eval(best, 0, start) 124 } 125 if best_dist == 0 { found = 1; g = EVO_G } else { 126 // next generation: elitism slot 0 = best; rest = crossover(tournament,tournament)+mutate 127 var j2: i64 = 0 128 while j2 < glen { nxt[j2] = best[j2]; j2 = j2 + 1 } 129 p = 1 130 while p < EVO_P { 131 let pa: i64 = evc_tourney(fit, state) * glen 132 let pb: i64 = evc_tourney(fit, state) * glen 133 let cut: i64 = (evc_rand(state) % (EVO_L - 1)) + 1 // 1..L-1 134 var jj: i64 = 0 135 while jj < EVO_L { 136 if jj < cut { 137 nxt[p*glen + jj*2] = pop[pa + jj*2]; nxt[p*glen + jj*2 + 1] = pop[pa + jj*2 + 1] 138 } else { 139 nxt[p*glen + jj*2] = pop[pb + jj*2]; nxt[p*glen + jj*2 + 1] = pop[pb + jj*2 + 1] 140 } 141 jj = jj + 1 142 } 143 // mutate the child (single point) 144 let mi: i64 = evc_rand(state) % EVO_L 145 if (evc_rand(state) % 2) == 0 { nxt[p*glen + mi*2] = evc_rand(state) % 3 } else { nxt[p*glen + mi*2 + 1] = (evc_rand(state) % 9) + 1 } 146 p = p + 1 147 } 148 // swap pop <- nxt 149 var c: i64 = 0 150 while c < EVO_P * glen { pop[c] = nxt[c]; c = c + 1 } 151 g = g + 1 152 } 153 } 154 155 if found == 1 { evc_p("EVO-X FOUND gen=" as *u8) } else { evc_p("EVO-X NEAR gen=" as *u8) } 156 let lb: *u8 = sys_mmap(64); var lo: i64 = 0 157 lo = evc_catn(lb, 0, best_gen); sys_write(1, lb, lo) 158 evc_p(" dist=" as *u8); lo = evc_catn(lb, 0, best_dist); sys_write(1, lb, lo) 159 evc_p(" result=" as *u8); lo = evc_catn(lb, 0, best_res); sys_write(1, lb, lo) 160 evc_p(" target=" as *u8); lo = evc_catn(lb, 0, target); sys_write(1, lb, lo) 161 evc_p(" genome=" as *u8) 162 var jg: i64 = 0 163 while jg < EVO_L { 164 let op: i64 = best[jg*2]; let n: i64 = best[jg*2+1] 165 if op == 0 { evc_p("a" as *u8) } else { if op == 1 { evc_p("m" as *u8) } else { evc_p("s" as *u8) } } 166 lo = evc_catn(lb, 0, n); sys_write(1, lb, lo); evc_p(" " as *u8) 167 jg = jg + 1 168 } 169 evc_p("\n" as *u8) 170 171 // materialize the discovered champion as a real sovereign organ 172 let path: *u8 = sys_mmap(512); var po: i64 = 0 173 po = evc_cat(path, po, "runtime/_hdl_build/" as *u8); po = evc_cat(path, po, base_name); po = evc_cat(path, po, ".nx" as *u8); path[po] = 0 as u8 174 let buf: *u8 = sys_mmap(EVO_MAGIC_65536); var o: i64 = 0 175 o = evc_cat(buf, o, "// DISCOVERED BY nx_evo_cross (evolutionary synthesis w/ crossover) -- op-list FOUND by search, not hand-written. license_tier: ORIGINAL\n" as *u8) 176 o = evc_cat(buf, o, "import \"nx_syscalls.nx\"\nfunc main() -> i64 {\n var acc: i64 = " as *u8); o = evc_catn(buf, o, start); o = evc_cat(buf, o, "\n" as *u8) 177 jg = 0 178 while jg < EVO_L { 179 let op: i64 = best[jg*2]; let n: i64 = best[jg*2+1] 180 o = evc_cat(buf, o, " acc = acc " as *u8) 181 if op == 0 { o = evc_cat(buf, o, "+ " as *u8) } else { if op == 1 { o = evc_cat(buf, o, "* " as *u8) } else { o = evc_cat(buf, o, "- " as *u8) } } 182 o = evc_catn(buf, o, n); o = evc_cat(buf, o, "\n" as *u8) 183 jg = jg + 1 184 } 185 o = evc_cat(buf, o, " sys_write(1, \"RESULT=\" as *u8, 7)\n var mm: i64 = acc\n if mm < 0 { sys_write(1, \"-\" as *u8, 1); mm = 0 - mm }\n let t: *u8 = sys_mmap(28)\n var k: i64 = 0\n if mm == 0 { t[0] = 48 as u8; k = 1 }\n while mm > 0 { t[k] = (48 + (mm % 10)) as u8; mm = mm / 10; k = k + 1 }\n while k > 0 { k = k - 1; sys_write(1, (((t as i64)+k) as *u8), 1) }\n sys_write(1, \"\\n\" as *u8, 1)\n return 0\n}\n" as *u8) 186 let fd: i64 = sys_openat_wr(path, 420) 187 if fd < 0 { evc_p("EVO-X verdict=RED reason=champion-unwritable\n" as *u8); return 1 } 188 sys_write(fd, buf, o); sys_close(fd) 189 evc_p("EVO-X champion written: " as *u8); evc_p(path); evc_p("\n" as *u8) 190 return 0 191}