SOURCE-ALIGNED TUTORIAL · STEP-BY-STEP SNAPSHOTS

ROSE
step by step

Follow one generation from the raw population and elite selection through relative-order estimation, position-by-position sampling, and the next population—with numeric snapshots traceable to the Python implementation.

01 · GENERATION LOOP

What ROSE learns in one generation

Evaluate

Send every permutation to the same evaluator, producing one fitness value or a Pareto selection score.

Select

Rank in the objective direction and retain the elite fraction specified by selection ratio.

Fit

Convert elites to inverse positions, then fit exact-position and signed-distance statistics.

Sample

Sample each item into a free locus by mixing node and relative-order evidence.

Repeat

Evaluate the new population, record diagnostics, and fit the next estimator snapshot.

Unit of progress: Fair comparisons should use objective evaluations, not generation count alone, because different population sizes change the cost of a generation.

02 · SELECTION SNAPSHOT

Begin with a visible population

Example: minimization with n=6, population=5, and selection ratio=40%, so max(1, round(5×0.40)) = 2 elites are retained after fitness sorting.

P0 · f=18[1, 4, 0, 3, 5, 2]

P1 · f=11 · ELITE[1, 3, 5, 0, 4, 2]

P2 · f=15[3, 1, 0, 5, 2, 4]

P3 · f=9 · ELITE[1, 5, 3, 0, 2, 4]

P4 · f=21[4, 0, 2, 1, 5, 3]

order = argsort(fitness)                  # minimization
k = max(1, round(population × ratio/100))
selected = population[order[:k]]         # P3, P1

Minimization

argsort(fitness) ascending

Maximization

argsort(fitness)[::-1] descending

03 · FIT SNAPSHOT

From permutations to statistic matrices

3.1 Invert each order into item positions

A permutation says which item occupies locus p; the estimator asks where item j is. An inverse array is therefore built once, making every pair lookup O(1).

Elite	Permutation	pos[0..5]
P3	`1 5 3 0 2 4`	`3 0 4 2 5 1`
P1	`1 3 5 0 4 2`	`3 0 5 1 4 2`

positions[row, item] = locus

P3: pos(1)=0, pos(3)=2
P1: pos(1)=0, pos(3)=1

Δ(1,3) = pos(3)-pos(1)
P3 → +2
P1 → +1

NODE / EXACT POSITION

N[j,p]

Count how often item j occupies locus p, add smoothing α to every cell, then normalize each item row to one.

N[j,p] = (count(j at p)+α)/(k+nα)
α=1, k=2
item 1 observed at p=0 twice
N[1] = [3,1,1,1,1,1] / 8

RELATIVE ORDER

Δπ(i,j)

Signed displacement: positive means j follows i; negative means j precedes i, encoding direction and distance together.

Δπ(i,j)=posπ(j)-posπ(i)
M[i,j]=mean Δ
L[i,j]=min Δ
U[i,j]=max Δ
S[i,j]=population SD of Δ

Snapshot for reference=1, target=3

observations+2, +1

count2

mean M1.5

min L1

max U2

SD S0.5

The implementation uses population standard deviation (divide by k), not sample SD (divide by k−1), and sets the i=j diagonal count to zero because a self-distance carries no information.

04 · THREE ESTIMATORS

Three variants store and sample differently

ROSE · MULTI-REFERENCE

Average targets predicted by several references

Use an active roll of placed items. Every reference i predicts target_i = pos(i)+M[i,j], then average those targets. It does not draw Δ from [L,U].

targets = [pos(i)+M[i,j]]
target = mean(targets)
scale = max(mean(S[i,j]),1)

SR-ROSE · COMPACT RANGE

Choose one reference and sample a distance

Choose a reference uniformly or by confidence=1/SD; draw integer Δ from Normal(M,S), truncated to [L,U] and excluding zero.

i ~ reference policy
Δ ~ TruncNormal(M[i,j],S[i,j],L,U)
target = pos(i)+Δ

SH-ROSE · HISTOGRAM

Read empirical distance probability

Store H[i,j,d] over 2n−1 bins and score each free locus p using d=p−pos(i). This preserves multimodality but costs O(n³) memory.

d = p-pos(i)
relative_score(p)=log H[i,j,d]
confidence(i)=1/entropy(H[i,j,:])

Variant	Reference	Distance model	Memory	Use when
ROSE	many in roll	M, S; average targets	O(n²)	stable consensus is useful
SR-ROSE	one	M, L, U, S; truncated draw	O(n²)	compact diversity is needed
SH-ROSE	one	full empirical histogram	O(n³)	distance distributions are multimodal

05 · SAMPLING SNAPSHOT

How one item is placed into a free locus

Suppose target item j=3 is being placed, reference i=1 is already at locus 0, and free loci are {1,2,4,5}. From the previous snapshot SR-ROSE learned M=1.5, L=1, U=2, S=0.5.

Choose construction order

Shuffle jobs with a deterministic SplitMix64 seed to avoid item-number ordering bias.

Form active roll

all, fixed or random 1..max_roll

Build node score

node(p)=log(max(N[3,p],ε))

Build relative score

Example draw Δ=2, so target=0+2=2.

