algorithm.bend
unified-nsga-iii@0.1.2.0 · 406 lines · 0 definitions
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
15import Base
16import unified-nsga-iii@0.1.2.0/individual.bend as Ind
17import unified-nsga-iii@0.1.2.0/non_dominated_sort.bend as NDS
18import unified-nsga-iii@0.1.2.0/normalization.bend as Norm
19import unified-nsga-iii@0.1.2.0/reference_directions.bend as Refs
20import unified-nsga-iii@0.1.2.0/survival.bend as Surv
21import unified-nsga-iii@0.1.2.0/bounds.bend as Bounds
22import unified-nsga-iii@0.1.2.0/rng.bend as Rng
23import unified-nsga-iii@0.1.2.0/sbx.bend as Sbx
24import unified-nsga-iii@0.1.2.0/polynomial_mutation.bend as Poly
25import unified-nsga-iii@0.1.2.0/problems.bend as Prob
26import unified-nsga-iii@0.1.2.0/tournament.bend as Tour
27import unified-nsga-iii@0.1.2.0/util.bend as Util
28
29type 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
39def 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
42def 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
47def cfg_pop(c: Config) -> Nat:
48 match c:
49 case MkConfig{dirs, pop_size, gens, seed, mode, elim_dups}:
50 pop_size
51
52def cfg_gens(c: Config) -> Nat:
53 match c:
54 case MkConfig{dirs, pop_size, gens, seed, mode, elim_dups}:
55 gens
56
57def cfg_seed(c: Config) -> Nat:
58 match c:
59 case MkConfig{dirs, pop_size, gens, seed, mode, elim_dups}:
60 seed
61
62def cfg_mode(c: Config) -> Tour.Mode:
63 match c:
64 case MkConfig{dirs, pop_size, gens, seed, mode, elim_dups}:
65 mode
66
67def 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.
73def 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).
77def oracle_zdt1() -> Config:
78 mk(Refs.das_dennis(2n, 12n), 52n, 100n, 1n, Tour.pymoo(), True{})
79
80def oracle_dtlz2() -> Config:
81 mk(Refs.das_dennis(3n, 12n), 92n, 150n, 1n, Tour.pymoo(), True{})
82
83def 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
86def 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
103def 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
106type IHold is Data:
107 IH{
108 rng: Rng.State
109 acc: List<&2, Ind.Individual>
110 }
111
112def 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
116def 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
121def 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
128def 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
131def 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
138def vars_of(xs: List<&2, Ind.Individual>) -> List<&2, List<&2, F32>>:
139 vars_of.go(xs, Nil{})
140
141def 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
148def 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
152def pred_or_zero(n: Nat) -> Nat:
153 match n:
154 case 0n:
155 0n
156 case 1n+p:
157 p
158
159def dec_if(n: Nat, hit: Bool) -> Nat:
160 match hit:
161 case True{}:
162 pred_or_zero(n)
163 case False{}:
164 n
165
166def wrap_pair.go(+pair: Nat, ok: Bool) -> Nat:
167 match ok:
168 case True{}:
169 pair
170 case False{}:
171 0n
172
173def wrap_pair(+pair: Nat, +n: Nat) -> Nat:
174 wrap_pair.go(pair, Nat.is_lt(1n+pair, n))
175
176type FHold is Data:
177 FH{
178 rng: Rng.State
179 acc: List<&2, Ind.Individual>
180 }
181
182def 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
186def 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
193def 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
200def 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
204def 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
211def 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
223def 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
227def 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
231def 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
235def 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
239def 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
262type 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
271def 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
275def 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
280def 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
285def 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
290def 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
306def 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
313def 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
323def nd_front(+pop: List<&2, Ind.Individual>) -> List<&2, Ind.Individual>:
324 Surv.gather(pop, Surv.front0(NDS.sort(pop)))
325
326def 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
336type GHold is Data:
337 GH{
338 st: Norm.State
339 xs: List<&2, Ind.Individual>
340 rng: Rng.State
341 }
342
343def one_gen.prep(+rng: Rng.State, pair: Norm.State & List<&2, Ind.Individual>) -> GHold:
344 (st, xs) = pair
345 GH{st, xs, rng}
346
347def 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
351def 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
365def 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
369def 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
374def gen_pop(hold: GHold) -> List<&2, Ind.Individual>:
375 match hold:
376 case GH{st, xs, rng}:
377 xs
378
379def 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
386def 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
390def 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
394def 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
401def 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
405def run_zdt1_smoke() -> List<&2, Ind.Individual>:
406 run(Prob.zdt1(30n), smoke_zdt1())