nx_simulated_annealing_gate.nx source

1import "nx_gate_gn.nx" 2import "nx_gate_base.nx" 3// nx_simulated_annealing_gate.nx -- SIMULATED ANNEALING (Kirkpatrick 1983): the canonical metaheuristic that ESCAPES 4// local optima by accepting worse moves with probability exp(-delta/T), with temperature T cooling over time (operator: 5// build the mechanistic-AI foundation -- Paradiseo/metaheuristics were primary links). Where greedy HILL-CLIMBING gets 6// trapped in a local minimum, SA's Metropolis acceptance lets it climb OUT early (high T) then settle (low T) into the 7// GLOBAL minimum. Stochastic but REPRODUCIBLE (sovereign LCG). Uses our f32 exp. NO LLM. Demo: a double-well function 8// where hill-climbing stalls at the local min (f=3) but SA reaches the global min (f=1). 9// T0 LANDSCAPE: f(x) over x=0..10 with a LOCAL min at x=2 (f=3) and the GLOBAL min at x=8 (f=1), a hill between. 10// T1 HILL-CLIMBING TRAP: greedy descent from x=0 stalls at the local min x=2 (f=3) -- misses the global. 11// T2 METROPOLIS: SA accepts a worse move (delta>0) with probability exp(-delta/T) -- exploration. 12// T3 COOLING: T decreases geometrically (T *= alpha) -- exploration -> exploitation. 13// T4 ESCAPE: SA's best-found reaches the GLOBAL min x=8 (f=1), beating hill-climbing's f=3. 14// T5 = simulated annealing escaped the local optimum via Metropolis + cooling, mechanistic, reproducible, no LLM. 15// license_tier: ORIGINAL 16import "nx_f32_hw.nx" 17import "nx_syscalls.nx" 18 19func grow(name: *u8, ok: i64) -> i64 { if ok==1 { gw(" PASS " as *u8) } else { gw(" FAIL " as *u8) } gw(name); gw(" 20" as *u8); return ok } 21func f32_le(x: i64, y: i64) -> i64 { let d: i64=f32_sub(x,y) & 0xFFFFFFFF; if ((d>>31)&1)==1 { return 1 } if (d & 0x7FFFFFFF)==0 { return 1 } return 0 } 22func f32_exp(x: i64) -> i64 { 23 let log2e: i64=f32_div(f32_of(1442695),f32_of(1000000)); let ln2: i64=f32_div(f32_of(693147),f32_of(1000000)); let half: i64=f32_div(f32_of(1),f32_of(2)) 24 let t: i64=f32_mul(x, log2e); var n: i64=0; if f32_le(f32_of(0), t)==1 { n=f32_int(f32_add(t,half)) } else { n=f32_int(f32_sub(t,half)) } 25 let arg: i64=f32_mul(f32_sub(t, f32_of(n)), ln2); var p2f: i64=f32_of(1); var term: i64=f32_of(1); var k: i64=1 26 while k<=8 { term=f32_div(f32_mul(term,arg), f32_of(k)); p2f=f32_add(p2f,term); k=k+1 } 27 var ef: i64=n+127; if ef<=0 { return f32_of(0) } if ef>=255 { ef=254 } return f32_mul(p2f, (ef & 0xFF) << 23) 28} 29func rng(st: *i64) -> i64 { st[0]=((st[0]*1103515245)+12345) & 0x7FFFFFFF; return st[0] } 30func rng_n(st: *i64, n: i64) -> i64 { return ((rng(st)>>16)&0x7FFF)%n } // HIGH bits -- LCG low bits have tiny period 31// double-well landscape. 32func fval(x: i64, F: *i64) -> i64 { if x<0 { return 999 } if x>10 { return 999 } return F[x] } 33 34func main() -> i64 { 35 gw("=== nx_simulated_annealing_gate: Simulated Annealing -- escape local optima via Metropolis + cooling, no LLM ===\n" as *u8) 36 var pass: i64=0; var total: i64=0 37 let F: *i64=sys_mmap(128) as *i64 38 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 39 40 // T0. 41 total=total+1; pass=pass+1 42 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), hill at x=5\n" as *u8) 43 44 // T1 hill-climbing from x=0. 45 var hx: i64=0 46 var moved: i64=1 47 while moved==1 { moved=0 48 let l: i64=fval(hx-1,F); let r: i64=fval(hx+1,F) 49 if l<fval(hx,F) { if f32_le(f32_of(l),f32_of(r))==1 { hx=hx-1; moved=1 } else { hx=hx+1; moved=1 } } 50 else { if r<fval(hx,F) { hx=hx+1; moved=1 } } 51 } 52 total=total+1; if hx==2 { if fval(hx,F)==3 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) } 53 gw("T1 HILL-CLIMBING TRAP: greedy descent from x=0 stalls at x=" as *u8); gn(hx); gw(" (f=" as *u8); gn(fval(hx,F)); gw(") -- the LOCAL min, misses the global\n" as *u8) 54 55 // T2 + T3 + T4 simulated annealing. 56 let st: *i64=sys_mmap(16) as *i64; st[0]=98765 57 var x: i64=0; var T: i64=f32_of(20); let alpha: i64=f32_div(f32_of(97),f32_of(100)) 58 var bestx: i64=x; var bestf: i64=fval(x,F) 59 var accepted_worse: i64=0; var Tlog0: i64=T; var step: i64=0 60 while step<800 { 61 var dir: i64=1; if rng_n(st,2)==0 { dir=0-1 } 62 let nx: i64=x+dir 63 if nx>=0 { if nx<=10 { 64 let delta: i64=fval(nx,F)-fval(x,F) 65 if delta<=0 { x=nx } else { 66 let p: i64=f32_exp(f32_div(f32_of(0-delta), T)) // exp(-delta/T) 67 let u: i64=f32_div(f32_of(rng_n(st,1000)), f32_of(1000)) 68 if f32_le(u,p)==1 { x=nx; accepted_worse=accepted_worse+1 } 69 } 70 } } 71 if fval(x,F)<bestf { bestf=fval(x,F); bestx=x } 72 T=f32_mul(T,alpha); step=step+1 73 } 74 // T2 metropolis: accepted some worse moves. 75 total=total+1; if accepted_worse>0 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } 76 gw("T2 METROPOLIS: SA accepted " as *u8); gn(accepted_worse); gw(" worse moves with prob exp(-delta/T) -- the exploration that escapes traps\n" as *u8) 77 78 // T3 cooling. 79 total=total+1; if f32_le(T,Tlog0)==1 { if f32_le(T,f32_of(1))==1 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) } 80 gw("T3 COOLING: T fell from 20 to " as *u8); gn(f32_int(f32_mul(T,f32_of(1000)))); gw("m/1000 (geometric T*=0.97) -- explore then exploit\n" as *u8) 81 82 // T4 escape. 83 total=total+1; if bestx==8 { if bestf==1 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) } 84 gw("T4 ESCAPE: SA best-found x=" as *u8); gn(bestx); gw(" (f=" as *u8); gn(bestf); gw(") = the GLOBAL min, beating hill-climbing's f=3\n" as *u8) 85 86 // T5. 87 total=total+1; if bestf==1 { if accepted_worse>0 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) } 88 gw("T5 SIMULATED ANNEALING: Metropolis acceptance + geometric cooling escaped the local optimum to the global min, no LLM\n" as *u8) 89 90 gw("\n SIMULATED ANNEALING (Kirkpatrick): greedy hill-climbing trapped at the local min (f=3); SA accepted worse moves early (high T,\n" as *u8) 91 gw(" exp(-delta/T) ~ 1) to climb OUT, then cooled (T*=0.97) to settle into the GLOBAL min (f=1). Stochastic but reproducible\n" as *u8) 92 gw(" (sovereign LCG), using our f32 exp. NO LLM. With nx_genetic_algorithm + nx_pareto_moea this gives the metaheuristic core of\n" as *u8) 93 gw(" the foundation; next tabu search + ant colony round out the metaheuristics. All mechanistic.\n" as *u8) 94 gw("SIMULATED-ANNEALING verdict=" as *u8) 95 if pass==total { gw("GREEN passes=" as *u8); gn(pass); gw("/" as *u8); gn(total); gw(" -- SA escaped the local optimum to the global min, reproducible, no LLM\n" as *u8); sys_exit(0); return 0 } 96 gw("RED passes=" as *u8); gn(pass); gw("/" as *u8); gn(total); gw("\n" as *u8); sys_exit(1); return 1 97}