Mix scores

score=λ·node+(1−λ)·relative

Masked softmax

Compute only over free loci; occupied loci cannot be sampled.

Weighted choice

Accumulate weights until the random threshold is crossed, then commit the item.

Update state

Write result and pos(j), append history, and remove the locus from free.

Worked calculationλ=0.25 · temperature=1.0 · target=2 · scale=max(S,1)=1

free = [1, 2, 4, 5]

p	N[3,p]	node=log N	relative=−\|p−2\|/1	mixed score	softmax P
1	.125	−2.079	−1	−1.270	23.7%
2	.250	−1.386	0	−0.347	59.7%
4	.125	−2.079	−2	−2.020	11.2%
5	.125	−2.079	−3	−2.770	5.3%

Probabilities are rounded for teaching. The implementation subtracts max(score) before exp for numerical stability and falls back to uniform choice when weights are non-finite or sum to a non-positive value.

SR-ROSE truncated-normal fallback

A Box–Muller normal draw is rounded to an integer and accepted only inside [L,U] and when nonzero. After 32 rejected draws, sampling falls back to uniform over legal integers in the learned range; the range is never widened.

repeat at most 32 times:
    z = BoxMuller(U₁,U₂)
    Δ = round(M + S·z)
    accept if L ≤ Δ ≤ U and Δ ≠ 0
fallback: uniform({L..U} \ {0})

06 · WITH TEMPLATE (WT)

Punch selected loci and reconstruct only what was removed

PARENT

153024

↓ sample ratio 50%: punch loci 1,3,5

PUNCHED TEMPLATE

1_3_2_

↓ free={1,3,5}, jobs={5,0,4}; fixed items may act as references

CHILD

143520

A template is not ordinary mutation

Retained loci reserve their items and also provide reference context; only punched loci are regenerated by the ROSE sampler.

Parent-wise replacement

Each child is compared only with its own parent. A non-improving child is replaced by that parent before the next fit, providing explicit local elitism.

survivor = child  if f(child) < f(parent)   # minimization
           parent otherwise

# strict improvement: equal fitness does not replace the parent

07 · UPDATE AND SNAPSHOT

One generation snapshot becomes the next prior

No estimator yet

Generate random permutations; the same seed reproduces the initial population.

G0 FIT

N₀, M₀, L₀, U₀, S₀

Statistics are fitted from G0 elites only, not the full population.

G1 SAMPLE

Read snapshot without mutation

All offspring in the generation use the same fitted snapshot; earlier candidates do not silently alter later sampling.

G1 FIT

N₁, M₁, L₁, U₁, S₁

Only after evaluation and selection is the estimator atomically replaced for G2.

What an experiment snapshot should record

seedgenerationevaluationsselected indicesbest / mean / worstexact-position entropyrelative SD meanduplicate ratefallback countsroll-size distributionreference frequencyWT improvement rate

08 · COMPLEXITY AND PARAMETERS

Cost and meaning of every control

Parameter	Meaning	When increased
`selection_ratio`	fraction of survivors used to fit	broader, less selective model
`smoothing α`	pseudocount for N and H	fewer zero probabilities, more exploration
`node_weight λ`	exact-position vs relative evidence	more reliance on locus frequency
`temperature T`	divides score before softmax	flatter distribution and more exploration
`roll_mode / roll size`	number of placed references considered	wider context, potentially conflicting consensus
`template_sample_ratio`	percentage of loci punched and regenerated	larger step away from the parent

ROSE / SR-ROSE

O(n²) memory

N, M, L, U, S, and count are n×n; no per-elite tensor is retained.

SH-ROSE

O(n³) memory

Adds H with n×n×(2n−1) bins for counts and probabilities.

Construct one permutation

≈ O(n²)

Makes n commits while scoring a shrinking set of free loci.

Numba acceleration: The elite×pair fitting loop uses fixed-size NumPy arrays and a Numba kernel. Sampling still maintains free-locus state, history, and deterministic RNG semantics.

09 · IMPLEMENTATION MAP

Where each documented behavior lives

Published name	Python class	Responsibility	Source
ROSE / ROSE-WT	`ROSE` `TemplateROSE`	multi-reference mean + optional punched template	`models/rose.py`
SR-ROSE / SR-ROSE-WT	`ROSESingleRef` `TemplateROSESingleRef`	single-reference compact range sampling	`models/rose.py`
SH-ROSE / SH-ROSE-WT	`ROSESingleRefHistogram` `TemplateROSESingleRefHistogram`	single-reference empirical histogram	`models/rose_histogram.py`
Fast estimator fitting	`fit_rose_estimators_numba`	fit N, M, L, U, S, and count from elites	`models/rose_numba.py`

Testable invariants

every offspring is a permutation of 0..n−1
every row of N sums to one
M[j,i] = −M[i,j]
L[j,i] = −U[i,j]
same config and seed reproduce the result

Do not over-interpret the model

M is an elite mean, not a constraint
[L,U] is an observed range, not a confidence interval
low SD may result from few elites; report count
good fitness does not prove universal superiority

GitHub repository ↗ROSE.md ↗rose.py ↗Sampling notes →