1	# Unsga3Algorithm.Run — C# Unsga3.Algorithm.Unsga3Algorithm.
2	# init → evaluate → loop: tournament parents → SBX (η=30, p=1.0) →
3	# polynomial mutation (η=20, p=1/n) → evaluate → survival Select
4	# with persistent Normalization. Defaults match C# operator defaults.
5	# Mating tournament for A/B is PymooCompatible. RankNicheDistance (C#
6	# ctor default) is rank → niche count → perpendicular distance → coin.
7	# Survival niching in Run threads rng (C# Select(..., rng): random among
8	# equal min-count niches). Empty niches
9	# take closest; extras are random among near-best on that ray. Uniform
10	# inNiche[Next] with this LCG collapsed oracle ZDT2.
11	# Duplicate keys round each decision variable to 12 decimal places
12	# (round(x*1e12)/1e12). That is not C# ToString("G12") (12 significant
13	# digits). Small variables diverge; see src/g12_key.bend.
14	
15	import Base
16	import ./individual.bend as Ind
17	import ./non_dominated_sort.bend as NDS
18	import ./normalization.bend as Norm
19	import ./reference_directions.bend as Refs
20	import ./survival.bend as Surv
21	import ./bounds.bend as Bounds
22	import ./rng.bend as Rng
23	import ./sbx.bend as Sbx
24	import ./polynomial_mutation.bend as Poly
25	import ./problems.bend as Prob
26	import ./tournament.bend as Tour
27	import ./util.bend as Util
28	
29	type Config is Data:
30	  MkConfig{
31	    dirs: List<&2, List<&2, F32>>
32	    pop_size: Nat
33	    gens: Nat
34	    seed: Nat
35	    mode: Tour.Mode
36	    elim_dups: Bool
37	  }
38	
39	def mk(+dirs: List<&2, List<&2, F32>>, +pop_size: Nat, +gens: Nat, +seed: Nat, +mode: Tour.Mode, +elim_dups: Bool) -> Config:
40	  MkConfig{dirs, pop_size, gens, seed, mode, elim_dups}
41	
42	def cfg_dirs(c: Config) -> List<&2, List<&2, F32>>:
43	  match c:
44	    case MkConfig{dirs, pop_size, gens, seed, mode, elim_dups}:
45	      dirs
46	
47	def cfg_pop(c: Config) -> Nat:
48	  match c:
49	    case MkConfig{dirs, pop_size, gens, seed, mode, elim_dups}:
50	      pop_size
51	
52	def cfg_gens(c: Config) -> Nat:
53	  match c:
54	    case MkConfig{dirs, pop_size, gens, seed, mode, elim_dups}:
55	      gens
56	
57	def cfg_seed(c: Config) -> Nat:
58	  match c:
59	    case MkConfig{dirs, pop_size, gens, seed, mode, elim_dups}:
60	      seed
61	
62	def cfg_mode(c: Config) -> Tour.Mode:
63	  match c:
64	    case MkConfig{dirs, pop_size, gens, seed, mode, elim_dups}:
65	      mode
66	
67	def cfg_elim(c: Config) -> Bool:
68	  match c:
69	    case MkConfig{dirs, pop_size, gens, seed, mode, elim_dups}:
70	      elim_dups
71	
72	# Smoke (not oracle): ZDT1 n=30, partitions=4 → 5 refs, pop=8, gens=3, seed=1.
73	def smoke_zdt1() -> Config:
74	  mk(Refs.das_dennis(2n, 4n), 8n, 3n, 1n, Tour.pymoo(), True{})
75	
76	# C# OracleCompare / EQUIVALENCE-style settings (not the smoke default).
77	def oracle_zdt1() -> Config:
78	  mk(Refs.das_dennis(2n, 12n), 52n, 100n, 1n, Tour.pymoo(), True{})
79	
80	def oracle_dtlz2() -> Config:
81	  mk(Refs.das_dennis(3n, 12n), 92n, 150n, 1n, Tour.pymoo(), True{})
82	
83	def get_ind(+pop: List<&2, Ind.Individual>, i: Nat) -> Ind.Individual:
84	  Maybe.default(&2, Ind.Individual, List.get(&2, Ind.Individual, pop, i), Ind.from_variables(Nil{}, 1n))
85	
86	def rand_xs.go(+box: Bounds.Box, fuel: Nat, +i: Nat, rng: Rng.State, acc: List<&2, F32>) -> Rng.State & List<&2, F32>:
87	  match fuel:
88	    case 0n:
89	      (rng, List.reverse(&2, F32, acc))
90	    case 1n+f:
91	      +iv = Bounds.at(box, i)
92	      +rng2 = Rng.next_double(rng)
93	      +lo = Bounds.lo(iv)
94	      +hi = Bounds.hi(iv)
95	      rand_xs.go(
96	        box,
97	        f,
98	        1n+i,
99	        rng2,
100	        F32.add(lo, F32.mul(F32.sub(hi, lo), Rng.last_double(rng2))) <> acc
101	      )
102	
103	def rand_xs(+box: Bounds.Box, rng: Rng.State) -> Rng.State & List<&2, F32>:
104	  rand_xs.go(box, Bounds.n_var(box), 0n, rng, Nil{})
105	
106	type IHold is Data:
107	  IH{
108	    rng: Rng.State
109	    acc: List<&2, Ind.Individual>
110	  }
111	
112	def init_next.xs(+n_obj: Nat, acc: List<&2, Ind.Individual>, pair: Rng.State & List<&2, F32>) -> IHold:
113	  (rng, xs) = pair
114	  IH{rng, Ind.from_variables(xs, n_obj) <> acc}
115	
116	def init_next(+box: Bounds.Box, +n_obj: Nat, hold: IHold) -> IHold:
117	  match hold:
118	    case IH{rng, acc}:
119	      init_next.xs(n_obj, acc, rand_xs(box, rng))
120	
121	def init_loop(fuel: Nat, hold: IHold, +box: Bounds.Box, +n_obj: Nat) -> Rng.State & List<&2, Ind.Individual>:
122	  match fuel hold:
123	    case 0n IH{rng, acc}:
124	      (rng, List.reverse(&2, Ind.Individual, acc))
125	    case 1n+f h:
126	      init_loop(f, init_next(box, n_obj, h), box, n_obj)
127	
128	def init_pop(+prob: Prob.Problem, n: Nat, rng: Rng.State) -> Rng.State & List<&2, Ind.Individual>:
129	  init_loop(n, IH{rng, Nil{}}, Prob.box_of(prob), Prob.n_obj(prob))
130	
131	def vars_of.go(xs: List<&2, Ind.Individual>, acc: List<&2, List<&2, F32>>) -> List<&2, List<&2, F32>>:
132	  match xs:
133	    case Nil{}:
134	      List.reverse(&2, List<&2, F32>, acc)
135	    case +ind <> rest:
136	      vars_of.go(rest, Util.g12_vec(Ind.variables(ind)) <> acc)
137	
138	def vars_of(xs: List<&2, Ind.Individual>) -> List<&2, List<&2, F32>>:
139	  vars_of.go(xs, Nil{})
140	
141	def try_add.go(+acc: List<&2, Ind.Individual>, +child: Ind.Individual, +seen: List<&2, List<&2, F32>>, +key: List<&2, F32>, skip: Bool) -> List<&2, Ind.Individual> & List<&2, List<&2, F32>> & Bool:
142	  match skip:
143	    case True{}:
144	      (acc, seen, False{})
145	    case False{}:
146	      (List.append(&2, Ind.Individual, acc, [child]), key <> seen, True{})
147	
148	def try_add(+acc: List<&2, Ind.Individual>, +child: Ind.Individual, +seen: List<&2, List<&2, F32>>, elim: Bool) -> List<&2, Ind.Individual> & List<&2, List<&2, F32>> & Bool:
149	  +key = Util.g12_vec(Ind.variables(child))
150	  try_add.go(acc, child, seen, key, Bool.and(elim, Util.has_f32s(key, seen)))
151	
152	def pred_or_zero(n: Nat) -> Nat:
153	  match n:
154	    case 0n:
155	      0n
156	    case 1n+p:
157	      p
158	
159	def dec_if(n: Nat, hit: Bool) -> Nat:
160	  match hit:
161	    case True{}:
162	      pred_or_zero(n)
163	    case False{}:
164	      n
165	
166	def wrap_pair.go(+pair: Nat, ok: Bool) -> Nat:
167	  match ok:
168	    case True{}:
169	      pair
170	    case False{}:
171	      0n
172	
173	def wrap_pair(+pair: Nat, +n: Nat) -> Nat:
174	  wrap_pair.go(pair, Nat.is_lt(1n+pair, n))
175	
176	type FHold is Data:
177	  FH{
178	    rng: Rng.State
179	    acc: List<&2, Ind.Individual>
180	  }
181	
182	def fallback_next.m(acc: List<&2, Ind.Individual>, pair: Rng.State & Ind.Individual) -> FHold:
183	  (rng, extra) = pair
184	  FH{rng, List.append(&2, Ind.Individual, acc, [extra])}
185	
186	def fallback_next(+parents: List<&2, Ind.Individual>, +prob: Prob.Problem, +mut_p: F32, hold: FHold) -> FHold:
187	  match hold:
188	    case FH{rng, acc}:
189	      +n = Util.list_len(Ind.Individual, parents)
190	      +rng_i = Rng.next_nat(rng, n)
191	      fallback_next.m(acc, Poly.mutate(Poly.default(), get_ind(parents, Rng.last_nat(rng_i)), Prob.box_of(prob), rng_i, mut_p))
192	
193	def fallback_loop(need: Nat, hold: FHold, +parents: List<&2, Ind.Individual>, +prob: Prob.Problem, +mut_p: F32) -> Rng.State & List<&2, Ind.Individual>:
194	  match need hold:
195	    case 0n FH{rng, acc}:
196	      (rng, acc)
197	    case 1n+k h:
198	      fallback_loop(k, fallback_next(parents, prob, mut_p, h), parents, prob, mut_p)
199	
200	def offs_add2.hit(+need1: Nat, trip: List<&2, Ind.Individual> & List<&2, List<&2, F32>> & Bool) -> Nat & List<&2, Ind.Individual> & List<&2, List<&2, F32>>:
201	  (acc2, seen2, hit2) = trip
202	  (dec_if(need1, hit2), acc2, seen2)
203	
204	def offs_add2.rest(+need1: Nat, +elim: Bool, +c2: Ind.Individual, acc1: List<&2, Ind.Individual>, seen1: List<&2, List<&2, F32>>, done: Bool) -> Nat & List<&2, Ind.Individual> & List<&2, List<&2, F32>>:
205	  match done:
206	    case True{}:
207	      (0n, acc1, seen1)
208	    case False{}:
209	      offs_add2.hit(need1, try_add(acc1, c2, seen1, elim))
210	
211	def offs_add2(
212	  +need: Nat,
213	  acc: List<&2, Ind.Individual>,
214	  seen: List<&2, List<&2, F32>>,
215	  +elim: Bool,
216	  +c2: Ind.Individual,
217	  trip: List<&2, Ind.Individual> & List<&2, List<&2, F32>> & Bool
218	) -> Nat & List<&2, Ind.Individual> & List<&2, List<&2, F32>>:
219	  (acc1, seen1, hit1) = trip
220	  +need1 = dec_if(need, hit1)
221	  offs_add2.rest(need1, elim, c2, acc1, seen1, Nat.is_eq(need1, 0n))
222	
223	def offs_pair.done(rng3: Rng.State, trip: Nat & List<&2, Ind.Individual> & List<&2, List<&2, F32>>) -> Rng.State & Nat & List<&2, Ind.Individual> & List<&2, List<&2, F32>>:
224	  (need2, acc2, seen2) = trip
225	  (rng3, need2, acc2, seen2)
226	
227	def offs_pair.m2(+need: Nat, +acc: List<&2, Ind.Individual>, +seen: List<&2, List<&2, F32>>, +elim: Bool, +m1: Ind.Individual, pair: Rng.State & Ind.Individual) -> Rng.State & Nat & List<&2, Ind.Individual> & List<&2, List<&2, F32>>:
228	  (rng3, m2) = pair
229	  offs_pair.done(rng3, offs_add2(need, acc, seen, elim, m2, try_add(acc, m1, seen, elim)))
230	
231	def offs_pair.m1(+need: Nat, +acc: List<&2, Ind.Individual>, +seen: List<&2, List<&2, F32>>, +prob: Prob.Problem, +mut_p: F32, +elim: Bool, +c2: Ind.Individual, pair: Rng.State & Ind.Individual) -> Rng.State & Nat & List<&2, Ind.Individual> & List<&2, List<&2, F32>>:
232	  (rng2, m1) = pair
233	  offs_pair.m2(need, acc, seen, elim, m1, Poly.mutate(Poly.default(), c2, Prob.box_of(prob), rng2, mut_p))
234	
235	def offs_pair.sbx(+need: Nat, +acc: List<&2, Ind.Individual>, +seen: List<&2, List<&2, F32>>, +prob: Prob.Problem, +mut_p: F32, +elim: Bool, trip: Rng.State & Ind.Individual & Ind.Individual) -> Rng.State & Nat & List<&2, Ind.Individual> & List<&2, List<&2, F32>>:
236	  (rng1, c1, c2) = trip
237	  offs_pair.m1(need, acc, seen, prob, mut_p, elim, c2, Poly.mutate(Poly.default(), c1, Prob.box_of(prob), rng1, mut_p))
238	
239	def offs_pair(
240	  +parents: List<&2, Ind.Individual>,
241	  +pair: Nat,
242	  +need: Nat,
243	  +acc: List<&2, Ind.Individual>,
244	  +seen: List<&2, List<&2, F32>>,
245	  rng: Rng.State,
246	  +prob: Prob.Problem,
247	  +mut_p: F32,
248	  +elim: Bool
249	) -> Rng.State & Nat & List<&2, Ind.Individual> & List<&2, List<&2, F32>>:
250	  +n = Util.list_len(Ind.Individual, parents)
251	  +p0 = wrap_pair(pair, n)
252	  offs_pair.sbx(
253	    need,
254	    acc,
255	    seen,
256	    prob,
257	    mut_p,
258	    elim,
259	    Sbx.crossover(Sbx.default(), get_ind(parents, p0), get_ind(parents, 1n+p0), Prob.box_of(prob), rng)
260	  )
261	
262	type OHold is Data:
263	  OH{
264	    need: Nat
265	    pair: Nat
266	    rng: Rng.State
267	    acc: List<&2, Ind.Individual>
268	    seen: List<&2, List<&2, F32>>
269	  }
270	
271	def offs_next.q(+pair0: Nat, quad: Rng.State & Nat & List<&2, Ind.Individual> & List<&2, List<&2, F32>>) -> OHold:
272	  (rng, need, acc, seen) = quad
273	  OH{need, Nat.add(pair0, 2n), rng, acc, seen}
274	
275	def offs_next(+parents: List<&2, Ind.Individual>, +prob: Prob.Problem, +mut_p: F32, +elim: Bool, hold: OHold) -> OHold:
276	  match hold:
277	    case OH{need, +pair, rng, acc, seen}:
278	      offs_next.q(pair, offs_pair(parents, pair, need, acc, seen, rng, prob, mut_p, elim))
279	
280	def offs_done(+parents: List<&2, Ind.Individual>, +prob: Prob.Problem, +mut_p: F32, hold: OHold) -> Rng.State & List<&2, Ind.Individual>:
281	  match hold:
282	    case OH{nrest, pair, rng, acc, seen}:
283	      fallback_loop(nrest, FH{rng, acc}, parents, prob, mut_p)
284	
285	def offs_have(hold: OHold) -> Rng.State & List<&2, Ind.Individual>:
286	  match hold:
287	    case OH{need, pair, rng, acc, seen}:
288	      (rng, acc)
289	
290	def offs_loop(
291	  fuel: Nat,
292	  hold: OHold,
293	  +parents: List<&2, Ind.Individual>,
294	  +prob: Prob.Problem,
295	  +mut_p: F32,
296	  +elim: Bool
297	) -> Rng.State & List<&2, Ind.Individual>:
298	  match fuel hold:
299	    case 0n h:
300	      offs_done(parents, prob, mut_p, h)
301	    case 1n+f OH{0n, pair, rng, acc, seen}:
302	      offs_have(OH{0n, pair, rng, acc, seen})
303	    case 1n+f OH{1n+k, pair, rng, acc, seen}:
304	      offs_loop(f, offs_next(parents, prob, mut_p, elim, OH{1n+k, pair, rng, acc, seen}), parents, prob, mut_p, elim)
305	
306	def seen_start(+parents: List<&2, Ind.Individual>, elim: Bool) -> List<&2, List<&2, F32>>:
307	  match elim:
308	    case True{}:
309	      vars_of(parents)
310	    case False{}:
311	      Nil{}
312	
313	def create_offspring(+prob: Prob.Problem, +parents: List<&2, Ind.Individual>, +n: Nat, rng: Rng.State, +elim: Bool) -> Rng.State & List<&2, Ind.Individual>:
314	  offs_loop(
315	    Nat.mul(n, 40n),
316	    OH{n, 0n, rng, Nil{}, seen_start(parents, elim)},
317	    parents,
318	    prob,
319	    Poly.typical_probability(Prob.n_var(prob)),
320	    elim
321	  )
322	
323	def nd_front(+pop: List<&2, Ind.Individual>) -> List<&2, Ind.Individual>:
324	  Surv.gather(pop, Surv.front0(NDS.sort(pop)))
325	
326	def emit_front(xs: List<&2, Ind.Individual>) -> IO(Unit):
327	  match xs:
328	    case Nil{}:
329	      do IO<Unit>:
330	        return Unit{}
331	    case ind <> rest:
332	      do IO<Unit>:
333	        IO.print(Util.show_f32s(Ind.objectives(ind)))
334	        emit_front(rest)
335	
336	type GHold is Data:
337	  GH{
338	    st: Norm.State
339	    xs: List<&2, Ind.Individual>
340	    rng: Rng.State
341	  }
342	
343	def one_gen.prep(+rng: Rng.State, pair: Norm.State & List<&2, Ind.Individual>) -> GHold:
344	  (st, xs) = pair
345	  GH{st, xs, rng}
346	
347	def one_gen.s(+prob: Prob.Problem, +cfg: Config, trip: Norm.State & List<&2, Ind.Individual> & Rng.State) -> GHold:
348	  (st, xs, rng) = trip
349	  one_gen.prep(rng, Tour.prepare(xs, cfg_dirs(cfg), st))
350	
351	def one_gen.o(+prob: Prob.Problem, +cfg: Config, +pop: List<&2, Ind.Individual>, +state: Norm.State, trip: Rng.State & List<&2, Ind.Individual>) -> GHold:
352	  (rng2, offs) = trip
353	  one_gen.s(
354	    prob,
355	    cfg,
356	    Surv.select_st(
357	      List.append(&2, Ind.Individual, pop, Prob.evaluate_all(prob, offs)),
358	      cfg_pop(cfg),
359	      cfg_dirs(cfg),
360	      state,
361	      rng2
362	    )
363	  )
364	
365	def one_gen.p(+prob: Prob.Problem, +cfg: Config, +pop: List<&2, Ind.Individual>, +state: Norm.State, trip: Rng.State & List<&2, Ind.Individual>) -> GHold:
366	  (rng1, parents) = trip
367	  one_gen.o(prob, cfg, pop, state, create_offspring(prob, parents, cfg_pop(cfg), rng1, cfg_elim(cfg)))
368	
369	def one_gen(+prob: Prob.Problem, +cfg: Config, hold: GHold) -> GHold:
370	  match hold:
371	    case GH{st, +xs, rng}:
372	      one_gen.p(prob, cfg, xs, st, Tour.select_parents(cfg_mode(cfg), xs, cfg_pop(cfg), rng))
373	
374	def gen_pop(hold: GHold) -> List<&2, Ind.Individual>:
375	  match hold:
376	    case GH{st, xs, rng}:
377	      xs
378	
379	def gen_loop(fuel: Nat, hold: GHold, +prob: Prob.Problem, +cfg: Config) -> List<&2, Ind.Individual>:
380	  match fuel hold:
381	    case 0n h:
382	      gen_pop(h)
383	    case 1n+g h:
384	      gen_loop(g, one_gen(prob, cfg, h), prob, cfg)
385	
386	def run.after_prep(+prob: Prob.Problem, +cfg: Config, rng: Rng.State, pair: Norm.State & List<&2, Ind.Individual>) -> List<&2, Ind.Individual>:
387	  (st1, pop1) = pair
388	  gen_loop(cfg_gens(cfg), GH{st1, pop1, rng}, prob, cfg)
389	
390	def run.go(+prob: Prob.Problem, +cfg: Config, pair: Rng.State & List<&2, Ind.Individual>) -> List<&2, Ind.Individual>:
391	  (rng, raw) = pair
392	  run.after_prep(prob, cfg, rng, Tour.prepare(Prob.evaluate_all(prob, raw), cfg_dirs(cfg), Norm.new_state(Prob.n_obj(prob))))
393	
394	def run.sized(+prob: Prob.Problem, +cfg: Config, n: Nat) -> List<&2, Ind.Individual>:
395	  match n:
396	    case 0n:
397	      Nil{}
398	    case 1n+p:
399	      run.go(prob, cfg, init_pop(prob, 1n+p, Rng.from_nat(cfg_seed(cfg))))
400	
401	def run(+prob: Prob.Problem, +cfg: Config) -> List<&2, Ind.Individual>:
402	  +n = cfg_pop(cfg)
403	  Util.list_take_pad(Ind.Individual, Ind.from_objectives(Nil{}), run.sized(prob, cfg, n), n)
404	
405	def run_zdt1_smoke() -> List<&2, Ind.Individual>:
406	  run(Prob.zdt1(30n), smoke_zdt1())