Multi-reference mean
Predicts a target position from several recently placed references, averages those predictions, then combines the relative-order score with the learned position probability.
Permutation estimation-of-distribution algorithm
ROSE
Algorithm
Relative Order SEquencer learns not only where an item appears, but which items precede it and how far apart they tend to be. It turns relative order into a reusable probabilistic language for permutation optimization.
Origin · the question before the algorithm
The problem was not the permutation. It was what we asked the model to remember.
ROSE began with a simple dissatisfaction. Every permutation contains the same items exactly once. What distinguishes a good solution is not its inventory, but the structure among its members. A learning algorithm must first decide what “structure” means.
Classical permutation research made this question unavoidable. Goldberg and Lingle showed why allele and locus cannot be treated as casually as in a binary chromosome: moving one item changes the interpretation of many positions. Order-based representations later showed that “before and after” can itself be a building block.
Our work with COINCIDENCE made the contrast tangible. A node/position model asks where an item tends to occur. An edge model asks which item tends to follow another. Both are useful, but neither fully describes a pattern we repeatedly observed: two items may retain a meaningful order without remaining adjacent, and their separation may carry information too.
That led to the question behind ROSE: if A tends to precede C, can the model also learn how far C tends to be from A?
From order to distance
Precedence tells a direction. ROSE retains the distance as well.
ADBEC
pos(A)=0 · pos(C)=4 · Δ(A,C)=+4The sign of Δ preserves who comes first; its magnitude preserves separation. An edge is the special case |Δ|=1, while precedence keeps the sign and discards magnitude. Relative displacement therefore connects familiar representations instead of replacing them.
This was the conceptual leap: estimate a distribution over signed pair distances, then use those relations to reconstruct a new valid permutation. “Relative Order SEquencer” names the act of sequencing; “estimator” describes its statistical machinery.
Algorithm family
Three ways to learn relative order
Single-reference range
Chooses one real reference and samples a signed distance from a truncated normal described by mean, minimum, maximum and standard deviation. No histogram is stored.
Single-reference histogram
Retains the empirical signed-distance distribution. It is more expressive, but its dense distance tensor costs substantially more memory.
/WT · With Template — Each family can preserve part of a parent, punch selected positions, regenerate only the removed items, and keep the offspring only when it improves on that parent.
Research interpretation
What current evidence permits us to say
In the current permutation flow-shop experiments, ROSE/WT can be effective for makespan and total machine idle time, while total flow time may expose local traps. This is an observation—not a universal ranking. Results should be reported separately by objective, instance, evaluation budget and seed.