tournament.bend
unified-nsga-iii@0.1.2.0 · 188 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. This slice is
6# unconstrained, so CV branches are unused (all individuals are treated
7# feasible). A/B does not score this path; see src/trn_seed682.bend.
8
9import Base
10import unified-nsga-iii@0.1.2.0/individual.bend as Ind
11import unified-nsga-iii@0.1.2.0/non_dominated_sort.bend as NDS
12import unified-nsga-iii@0.1.2.0/normalization.bend as Norm
13import unified-nsga-iii@0.1.2.0/survival.bend as Surv
14import unified-nsga-iii@0.1.2.0/rng.bend as Rng
15import unified-nsga-iii@0.1.2.0/util.bend as Util
16
17type Mode is Data:
18 PymooCompatible{}
19 RankNicheDistance{}
20
21def pymoo() -> Mode:
22 PymooCompatible{}
23
24def rank_niche() -> Mode:
25 RankNicheDistance{}
26
27def get_ind(+pop: List<&2, Ind.Individual>, i: Nat) -> Ind.Individual:
28 Maybe.default(&2, Ind.Individual, List.get(&2, Ind.Individual, pop, i), Ind.from_objectives(Nil{}))
29
30def coin(a: Ind.Individual, b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
31 +rng2 = Rng.next_double(rng)
32 (rng2, Bool.pick(Ind.Individual, F32.is_lt(Rng.last_double(rng2), 0.5), a, b))
33
34def cmp_pick(a: Ind.Individual, b: Ind.Individual, rng: Rng.State, ab: Bool, ba: Bool) -> Rng.State & Ind.Individual:
35 match ab ba:
36 case True{} _:
37 (rng, a)
38 case False{} True{}:
39 (rng, b)
40 case False{} False{}:
41 coin(a, b, rng)
42
43def by_dist(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
44 +da = Ind.perp_dist(a)
45 +db = Ind.perp_dist(b)
46 cmp_pick(a, b, rng, F32.is_lt(da, db), F32.is_lt(db, da))
47
48def by_rank.eq(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual:
49 match same:
50 case True{}:
51 by_dist(a, b, rng)
52 case False{}:
53 cmp_pick(a, b, rng, Nat.is_lt(Ind.rank(a), Ind.rank(b)), Nat.is_lt(Ind.rank(b), Ind.rank(a)))
54
55def by_rank(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
56 by_rank.eq(a, b, rng, Nat.is_eq(Ind.rank(a), Ind.rank(b)))
57
58def winner_pymoo.same(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual:
59 match same:
60 case True{}:
61 by_rank(a, b, rng)
62 case False{}:
63 coin(a, b, rng)
64
65def winner_pymoo(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
66 winner_pymoo.same(a, b, rng, Nat.is_eq(Ind.associated_ref(a), Ind.associated_ref(b)))
67
68# Equal niche counts fall through to perpendicular distance (then coin).
69# A count tie used to coin immediately and skip distance.
70def by_niche.eq(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual:
71 match same:
72 case True{}:
73 by_dist(a, b, rng)
74 case False{}:
75 cmp_pick(a, b, rng, Nat.is_lt(Ind.niche(a), Ind.niche(b)), Nat.is_lt(Ind.niche(b), Ind.niche(a)))
76
77def by_niche(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
78 by_niche.eq(a, b, rng, Nat.is_eq(Ind.niche(a), Ind.niche(b)))
79
80def winner_rnd.eq(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual:
81 match same:
82 case True{}:
83 by_niche(a, b, rng)
84 case False{}:
85 cmp_pick(a, b, rng, Nat.is_lt(Ind.rank(a), Ind.rank(b)), Nat.is_lt(Ind.rank(b), Ind.rank(a)))
86
87def winner_rnd(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
88 winner_rnd.eq(a, b, rng, Nat.is_eq(Ind.rank(a), Ind.rank(b)))
89
90def winner(mode: Mode, +a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
91 match mode:
92 case PymooCompatible{}:
93 winner_pymoo(a, b, rng)
94 case RankNicheDistance{}:
95 winner_rnd(a, b, rng)
96
97def one(+mode: Mode, +pop: List<&2, Ind.Individual>, rng: Rng.State) -> Rng.State & Ind.Individual:
98 +n = Util.list_len(Ind.Individual, pop)
99 +rng_a = Rng.next_nat(rng, n)
100 +ia = Rng.last_nat(rng_a)
101 +rng_b = Rng.next_except(rng_a, n, ia)
102 +ib = Rng.last_nat(rng_b)
103 winner(mode, get_ind(pop, ia), get_ind(pop, ib), rng_b)
104
105type PHold is Data:
106 PH{
107 rng: Rng.State
108 acc: List<&2, Ind.Individual>
109 }
110
111def parents_next.w(acc: List<&2, Ind.Individual>, pair: Rng.State & Ind.Individual) -> PHold:
112 (rng, w) = pair
113 PH{rng, w <> acc}
114
115def parents_next(+mode: Mode, +pop: List<&2, Ind.Individual>, hold: PHold) -> PHold:
116 match hold:
117 case PH{rng, acc}:
118 parents_next.w(acc, one(mode, pop, rng))
119
120def parents_loop(fuel: Nat, hold: PHold, +mode: Mode, +pop: List<&2, Ind.Individual>) -> Rng.State & List<&2, Ind.Individual>:
121 match fuel hold:
122 case 0n PH{rng, acc}:
123 (rng, List.reverse(&2, Ind.Individual, acc))
124 case 1n+f h:
125 parents_loop(f, parents_next(mode, pop, h), mode, pop)
126
127def select_parents(+mode: Mode, +pop: List<&2, Ind.Individual>, count: Nat, rng: Rng.State) -> Rng.State & List<&2, Ind.Individual>:
128 parents_loop(count, PH{rng, Nil{}}, mode, pop)
129
130def parents_of(pair: Rng.State & List<&2, Ind.Individual>) -> List<&2, Ind.Individual>:
131 (rng, xs) = pair
132 xs
133
134def stamp_front(idxs: List<&2, Nat>, +pop: List<&2, Ind.Individual>, +r: Nat) -> List<&2, Ind.Individual>:
135 match idxs:
136 case Nil{}:
137 pop
138 case +i <> rest:
139 stamp_front(rest, List.set(&2, Ind.Individual, pop, i, Ind.set_rank(get_ind(pop, i), r)), r)
140
141def stamp_ranks(fronts: List<&2, List<&2, Nat>>, pop: List<&2, Ind.Individual>, +r: Nat) -> List<&2, Ind.Individual>:
142 match fronts:
143 case Nil{}:
144 pop
145 case fr <> rest:
146 stamp_ranks(rest, stamp_front(fr, pop, r), 1n+r)
147
148def stamp_asgs.one(+a: Surv.Assignment, +ind: Ind.Individual) -> Ind.Individual:
149 Ind.stamp(ind, Ind.rank(ind), Surv.asg_count(a), Surv.asg_ref(a), Surv.asg_dist(a))
150
151# Zip pop with assignments. Mid-split both lists at the same mid.
152def stamp_asgs.go(+fuel: Nat, pop: List<&2, Ind.Individual>, +asgs: List<&2, Surv.Assignment>) -> List<&2, Ind.Individual>:
153 match fuel pop:
154 case 0n Nil{}:
155 Nil{}
156 case 0n +ind <> rest:
157 match asgs:
158 case Nil{}:
159 {ind <> rest : List<&2, Ind.Individual>}
160 case +a <> as:
161 stamp_asgs.one(a, ind) <> stamp_asgs.go(0n, rest, as)
162 case 1n+p Nil{}:
163 Nil{}
164 case 1n+p +ind <> Nil{}:
165 match asgs:
166 case Nil{}:
167 ind <> Nil{}
168 case +a <> as:
169 stamp_asgs.one(a, ind) <> Nil{}
170 case 1n+p h <> t:
171 +all = {h <> t : List<&2, Ind.Individual>}
172 +mid = Nat.div(Util.list_len(Ind.Individual, all), 2n)
173 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))
174 List.append(&2, Ind.Individual, lo, hi)
175
176def stamp_asgs(+pop: List<&2, Ind.Individual>, asgs: List<&2, Surv.Assignment>) -> List<&2, Ind.Individual>:
177 stamp_asgs.go(Util.list_len(Ind.Individual, pop), pop, asgs)
178
179def 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>:
180 (st, F) = pair
181 +ranked = stamp_ranks(fronts, pop, 0n)
182 (st, stamp_asgs(ranked, Surv.associate(ranked, F, dirs)))
183
184# Recompute ranks + niche association (C# PrepareForSelection). Threads
185# the persistent Normalization state.
186def prepare(+pop: List<&2, Ind.Individual>, +dirs: List<&2, List<&2, F32>>, state: Norm.State) -> Norm.State & List<&2, Ind.Individual>:
187 +fronts = NDS.sort(pop)
188 prepare.with(dirs, pop, fronts, Norm.normalize_nd(state, pop, Surv.front0(fronts)))