non_dominated_sort.bend
unified-nsga-iii@0.1.2.0 · 228 lines · 0 definitions
1# NonDominatedSort — C# Unsga3.Core.NonDominatedSort.
2# Fast non-dominated sorting by peeling (Deb et al.). v0: Pareto on
3# objectives only (no constraint-domination until constraints exist).
4#
5# Layout (Bend guide: Arrays cannot ride a fork tree; List.get is a
6# cons walk): one sequential pass materializes `Row{index, objectives}`
7# so the peel never `List.get`s a fat Individual. Per-candidate split
8# still mid-splits `a b = f(lo) f(hi)` (same front/leftover order as
9# the tail-first walk). Inner is_dominated stays a sequential OR so a
10# first hit skips the rest. Same dominance definition; same ranks and
11# index order for the same population.
12
13import Base
14import unified-nsga-iii@0.1.2.0/individual.bend as Ind
15import unified-nsga-iii@0.1.2.0/util.bend as Util
16
17# One sort-row: population index plus the objective vector. Built once
18# per `sort`; leftover peels reuse the same rows (no re-index).
19type Row is Data:
20 Row{
21 i: Nat
22 f: List<&2, F32>
23 }
24
25def row_idx(r: Row) -> Nat:
26 match r:
27 case Row{i, f}:
28 i
29
30def row_f(r: Row) -> List<&2, F32>:
31 match r:
32 case Row{i, f}:
33 f
34
35def rows_of.go(pop: List<&2, Ind.Individual>, +i: Nat) -> List<&2, Row>:
36 match pop:
37 case Nil{}:
38 Nil{}
39 case +h <> t:
40 Row{i, Ind.objectives(h)} <> rows_of.go(t, 1n+i)
41
42def rows_of(+pop: List<&2, Ind.Individual>) -> List<&2, Row>:
43 rows_of.go(pop, 0n)
44
45def row_idxs(rs: List<&2, Row>) -> List<&2, Nat>:
46 match rs:
47 case Nil{}:
48 Nil{}
49 case +r <> t:
50 row_idx(r) <> row_idxs(t)
51
52def verdict.a(bb: Bool) -> Nat:
53 match bb:
54 case True{}:
55 0n
56 case False{}:
57 1n
58
59def verdict.b(bb: Bool) -> Nat:
60 match bb:
61 case True{}:
62 2n
63 case False{}:
64 0n
65
66# Minimization: 0n = mutual non-domination, 1n = a dominates b, 2n = b dominates a.
67def verdict(ab: Bool, bb: Bool) -> Nat:
68 match ab:
69 case True{}:
70 verdict.a(bb)
71 case False{}:
72 verdict.b(bb)
73
74def compare_pareto.go(a: List<&2, F32>, b: List<&2, F32>, ab: Bool, bb: Bool) -> Nat:
75 # Unequal lengths: mutual non-domination (0), even if the shared prefix
76 # is strictly better. C# ComparePareto throws. ZDT/DTLZ use one length.
77 # Locked by src/nds_unequal.bend.
78 match a b:
79 case Nil{} Nil{}:
80 verdict(ab, bb)
81 case +x <> xs +y <> ys:
82 compare_pareto.go(xs, ys, Bool.or(ab, F32.is_lt(x, y)), Bool.or(bb, F32.is_lt(y, x)))
83 case Nil{} y <> ys:
84 0n
85 case x <> xs Nil{}:
86 0n
87
88def compare_pareto(a: List<&2, F32>, b: List<&2, F32>) -> Nat:
89 compare_pareto.go(a, b, False{}, False{})
90
91def dominates.is1(p: Nat) -> Bool:
92 match p:
93 case 0n:
94 True{}
95 case 1n+q:
96 False{}
97
98def dominates.fin(c: Nat) -> Bool:
99 match c:
100 case 0n:
101 False{}
102 case 1n+p:
103 dominates.is1(p)
104
105def dominates(a: Ind.Individual, b: Ind.Individual) -> Bool:
106 dominates.fin(compare_pareto(Ind.objectives(a), Ind.objectives(b)))
107
108def dominates_ff(+fa: List<&2, F32>, +fb: List<&2, F32>) -> Bool:
109 dominates.fin(compare_pareto(fa, fb))
110
111# Sequential OR so a first hit can skip the rest. Candidate-level
112# parallelism lives in split_walk (coarse mid-split). Walks `all`
113# rows directly — no List.get into the population.
114def is_dominated(+all: List<&2, Row>, +i: Nat, +fi: List<&2, F32>) -> Bool:
115 match all:
116 case Nil{}:
117 False{}
118 case +r <> rs:
119 match r:
120 case Row{+j, +fj}:
121 Bool.or(
122 Bool.and(Bool.not(Nat.is_eq(i, j)), dominates_ff(fj, fi)),
123 is_dominated(rs, i, fi)
124 )
125
126def row_dom(+all: List<&2, Row>, +r: Row) -> Bool:
127 match r:
128 case Row{+i, +f}:
129 is_dominated(all, i, f)
130
131# Split remaining into (front indices, leftover rows). Same front
132# membership and leftover order as the old index-list peel.
133# |front| + |leftover| = |remaining| by construction.
134type Split is Data:
135 Split{
136 ff: List<&2, Nat>
137 ot: List<&2, Row>
138 }
139
140def split_put(+r: Row, s: Split, dominated: Bool) -> Split:
141 match s:
142 case Split{ff, ot}:
143 match dominated:
144 case True{}:
145 Split{ff, r <> ot}
146 case False{}:
147 Split{row_idx(r) <> ff, ot}
148
149def split_cat(a: Split, b: Split) -> Split:
150 match a b:
151 case Split{ff1, ot1} Split{ff2, ot2}:
152 Split{List.append(&2, Nat, ff1, ff2), List.append(&2, Row, ot1, ot2)}
153
154# Per-candidate split is independent given `all`. Mid-split then
155# concatenate fronts / leftovers so order matches the tail-first walk.
156def split_walk.go(+all: List<&2, Row>, +fuel: Nat, cand: List<&2, Row>) -> Split:
157 match fuel cand:
158 case 0n Nil{}:
159 Split{Nil{}, Nil{}}
160 case 0n +r <> rest:
161 split_put(r, split_walk.go(all, 0n, rest), row_dom(all, r))
162 case 1n+p Nil{}:
163 Split{Nil{}, Nil{}}
164 case 1n+p +r <> Nil{}:
165 split_put(r, Split{Nil{}, Nil{}}, row_dom(all, r))
166 case 1n+p h <> t:
167 +xs = {h <> t : List<&2, Row>}
168 +mid = Nat.div(Util.list_len(Row, xs), 2n)
169 lo hi = split_walk.go(all, p, List.take(&2, Row, xs, mid)) split_walk.go(all, p, List.drop(&2, Row, xs, mid))
170 split_cat(lo, hi)
171
172def split_walk(+all: List<&2, Row>, +cand: List<&2, Row>) -> Split:
173 split_walk.go(all, Util.list_len(Row, cand), cand)
174
175# Empty first front (unreachable on a finite Pareto set) keeps the head
176# so peel stays a partition.
177def split_ne(+r: Row, +rest: List<&2, Row>, s: Split) -> Split:
178 match s:
179 case Split{ff, ot}:
180 match ff:
181 case Nil{}:
182 Split{row_idx(r) <> Nil{}, rest}
183 case h <> t:
184 Split{h <> t, ot}
185
186def split_front(remaining: List<&2, Row>) -> Split:
187 match remaining:
188 case Nil{}:
189 Split{Nil{}, Nil{}}
190 case +r <> +rest:
191 split_ne(r, rest, split_walk(r <> rest, r <> rest))
192
193def split_fst(s: Split) -> List<&2, Nat>:
194 match s:
195 case Split{ff, ot}:
196 ff
197
198def split_snd(s: Split) -> List<&2, Row>:
199 match s:
200 case Split{ff, ot}:
201 ot
202
203def peel(fuel: Nat, remaining: List<&2, Row>) -> List<&2, List<&2, Nat>>:
204 match fuel remaining:
205 case 0n Nil{}:
206 Nil{}
207 case 1n+f Nil{}:
208 Nil{}
209 case 0n +r <> +rest:
210 row_idxs({r <> rest : List<&2, Row>}) <> Nil{}
211 case 1n+f +r <> +rest:
212 +s = split_front({r <> rest : List<&2, Row>})
213 split_fst(s) <> peel(f, split_snd(s))
214
215def sort(population: List<&2, Ind.Individual>) -> List<&2, List<&2, Nat>>:
216 match population:
217 case Nil{}:
218 Nil{}
219 case +h <> +t:
220 +rs = rows_of.go({h <> t : List<&2, Ind.Individual>}, 0n)
221 peel(Util.list_len(Row, rs), rs)
222
223def front_index_count(fronts: List<&2, List<&2, Nat>>) -> Nat:
224 match fronts:
225 case Nil{}:
226 0n
227 case h <> t:
228 Nat.add(Util.list_len(Nat, h), front_index_count(t))