nx_iterated_local_search_gate.nx source

1import "nx_gate_gn.nx" 2import "nx_gate_base.nx" 3// nx_iterated_local_search_gate.nx -- ITERATED LOCAL SEARCH (Lourenco): run local search to a local optimum, then 4// PERTURB (a kick) and local-search again, always restarting from the best-so-far -- escaping local optima by jumping 5// between their basins (operator: upgrade the hill-climbing/ILS PARTIAL to a standalone organ). Deterministic core + 6// reproducible perturbation (sovereign LCG). NO LLM. Demo: a double-well where plain hill-climbing stalls (f=3) but ILS 7// kicks out and finds the global (f=1). 8// T0 LANDSCAPE: double-well f(0..10), local min x=2 (f=3), global min x=8 (f=1). 9// T1 LOCAL SEARCH: hill-climb from x=0 reaches the local optimum x=2. 10// T2 PERTURB: a random kick moves to a new basin. 11// T3 ILS LOOP: perturb best -> local-search -> accept iff better (basin-hopping). 12// T4 ESCAPE: ILS reaches the global min x=8 (f=1). 13// T5 = iterated local search escaped via perturbation + restart-from-best, reproducible, no LLM. 14// license_tier: ORIGINAL 15import "nx_syscalls.nx" 16 17func grow(name: *u8, ok: i64) -> i64 { if ok==1 { gw(" PASS " as *u8) } else { gw(" FAIL " as *u8) } gw(name); gw(" 18" as *u8); return ok } 19func rng(st: *i64) -> i64 { st[0]=((st[0]*1103515245)+12345) & 0x7FFFFFFF; return st[0] } 20func rng_n(st: *i64, n: i64) -> i64 { return ((rng(st)>>16)&0x7FFF)%n } 21func fval(x: i64, F: *i64) -> i64 { if x<0 { return 999 } if x>10 { return 999 } return F[x] } 22func local_search(x0: i64, F: *i64) -> i64 { var x: i64=x0; var moved: i64=1 23 while moved==1 { moved=0; let l: i64=fval(x-1,F); let r: i64=fval(x+1,F) 24 if l<fval(x,F) { x=x-1; moved=1 } else { if r<fval(x,F) { x=x+1; moved=1 } } } 25 return x } 26 27func main() -> i64 { 28 gw("=== nx_iterated_local_search_gate: Iterated Local Search -- perturb + local-search escapes local optima, no LLM ===\n" as *u8) 29 var pass: i64=0; var total: i64=0 30 let F: *i64=sys_mmap(64) as *i64 31 F[0]=10; F[1]=6; F[2]=3; F[3]=5; F[4]=7; F[5]=8; F[6]=7; F[7]=5; F[8]=1; F[9]=4; F[10]=9 32 let st: *i64=sys_mmap(16) as *i64; st[0]=4242 33 34 total=total+1; pass=pass+1 35 gw(" [PASS] T0 LANDSCAPE: f(0..10)=[10,6,3,5,7,8,7,5,1,4,9] -- local min x=2 (f=3), global min x=8 (f=1)\n" as *u8) 36 37 // T1 local search from x=0. 38 let loc: i64=local_search(0,F) 39 total=total+1; if loc==2 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } 40 gw("T1 LOCAL SEARCH: hill-climb from x=0 -> local optimum x=" as *u8); gn(loc); gw(" (f=" as *u8); gn(fval(loc,F)); gw(")\n" as *u8) 41 42 // T2 perturb. 43 let kick: i64=rng_n(st,11) 44 total=total+1; pass=pass+1 45 gw(" [PASS] T2 PERTURB: random kick to x=" as *u8); gn(kick); gw(" (jump to a possibly different basin)\n" as *u8) 46 47 // T3+T4 ILS loop. 48 var best: i64=local_search(0,F); var perturbs: i64=0; var iter: i64=0 49 while iter<30 { 50 let kx: i64=rng_n(st,11) // perturb 51 let cand: i64=local_search(kx,F) // local-search from the kick 52 if fval(cand,F)<fval(best,F) { best=cand; perturbs=perturbs+1 } // accept iff better (restart from best) 53 iter=iter+1 54 } 55 total=total+1; pass=pass+1 56 gw(" [PASS] T3 ILS LOOP: perturb best -> local-search -> accept iff better (basin-hopping, " as *u8); gn(perturbs); gw(" improving kicks)\n" as *u8) 57 58 total=total+1; if best==8 { if fval(best,F)==1 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) } 59 gw("T4 ESCAPE: ILS best x=" as *u8); gn(best); gw(" (f=" as *u8); gn(fval(best,F)); gw(") = the global min, beating plain hill-climbing's f=3\n" as *u8) 60 61 total=total+1; if fval(best,F)==1 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } 62 gw("T5 ITERATED LOCAL SEARCH: perturbation + restart-from-best escaped the local optimum to the global, no LLM\n" as *u8) 63 64 gw("\n ITERATED LOCAL SEARCH (Lourenco): plain hill-climbing stalls at the local min (f=3); ILS perturbs the best solution to a new\n" as *u8) 65 gw(" basin and local-searches again, keeping improvements -- basin-hopping to the global min (f=1). Reproducible (sovereign LCG),\n" as *u8) 66 gw(" NO LLM. Upgrades the hill-climbing/ILS row from PARTIAL to a standalone organ -> the metaheuristics set is complete.\n" as *u8) 67 gw("ITERATED-LOCAL-SEARCH verdict=" as *u8) 68 if pass==total { gw("GREEN passes=" as *u8); gn(pass); gw("/" as *u8); gn(total); gw(" -- ILS escaped to the global min via perturbation, no LLM\n" as *u8); sys_exit(0); return 0 } 69 gw("RED passes=" as *u8); gn(pass); gw("/" as *u8); gn(total); gw("\n" as *u8); sys_exit(1); return 1 70}