tournament.bend source
tournament.bend on the hub · documented module
# Mating tournament — C# TournamentSelection / TournamentMode.# Default for algorithm A/B is PymooCompatible (pymoo# comp_by_rank_and_ref_line_dist): same niche → rank then perp dist;# else random. RankNicheDistance (C# WinnerRankNicheDistance) is# rank → niche count → perpendicular distance → coin.# Both modes take CV first. Feasible (cv ≤ 0) beats infeasible.# PymooCompatible: if either is infeasible, smaller CV wins and equal# CV is a coin (no rank / distance). RankNicheDistance: both infeasible# and unequal CV → smaller CV; equal CV falls through to rank.# cv 0 on both sides keeps the feasible comparators. A/B stays# PymooCompatible. See src/trn_seed682.bend.import Baseimport ./individual.bend as Indimport ./non_dominated_sort.bend as NDSimport ./normalization.bend as Normimport ./survival.bend as Survimport ./rng.bend as Rngimport ./util.bend as Utiltype Mode is Data: PymooCompatible{} RankNicheDistance{}def pymoo() -> Mode: PymooCompatible{}def rank_niche() -> Mode: RankNicheDistance{}def get_ind(+pop: List<&2, Ind.Individual>, i: Nat) -> Ind.Individual: Maybe.default(&2, Ind.Individual, List.get(&2, Ind.Individual, pop, i), Ind.from_objectives(Nil{}))def coin(a: Ind.Individual, b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual: +rng2 = Rng.next_double(rng) (rng2, Bool.pick(Ind.Individual, F32.is_lt(Rng.last_double(rng2), 0.5), a, b))def cmp_pick(a: Ind.Individual, b: Ind.Individual, rng: Rng.State, ab: Bool, ba: Bool) -> Rng.State & Ind.Individual: match ab ba: case True{} _: (rng, a) case False{} True{}: (rng, b) case False{} False{}: coin(a, b, rng)def by_dist(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual: +da = Ind.perp_dist(a) +db = Ind.perp_dist(b) cmp_pick(a, b, rng, F32.is_lt(da, db), F32.is_lt(db, da))def by_rank.eq(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual: match same: case True{}: by_dist(a, b, rng) case False{}: cmp_pick(a, b, rng, Nat.is_lt(Ind.rank(a), Ind.rank(b)), Nat.is_lt(Ind.rank(b), Ind.rank(a)))def by_rank(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual: by_rank.eq(a, b, rng, Nat.is_eq(Ind.rank(a), Ind.rank(b)))def winner_pymoo.same(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual: match same: case True{}: by_rank(a, b, rng) case False{}: coin(a, b, rng)def winner_pymoo.cv_b(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, b_lt: Bool) -> Rng.State & Ind.Individual: match b_lt: case True{}: (rng, b) case False{}: coin(a, b, rng)# Either infeasible: smaller CV, else coin. Does not read rank.def winner_pymoo.cv(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, a_lt: Bool, b_lt: Bool) -> Rng.State & Ind.Individual: match a_lt: case True{}: (rng, a) case False{}: winner_pymoo.cv_b(a, b, rng, b_lt)def winner_pymoo.gate(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, either: Bool) -> Rng.State & Ind.Individual: match either: case True{}: 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))) case False{}: winner_pymoo.same(a, b, rng, Nat.is_eq(Ind.associated_ref(a), Ind.associated_ref(b)))def winner_pymoo(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual: winner_pymoo.gate( a, b, rng, Bool.or(Bool.not(Ind.feasible(a)), Bool.not(Ind.feasible(b))) )# Equal niche counts fall through to perpendicular distance (then coin).# A count tie used to coin immediately and skip distance.def by_niche.eq(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual: match same: case True{}: by_dist(a, b, rng) case False{}: cmp_pick(a, b, rng, Nat.is_lt(Ind.niche(a), Ind.niche(b)), Nat.is_lt(Ind.niche(b), Ind.niche(a)))def by_niche(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual: by_niche.eq(a, b, rng, Nat.is_eq(Ind.niche(a), Ind.niche(b)))def winner_rnd.eq(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual: match same: case True{}: by_niche(a, b, rng) case False{}: cmp_pick(a, b, rng, Nat.is_lt(Ind.rank(a), Ind.rank(b)), Nat.is_lt(Ind.rank(b), Ind.rank(a)))def winner_rnd.cv_b(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, b_lt: Bool) -> Rng.State & Ind.Individual: match b_lt: case True{}: (rng, b) case False{}: winner_rnd.eq(a, b, rng, Nat.is_eq(Ind.rank(a), Ind.rank(b)))# Both infeasible. Equal CV falls through to rank (not a coin, not Pareto).def winner_rnd.cv(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, a_lt: Bool, b_lt: Bool) -> Rng.State & Ind.Individual: match a_lt: case True{}: (rng, a) case False{}: winner_rnd.cv_b(a, b, rng, b_lt)def winner_rnd.gate(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, a_feas: Bool, b_feas: Bool) -> Rng.State & Ind.Individual: match a_feas b_feas: case True{} False{}: (rng, a) case False{} True{}: (rng, b) case True{} True{}: winner_rnd.eq(a, b, rng, Nat.is_eq(Ind.rank(a), Ind.rank(b))) case False{} False{}: 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)))def winner_rnd(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual: winner_rnd.gate(a, b, rng, Ind.feasible(a), Ind.feasible(b))def winner(mode: Mode, +a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual: match mode: case PymooCompatible{}: winner_pymoo(a, b, rng) case RankNicheDistance{}: winner_rnd(a, b, rng)def one(+mode: Mode, +pop: List<&2, Ind.Individual>, rng: Rng.State) -> Rng.State & Ind.Individual: +n = Util.list_len(Ind.Individual, pop) +rng_a = Rng.next_nat(rng, n) +ia = Rng.last_nat(rng_a) +rng_b = Rng.next_except(rng_a, n, ia) +ib = Rng.last_nat(rng_b) winner(mode, get_ind(pop, ia), get_ind(pop, ib), rng_b)type PHold is Data: PH{ rng: Rng.State acc: List<&2, Ind.Individual> }def parents_next.w(acc: List<&2, Ind.Individual>, pair: Rng.State & Ind.Individual) -> PHold: (rng, w) = pair PH{rng, w <> acc}def parents_next(+mode: Mode, +pop: List<&2, Ind.Individual>, hold: PHold) -> PHold: match hold: case PH{rng, acc}: parents_next.w(acc, one(mode, pop, rng))def parents_loop(fuel: Nat, hold: PHold, +mode: Mode, +pop: List<&2, Ind.Individual>) -> Rng.State & List<&2, Ind.Individual>: match fuel hold: case 0n PH{rng, acc}: (rng, List.reverse(&2, Ind.Individual, acc)) case 1n+f h: parents_loop(f, parents_next(mode, pop, h), mode, pop)def select_parents(+mode: Mode, +pop: List<&2, Ind.Individual>, count: Nat, rng: Rng.State) -> Rng.State & List<&2, Ind.Individual>: parents_loop(count, PH{rng, Nil{}}, mode, pop)def parents_of(pair: Rng.State & List<&2, Ind.Individual>) -> List<&2, Ind.Individual>: (rng, xs) = pair xsdef stamp_front(idxs: List<&2, Nat>, +pop: List<&2, Ind.Individual>, +r: Nat) -> List<&2, Ind.Individual>: match idxs: case Nil{}: pop case +i <> rest: stamp_front(rest, List.set(&2, Ind.Individual, pop, i, Ind.set_rank(get_ind(pop, i), r)), r)def stamp_ranks(fronts: List<&2, List<&2, Nat>>, pop: List<&2, Ind.Individual>, +r: Nat) -> List<&2, Ind.Individual>: match fronts: case Nil{}: pop case fr <> rest: stamp_ranks(rest, stamp_front(fr, pop, r), 1n+r)def stamp_asgs.one(+a: Surv.Assignment, +ind: Ind.Individual) -> Ind.Individual: Ind.stamp(ind, Ind.rank(ind), Surv.asg_count(a), Surv.asg_ref(a), Surv.asg_dist(a))# Zip pop with assignments. Mid-split both lists at the same mid.def stamp_asgs.go(+fuel: Nat, pop: List<&2, Ind.Individual>, +asgs: List<&2, Surv.Assignment>) -> List<&2, Ind.Individual>: match fuel pop: case 0n Nil{}: Nil{} case 0n +ind <> rest: match asgs: case Nil{}: {ind <> rest : List<&2, Ind.Individual>} case +a <> as: stamp_asgs.one(a, ind) <> stamp_asgs.go(0n, rest, as) case 1n+p Nil{}: Nil{} case 1n+p +ind <> Nil{}: match asgs: case Nil{}: ind <> Nil{} case +a <> as: stamp_asgs.one(a, ind) <> Nil{} case 1n+p h <> t: +all = {h <> t : List<&2, Ind.Individual>} +mid = Nat.div(Util.list_len(Ind.Individual, all), 2n) 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)) List.append(&2, Ind.Individual, lo, hi)def stamp_asgs(+pop: List<&2, Ind.Individual>, asgs: List<&2, Surv.Assignment>) -> List<&2, Ind.Individual>: stamp_asgs.go(Util.list_len(Ind.Individual, pop), pop, asgs)def 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>: (st, F) = pair +ranked = stamp_ranks(fronts, pop, 0n) (st, stamp_asgs(ranked, Surv.associate(ranked, F, dirs)))# Recompute ranks + niche association (C# PrepareForSelection). Threads# the persistent Normalization state.def prepare(+pop: List<&2, Ind.Individual>, +dirs: List<&2, List<&2, F32>>, state: Norm.State) -> Norm.State & List<&2, Ind.Individual>: +fronts = NDS.sort(pop) prepare.with(dirs, pop, fronts, Norm.normalize_nd(state, pop, Surv.front0(fronts)))