tournament.bend
unified-nsga-iii@0.2.1.0 · 245 lines · 0 definitions
1# Mating tournament — C# TournamentSelection / TournamentMode.
2# Default for algorithm A/B is PymooCompatible (pymoo
3# comp_by_rank_and_ref_line_dist): same niche → rank then perp dist;
4# else random. RankNicheDistance (C# WinnerRankNicheDistance) is
5# rank → niche count → perpendicular distance → coin.
6# Both modes take CV first. Feasible (cv ≤ 0) beats infeasible.
7# PymooCompatible: if either is infeasible, smaller CV wins and equal
8# CV is a coin (no rank / distance). RankNicheDistance: both infeasible
9# and unequal CV → smaller CV; equal CV falls through to rank.
10# cv 0 on both sides keeps the feasible comparators. A/B stays
11# PymooCompatible. See src/trn_seed682.bend.
12
13import Base
14import unified-nsga-iii@0.2.1.0/individual.bend as Ind
15import unified-nsga-iii@0.2.1.0/non_dominated_sort.bend as NDS
16import unified-nsga-iii@0.2.1.0/normalization.bend as Norm
17import unified-nsga-iii@0.2.1.0/survival.bend as Surv
18import unified-nsga-iii@0.2.1.0/rng.bend as Rng
19import unified-nsga-iii@0.2.1.0/util.bend as Util
20
21type Mode is Data:
22 PymooCompatible{}
23 RankNicheDistance{}
24
25def pymoo() -> Mode:
26 PymooCompatible{}
27
28def rank_niche() -> Mode:
29 RankNicheDistance{}
30
31def get_ind(+pop: List<&2, Ind.Individual>, i: Nat) -> Ind.Individual:
32 Maybe.default(&2, Ind.Individual, List.get(&2, Ind.Individual, pop, i), Ind.from_objectives(Nil{}))
33
34def coin(a: Ind.Individual, b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
35 +rng2 = Rng.next_double(rng)
36 (rng2, Bool.pick(Ind.Individual, F32.is_lt(Rng.last_double(rng2), 0.5), a, b))
37
38def cmp_pick(a: Ind.Individual, b: Ind.Individual, rng: Rng.State, ab: Bool, ba: Bool) -> Rng.State & Ind.Individual:
39 match ab ba:
40 case True{} _:
41 (rng, a)
42 case False{} True{}:
43 (rng, b)
44 case False{} False{}:
45 coin(a, b, rng)
46
47def by_dist(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
48 +da = Ind.perp_dist(a)
49 +db = Ind.perp_dist(b)
50 cmp_pick(a, b, rng, F32.is_lt(da, db), F32.is_lt(db, da))
51
52def by_rank.eq(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual:
53 match same:
54 case True{}:
55 by_dist(a, b, rng)
56 case False{}:
57 cmp_pick(a, b, rng, Nat.is_lt(Ind.rank(a), Ind.rank(b)), Nat.is_lt(Ind.rank(b), Ind.rank(a)))
58
59def by_rank(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
60 by_rank.eq(a, b, rng, Nat.is_eq(Ind.rank(a), Ind.rank(b)))
61
62def winner_pymoo.same(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual:
63 match same:
64 case True{}:
65 by_rank(a, b, rng)
66 case False{}:
67 coin(a, b, rng)
68
69def winner_pymoo.cv_b(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, b_lt: Bool) -> Rng.State & Ind.Individual:
70 match b_lt:
71 case True{}:
72 (rng, b)
73 case False{}:
74 coin(a, b, rng)
75
76# Either infeasible: smaller CV, else coin. Does not read rank.
77def winner_pymoo.cv(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, a_lt: Bool, b_lt: Bool) -> Rng.State & Ind.Individual:
78 match a_lt:
79 case True{}:
80 (rng, a)
81 case False{}:
82 winner_pymoo.cv_b(a, b, rng, b_lt)
83
84def winner_pymoo.gate(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, either: Bool) -> Rng.State & Ind.Individual:
85 match either:
86 case True{}:
87 winner_pymoo.cv(a, b, rng, F32.is_lt(Ind.constraint_violation(a), Ind.constraint_violation(b)), F32.is_lt(Ind.constraint_violation(b), Ind.constraint_violation(a)))
88 case False{}:
89 winner_pymoo.same(a, b, rng, Nat.is_eq(Ind.associated_ref(a), Ind.associated_ref(b)))
90
91def winner_pymoo(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
92 winner_pymoo.gate(
93 a,
94 b,
95 rng,
96 Bool.or(Bool.not(Ind.feasible(a)), Bool.not(Ind.feasible(b)))
97 )
98
99# Equal niche counts fall through to perpendicular distance (then coin).
100# A count tie used to coin immediately and skip distance.
101def by_niche.eq(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual:
102 match same:
103 case True{}:
104 by_dist(a, b, rng)
105 case False{}:
106 cmp_pick(a, b, rng, Nat.is_lt(Ind.niche(a), Ind.niche(b)), Nat.is_lt(Ind.niche(b), Ind.niche(a)))
107
108def by_niche(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
109 by_niche.eq(a, b, rng, Nat.is_eq(Ind.niche(a), Ind.niche(b)))
110
111def winner_rnd.eq(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual:
112 match same:
113 case True{}:
114 by_niche(a, b, rng)
115 case False{}:
116 cmp_pick(a, b, rng, Nat.is_lt(Ind.rank(a), Ind.rank(b)), Nat.is_lt(Ind.rank(b), Ind.rank(a)))
117
118def winner_rnd.cv_b(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, b_lt: Bool) -> Rng.State & Ind.Individual:
119 match b_lt:
120 case True{}:
121 (rng, b)
122 case False{}:
123 winner_rnd.eq(a, b, rng, Nat.is_eq(Ind.rank(a), Ind.rank(b)))
124
125# Both infeasible. Equal CV falls through to rank (not a coin, not Pareto).
126def winner_rnd.cv(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, a_lt: Bool, b_lt: Bool) -> Rng.State & Ind.Individual:
127 match a_lt:
128 case True{}:
129 (rng, a)
130 case False{}:
131 winner_rnd.cv_b(a, b, rng, b_lt)
132
133def winner_rnd.gate(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, a_feas: Bool, b_feas: Bool) -> Rng.State & Ind.Individual:
134 match a_feas b_feas:
135 case True{} False{}:
136 (rng, a)
137 case False{} True{}:
138 (rng, b)
139 case True{} True{}:
140 winner_rnd.eq(a, b, rng, Nat.is_eq(Ind.rank(a), Ind.rank(b)))
141 case False{} False{}:
142 winner_rnd.cv(a, b, rng, F32.is_lt(Ind.constraint_violation(a), Ind.constraint_violation(b)), F32.is_lt(Ind.constraint_violation(b), Ind.constraint_violation(a)))
143
144def winner_rnd(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
145 winner_rnd.gate(a, b, rng, Ind.feasible(a), Ind.feasible(b))
146
147def winner(mode: Mode, +a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
148 match mode:
149 case PymooCompatible{}:
150 winner_pymoo(a, b, rng)
151 case RankNicheDistance{}:
152 winner_rnd(a, b, rng)
153
154def one(+mode: Mode, +pop: List<&2, Ind.Individual>, rng: Rng.State) -> Rng.State & Ind.Individual:
155 +n = Util.list_len(Ind.Individual, pop)
156 +rng_a = Rng.next_nat(rng, n)
157 +ia = Rng.last_nat(rng_a)
158 +rng_b = Rng.next_except(rng_a, n, ia)
159 +ib = Rng.last_nat(rng_b)
160 winner(mode, get_ind(pop, ia), get_ind(pop, ib), rng_b)
161
162type PHold is Data:
163 PH{
164 rng: Rng.State
165 acc: List<&2, Ind.Individual>
166 }
167
168def parents_next.w(acc: List<&2, Ind.Individual>, pair: Rng.State & Ind.Individual) -> PHold:
169 (rng, w) = pair
170 PH{rng, w <> acc}
171
172def parents_next(+mode: Mode, +pop: List<&2, Ind.Individual>, hold: PHold) -> PHold:
173 match hold:
174 case PH{rng, acc}:
175 parents_next.w(acc, one(mode, pop, rng))
176
177def parents_loop(fuel: Nat, hold: PHold, +mode: Mode, +pop: List<&2, Ind.Individual>) -> Rng.State & List<&2, Ind.Individual>:
178 match fuel hold:
179 case 0n PH{rng, acc}:
180 (rng, List.reverse(&2, Ind.Individual, acc))
181 case 1n+f h:
182 parents_loop(f, parents_next(mode, pop, h), mode, pop)
183
184def select_parents(+mode: Mode, +pop: List<&2, Ind.Individual>, count: Nat, rng: Rng.State) -> Rng.State & List<&2, Ind.Individual>:
185 parents_loop(count, PH{rng, Nil{}}, mode, pop)
186
187def parents_of(pair: Rng.State & List<&2, Ind.Individual>) -> List<&2, Ind.Individual>:
188 (rng, xs) = pair
189 xs
190
191def stamp_front(idxs: List<&2, Nat>, +pop: List<&2, Ind.Individual>, +r: Nat) -> List<&2, Ind.Individual>:
192 match idxs:
193 case Nil{}:
194 pop
195 case +i <> rest:
196 stamp_front(rest, List.set(&2, Ind.Individual, pop, i, Ind.set_rank(get_ind(pop, i), r)), r)
197
198def stamp_ranks(fronts: List<&2, List<&2, Nat>>, pop: List<&2, Ind.Individual>, +r: Nat) -> List<&2, Ind.Individual>:
199 match fronts:
200 case Nil{}:
201 pop
202 case fr <> rest:
203 stamp_ranks(rest, stamp_front(fr, pop, r), 1n+r)
204
205def stamp_asgs.one(+a: Surv.Assignment, +ind: Ind.Individual) -> Ind.Individual:
206 Ind.stamp(ind, Ind.rank(ind), Surv.asg_count(a), Surv.asg_ref(a), Surv.asg_dist(a))
207
208# Zip pop with assignments. Mid-split both lists at the same mid.
209def stamp_asgs.go(+fuel: Nat, pop: List<&2, Ind.Individual>, +asgs: List<&2, Surv.Assignment>) -> List<&2, Ind.Individual>:
210 match fuel pop:
211 case 0n Nil{}:
212 Nil{}
213 case 0n +ind <> rest:
214 match asgs:
215 case Nil{}:
216 {ind <> rest : List<&2, Ind.Individual>}
217 case +a <> as:
218 stamp_asgs.one(a, ind) <> stamp_asgs.go(0n, rest, as)
219 case 1n+p Nil{}:
220 Nil{}
221 case 1n+p +ind <> Nil{}:
222 match asgs:
223 case Nil{}:
224 ind <> Nil{}
225 case +a <> as:
226 stamp_asgs.one(a, ind) <> Nil{}
227 case 1n+p h <> t:
228 +all = {h <> t : List<&2, Ind.Individual>}
229 +mid = Nat.div(Util.list_len(Ind.Individual, all), 2n)
230 lo hi = stamp_asgs.go(p, List.take(&2, Ind.Individual, all, mid), List.take(&2, Surv.Assignment, asgs, mid)) stamp_asgs.go(p, List.drop(&2, Ind.Individual, all, mid), List.drop(&2, Surv.Assignment, asgs, mid))
231 List.append(&2, Ind.Individual, lo, hi)
232
233def stamp_asgs(+pop: List<&2, Ind.Individual>, asgs: List<&2, Surv.Assignment>) -> List<&2, Ind.Individual>:
234 stamp_asgs.go(Util.list_len(Ind.Individual, pop), pop, asgs)
235
236def prepare.with(+dirs: List<&2, List<&2, F32>>, +pop: List<&2, Ind.Individual>, +fronts: List<&2, List<&2, Nat>>, pair: Norm.State & List<&2, List<&2, F32>>) -> Norm.State & List<&2, Ind.Individual>:
237 (st, F) = pair
238 +ranked = stamp_ranks(fronts, pop, 0n)
239 (st, stamp_asgs(ranked, Surv.associate(ranked, F, dirs)))
240
241# Recompute ranks + niche association (C# PrepareForSelection). Threads
242# the persistent Normalization state.
243def prepare(+pop: List<&2, Ind.Individual>, +dirs: List<&2, List<&2, F32>>, state: Norm.State) -> Norm.State & List<&2, Ind.Individual>:
244 +fronts = NDS.sort(pop)
245 prepare.with(dirs, pop, fronts, Norm.normalize_nd_cv(state, pop, Surv.front0(fronts)))