Coincidence becomes memory, and memory becomes the next permutation.

One generation: from evaluated solutions to a new population

COIN is an estimation-of-distribution algorithm for permutations. It does not cross two parents. It turns selected permutations into coincidence counts, updates a probabilistic weight model, and constructs the next population by sampling only unused items.

1. EvaluateSend every permutation to the same evaluator. A single-objective run returns a scalar fitness; a multi-objective run returns an objective vector.
2. SelectChoose a better tail as reward evidence and a worse tail as punishment evidence.
3. CountTranslate each selected permutation into edge events, position–item events, or both, depending on the variant.
4. LearnConservative learning redistributes integer weight; reconstruction learning rebuilds weights from the latest reward counts.
5. SampleRoulette-sample from eligible unused items. Missing values and duplicates are impossible by construction.
6. RepeatEvaluate the new population, update progress and archives, then create the next model snapshot.

The mathematical object being learned

Let a candidate permutation be π=(π₀,π₁,…,πₙ₋₁), where every item in {0,…,n−1} occurs exactly once. COIN does not assign an independent probability to each complete permutation—there are n! of them. Instead, it factorises useful evidence into a quadratic model. Edge variants use directed adjacency indicators; Node variants use position–item indicators.

E(i,j|π) = 1 if successorπ(i)=j; otherwise 0

N(p,j|π) = 1 if π[p]=j; otherwise 0

For reward set B and punishment set W, COIN forms count matrices R=Σπ∈B feature(π) and Q=Σπ∈W feature(π). The feature is E, N, or both. The evaluator can therefore change from TSP to Flow Shop, Sudoku or RNA while the model consumes the same selected-permutation interface.

Why quadratic memory is a deliberate compromise

A full joint distribution over permutations is intractable. An n×n coincidence model uses Θ(n²) memory and exposes a strong first-order learning signal. It cannot directly represent every long subsequence or higher-order dependency, but repeated sampling can assemble longer structures from compatible pairwise evidence. Hybrid variants extend this vocabulary without escalating to an exponential model.

Reward and punishment are selected evidence

With population 8 and reward/punishment ratios 25:25 in a minimization problem, the two lowest-fitness permutations reward the model and the two highest-fitness permutations punish it. The middle four are still evaluated and can update best-so-far, but they do not write model evidence in that generation.

A complete worked generation

Assume n=6, minimization, population size 8, reward 25%, punishment 25%, and Conservative learning. Sorting fitness selects two reward and two punishment permutations. The learner then counts events—not objective values. A solution with fitness 19 and one with fitness 22 each contribute one vote per observed event; the fitness gap does not automatically give the first solution a larger vote.

For Edge COIN, reward permutation [1,3,5,0,4,2] increments six cells. If the second reward permutation contains 1→5 rather than 1→3, both successor hypotheses receive support. Punishment counts identify transitions characteristic of poor solutions. Conservative updating then transfers available row mass without turning a legal transition into a permanent zero.

Selection pressure and information quality

Very small reward sets learn aggressively from a few individuals and may lock onto accidental patterns. Very large sets dilute the distinction between strong and ordinary solutions. Punishment can accelerate rejection of repeatedly poor traits, but an excessive punishment fraction may suppress edges that are bad only in a particular context. Parameter grids should therefore report both quality and stability across seeds.

Edge COIN: learn what should follow what

Edge COIN stores an n×n matrix H[a,b]. Each cell is the integer sampling weight for placing item b after item a. The permutation [1,3,5,0,4,2] contributes directed events 1→3, 3→5, 5→0, 0→4, 4→2, and the cycle-closing edge 2→1.

Two learning modes

Roulette sampling under a permutation constraint

The matrix row is not sampled over all columns. At construction step t, COIN creates an eligibility mask from items already used. It sums only eligible weights, draws an integer or floating threshold in that reduced total, and scans cumulative weight until the threshold is crossed. After selection, that item becomes ineligible for every later step.

eligible = not_used AND legal_for_problem
total = sum(weight[row,j] for j in eligible)
r = random(0,total)
next = first j whose cumulative eligible weight exceeds r
used[next] = true

This conditional renormalisation changes as the permutation grows. A high-weight successor may be unavailable because it was selected earlier, so lower-ranked alternatives remain important. Positive minimum weights are therefore not cosmetic: they keep a feasible completion path available when preferred edges conflict.

Readable and optimized implementations

The library contains an independently readable ReferenceEdgeCoin and an optimized NumPy/Numba implementation. Equivalence tests compare initialized weights, seeded populations, reward and punishment counts, updated matrices and generation records. Optimization is accepted only after behavior is shown to match—not merely because final fitness looks similar.

Node/Position models: NB-COIN and CNB-COIN

positions = shuffle(0..n-1)
for p in positions:
    x[p] ~ W[p, unused]

for p in range(n):
    x[p] ~ W[p, unused]

