normalization.bend
unified-nsga-iii@0.2.1.0 · 671 lines · 0 definitions
1# Normalization — C# Unsga3.Core.Normalization (v0).
2# Persistent ideal / worst, ASF extreme points (previous extremes ∪ ND,
3# or the whole population when the ND index set is empty), intercept
4# hyperplane nadir via (E−ideal)·b = 1, then C# front/pop/unit fallbacks.
5# ASF: floor 1e-3 on ideal-translated objectives; preferred axis weight 1,
6# other axes 1e-6 (divide form).
7
8import Base
9import unified-nsga-iii@0.2.1.0/individual.bend as Ind
10import unified-nsga-iii@0.2.1.0/util.bend as Util
11
12type State is Data:
13 MkState{
14 n_objectives: Nat
15 ideal: List<&2, F32>
16 worst: List<&2, F32>
17 nadir: List<&2, F32>
18 intercepts: List<&2, F32>
19 extremes: List<&2, List<&2, F32>>
20 }
21
22def new_state(n_objectives: Nat) -> State:
23 MkState{n_objectives, Nil{}, Nil{}, Nil{}, Nil{}, Nil{}}
24
25def state_n(st: State) -> Nat:
26 match st:
27 case MkState{n_objectives, ideal, worst, nadir, intercepts, extremes}:
28 n_objectives
29
30def state_ideal(st: State) -> List<&2, F32>:
31 match st:
32 case MkState{n_objectives, ideal, worst, nadir, intercepts, extremes}:
33 ideal
34
35# Column min/max are associative. Mid-split then vec_min / vec_max.
36def col_min.go(+fuel: Nat, pop: List<&2, Ind.Individual>) -> List<&2, F32>:
37 match fuel pop:
38 case 0n Nil{}:
39 Nil{}
40 case 0n ind <> xs:
41 Util.vec_min(Ind.objectives(ind), col_min.go(0n, xs))
42 case 1n+p Nil{}:
43 Nil{}
44 case 1n+p ind <> Nil{}:
45 Ind.objectives(ind)
46 case 1n+p h <> t:
47 +all = {h <> t : List<&2, Ind.Individual>}
48 +mid = Nat.div(Util.list_len(Ind.Individual, all), 2n)
49 lo hi = col_min.go(p, List.take(&2, Ind.Individual, all, mid)) col_min.go(p, List.drop(&2, Ind.Individual, all, mid))
50 Util.vec_min(lo, hi)
51
52def col_min(+pop: List<&2, Ind.Individual>) -> List<&2, F32>:
53 col_min.go(Util.list_len(Ind.Individual, pop), pop)
54
55def col_max.go(+fuel: Nat, pop: List<&2, Ind.Individual>) -> List<&2, F32>:
56 match fuel pop:
57 case 0n Nil{}:
58 Nil{}
59 case 0n ind <> xs:
60 Util.vec_max(Ind.objectives(ind), col_max.go(0n, xs))
61 case 1n+p Nil{}:
62 Nil{}
63 case 1n+p ind <> Nil{}:
64 Ind.objectives(ind)
65 case 1n+p h <> t:
66 +all = {h <> t : List<&2, Ind.Individual>}
67 +mid = Nat.div(Util.list_len(Ind.Individual, all), 2n)
68 lo hi = col_max.go(p, List.take(&2, Ind.Individual, all, mid)) col_max.go(p, List.drop(&2, Ind.Individual, all, mid))
69 Util.vec_max(lo, hi)
70
71def col_max(+pop: List<&2, Ind.Individual>) -> List<&2, F32>:
72 col_max.go(Util.list_len(Ind.Individual, pop), pop)
73
74def get_ind(+pop: List<&2, Ind.Individual>, i: Nat) -> Maybe<&2, Ind.Individual>:
75 List.get(&2, Ind.Individual, pop, i)
76
77def max_at.go(acc: List<&2, F32>, m: Maybe<&2, Ind.Individual>) -> List<&2, F32>:
78 match m:
79 case None{}:
80 acc
81 case Some{ind}:
82 Util.vec_max(acc, Ind.objectives(ind))
83
84def max_at(+pop: List<&2, Ind.Individual>, acc: List<&2, F32>, i: Nat) -> List<&2, F32>:
85 max_at.go(acc, get_ind(pop, i))
86
87def col_max_idx.go(+pop: List<&2, Ind.Individual>, +fuel: Nat, idxs: List<&2, Nat>) -> List<&2, F32>:
88 match fuel idxs:
89 case 0n Nil{}:
90 Nil{}
91 case 0n +i <> rest:
92 max_at(pop, col_max_idx.go(pop, 0n, rest), i)
93 case 1n+p Nil{}:
94 Nil{}
95 case 1n+p +i <> Nil{}:
96 max_at(pop, Nil{}, i)
97 case 1n+p h <> t:
98 +all = {h <> t : List<&2, Nat>}
99 +mid = Nat.div(Util.list_len(Nat, all), 2n)
100 lo hi = col_max_idx.go(pop, p, List.take(&2, Nat, all, mid)) col_max_idx.go(pop, p, List.drop(&2, Nat, all, mid))
101 Util.vec_max(lo, hi)
102
103def col_max_idx(+pop: List<&2, Ind.Individual>, idxs: List<&2, Nat>) -> List<&2, F32>:
104 match idxs:
105 case Nil{}:
106 col_max(pop)
107 case +i <> +rest:
108 +xs = {i <> rest : List<&2, Nat>}
109 col_max_idx.go(pop, Util.list_len(Nat, xs), xs)
110
111def merge_ideal(prev: List<&2, F32>, cur: List<&2, F32>) -> List<&2, F32>:
112 match prev:
113 case Nil{}:
114 cur
115 case x <> xs:
116 Util.vec_min(x <> xs, cur)
117
118def merge_worst(prev: List<&2, F32>, cur: List<&2, F32>) -> List<&2, F32>:
119 match prev:
120 case Nil{}:
121 cur
122 case x <> xs:
123 Util.vec_max(x <> xs, cur)
124
125def nd_or_all(nd: List<&2, Nat>, n: Nat) -> List<&2, Nat>:
126 match nd:
127 case Nil{}:
128 List.range(n)
129 case h <> t:
130 h <> t
131
132def obj_at.go(m: Maybe<&2, Ind.Individual>) -> List<&2, F32>:
133 match m:
134 case None{}:
135 Nil{}
136 case Some{ind}:
137 Ind.objectives(ind)
138
139def obj_at(+pop: List<&2, Ind.Individual>, i: Nat) -> List<&2, F32>:
140 obj_at.go(get_ind(pop, i))
141
142def gather_objs.one(+pop: List<&2, Ind.Individual>, +i: Nat) -> List<&2, F32>:
143 obj_at(pop, i)
144
145def gather_objs(+pop: List<&2, Ind.Individual>, +idxs: List<&2, Nat>) -> List<&2, List<&2, F32>>:
146 Util.map_halves(~Nat, ~List<&2, F32>, ~List<&2, Ind.Individual>, ~gather_objs.one, pop, idxs)
147
148def map_norm.one(+ideal: List<&2, F32>, +nadir: List<&2, F32>, +ind: Ind.Individual) -> List<&2, F32>:
149 Util.vec_norm_div(Ind.objectives(ind), ideal, nadir)
150
151# Independent per individual given ideal/nadir. Mid-split + parallel recurse.
152def map_norm.go(+ideal: List<&2, F32>, +nadir: List<&2, F32>, +fuel: Nat, pop: List<&2, Ind.Individual>) -> List<&2, List<&2, F32>>:
153 match fuel pop:
154 case 0n Nil{}:
155 Nil{}
156 case 0n h <> t:
157 map_norm.one(ideal, nadir, h) <> map_norm.go(ideal, nadir, 0n, t)
158 case 1n+p Nil{}:
159 Nil{}
160 case 1n+p h <> Nil{}:
161 map_norm.one(ideal, nadir, h) <> Nil{}
162 case 1n+p h <> t:
163 +all = {h <> t : List<&2, Ind.Individual>}
164 +mid = Nat.div(Util.list_len(Ind.Individual, all), 2n)
165 lo hi = map_norm.go(ideal, nadir, p, List.take(&2, Ind.Individual, all, mid)) map_norm.go(ideal, nadir, p, List.drop(&2, Ind.Individual, all, mid))
166 List.append(&2, List<&2, F32>, lo, hi)
167
168def map_norm(+ideal: List<&2, F32>, +nadir: List<&2, F32>, +pop: List<&2, Ind.Individual>) -> List<&2, List<&2, F32>>:
169 map_norm.go(ideal, nadir, Util.list_len(Ind.Individual, pop), pop)
170
171def n_obj_pop(pop: List<&2, Ind.Individual>) -> Nat:
172 match pop:
173 case Nil{}:
174 0n
175 case ind <> rest:
176 Ind.n_obj(ind)
177
178# ASF on ideal-translated objectives (pymoo __F = F − ideal).
179def asf_term(+fj: F32, +ij: F32, on_axis: Bool) -> F32:
180 +raw = F32.sub(fj, ij)
181 +v = Bool.pick(F32, F32.is_lt(raw, 1.0e-3), 0.0, raw)
182 +w = Bool.pick(F32, on_axis, 1.0, 1.0e-6)
183 F32.div(v, w)
184
185def asf.go(f: List<&2, F32>, ideal: List<&2, F32>, +axis: Nat, +j: Nat, acc: F32) -> F32:
186 match f ideal:
187 case Nil{} ys:
188 acc
189 case xs Nil{}:
190 acc
191 case x <> xs y <> ys:
192 asf.go(xs, ys, axis, 1n+j, F32.max(acc, asf_term(x, y, Nat.is_eq(j, axis))))
193
194def asf(f: List<&2, F32>, +axis: Nat, +ideal: List<&2, F32>) -> F32:
195 match f ideal:
196 case Nil{} ys:
197 0.0
198 case xs Nil{}:
199 0.0
200 case x <> xs y <> ys:
201 asf.go(xs, ys, axis, 1n, asf_term(x, y, Nat.is_eq(0n, axis)))
202
203def pick_axis.go(rest: List<&2, List<&2, F32>>, +ideal: List<&2, F32>, +axis: Nat, +best_f: List<&2, F32>, +best_asf: F32) -> List<&2, F32>:
204 match rest:
205 case Nil{}:
206 best_f
207 case +f <> fs:
208 +a = asf(f, axis, ideal)
209 pick_axis.go(
210 fs,
211 ideal,
212 axis,
213 Bool.pick(List<&2, F32>, F32.is_lt(a, best_asf), f, best_f),
214 Bool.pick(F32, F32.is_lt(a, best_asf), a, best_asf)
215 )
216
217def pick_axis(cand: List<&2, List<&2, F32>>, +ideal: List<&2, F32>, +axis: Nat) -> List<&2, F32>:
218 match cand:
219 case Nil{}:
220 Nil{}
221 case +h <> t:
222 pick_axis.go(t, ideal, axis, h, asf(h, axis, ideal))
223
224type ExtCtx is Data:
225 ExtCtx{
226 cand: List<&2, List<&2, F32>>
227 ideal: List<&2, F32>
228 }
229
230def pick_axis.one(+ctx: ExtCtx, +axis: Nat) -> List<&2, F32>:
231 match ctx:
232 case ExtCtx{cand, ideal}:
233 pick_axis(cand, ideal, axis)
234
235# One ASF extreme per axis; axes are independent.
236def pick_extremes(+cand: List<&2, List<&2, F32>>, +ideal: List<&2, F32>, m: Nat) -> List<&2, List<&2, F32>>:
237 Util.map_halves(~Nat, ~List<&2, F32>, ~ExtCtx, ~pick_axis.one, ExtCtx{cand, ideal}, List.range(m))
238
239def get_row(+mat: List<&2, List<&2, F32>>, i: Nat) -> List<&2, F32>:
240 Maybe.default(&2, List<&2, F32>, List.get(&2, List<&2, F32>, mat, i), Nil{})
241
242def mat_get(+mat: List<&2, List<&2, F32>>, i: Nat, j: Nat) -> F32:
243 Util.get_f32(get_row(mat, i), j)
244
245def swap_rows.do(+mat: List<&2, List<&2, F32>>, +i: Nat, +k: Nat) -> List<&2, List<&2, F32>>:
246 +ri = get_row(mat, i)
247 +rk = get_row(mat, k)
248 List.set(&2, List<&2, F32>, List.set(&2, List<&2, F32>, mat, i, rk), k, ri)
249
250def swap_rows.when(+mat: List<&2, List<&2, F32>>, +i: Nat, +k: Nat, same: Bool) -> List<&2, List<&2, F32>>:
251 match same:
252 case True{}:
253 mat
254 case False{}:
255 swap_rows.do(mat, i, k)
256
257def swap_rows(+mat: List<&2, List<&2, F32>>, +i: Nat, +k: Nat) -> List<&2, List<&2, F32>>:
258 swap_rows.when(mat, i, k, Nat.is_eq(i, k))
259
260def scale_vec.go(fuel: Nat, +row: List<&2, F32>, +j: Nat, +div: F32) -> List<&2, F32>:
261 match fuel:
262 case 0n:
263 row
264 case 1n+f:
265 scale_vec.go(f, Util.set_f32(row, j, F32.div(Util.get_f32(row, j), div)), 1n+j, div)
266
267def scale_row(+mat: List<&2, List<&2, F32>>, +col: Nat, +n: Nat, +div: F32) -> List<&2, List<&2, F32>>:
268 List.set(&2, List<&2, F32>, mat, col, scale_vec.go(1n+Nat.sub(n, col), get_row(mat, col), col, div))
269
270def axpy_vec.go(fuel: Nat, +row: List<&2, F32>, +piv: List<&2, F32>, +j: Nat, +factor: F32) -> List<&2, F32>:
271 match fuel:
272 case 0n:
273 row
274 case 1n+f:
275 +x = Util.get_f32(row, j)
276 +p = Util.get_f32(piv, j)
277 axpy_vec.go(f, Util.set_f32(row, j, F32.sub(x, F32.mul(factor, p))), piv, 1n+j, factor)
278
279def axpy_row(+mat: List<&2, List<&2, F32>>, +row: Nat, +col: Nat, +n: Nat, +factor: F32, +piv: List<&2, F32>) -> List<&2, List<&2, F32>>:
280 List.set(&2, List<&2, F32>, mat, row, axpy_vec.go(1n+Nat.sub(n, col), get_row(mat, row), piv, col, factor))
281
282def find_pivot.go(fuel: Nat, +mat: List<&2, List<&2, F32>>, +col: Nat, +row: Nat, +best_row: Nat, +best: F32) -> Nat:
283 match fuel:
284 case 0n:
285 best_row
286 case 1n+f:
287 +v = F32.abs(mat_get(mat, row, col))
288 find_pivot.go(
289 f,
290 mat,
291 col,
292 1n+row,
293 Bool.pick(Nat, F32.is_gt(v, best), row, best_row),
294 F32.max(v, best)
295 )
296
297def find_pivot(+mat: List<&2, List<&2, F32>>, +col: Nat, +n: Nat) -> Nat:
298 find_pivot.go(Nat.sub(n, col), mat, col, col, col, F32.abs(mat_get(mat, col, col)))
299
300def elim_one(+row: Nat, +col: Nat, +n: Nat, +piv: List<&2, F32>, +mat: List<&2, List<&2, F32>>, skip: Bool) -> List<&2, List<&2, F32>>:
301 match skip:
302 case True{}:
303 mat
304 case False{}:
305 axpy_row(mat, row, col, n, mat_get(mat, row, col), piv)
306
307def elim_rows(fuel: Nat, +row: Nat, +col: Nat, +n: Nat, +piv: List<&2, F32>, mat: List<&2, List<&2, F32>>) -> List<&2, List<&2, F32>>:
308 match fuel:
309 case 0n:
310 mat
311 case 1n+f:
312 elim_rows(f, 1n+row, col, n, piv, elim_one(row, col, n, piv, mat, Nat.is_eq(row, col)))
313
314def ge_step(+col: Nat, +n: Nat, +mat: List<&2, List<&2, F32>>, +pivot: Nat, tiny: Bool) -> Maybe<&2, List<&2, List<&2, F32>>>:
315 match tiny:
316 case True{}:
317 None{}
318 case False{}:
319 +swapped = swap_rows(mat, col, pivot)
320 +div = mat_get(swapped, col, col)
321 +scaled = scale_row(swapped, col, n, div)
322 Some{elim_rows(n, 0n, col, n, get_row(scaled, col), scaled)}
323
324def ge_col.go(fuel: Nat, +col: Nat, +n: Nat, acc: Maybe<&2, List<&2, List<&2, F32>>>) -> Maybe<&2, List<&2, List<&2, F32>>>:
325 match fuel acc:
326 case f None{}:
327 None{}
328 case 0n Some{mat}:
329 Some{mat}
330 case 1n+f Some{+mat}:
331 +pivot = find_pivot(mat, col, n)
332 ge_col.go(
333 f,
334 1n+col,
335 n,
336 ge_step(col, n, mat, pivot, F32.is_lt(F32.abs(mat_get(mat, pivot, col)), 1.0e-14))
337 )
338
339def ge_col(fuel: Nat, +col: Nat, +n: Nat, mat: List<&2, List<&2, F32>>) -> Maybe<&2, List<&2, List<&2, F32>>>:
340 ge_col.go(fuel, col, n, Some{mat})
341
342def extract_x.go(fuel: Nat, +mat: List<&2, List<&2, F32>>, +n: Nat, +i: Nat, acc: List<&2, F32>) -> List<&2, F32>:
343 match fuel:
344 case 0n:
345 acc
346 case 1n+f:
347 extract_x.go(f, mat, n, 1n+i, List.append(&2, F32, acc, [mat_get(mat, i, n)]))
348
349def extract_x(+mat: List<&2, List<&2, F32>>, +n: Nat) -> List<&2, F32>:
350 extract_x.go(n, mat, n, 0n, Nil{})
351
352def solve_linear.go(done: Maybe<&2, List<&2, List<&2, F32>>>, +n: Nat) -> Maybe<&2, List<&2, F32>>:
353 match done:
354 case None{}:
355 None{}
356 case Some{mat}:
357 Some{extract_x(mat, n)}
358
359def build_aug(+ideal: List<&2, F32>, ext: List<&2, List<&2, F32>>) -> List<&2, List<&2, F32>>:
360 match ext:
361 case Nil{}:
362 Nil{}
363 case row <> rest:
364 List.append(&2, F32, Util.vec_sub(row, ideal), [1.0]) <> build_aug(ideal, rest)
365
366def solve_linear(+ext: List<&2, List<&2, F32>>, +ideal: List<&2, F32>, +n: Nat) -> Maybe<&2, List<&2, F32>>:
367 solve_linear.go(ge_col(n, 0n, n, build_aug(ideal, ext)), n)
368
369def intercept_bad(+inv: F32) -> Bool:
370 Bool.or(
371 F32.is_ne(inv, inv),
372 Bool.or(F32.is_le(inv, 1.0e-6), F32.is_ne(F32.mul(inv, 0.0), 0.0))
373 )
374
375def inv_ok.fin(+inv: F32, bad: Bool) -> Maybe<&2, F32>:
376 match bad:
377 case True{}:
378 None{}
379 case False{}:
380 Some{inv}
381
382def inv_ok.pos(+xj: F32, tiny: Bool) -> Maybe<&2, F32>:
383 match tiny:
384 case True{}:
385 None{}
386 case False{}:
387 +inv = F32.div(1.0, xj)
388 inv_ok.fin(inv, intercept_bad(inv))
389
390# C#: |x| < 1e-12 or x < 0 fails; then intercept = 1/x must be finite and > 1e-6.
391def inv_ok(+xj: F32) -> Maybe<&2, F32>:
392 inv_ok.pos(xj, Bool.or(F32.is_lt(F32.abs(xj), 1.0e-12), F32.is_lt(xj, 0.0)))
393
394def intercepts_from_x.one(h: Maybe<&2, F32>, ys: List<&2, F32>) -> Maybe<&2, List<&2, F32>>:
395 match h:
396 case None{}:
397 None{}
398 case Some{inv}:
399 Some{inv <> ys}
400
401def intercepts_from_x.cons(+xj: F32, rest: Maybe<&2, List<&2, F32>>) -> Maybe<&2, List<&2, F32>>:
402 match rest:
403 case None{}:
404 None{}
405 case Some{ys}:
406 intercepts_from_x.one(inv_ok(xj), ys)
407
408def intercepts_from_x(x: List<&2, F32>) -> Maybe<&2, List<&2, F32>>:
409 match x:
410 case Nil{}:
411 Some{Nil{}}
412 case xj <> xs:
413 intercepts_from_x.cons(xj, intercepts_from_x(xs))
414
415def try_intercepts.go(x: Maybe<&2, List<&2, F32>>) -> Maybe<&2, List<&2, F32>>:
416 match x:
417 case None{}:
418 None{}
419 case Some{xs}:
420 intercepts_from_x(xs)
421
422def try_intercepts(+ext: List<&2, List<&2, F32>>, +ideal: List<&2, F32>) -> Maybe<&2, List<&2, F32>>:
423 try_intercepts.go(solve_linear(ext, ideal, Util.list_len(F32, ideal)))
424
425def add_ideal(ideal: List<&2, F32>, icepts: List<&2, F32>) -> List<&2, F32>:
426 match ideal icepts:
427 case Nil{} zs:
428 Nil{}
429 case xs Nil{}:
430 Nil{}
431 case x <> xs z <> zs:
432 F32.add(x, z) <> add_ideal(xs, zs)
433
434def clamp_worst(nadir: List<&2, F32>, worst: List<&2, F32>) -> List<&2, F32>:
435 match nadir worst:
436 case Nil{} ws:
437 Nil{}
438 case ns Nil{}:
439 ns
440 case +n <> ns +w <> ws:
441 Bool.pick(F32, F32.is_gt(n, w), w, n) <> clamp_worst(ns, ws)
442
443def nadir_from_maybe(m: Maybe<&2, List<&2, F32>>, +ideal: List<&2, F32>, +worst: List<&2, F32>, +front: List<&2, F32>) -> List<&2, F32>:
444 match m:
445 case None{}:
446 front
447 case Some{icepts}:
448 clamp_worst(add_ideal(ideal, icepts), worst)
449
450def fallback_pop(nadir: List<&2, F32>, ideal: List<&2, F32>, wpop: List<&2, F32>) -> List<&2, F32>:
451 match nadir ideal wpop:
452 case Nil{} ils wps:
453 Nil{}
454 case ns Nil{} wps:
455 ns
456 case ns ils Nil{}:
457 ns
458 case +n <> ns +i <> ils +w <> wps:
459 Bool.pick(F32, F32.is_le(F32.sub(n, i), 1.0e-6), w, n) <> fallback_pop(ns, ils, wps)
460
461def fallback_unit(nadir: List<&2, F32>, ideal: List<&2, F32>) -> List<&2, F32>:
462 match nadir ideal:
463 case Nil{} ils:
464 Nil{}
465 case ns Nil{}:
466 ns
467 case +n <> ns +i <> ils:
468 Bool.pick(F32, F32.is_le(F32.sub(n, i), 1.0e-6), F32.add(i, 1.0), n) <> fallback_unit(ns, ils)
469
470def spans_or_one(nadir: List<&2, F32>, ideal: List<&2, F32>) -> List<&2, F32>:
471 match nadir ideal:
472 case Nil{} ils:
473 Nil{}
474 case ns Nil{}:
475 Nil{}
476 case +n <> ns +i <> ils:
477 +span = F32.sub(n, i)
478 Bool.pick(F32, F32.is_le(span, 1.0e-12), 1.0, span) <> spans_or_one(ns, ils)
479
480def normalize_nd.body(+ideal0: List<&2, F32>, +worst0: List<&2, F32>, +ext0: List<&2, List<&2, F32>>, +pop: List<&2, Ind.Individual>, nd: List<&2, Nat>) -> State & List<&2, List<&2, F32>>:
481 +mn = col_min(pop)
482 +mx = col_max(pop)
483 +ideal = merge_ideal(ideal0, mn)
484 +worst = merge_worst(worst0, mx)
485 +nd_use = nd_or_all(nd, Util.list_len(Ind.Individual, pop))
486 +front = col_max_idx(pop, nd_use)
487 +cand = List.append(&2, List<&2, F32>, ext0, gather_objs(pop, nd_use))
488 +m = n_obj_pop(pop)
489 +ext = pick_extremes(cand, ideal, m)
490 +nadir0 = nadir_from_maybe(try_intercepts(ext, ideal), ideal, worst, front)
491 +nadir1 = fallback_pop(nadir0, ideal, mx)
492 +nadir = fallback_unit(nadir1, ideal)
493 (MkState{m, ideal, worst, nadir, spans_or_one(nadir, ideal), ext}, map_norm(ideal, nadir, pop))
494
495def normalize_nd.go(state: State, +pop: List<&2, Ind.Individual>, nd: List<&2, Nat>) -> State & List<&2, List<&2, F32>>:
496 match state:
497 case MkState{n_objectives, ideal, worst, nadir, intercepts, extremes}:
498 normalize_nd.body(ideal, worst, extremes, pop, nd)
499
500# A computed Bool is matched only as a parameter. The recursive result
501# is an argument, so these walks are not mutually recursive.
502def has_infeas.on(later: Bool, feas: Bool) -> Bool:
503 match feas:
504 case False{}:
505 True{}
506 case True{}:
507 later
508
509def has_infeas(pop: List<&2, Ind.Individual>) -> Bool:
510 match pop:
511 case Nil{}:
512 False{}
513 case h <> t:
514 has_infeas.on(has_infeas(t), Ind.feasible(h))
515
516def has_feas.on(later: Bool, feas: Bool) -> Bool:
517 match feas:
518 case True{}:
519 True{}
520 case False{}:
521 later
522
523def has_feas(pop: List<&2, Ind.Individual>) -> Bool:
524 match pop:
525 case Nil{}:
526 False{}
527 case h <> t:
528 has_feas.on(has_feas(t), Ind.feasible(h))
529
530def feas_inds.on(+h: Ind.Individual, rest: List<&2, Ind.Individual>, ok: Bool) -> List<&2, Ind.Individual>:
531 match ok:
532 case True{}:
533 h <> rest
534 case False{}:
535 rest
536
537def feas_inds(pop: List<&2, Ind.Individual>) -> List<&2, Ind.Individual>:
538 match pop:
539 case Nil{}:
540 Nil{}
541 case +h <> t:
542 feas_inds.on(h, feas_inds(t), Ind.feasible(h))
543
544def feas_idx.on(+i: Nat, rest: List<&2, Nat>, ok: Bool) -> List<&2, Nat>:
545 match ok:
546 case True{}:
547 i <> rest
548 case False{}:
549 rest
550
551def feas_idx.go(pop: List<&2, Ind.Individual>, +i: Nat) -> List<&2, Nat>:
552 match pop:
553 case Nil{}:
554 Nil{}
555 case h <> t:
556 feas_idx.on(i, feas_idx.go(t, 1n+i), Ind.feasible(h))
557
558def feas_idx(pop: List<&2, Ind.Individual>) -> List<&2, Nat>:
559 feas_idx.go(pop, 0n)
560
561def keep_in.go(idxs: List<&2, Nat>, +pool: List<&2, Nat>) -> List<&2, Nat>:
562 match idxs:
563 case Nil{}:
564 Nil{}
565 case +i <> t:
566 Util.keep_if(Nat, i, keep_in.go(t, pool), Util.in_nats(i, pool))
567
568def keep_in(idxs: List<&2, Nat>, +pool: List<&2, Nat>) -> List<&2, Nat>:
569 keep_in.go(idxs, pool)
570
571def nd_mixed.use(pool: List<&2, Nat>, kept: List<&2, Nat>) -> List<&2, Nat>:
572 match kept:
573 case Nil{}:
574 pool
575 case a <> b:
576 a <> b
577
578# ND indices restricted to feasible members. Empty or fully infeasible
579# fronts fall back to every feasible index (C# ExtremeIndices).
580def nd_mixed.go(nd: List<&2, Nat>, +pool: List<&2, Nat>) -> List<&2, Nat>:
581 match nd:
582 case Nil{}:
583 pool
584 case h <> t:
585 nd_mixed.use(pool, keep_in(h <> t, pool))
586
587def nd_mixed(pop: List<&2, Ind.Individual>, nd: List<&2, Nat>) -> List<&2, Nat>:
588 nd_mixed.go(nd, feas_idx(pop))
589
590# All-infeasible: do not write ideal / nadir. A fresh state projects with
591# this generation's min/max only. A persisted state reuses its hyperplane.
592def project_fixed.back(n: Nat, +ideal: List<&2, F32>, worst: List<&2, F32>, +nadir: List<&2, F32>, intercepts: List<&2, F32>, extremes: List<&2, List<&2, F32>>, +pop: List<&2, Ind.Individual>, open: Bool) -> State & List<&2, List<&2, F32>>:
593 match open:
594 case True{}:
595 (MkState{n, ideal, worst, nadir, intercepts, extremes}, map_norm(col_min(pop), col_max(pop), pop))
596 case False{}:
597 (MkState{n, ideal, worst, nadir, intercepts, extremes}, map_norm(ideal, nadir, pop))
598
599def project_fixed.ideal(n: Nat, ideal: List<&2, F32>, worst: List<&2, F32>, nadir: List<&2, F32>, intercepts: List<&2, F32>, extremes: List<&2, List<&2, F32>>, +pop: List<&2, Ind.Individual>) -> State & List<&2, List<&2, F32>>:
600 match ideal:
601 case Nil{}:
602 project_fixed.back(n, ideal, worst, nadir, intercepts, extremes, pop, True{})
603 case h <> t:
604 project_fixed.back(n, h <> t, worst, nadir, intercepts, extremes, pop, False{})
605
606def project_fixed(state: State, +pop: List<&2, Ind.Individual>) -> State & List<&2, List<&2, F32>>:
607 match state:
608 case MkState{n_objectives, ideal, worst, nadir, intercepts, extremes}:
609 project_fixed.ideal(n_objectives, ideal, worst, nadir, intercepts, extremes, pop)
610
611# Stats (ideal, worst, extremes, nadir) use the feasible subset.
612# Every member, including infeasible, is translated by that hyperplane.
613def normalize_mixed(state: State, +pop: List<&2, Ind.Individual>, nd: List<&2, Nat>) -> State & List<&2, List<&2, F32>>:
614 match state:
615 case MkState{n_objectives, ideal, worst, nadir, intercepts, extremes}:
616 +stat = feas_inds(pop)
617 +use = nd_mixed(pop, nd)
618 +mn = col_min(stat)
619 +mx = col_max(stat)
620 +ideal2 = merge_ideal(ideal, mn)
621 +worst2 = merge_worst(worst, mx)
622 +front = col_max_idx(pop, use)
623 +cand = List.append(&2, List<&2, F32>, extremes, gather_objs(pop, use))
624 +m = n_obj_pop(pop)
625 +ext = pick_extremes(cand, ideal2, m)
626 +nadir0 = nadir_from_maybe(try_intercepts(ext, ideal2), ideal2, worst2, front)
627 +nadir1 = fallback_pop(nadir0, ideal2, mx)
628 +nadir2 = fallback_unit(nadir1, ideal2)
629 (MkState{m, ideal2, worst2, nadir2, spans_or_one(nadir2, ideal2), ext}, map_norm(ideal2, nadir2, pop))
630
631def normalize_nd.bad(state: State, +pop: List<&2, Ind.Individual>, nd: List<&2, Nat>, feas: Bool) -> State & List<&2, List<&2, F32>>:
632 match feas:
633 case False{}:
634 project_fixed(state, pop)
635 case True{}:
636 normalize_mixed(state, pop, nd)
637
638def normalize_nd.pick(state: State, +pop: List<&2, Ind.Individual>, nd: List<&2, Nat>, bad: Bool) -> State & List<&2, List<&2, F32>>:
639 match bad:
640 case False{}:
641 normalize_nd.go(state, pop, nd)
642 case True{}:
643 normalize_nd.bad(state, pop, nd, has_feas(pop))
644
645# Public normalize stays the all-member hyperplane. `Laws.normalize_len`
646# unfolds this function. Constrained Run uses `normalize_nd_cv`.
647def normalize_nd(state: State, +pop: List<&2, Ind.Individual>, nd: List<&2, Nat>) -> State & List<&2, List<&2, F32>>:
648 match pop:
649 case Nil{}:
650 (state, Nil{})
651 case h <> t:
652 normalize_nd.go(state, h <> t, nd)
653
654# Feasible-only ideal / nadir when any member is infeasible.
655# All-feasible and empty pools are `normalize_nd`.
656def normalize_nd_cv(state: State, +pop: List<&2, Ind.Individual>, nd: List<&2, Nat>) -> State & List<&2, List<&2, F32>>:
657 match pop:
658 case Nil{}:
659 (state, Nil{})
660 case h <> t:
661 normalize_nd.pick(state, h <> t, nd, has_infeas(h <> t))
662
663def normalize(state: State, pop: List<&2, Ind.Individual>) -> State & List<&2, List<&2, F32>>:
664 normalize_nd(state, pop, Nil{})
665
666def normalize_vecs.snd(pair: State & List<&2, List<&2, F32>>) -> List<&2, List<&2, F32>>:
667 (state, vecs) = pair
668 vecs
669
670def normalize_vecs(+xs: List<&2, Ind.Individual>) -> List<&2, List<&2, F32>>:
671 normalize_vecs.snd(normalize(new_state(n_obj_pop(xs)), xs))