survival.bend
unified-nsga-iii@0.1.2.0 · 882 lines · 0 definitions
1# Survival / niching — C# ReferencePointManager + NondominatedSortingSurvival.
2# Independent maps (associate / histograms / gather) use mid-split
3# `a b = f(lo) f(hi)`. Nearest-ref stays sequential (associate_raw already
4# splits per individual). Last-front fill builds `NRow{i, ref, dist}` once
5# so the sequential niche loop never `List.get`s an Assignment (or a fat
6# Individual) per remaining candidate. Same pick rules / same RNG order.
7# Associate normalized individuals to Das–Dennis rays; select `target_size`
8# from a combined pool (fill complete fronts, niche-preserve the last).
9# Deterministic when C# rng is null (`select`): lowest ref among min-count
10# niches, then min perpendicular distance if that niche is empty, else
11# lowest index. `select_st` (Run) threads rng: random among equal
12# min-count niches (C# Select(..., rng)). Empty niches take the closest
13# unused member; extras draw among members within 2×best+0.01 of the
14# ray — not uniform inNiche[rng.Next], which collapsed oracle ZDT2.
15
16import Base
17import unified-nsga-iii@0.1.2.0/individual.bend as Ind
18import unified-nsga-iii@0.1.2.0/non_dominated_sort.bend as NDS
19import unified-nsga-iii@0.1.2.0/normalization.bend as Norm
20import unified-nsga-iii@0.1.2.0/rng.bend as Rng
21import unified-nsga-iii@0.1.2.0/util.bend as Util
22
23type Assignment is Data:
24 MkAssignment{
25 reference_index: Nat
26 perpendicular_distance: F32
27 niche_count: Nat
28 }
29
30def asg_ref(a: Assignment) -> Nat:
31 match a:
32 case MkAssignment{reference_index, perpendicular_distance, niche_count}:
33 reference_index
34
35def asg_dist(a: Assignment) -> F32:
36 match a:
37 case MkAssignment{reference_index, perpendicular_distance, niche_count}:
38 perpendicular_distance
39
40def asg_count(a: Assignment) -> Nat:
41 match a:
42 case MkAssignment{reference_index, perpendicular_distance, niche_count}:
43 niche_count
44
45def get_asg(asgs: List<&2, Assignment>, i: Nat) -> Assignment:
46 Maybe.default(&2, Assignment, List.get(&2, Assignment, asgs, i), MkAssignment{0n, 0.0, 0n})
47
48def get_ind(+pop: List<&2, Ind.Individual>, i: Nat) -> Ind.Individual:
49 Maybe.default(&2, Ind.Individual, List.get(&2, Ind.Individual, pop, i), Ind.from_objectives(Nil{}))
50
51# Last-front row: population index plus the two fields the fill loop
52# reads. Built once from `asgs` so each pick walks this thin list
53# instead of `List.get` into the combined-pool assignment spine.
54type NRow is Data:
55 NRow{
56 i: Nat
57 r: Nat
58 d: F32
59 }
60
61def nrow_i(row: NRow) -> Nat:
62 match row:
63 case NRow{i, r, d}:
64 i
65
66def nrow_r(row: NRow) -> Nat:
67 match row:
68 case NRow{i, r, d}:
69 r
70
71def nrow_d(row: NRow) -> F32:
72 match row:
73 case NRow{i, r, d}:
74 d
75
76def nrows_of.go(+asgs: List<&2, Assignment>, cand: List<&2, Nat>, acc: List<&2, NRow>) -> List<&2, NRow>:
77 match cand:
78 case Nil{}:
79 List.reverse(&2, NRow, acc)
80 case +i <> rest:
81 +a = get_asg(asgs, i)
82 nrows_of.go(asgs, rest, NRow{i, asg_ref(a), asg_dist(a)} <> acc)
83
84def nrows_of(+asgs: List<&2, Assignment>, +cand: List<&2, Nat>) -> List<&2, NRow>:
85 nrows_of.go(asgs, cand, Nil{})
86
87def first_row_i(rows: List<&2, NRow>) -> Nat:
88 match rows:
89 case Nil{}:
90 0n
91 case +row <> _:
92 nrow_i(row)
93
94def first_row_r(rows: List<&2, NRow>) -> Nat:
95 match rows:
96 case Nil{}:
97 0n
98 case +row <> _:
99 nrow_r(row)
100
101def get_nrow(rows: List<&2, NRow>, i: Nat) -> NRow:
102 Maybe.default(&2, NRow, List.get(&2, NRow, rows, i), NRow{0n, 0n, 0.0})
103
104def drop_nrow.put(+row: NRow, rest: List<&2, NRow>, drop: Bool) -> List<&2, NRow>:
105 match drop:
106 case True{}:
107 rest
108 case False{}:
109 row <> rest
110
111def drop_nrow(rows: List<&2, NRow>, +pick: Nat) -> List<&2, NRow>:
112 match rows:
113 case Nil{}:
114 Nil{}
115 case +row <> rest:
116 drop_nrow.put(row, drop_nrow(rest, pick), Nat.is_eq(nrow_i(row), pick))
117
118def keep_nat(h: Nat, rest: List<&2, Nat>, keep: Bool) -> List<&2, Nat>:
119 match keep:
120 case True{}:
121 h <> rest
122 case False{}:
123 rest
124
125def uniq_refs.go(rows: List<&2, NRow>, +acc: List<&2, Nat>) -> List<&2, Nat>:
126 match rows:
127 case Nil{}:
128 List.reverse(&2, Nat, acc)
129 case +row <> rest:
130 +r = nrow_r(row)
131 uniq_refs.go(rest, keep_nat(r, acc, Bool.not(Util.in_nats(r, acc))))
132
133def uniq_refs(rows: List<&2, NRow>) -> List<&2, Nat>:
134 uniq_refs.go(rows, Nil{})
135
136def min_count_rows.go(+counts: List<&2, Nat>, rows: List<&2, NRow>, +acc: Nat) -> Nat:
137 match rows:
138 case Nil{}:
139 acc
140 case +row <> rest:
141 min_count_rows.go(counts, rest, Util.nat_min(acc, Util.get_nat(counts, nrow_r(row))))
142
143def min_count_rows(+counts: List<&2, Nat>, rows: List<&2, NRow>) -> Nat:
144 min_count_rows.go(counts, rows, 4294967295n)
145
146def refs_at_seq(+counts: List<&2, Nat>, +need: Nat, refs: List<&2, Nat>) -> List<&2, Nat>:
147 match refs:
148 case Nil{}:
149 Nil{}
150 case +r <> rest:
151 keep_nat(r, refs_at_seq(counts, need, rest), Nat.is_eq(Util.get_nat(counts, r), need))
152
153def in_ref_rows(+r: Nat, rows: List<&2, NRow>) -> List<&2, NRow>:
154 match rows:
155 case Nil{}:
156 Nil{}
157 case +row <> rest:
158 Util.keep_if(NRow, row, in_ref_rows(r, rest), Nat.is_eq(nrow_r(row), r))
159
160def argmin_dist_rows.go(rows: List<&2, NRow>, +best_i: Nat, +best_d: F32) -> Nat:
161 match rows:
162 case Nil{}:
163 best_i
164 case +row <> rest:
165 +d = nrow_d(row)
166 +lt = F32.is_lt(d, best_d)
167 argmin_dist_rows.go(rest, Bool.pick(Nat, lt, nrow_i(row), best_i), Bool.pick(F32, lt, d, best_d))
168
169def argmin_dist_rows(rows: List<&2, NRow>) -> Nat:
170 match rows:
171 case Nil{}:
172 0n
173 case +row <> rest:
174 argmin_dist_rows.go(rest, nrow_i(row), nrow_d(row))
175
176def min_dist_rows.go(rows: List<&2, NRow>, +acc: F32) -> F32:
177 match rows:
178 case Nil{}:
179 acc
180 case +row <> rest:
181 +d = nrow_d(row)
182 min_dist_rows.go(rest, Bool.pick(F32, F32.is_lt(d, acc), d, acc))
183
184def min_dist_rows(rows: List<&2, NRow>) -> F32:
185 match rows:
186 case Nil{}:
187 0.0
188 case +row <> rest:
189 min_dist_rows.go(rest, nrow_d(row))
190
191def min_idx_rows.go(rows: List<&2, NRow>, +acc: Nat) -> Nat:
192 match rows:
193 case Nil{}:
194 acc
195 case +row <> rest:
196 min_idx_rows.go(rest, Util.nat_min(acc, nrow_i(row)))
197
198def min_idx_rows(rows: List<&2, NRow>) -> Nat:
199 match rows:
200 case Nil{}:
201 0n
202 case +row <> rest:
203 min_idx_rows.go(rest, nrow_i(row))
204
205def near_rows(+lim: F32, rows: List<&2, NRow>) -> List<&2, NRow>:
206 match rows:
207 case Nil{}:
208 Nil{}
209 case +row <> rest:
210 Util.keep_if(NRow, row, near_rows(lim, rest), F32.is_le(nrow_d(row), lim))
211
212def perp.big(+f: List<&2, F32>, +w: List<&2, F32>, +ww: F32) -> F32:
213 +t = F32.div(Util.vec_dot(f, w), ww)
214 F32.sqrt(Util.vec_sqnorm(Util.vec_sub(f, Util.vec_scale(t, w))))
215
216def perp.zero(+f: List<&2, F32>, tiny: Bool) -> F32:
217 match tiny:
218 case True{}:
219 F32.sqrt(Util.vec_sqnorm(f))
220 case False{}:
221 0.0
222
223def perp.pick(+f: List<&2, F32>, +w: List<&2, F32>, +ww: F32, tiny: Bool) -> F32:
224 match tiny:
225 case True{}:
226 perp.zero(f, True{})
227 case False{}:
228 perp.big(f, w, ww)
229
230def perp(+f: List<&2, F32>, +w: List<&2, F32>) -> F32:
231 +ww = Util.vec_sqnorm(w)
232 perp.pick(f, w, ww, F32.is_lt(ww, 0.0000000000000001))
233
234# First-min on strict `<` (ties keep the lower index). Sequential over
235# dirs; associate_raw already mid-splits per individual.
236def nearest_go(+f: List<&2, F32>, dirs: List<&2, List<&2, F32>>, +i: Nat, +best_i: Nat, +best_d: F32) -> Assignment:
237 match dirs:
238 case Nil{}:
239 MkAssignment{best_i, best_d, 0n}
240 case +w <> ws:
241 +d = perp(f, w)
242 nearest_go(
243 f,
244 ws,
245 1n+i,
246 Bool.pick(Nat, F32.is_lt(d, best_d), i, best_i),
247 Bool.pick(F32, F32.is_lt(d, best_d), d, best_d)
248 )
249
250def nearest_one(f: List<&2, F32>, dirs: List<&2, List<&2, F32>>) -> Assignment:
251 nearest_go(f, dirs, 0n, 0n, 1000000000.0)
252
253def associate_head(+dirs: List<&2, List<&2, F32>>, +ind: Ind.Individual, F: List<&2, List<&2, F32>>) -> Assignment:
254 match F:
255 case Nil{}:
256 nearest_one(Ind.objectives(ind), dirs)
257 case f <> fs:
258 nearest_one(f, dirs)
259
260# Nearest-ref per individual is independent given dirs. Mid-split pop and F.
261def associate_raw.go(
262 +dirs: List<&2, List<&2, F32>>,
263 +fuel: Nat,
264 pop: List<&2, Ind.Individual>,
265 +F: List<&2, List<&2, F32>>
266) -> List<&2, Assignment>:
267 match fuel pop:
268 case 0n Nil{}:
269 Nil{}
270 case 0n ind <> rest:
271 match F:
272 case Nil{}:
273 nearest_one(Ind.objectives(ind), dirs) <> associate_raw.go(dirs, 0n, rest, Nil{})
274 case f <> fs:
275 nearest_one(f, dirs) <> associate_raw.go(dirs, 0n, rest, fs)
276 case 1n+p Nil{}:
277 Nil{}
278 case 1n+p ind <> Nil{}:
279 associate_head(dirs, ind, F) <> Nil{}
280 case 1n+p h <> t:
281 +all = {h <> t : List<&2, Ind.Individual>}
282 +mid = Nat.div(Util.list_len(Ind.Individual, all), 2n)
283 lo hi = associate_raw.go(dirs, p, List.take(&2, Ind.Individual, all, mid), List.take(&2, List<&2, F32>, F, mid)) associate_raw.go(dirs, p, List.drop(&2, Ind.Individual, all, mid), List.drop(&2, List<&2, F32>, F, mid))
284 List.append(&2, Assignment, lo, hi)
285
286def associate_raw(+pop: List<&2, Ind.Individual>, +F: List<&2, List<&2, F32>>, +dirs: List<&2, List<&2, F32>>) -> List<&2, Assignment>:
287 associate_raw.go(dirs, Util.list_len(Ind.Individual, pop), pop, F)
288
289# Histogram increments commute. Mid-split asgs, then add count vectors.
290def count_raw.go(+n: Nat, +fuel: Nat, asgs: List<&2, Assignment>) -> List<&2, Nat>:
291 match fuel asgs:
292 case 0n Nil{}:
293 Util.zeros_nat(n)
294 case 0n a <> rest:
295 Util.inc_at(count_raw.go(n, 0n, rest), asg_ref(a))
296 case 1n+p Nil{}:
297 Util.zeros_nat(n)
298 case 1n+p a <> Nil{}:
299 Util.inc_at(Util.zeros_nat(n), asg_ref(a))
300 case 1n+p h <> t:
301 +all = {h <> t : List<&2, Assignment>}
302 +mid = Nat.div(Util.list_len(Assignment, all), 2n)
303 lo hi = count_raw.go(n, p, List.take(&2, Assignment, all, mid)) count_raw.go(n, p, List.drop(&2, Assignment, all, mid))
304 Util.nats_add(lo, hi)
305
306def count_asg(+asgs: List<&2, Assignment>, +acc: List<&2, Nat>) -> List<&2, Nat>:
307 Util.nats_add(acc, count_raw.go(Util.list_len(Nat, acc), Util.list_len(Assignment, asgs), asgs))
308
309# Assignments whose reference_index lands in a length-n histogram.
310# Out-of-range refs are silent no-ops in inc_at / List.set.
311def in_bin_count(asgs: List<&2, Assignment>, +n: Nat) -> Nat:
312 match asgs:
313 case Nil{}:
314 0n
315 case +a <> rest:
316 Nat.add(Util.bin_hit(asg_ref(a), n), in_bin_count(rest, n))
317
318def with_counts.one(+counts: List<&2, Nat>, +a: Assignment) -> Assignment:
319 match a:
320 case MkAssignment{+r, d, n}:
321 MkAssignment{r, d, Util.get_nat(counts, r)}
322
323def with_counts(+counts: List<&2, Nat>, +asgs: List<&2, Assignment>) -> List<&2, Assignment>:
324 Util.map_halves(~Assignment, ~Assignment, ~List<&2, Nat>, ~with_counts.one, counts, asgs)
325
326def associate(+pop: List<&2, Ind.Individual>, +F: List<&2, List<&2, F32>>, +dirs: List<&2, List<&2, F32>>) -> List<&2, Assignment>:
327 +raw = associate_raw(pop, F, dirs)
328 with_counts(count_asg(raw, Util.zeros_nat(Util.list_len(List<&2, F32>, dirs))), raw)
329
330def front0(fronts: List<&2, List<&2, Nat>>) -> List<&2, Nat>:
331 match fronts:
332 case Nil{}:
333 Nil{}
334 case h <> t:
335 h
336
337def n_fronts(fronts: List<&2, List<&2, Nat>>) -> Nat:
338 Util.list_len(List<&2, Nat>, fronts)
339
340def head_len(fronts: List<&2, List<&2, Nat>>) -> Nat:
341 match fronts:
342 case Nil{}:
343 0n
344 case h <> t:
345 Util.list_len(Nat, h)
346
347def gather.one(+pop: List<&2, Ind.Individual>, +i: Nat) -> Ind.Individual:
348 get_ind(pop, i)
349
350def gather(+pop: List<&2, Ind.Individual>, +idxs: List<&2, Nat>) -> List<&2, Ind.Individual>:
351 Util.map_halves(~Nat, ~Ind.Individual, ~List<&2, Ind.Individual>, ~gather.one, pop, idxs)
352
353def cand_ref.one(+asgs: List<&2, Assignment>, +i: Nat) -> Nat:
354 asg_ref(get_asg(asgs, i))
355
356def cand_refs(+asgs: List<&2, Assignment>, cand: List<&2, Nat>) -> List<&2, Nat>:
357 Util.map_halves(~Nat, ~Nat, ~List<&2, Assignment>, ~cand_ref.one, asgs, cand)
358
359def min_count.go(+counts: List<&2, Nat>, +fuel: Nat, refs: List<&2, Nat>) -> Nat:
360 match fuel refs:
361 case 0n Nil{}:
362 4294967295n
363 case 0n +r <> rs:
364 Util.nat_min(Util.get_nat(counts, r), min_count.go(counts, 0n, rs))
365 case 1n+p Nil{}:
366 4294967295n
367 case 1n+p +r <> Nil{}:
368 Util.get_nat(counts, r)
369 case 1n+p h <> t:
370 +all = {h <> t : List<&2, Nat>}
371 +mid = Nat.div(Util.list_len(Nat, all), 2n)
372 lo hi = min_count.go(counts, p, List.take(&2, Nat, all, mid)) min_count.go(counts, p, List.drop(&2, Nat, all, mid))
373 Util.nat_min(lo, hi)
374
375def min_count(+counts: List<&2, Nat>, refs: List<&2, Nat>, acc: Nat) -> Nat:
376 match refs:
377 case Nil{}:
378 acc
379 case +r <> +rs:
380 +xs = {r <> rs : List<&2, Nat>}
381 Util.nat_min(acc, min_count.go(counts, Util.list_len(Nat, xs), xs))
382
383def cons_if(h: Nat, rest: List<&2, Nat>, keep: Bool) -> List<&2, Nat>:
384 match keep:
385 case True{}:
386 h <> rest
387 case False{}:
388 rest
389
390# First-occurrence unique (C# HashSet of refs-with-candidates).
391def uniq_nats.go(xs: List<&2, Nat>, +acc: List<&2, Nat>) -> List<&2, Nat>:
392 match xs:
393 case Nil{}:
394 List.reverse(&2, Nat, acc)
395 case +h <> t:
396 uniq_nats.go(t, cons_if(h, acc, Bool.not(Util.in_nats(h, acc))))
397
398def uniq_nats(xs: List<&2, Nat>) -> List<&2, Nat>:
399 uniq_nats.go(xs, Nil{})
400
401type CntNeed is Data:
402 CN{
403 counts: List<&2, Nat>
404 need: Nat
405 }
406
407def refs_at.ok(+ctx: CntNeed, +r: Nat) -> Bool:
408 match ctx:
409 case CN{counts, need}:
410 Nat.is_eq(Util.get_nat(counts, r), need)
411
412def refs_at(+counts: List<&2, Nat>, +need: Nat, refs: List<&2, Nat>) -> List<&2, Nat>:
413 Util.filter_halves(~Nat, ~CntNeed, ~refs_at.ok, CN{counts, need}, refs)
414
415def min_idx(xs: List<&2, Nat>, acc: Nat) -> Nat:
416 match xs:
417 case Nil{}:
418 acc
419 case +x <> rest:
420 min_idx(rest, Util.nat_min(acc, x))
421
422def min_idx_ne(xs: List<&2, Nat>) -> Nat:
423 match xs:
424 case Nil{}:
425 0n
426 case x <> rest:
427 min_idx(rest, x)
428
429def pick_ref(+asgs: List<&2, Assignment>, +counts: List<&2, Nat>, +cand: List<&2, Nat>) -> Nat:
430 +refs = cand_refs(asgs, cand)
431 min_idx_ne(refs_at(counts, min_count(counts, refs, 4294967295n), refs))
432
433type RefPick is Data:
434 RP{
435 asgs: List<&2, Assignment>
436 r: Nat
437 }
438
439def in_ref.ok(+ctx: RefPick, +i: Nat) -> Bool:
440 match ctx:
441 case RP{asgs, r}:
442 Nat.is_eq(asg_ref(get_asg(asgs, i)), r)
443
444def in_ref(+asgs: List<&2, Assignment>, +r: Nat, cand: List<&2, Nat>) -> List<&2, Nat>:
445 Util.filter_halves(~Nat, ~RefPick, ~in_ref.ok, RP{asgs, r}, cand)
446
447def argmin_join(+asgs: List<&2, Assignment>, +ia: Nat, +ib: Nat) -> Nat:
448 Bool.pick(Nat, F32.is_lt(asg_dist(get_asg(asgs, ib)), asg_dist(get_asg(asgs, ia))), ib, ia)
449
450def argmin_dist.go(+asgs: List<&2, Assignment>, +fuel: Nat, cand: List<&2, Nat>) -> Nat:
451 match fuel cand:
452 case 0n Nil{}:
453 0n
454 case 0n +i <> Nil{}:
455 i
456 case 0n +i <> +j <> js:
457 argmin_join(asgs, i, argmin_dist.go(asgs, 0n, j <> js))
458 case 1n+p Nil{}:
459 0n
460 case 1n+p +i <> Nil{}:
461 i
462 case 1n+p h <> t:
463 +all = {h <> t : List<&2, Nat>}
464 +mid = Nat.div(Util.list_len(Nat, all), 2n)
465 lo hi = argmin_dist.go(asgs, p, List.take(&2, Nat, all, mid)) argmin_dist.go(asgs, p, List.drop(&2, Nat, all, mid))
466 argmin_join(asgs, lo, hi)
467
468def argmin_dist(+asgs: List<&2, Assignment>, cand: List<&2, Nat>) -> Nat:
469 match cand:
470 case Nil{}:
471 0n
472 case +i <> +rest:
473 +xs = {i <> rest : List<&2, Nat>}
474 argmin_dist.go(asgs, Util.list_len(Nat, xs), xs)
475
476def pick_member.by(+asgs: List<&2, Assignment>, group: List<&2, Nat>, empty_niche: Bool) -> Nat:
477 match empty_niche:
478 case True{}:
479 argmin_dist(asgs, group)
480 case False{}:
481 min_idx_ne(group)
482
483# First remaining last-front index. Used when inNiche is empty
484# (C# would throw; never pick a phantom combined-pool index 0).
485def first_cand(cand: List<&2, Nat>) -> Nat:
486 match cand:
487 case Nil{}:
488 0n
489 case x <> _:
490 x
491
492def pick_member.by.safe(+asgs: List<&2, Assignment>, group: List<&2, Nat>, empty_niche: Bool, +fallback: Nat) -> Nat:
493 match group:
494 case Nil{}:
495 fallback
496 case g0 <> gs:
497 pick_member.by(asgs, {g0 <> gs : List<&2, Nat>}, empty_niche)
498
499def pick_member(+asgs: List<&2, Assignment>, +counts: List<&2, Nat>, +cand: List<&2, Nat>, +r: Nat) -> Nat:
500 pick_member.by.safe(asgs, in_ref(asgs, r, cand), Nat.is_eq(Util.get_nat(counts, r), 0n), first_cand(cand))
501
502# Affine API: advanced State; chosen index is `Rng.last_nat` (no pair match).
503# C# Select(..., rng): draw only when more than one min-count ref.
504def pick_ref.rng.go(+mins: List<&2, Nat>, n: Nat, +fallback: Nat, rng: Rng.State) -> Rng.State:
505 match n:
506 case 0n:
507 Rng.with_k(rng, fallback)
508 case 1n:
509 Rng.with_k(rng, min_idx_ne(mins))
510 case 1n+p:
511 +rng2 = Rng.next_nat(rng, 1n+p)
512 Rng.with_k(rng2, Util.get_nat(mins, Rng.last_nat(rng2)))
513
514def pick_ref.rng.after(+mins: List<&2, Nat>, +fallback: Nat, rng: Rng.State) -> Rng.State:
515 pick_ref.rng.go(mins, Util.list_len(Nat, mins), fallback, rng)
516
517def pick_ref.rng(+asgs: List<&2, Assignment>, +counts: List<&2, Nat>, +cand: List<&2, Nat>, rng: Rng.State) -> Rng.State:
518 +refs = uniq_nats(cand_refs(asgs, cand))
519 pick_ref.rng.after(
520 refs_at(counts, min_count(counts, refs, 4294967295n), refs),
521 asg_ref(get_asg(asgs, first_cand(cand))),
522 rng
523 )
524
525# Uniform inNiche[rng.Next] (C# non-empty + rng) lets far-from-ray last-front
526# junk into a niche. With this LCG that pile-up dominates ZDT2's concave
527# front (x0 → 0). Draw extras only among members within 2×best+0.01 of
528# the ray (first assignment to a niche stays closest).
529def near_lim(+best: F32) -> F32:
530 F32.add(F32.mul(best, 2.0), 0.01)
531
532def near_ok(+asgs: List<&2, Assignment>, +i: Nat, +lim: F32) -> Bool:
533 F32.is_le(asg_dist(get_asg(asgs, i)), lim)
534
535type NearPick is Data:
536 NP{
537 asgs: List<&2, Assignment>
538 lim: F32
539 }
540
541def near_members.ok(+ctx: NearPick, +i: Nat) -> Bool:
542 match ctx:
543 case NP{asgs, lim}:
544 near_ok(asgs, i, lim)
545
546def near_members(+asgs: List<&2, Assignment>, group: List<&2, Nat>, +lim: F32) -> List<&2, Nat>:
547 Util.filter_halves(~Nat, ~NearPick, ~near_members.ok, NP{asgs, lim}, group)
548
549def pick_among.rng(+group: List<&2, Nat>, n: Nat, +fallback: Nat, rng: Rng.State) -> Rng.State:
550 match n:
551 case 0n:
552 Rng.with_k(rng, fallback)
553 case 1n:
554 Rng.with_k(rng, min_idx_ne(group))
555 case 1n+p:
556 +rng2 = Rng.next_nat(rng, 1n+p)
557 Rng.with_k(rng2, Util.get_nat(group, Rng.last_nat(rng2)))
558
559def pick_near.rng(+asgs: List<&2, Assignment>, +group: List<&2, Nat>, rng: Rng.State) -> Rng.State:
560 +near = near_members(asgs, group, near_lim(asg_dist(get_asg(asgs, argmin_dist(asgs, group)))))
561 pick_among.rng(near, Util.list_len(Nat, near), first_cand(group), rng)
562
563def pick_member.rng.empty(+asgs: List<&2, Assignment>, +group: List<&2, Nat>, empty_niche: Bool, rng: Rng.State) -> Rng.State:
564 match empty_niche:
565 case True{}:
566 Rng.with_k(rng, argmin_dist(asgs, group))
567 case False{}:
568 pick_near.rng(asgs, group, rng)
569
570def pick_member.rng.by(+asgs: List<&2, Assignment>, group: List<&2, Nat>, empty_niche: Bool, +fallback: Nat, rng: Rng.State) -> Rng.State:
571 match group:
572 case Nil{}:
573 Rng.with_k(rng, fallback)
574 case g0 <> gs:
575 pick_member.rng.empty(asgs, {g0 <> gs : List<&2, Nat>}, empty_niche, rng)
576
577def pick_member.rng(+asgs: List<&2, Assignment>, +counts: List<&2, Nat>, +cand: List<&2, Nat>, +r: Nat, rng: Rng.State) -> Rng.State:
578 pick_member.rng.by(
579 asgs,
580 in_ref(asgs, r, cand),
581 Nat.is_eq(Util.get_nat(counts, r), 0n),
582 first_cand(cand),
583 rng
584 )
585
586def seed_raw.go(+asgs: List<&2, Assignment>, +n: Nat, +fuel: Nat, selected: List<&2, Nat>) -> List<&2, Nat>:
587 match fuel selected:
588 case 0n Nil{}:
589 Util.zeros_nat(n)
590 case 0n +i <> rest:
591 Util.inc_at(seed_raw.go(asgs, n, 0n, rest), asg_ref(get_asg(asgs, i)))
592 case 1n+p Nil{}:
593 Util.zeros_nat(n)
594 case 1n+p +i <> Nil{}:
595 Util.inc_at(Util.zeros_nat(n), asg_ref(get_asg(asgs, i)))
596 case 1n+p h <> t:
597 +all = {h <> t : List<&2, Nat>}
598 +mid = Nat.div(Util.list_len(Nat, all), 2n)
599 lo hi = seed_raw.go(asgs, n, p, List.take(&2, Nat, all, mid)) seed_raw.go(asgs, n, p, List.drop(&2, Nat, all, mid))
600 Util.nats_add(lo, hi)
601
602def seed_counts(+asgs: List<&2, Assignment>, +selected: List<&2, Nat>, +acc: List<&2, Nat>) -> List<&2, Nat>:
603 Util.nats_add(acc, seed_raw.go(asgs, Util.list_len(Nat, acc), Util.list_len(Nat, selected), selected))
604
605# fuel, k, cand first so the match follows binder order and fuel shrinks.
606def pick_ref.rows(+counts: List<&2, Nat>, +rows: List<&2, NRow>) -> Nat:
607 +refs = uniq_refs(rows)
608 min_idx_ne(refs_at_seq(counts, min_count_rows(counts, rows), refs))
609
610def pick_member.by.ne.rows(+group: List<&2, NRow>, empty_niche: Bool) -> Nat:
611 match empty_niche:
612 case True{}:
613 argmin_dist_rows(group)
614 case False{}:
615 min_idx_rows(group)
616
617def pick_member.by.rows(group: List<&2, NRow>, empty_niche: Bool, +fallback: Nat) -> Nat:
618 match group:
619 case Nil{}:
620 fallback
621 case g0 <> gs:
622 pick_member.by.ne.rows({g0 <> gs : List<&2, NRow>}, empty_niche)
623
624def pick_member.rows(+counts: List<&2, Nat>, +rows: List<&2, NRow>, +r: Nat) -> Nat:
625 pick_member.by.rows(in_ref_rows(r, rows), Nat.is_eq(Util.get_nat(counts, r), 0n), first_row_i(rows))
626
627def pick_ref.rng.rows(+counts: List<&2, Nat>, +rows: List<&2, NRow>, rng: Rng.State) -> Rng.State:
628 +refs = uniq_refs(rows)
629 pick_ref.rng.after(
630 refs_at_seq(counts, min_count_rows(counts, rows), refs),
631 first_row_r(rows),
632 rng
633 )
634
635def pick_among.nrows(+rows: List<&2, NRow>, n: Nat, +fallback: Nat, rng: Rng.State) -> Rng.State:
636 match n:
637 case 0n:
638 Rng.with_k(rng, fallback)
639 case 1n:
640 Rng.with_k(rng, first_row_i(rows))
641 case 1n+p:
642 +rng2 = Rng.next_nat(rng, 1n+p)
643 Rng.with_k(rng2, nrow_i(get_nrow(rows, Rng.last_nat(rng2))))
644
645def pick_near.rng.rows(+group: List<&2, NRow>, rng: Rng.State) -> Rng.State:
646 +near = near_rows(near_lim(min_dist_rows(group)), group)
647 pick_among.nrows(near, Util.list_len(NRow, near), first_row_i(group), rng)
648
649def pick_member.rng.empty.rows(+group: List<&2, NRow>, empty_niche: Bool, rng: Rng.State) -> Rng.State:
650 match empty_niche:
651 case True{}:
652 Rng.with_k(rng, argmin_dist_rows(group))
653 case False{}:
654 pick_near.rng.rows(group, rng)
655
656def pick_member.rng.by.rows(group: List<&2, NRow>, empty_niche: Bool, +fallback: Nat, rng: Rng.State) -> Rng.State:
657 match group:
658 case Nil{}:
659 Rng.with_k(rng, fallback)
660 case g0 <> gs:
661 pick_member.rng.empty.rows({g0 <> gs : List<&2, NRow>}, empty_niche, rng)
662
663def pick_member.rng.rows(+counts: List<&2, Nat>, +rows: List<&2, NRow>, +r: Nat, rng: Rng.State) -> Rng.State:
664 pick_member.rng.by.rows(
665 in_ref_rows(r, rows),
666 Nat.is_eq(Util.get_nat(counts, r), 0n),
667 first_row_i(rows),
668 rng
669 )
670
671def niche_loop(fuel: Nat, k: Nat, rows: List<&2, NRow>, +counts: List<&2, Nat>, selected: List<&2, Nat>) -> List<&2, Nat>:
672 match fuel k rows:
673 case 0n kk r:
674 selected
675 case f 0n r:
676 selected
677 case f kk Nil{}:
678 selected
679 case 1n+f 1n+krest +r0 <> +rs:
680 +rows2 = {r0 <> rs : List<&2, NRow>}
681 +r = pick_ref.rows(counts, rows2)
682 +pick = pick_member.rows(counts, rows2, r)
683 niche_loop(
684 f,
685 krest,
686 drop_nrow(rows2, pick),
687 Util.inc_at(counts, r),
688 List.append(&2, Nat, selected, [pick])
689 )
690
691def fill(fuel: Nat, fronts: List<&2, List<&2, Nat>>, fits: Bool, +acc: List<&2, Nat>, +target: Nat, +asgs: List<&2, Assignment>, +n_dirs: Nat) -> List<&2, Nat>:
692 match fuel fronts fits:
693 case 0n fs p:
694 acc
695 case f Nil{} p:
696 acc
697 case 1n+f +fr <> +rest False{}:
698 +need = Nat.sub(target, Util.list_len(Nat, acc))
699 +rows = nrows_of(asgs, fr)
700 niche_loop(
701 1n+Util.list_len(NRow, rows),
702 need,
703 rows,
704 seed_counts(asgs, acc, Util.zeros_nat(n_dirs)),
705 acc
706 )
707 case 1n+f +fr <> +rest True{}:
708 +new_acc = List.append(&2, Nat, acc, fr)
709 fill(
710 f,
711 rest,
712 Nat.is_le(Nat.add(Util.list_len(Nat, new_acc), head_len(rest)), target),
713 new_acc,
714 target,
715 asgs,
716 n_dirs
717 )
718
719def fill.wrap(+fronts: List<&2, List<&2, Nat>>, +target: Nat, +asgs: List<&2, Assignment>, +n_dirs: Nat) -> List<&2, Nat>:
720 fill(
721 1n+n_fronts(fronts),
722 fronts,
723 Nat.is_le(head_len(fronts), target),
724 Nil{},
725 target,
726 asgs,
727 n_dirs
728 )
729
730def niche_loop.rng(fuel: Nat, k: Nat, rows: List<&2, NRow>, +counts: List<&2, Nat>, selected: List<&2, Nat>, rng: Rng.State) -> List<&2, Nat> & Rng.State:
731 match fuel k rows:
732 case 0n kk r:
733 (selected, rng)
734 case f 0n r:
735 (selected, rng)
736 case f kk Nil{}:
737 (selected, rng)
738 case 1n+f 1n+krest +r0 <> +rs:
739 +rows2 = {r0 <> rs : List<&2, NRow>}
740 +rng1 = pick_ref.rng.rows(counts, rows2, rng)
741 +r = Rng.last_nat(rng1)
742 +rng2 = pick_member.rng.rows(counts, rows2, r, rng1)
743 +pick = Rng.last_nat(rng2)
744 niche_loop.rng(
745 f,
746 krest,
747 drop_nrow(rows2, pick),
748 Util.inc_at(counts, r),
749 List.append(&2, Nat, selected, [pick]),
750 rng2
751 )
752
753def fill.rng(fuel: Nat, fronts: List<&2, List<&2, Nat>>, fits: Bool, +acc: List<&2, Nat>, +target: Nat, +asgs: List<&2, Assignment>, +n_dirs: Nat, rng: Rng.State) -> List<&2, Nat> & Rng.State:
754 match fuel fronts fits:
755 case 0n fs p:
756 (acc, rng)
757 case f Nil{} p:
758 (acc, rng)
759 case 1n+f +fr <> +rest False{}:
760 +need = Nat.sub(target, Util.list_len(Nat, acc))
761 +rows = nrows_of(asgs, fr)
762 niche_loop.rng(
763 1n+Util.list_len(NRow, rows),
764 need,
765 rows,
766 seed_counts(asgs, acc, Util.zeros_nat(n_dirs)),
767 acc,
768 rng
769 )
770 case 1n+f +fr <> +rest True{}:
771 +new_acc = List.append(&2, Nat, acc, fr)
772 fill.rng(
773 f,
774 rest,
775 Nat.is_le(Nat.add(Util.list_len(Nat, new_acc), head_len(rest)), target),
776 new_acc,
777 target,
778 asgs,
779 n_dirs,
780 rng
781 )
782
783def fill.wrap.rng(+fronts: List<&2, List<&2, Nat>>, +target: Nat, +asgs: List<&2, Assignment>, +n_dirs: Nat, rng: Rng.State) -> List<&2, Nat> & Rng.State:
784 fill.rng(
785 1n+n_fronts(fronts),
786 fronts,
787 Nat.is_le(head_len(fronts), target),
788 Nil{},
789 target,
790 asgs,
791 n_dirs,
792 rng
793 )
794
795def select_idx.with(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, +fronts: List<&2, List<&2, Nat>>, pair: Norm.State & List<&2, List<&2, F32>>) -> List<&2, Nat>:
796 (st, F) = pair
797 fill.wrap(fronts, target, associate(pop, F, dirs), Util.list_len(List<&2, F32>, dirs))
798
799def select_idx.big(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Nat>:
800 +fronts = NDS.sort(pop)
801 select_idx.with(pop, target, dirs, fronts, Norm.normalize_nd(Norm.new_state(0n), pop, front0(fronts)))
802
803def select_idx.dirs(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, empty_dirs: Bool) -> List<&2, Nat>:
804 match empty_dirs:
805 case True{}:
806 List.take(&2, Nat, List.range(Util.list_len(Ind.Individual, pop)), target)
807 case False{}:
808 select_idx.big(pop, target, dirs)
809
810def select_idx.by(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, small: Bool) -> List<&2, Nat>:
811 match small:
812 case True{}:
813 List.range(Util.list_len(Ind.Individual, pop))
814 case False{}:
815 select_idx.dirs(pop, target, dirs, List.is_empty(&2, List<&2, F32>, dirs))
816
817def unused_idxs(+used: List<&2, Nat>, +n: Nat) -> List<&2, Nat>:
818 Util.minus(List.range(n), used)
819
820# Length lock: |take(pad(core, want, n), want)| = want when want ≤ n.
821# Identity when core is already a unique subset of 0..n-1 of length want
822# (the fill / range / take paths used in A/B).
823def pad_idxs(+xs: List<&2, Nat>, +want: Nat, +n: Nat) -> List<&2, Nat>:
824 List.append(&2, Nat, xs, List.take(&2, Nat, unused_idxs(xs, n), Nat.sub(want, Util.list_len(Nat, xs))))
825
826def clip_idxs(+xs: List<&2, Nat>, +want: Nat) -> List<&2, Nat>:
827 List.take(&2, Nat, xs, want)
828
829def size_lock(+xs: List<&2, Nat>, +want: Nat, +n: Nat) -> List<&2, Nat>:
830 clip_idxs(List.append(&2, Nat, pad_idxs(xs, want, n), List.range(want)), want)
831
832def select_idx(+combined: List<&2, Ind.Individual>, +target_size: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Nat>:
833 +n = Util.list_len(Ind.Individual, combined)
834 +want = Util.nat_min(target_size, n)
835 size_lock(select_idx.by(combined, target_size, dirs, Nat.is_le(n, target_size)), want, n)
836
837def select(+combined: List<&2, Ind.Individual>, +target_size: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Ind.Individual>:
838 gather(combined, select_idx(combined, target_size, dirs))
839
840# Persistent-normalization Select for Unsga3Algorithm.Run. Threads rng
841# so last-front niching matches C# Select(..., rng) on min-count niche
842# ties. Empty niches take closest; extras are random among near-best
843# on that ray. v0 `select` stays the `rng == null` path (empty laws).
844def size_lock.rng(+want: Nat, +n: Nat, pair: List<&2, Nat> & Rng.State) -> List<&2, Nat> & Rng.State:
845 (xs, rng) = pair
846 (size_lock(xs, want, n), rng)
847
848def select_st.after(+st: Norm.State, +pop: List<&2, Ind.Individual>, pair: List<&2, Nat> & Rng.State) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
849 (idxs, rng2) = pair
850 (st, gather(pop, idxs), rng2)
851
852def select_st.with(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, +fronts: List<&2, List<&2, Nat>>, pair: Norm.State & List<&2, List<&2, F32>>, rng: Rng.State) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
853 (st, F) = pair
854 +n = Util.list_len(Ind.Individual, pop)
855 +want = Util.nat_min(target, n)
856 select_st.after(st, pop, size_lock.rng(want, n, fill.wrap.rng(fronts, target, associate(pop, F, dirs), Util.list_len(List<&2, F32>, dirs), rng)))
857
858def select_st.big(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, state: Norm.State, rng: Rng.State) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
859 +fronts = NDS.sort(pop)
860 select_st.with(pop, target, dirs, fronts, Norm.normalize_nd(state, pop, front0(fronts)), rng)
861
862def select_st.take(+pop: List<&2, Ind.Individual>, +target: Nat, state: Norm.State, rng: Rng.State) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
863 +n = Util.list_len(Ind.Individual, pop)
864 (state, gather(pop, size_lock(List.take(&2, Nat, List.range(n), target), Util.nat_min(target, n), n)), rng)
865
866def select_st.dirs(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, state: Norm.State, rng: Rng.State, empty_dirs: Bool) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
867 match empty_dirs:
868 case True{}:
869 select_st.take(pop, target, state, rng)
870 case False{}:
871 select_st.big(pop, target, dirs, state, rng)
872
873def select_st.by(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, state: Norm.State, rng: Rng.State, small: Bool) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
874 match small:
875 case True{}:
876 (state, pop, rng)
877 case False{}:
878 select_st.dirs(pop, target, dirs, state, rng, List.is_empty(&2, List<&2, F32>, dirs))
879
880def select_st(+combined: List<&2, Ind.Individual>, +target_size: Nat, +dirs: List<&2, List<&2, F32>>, state: Norm.State, rng: Rng.State) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
881 +n = Util.list_len(Ind.Individual, combined)
882 select_st.by(combined, target_size, dirs, state, rng, Nat.is_le(n, target_size))