Both versions learn position coincidences, but their sampling order is not equivalent. This distinction matters when early choices consume values that later positions also strongly prefer.

Why NB and CNB may diverge despite sharing W

Suppose positions 0 and 5 both strongly prefer item 1. NB-COIN may fill position 5 first and consume item 1; CNB-COIN always gives position 0 first access. Thus the factorized matrix alone does not fully determine the generated distribution—the order of conditional sampling is part of the algorithm. Reporting only “Node-based COIN” would hide this experimental variable.

SNE-COIN

Pure Edge COIN represents transitions strongly but does not give a unique probabilistic role to the first position. SNE-COIN adds a vector S[item] for the first member and retains H[a,b] for subsequent transitions.

This model is useful when the first locus has semantics: a depot, starting city, seed node, initial job or boundary condition.

Two Node–Edge hybrids, two different schemas

template: [1,_,3,_,_,6,_,7,_]
complete: [1,9,3,5,4,6,8,7,2]

x[0] ~ W[0,unused]
for p = 1..n-1:
  if Bernoulli(.5):
      x[p] ~ W[p,unused]
  else:
      x[p] ~ H[x[p-1],unused]

Choosing a representation from problem semantics

What each hybrid can preserve—and destroy

A Node anchor can protect an absolute position while splitting a good edge. An Edge completion can protect adjacency while moving an item away from a good locus. HNE-COIN makes that trade-off explicit through a retained-locus mask. CNE-COIN makes it stochastic at every link. An ablation should therefore record template density or Node-source ratio, not just the final algorithm label.

The complete COIN variant family

Multi-objective COIN does not change a variant’s representation or sampler. It changes the evidence interface: nondominated rank/Pareto depth and diversity-based selection scores replace scalar fitness sorting, while an external archive retains nondominated solutions.

From objective vectors to model evidence

For minimization, solution x dominates y when it is no worse in every objective and strictly better in at least one. Nondominated sorting partitions the population into depth 0, depth 1 and deeper fronts. COIN then combines depth with a diversity-aware selection score so that reward evidence is not drawn only from one extreme of the frontier.

1. Evaluate all candidates with the identical objective functions used by competing algorithms.
2. Perform nondominated sorting and compute diversity information.
3. Select reward and punishment evidence from the resulting ranking.
4. Update the same H, W, S or hybrid model used by the corresponding single-objective variant.
5. Merge candidates into the external archive and remove dominated or duplicate objective vectors.

Do not report only archive size

Every indicator must use a common normalization and a stated reference construction. For three or more objectives, pairwise 2-D projections are explanatory views, not replacements for dominance in the full objective space.

Parameters, complexity and diagnostics

A reproducible comparison protocol

1. Freeze the problemConstruct one immutable evaluator instance per benchmark and share it across all algorithms.
2. Equalize budgetsUse the same number of objective evaluations. Report early termination separately when an exact optimum is certified.
3. Control seedsRun a declared seed set, beginning with seed 1 for a quick demonstration but using multiple seeds for inference.
4. Preserve raw setsStore permutations, objective vectors, generation/evaluation index, parameter configuration and runtime.
5. Separate quality and speedReport objective evaluations to target, wall time, evaluator throughput and model overhead independently.
6. Use statistical summariesPublish median, mean, dispersion, success rate and paired comparisons—not only the most favorable run.

Failure modes visible in the model

Recommended learning-progress traces

Plot best-so-far for every objective against objective evaluations. Add archive size and nondominated ratio for MO runs, and optionally matrix entropy or effective row support to expose how fast the model concentrates. A minimization best-so-far curve must be non-increasing; an upward jump is a reporting or sign bug, not learning.

Source map: explanation to reusable library

Reusable interface boundary

Each model is responsible for initialization, population generation, and learning from selected permutations. The optimization driver owns evaluation budgets, objective direction, best-so-far records and termination. This separation lets the same COIN model solve Flow Shop, TSPTW, Linear Ordering, Sudoku, RNA candidate ordering, load partitioning and other permutation tasks without embedding domain code in the learner.

model = Variant(config, rng)
algorithm = PermutationCoinAlgorithm(model, problem)
result = algorithm.run(evaluation_budget)

# Multi-objective changes the orchestration:
algorithm = MultiObjectiveCoinAlgorithm(model, problem)
pareto_set = algorithm.run(evaluation_budget)

Tests required before a new variant joins the suite

• Every generated chromosome is a complete permutation.
• Reward and punishment counts match a hand-calculated fixture.
• Forbidden transitions retain zero while legal transitions retain positive support.
• Seeded sampling is reproducible.
• Optimized and readable kernels produce equivalent state transitions.
• The evaluator count equals the declared budget, including the final partial generation.
• Single-objective best-so-far has the correct monotonic direction.
• MO archives contain no dominated members or duplicate objective vectors under the declared policy.