chemart / ccm

hub:
  repo_type: generator
  builtin: ccm
  tags:
  - banzhaf-yamamoto
chemistries:
- id: ccm
  name: Chemical Casting Model (CCM)
  intuition: 'Emergent problem solving from purely local rules. The whole working memory is a single candidate
    solution - one atom per queen, or per graph vertex - and rules rewrite small groups of atoms, with
    the untouched atoms acting as catalysts. A rule fires only if it does not lower a *local* order degree,
    so nothing ever computes a global objective. Yet the system reliably reaches global optima like an
    eight-queens solution or a valid map colouring, because random local improvement plus the occasional
    frustrated move is enough to escape traps.

    '
  aliases:
  - chemical casting model
  - chemical computation model
  - CCM with FAM
  - annealed CCM
  origin: Kanada, 1992-1996
  book: 17.2.2
  refs:
  - '[438]'
  - '[439]'
  - https://ieeexplore.ieee.org/document/538377/
  - https://www.kanadas.com/Papers/CCM-papers.html
  family: application
  kind: generator
  constructive: false
  S:
    repr: 'atoms with a type and a state, optionally connected by links; the whole working memory is ONE
      point of the search space. A species is an atom in a state: q<row>=<column> for a queen (n-queens),
      v<i>=c<k> for a vertex with colour k (graph-coloring); structure ''(queen, row=r, column=c)'' or
      ''(vertex, id=i, color=k)''. Rows, columns, vertices and colours are numbered from 0

      '
    definition: explicit
    notes: 'Links are fixed during a run (the graph''s edges); in n-queens no link is used (HICSS-27 sec.
      4.1). The species set is finite: N^2 queen states or V x colors vertex states.

      '
  R:
    definition: explicit
    arity: variable
    scheme: 'LHS -> RHS: the matched atoms are rewritten and the unchanged ones are catalysts. n-queens
      swap rule with k catalysts: q<a>=ca + q<b>=cb + k queens -> q<a>=cb + q<b>=ca + the same k queens;
      moving rule: q<a>=c + all other queens -> q<a>=c'' + all other queens. graph-coloring: v<i>=c1 +
      k linked neighbours (or all of them) -> v<i>=c2 + the same neighbours. An instance reacts only if
      the instance order degree (sum of the pairwise LODs of the matched atoms) does not decrease

      '
    notes: 'LODs: n-queens o(x, y) = 0 if the queens can take each other (same column or diagonal), else
      1 (HICSS-27 fig. 4; Queens_Sort.order); graph-coloring o(v1, v2) = 1 if not connected or of different
      colours, else 0 (FUZZ-IEEE''95 sec. 3). Rules without catalysts react unconditionally and random-walk
      forever. Each recorded reaction is one accepted rule application; catalysts appear on both sides.

      '
  A:
    reactor: well-stirred-multiset
    dilution: none - the working memory keeps one atom per queen or vertex; a reaction rewrites atom states
    notes: 'Mathematical-random scheduling (HICSS-27 sec. 3.4): each test draws a rule instance at random.
      Frustration accumulation method (FAM, the annealing variant): each atom has a frustration f starting
      at f0; a tested instance with unsatisfied constraints that does not react multiplies f of its changed
      atoms by c, a reaction resets it to f0, and the reaction test becomes O'' >= O - F with F the summed
      frustration of the changed atoms. The run stops with the demos'' termination test (a run of failed
      tests of adaptive length) or after max_tests tests.

      '
  params:
  - name: problem
    type: enum
    default: n-queens
    choices:
    - n-queens
    - graph-coloring
    role: structural
    meaning: 'constraint satisfaction problem with its published rule and LOD: n-queens (HICSS-27 sec.
      4, Queens_Sort) or graph-coloring (FUZZ-IEEE''95 sec. 3, Kanada 1996 sec. 3.2, USAmap_color)'
  - name: N
    type: int
    default: 8
    min: 4
    max: 1000
    range: 'HICSS-27 fig. 7: 4..50; figs. 8-10: 8; fig. 12: 6 (the demo requires N >= 4)'
    role: structural
    meaning: 'n-queens only: board size and number of queen atoms'
  - name: graph
    type: enum
    default: usa-mainland
    choices:
    - usa-mainland
    - random
    - custom
    role: structural
    meaning: 'graph-coloring only: usa-mainland (the 48 contiguous states, 106 borders, of FUZZ-IEEE''95
      fig. 5 and USAmap_color); random (G(V, p), the model of the DSJC benchmark graphs of Kanada 1996
      table 2); custom (edges)'
  - name: V
    type: int
    default: 30
    min: 1
    max: 10000
    range: 'Kanada 1996 table 2: DSJC125.x and DSJC250.x'
    role: structural
    meaning: 'graph-coloring with graph=random: number of vertices'
  - name: edge_probability
    type: float
    default: 0.1
    min: 0.0
    max: 1.0
    range: 'DSJC: 0.1, 0.5, 0.9'
    role: structural
    meaning: 'graph-coloring with graph=random: probability of each edge'
  - name: edges
    type: list
    default: []
    role: structural
    meaning: 'graph-coloring with graph=custom: undirected edges [[u, v], ...] on vertices 0..max id'
  - name: colors
    type: int
    default: 4
    min: 2
    max: 1000
    range: 'USA map: 4; DSJC125.1: 5-6, DSJC125.5: 17-18, DSJC250.5: 29-31'
    role: structural
    meaning: 'graph-coloring only: number of colours'
  - name: rule
    type: enum
    default: single-catalyst
    choices:
    - no-catalyst
    - single-catalyst
    - double-catalyst
    - triple-catalyst
    - variable-catalyst
    range: 'HICSS-27 figs. 9-10: Nc = 0..3 swap catalysts; demos: no, single, double and variable catalyst
      rules'
    role: structural
    meaning: 'catalysts of the rule, i.e. its locality. n-queens: column swap of two queens with 0-3 random
      other queens as catalysts, or variable-catalyst = move one queen to another column with all other
      queens as catalysts. graph-coloring: recolour a vertex with 0-3 random linked neighbours as catalysts,
      or all its neighbours. More catalysts: fewer reactions, but easier trapping in local maxima'
  - name: acceptance
    type: enum
    default: non-decreasing
    choices:
    - non-decreasing
    - increasing
    role: selection
    meaning: 'reaction test on the instance order degree: non-decreasing IOD_before <= IOD_after (Kanada''s
      definition and demos) or increasing IOD_before < IOD_after (the book''s wording, HICSS-27 footnote
      3); frustration is subtracted from IOD_before in both'
  - name: frustration
    type: bool
    default: true
    role: thermodynamic
    meaning: frustration accumulation method (FAM), the book's annealing variant; false is the original
      CCM
  - name: f0
    type: float
    default: 1.0e-05
    min: 0.0
    max: 1000.0
    range: 'demos and Kanada 1996 table 2: 1e-5 (down to 1e-45 on DSJC250.5); fig. 15: 0.8'
    role: thermodynamic
    meaning: initial frustration of every atom, restored after each reaction of the atom (must be > 0
      with frustration)
  - name: c
    type: float
    default: 2.0
    min: 1.0
    max: 1000.0
    range: 'demos and Kanada 1996: 2; figs. 16-17: 1.1-4; fig. 15: 1.05'
    role: thermodynamic
    meaning: 'frustration growth factor: f -> c f after each failed test of an instance with unsatisfied
      constraints'
  - name: initial
    type: enum
    default: ordered
    choices:
    - ordered
    - random
    role: population
    meaning: 'initial working memory: ordered = all queens on the diagonal (column = row, HICSS-27 sec.
      4.1, Queens_Sort) or all vertices colour 0 (FUZZ-IEEE''95 sec. 3, USAmap_color); random = a random
      permutation of columns (HICSS-27 sec. 4.2) or random colours'
  - name: max_tests
    type: int
    default: 200000
    min: 1
    max: 1000000000
    role: population
    meaning: budget of rule tests (LHS matches); rules without catalysts never terminate and always stop
      here
  provides:
  - topology
  - stoichiometry
  - catalysts
  - initial-state
  - sequence-structure-function
  fidelity: reconstructed
  sources:
  - 'Kanada, Y. & Hirokawa, M. (1994). Stochastic problem solving by local computation based on self-organization
    paradigm. 27th HICSS, pp. 82-91 (book [439]). Sec. 3: atoms, rules, instances, LODs (self and mutual
    order degrees), instance order condition IOD_before <= IOD_after; sec. 4: the N-queens swap rule with
    a catalyst and its LOD (figs. 4-6); sec. 5: GOD, conflicting vs cooperative systems, catalysts (figs.
    8-11), local maxima (fig. 12); table 1. https://www.kanadas.com/CCM/HICSS27/probsolving-hicss.new.pdf'
  - 'Kanada, Y. (1995). Combinatorial problem solving using randomized dynamic tunneling on a production
    system. IEEE SMC''95, vol. 4, pp. 3784-3789 (book [438]). Sec. 2.1: atoms with type and state, links,
    reaction condition (sum of LODs of the atoms involved not decreased); sec. 2.2-4: CCM* (random rule
    composition) on 0-1 integer programming. https://www.kanadas.com/CCM/SMC95/tunneling.pdf'
  - 'Kanada, Y. (1995). Fuzzy constraint satisfaction using CCM - a local information based computation
    model. FUZZ-IEEE/IFES''95, pp. 2319-2326. Sec. 3: graph-colouring rule (fig. 3) and LOD, zero/two/variable
    catalysts (fig. 4), USA mainland map, mean degree 4.42, correct solution in every run, FAM needed
    by the variable-catalyst rule; table 2 (112 reactions, 4406 matchings on average). https://www.kanadas.com/CCM/FUZZ-IEEE95/fuzzycs-ccm.upd.pdf'
  - 'Kanada, Y. (1996). Constraint satisfaction by parallel optimization of local evaluation functions
    with annealing (manuscript, 2/4/96). Sec. 3.2: colouring rule/LOD, catalysts, termination by a number
    of failed trials; sec. 4: FAM (f -> c f on failure with unsatisfied constraints, reset to f0 on reaction,
    f0 = 1e-5, c = 2, fig. 11); sec. 6: DSJC results (table 2, figs. 16-17). https://www.kanadas.com/CCM/LargeCSP/largecsp.pdf'
  - 'Kanada, Y. (1996, JavaScript port 2025). N queens problem and sorting using CCM (Queens_Sort) and
    USA mainland map coloring using CCM (USAmap_color): reference programs with the no/single/double swap
    rules, the variable-catalyst moving rule, the recolouring rules, FAM (f0 = 1e-5, c = 2), the termination
    test and the USA border graph. https://www.kanadas.com/ccm/queens-sort/Queens_Sort.js , https://www.kanadas.com/ccm/coloring/USAmap_color.js
    , method pages https://www.kanadas.com/ccm/queens-sort/method.html , https://www.kanadas.com/ccm/coloring/method.html'
  reference_impl: Kanada's demo programs Queens_Sort.js and USAmap_color.js (kanadas.com/ccm, 1996 Java
    applets ported to JavaScript)
  decisions:
  - 'Book error: 17.2.2 credits the annealing variant with frustration to [438]. [438] (SMC''95) introduces
    CCM*, a randomized tunnelling by dynamic rule composition, and uses no frustration; FAM is from Kanada''s
    SWoPP''94 paper (Japanese, not used), FUZZ-IEEE''95 sec. 3-4 and the 1996 manuscript sec. 4, which
    are followed here. CCM* is not implemented.'
  - 'Book wording: a rule ''may be applied if the sum of LODs on the LHS is smaller than on the RHS''
    (strict). Kanada''s papers say the IOD must not decrease (HICSS-27 sec. 3.3, SMC''95 sec. 2.1), with
    the strict test as an allowed variant (HICSS-27 footnote 3). Both are offered as acceptance; the default
    is Kanada''s non-decreasing test.'
  - 'Reaction test and FAM follow the demos exactly: an instance whose matched pairs are all satisfied
    never reacts (and its frustration does not grow), so solved states are stationary under the non-decreasing
    test; otherwise it reacts if O'' >= O - F (or O'' > O - F), F = summed frustration of the changed
    atoms (catalysts not counted, 1996 sec. 4); on failure f -> c f for each changed atom, on reaction
    f -> f0. The 1996 manuscript prints O - F <= O'' - F'' with F'' after the update; its own worked example
    (fig. 11) and the demos compare against O - F only, which is used. The alternative of resetting f
    when constraints become satisfied by another reaction (1996 footnote) is not implemented.'
  - 'IOD pairs: only pairs involving a changed atom are summed (pairs of two catalysts are unchanged and
    cancel, 1996 sec. 3.2); the n-queens swap counts the swapped pair too, as Queens_Sort does. Rules
    without catalysts evaluate no pair and react unconditionally (demo swap0/change_color0; 1996 sec.
    3.2), so they random-walk and only max_tests stops them.'
  - 'n-queens LOD: HICSS-27 fig. 4 defines o only by diagonals, since the swap rule keeps one queen per
    row and column; Queens_Sort.order also sets o = 0 for a shared column, which the moving rule needs.
    The demo''s definition is used; under swap rules the two coincide.'
  - 'n-queens rules: swaps with 0-3 catalysts (HICSS-27 figs. 9-10 use Nc = 0..3; the demo 0..2) and the
    demo''s variable-catalyst moving rule. Atoms are drawn uniformly without repetition, as the demos''
    rejection loops do. The moving rule draws a new column different from the current one (the demo can
    redraw the same column, which counts as a reaction with no change); this matches USAmap_color.select_color
    and records no empty reactions. A rule matching more than N queens is rejected (HICSS-27 sec. 5.3).'
  - 'graph-coloring rules: the demo''s recolouring with one or two random neighbours as catalysts (vertices
    with too few neighbours are skipped as failed tests, USAmap_color.change_color1/2), extended to three,
    or all neighbours (variable catalyst, FUZZ-IEEE''95 fig. 4c). The new colour is drawn uniformly among
    the other colours (select_color); the papers draw from all colours but a same-colour draw can never
    change the state. The map''s graph is the demo''s; its mean degree 212/48 = 4.42 matches FUZZ-IEEE''95
    sec. 3.'
  - 'Termination as in the demos'' loopTick: with threshold T (1000 + N^2 for queens, 1000 for colouring),
    when T tests in a row fail the run stops if fewer than 20 T tests were made, else T doubles (the 1996
    manuscript''s ''maximum number of trials increased to 1/20 of the total number of LHS tests''). max_tests
    is a hard budget. GOD is never used by the dynamics; it is only reported (analysis).'
  - 'Published counts: FUZZ-IEEE''95 table 2 reports 112 reactions and 4406 LHS matchings on average for
    the USA map with the variable-catalyst rule and FAM, run with ''a slightly modified version of the
    rule and LOD'' in SOOC-94; Chemart''s demo-based rule gives about 117 reactions and 2500 tests (10
    seeds). The reaction count is checked in the tests (60-200); the matching count is not, since the
    modification is not described.'
  - 'Initial states follow the demos: queens on the diagonal (the GOD minimum, HICSS-27 sec. 4.1) and
    all vertices colour 0 (FUZZ-IEEE''95); HICSS-27 measured fig. 7 from random layouts, offered as initial=random.'
  - 'Not implemented: the TSP, 0-1 knapsack/integer programming and sorting casters (HICSS-27 table 1
    gives only counts; SMC''95 gives the 0-1 IPP rule but its runs need CCM*), fuzzy colouring (FUZZ-IEEE''95
    sec. 4-5) and parallel scheduling (1996 sec. 5). Timings (SOOC on Macintosh, C on a Cray CS6400) are
    not reproducible; tests check the qualitative claims and the counts.'
  - 'Observed network: species are the initial atom states and every atom state produced; reactions are
    the distinct accepted rule applications (changed atoms first, then catalysts on both sides) with counts;
    initial_state has one of each initial atom state. extras.analysis: tests, reactions, uphill_reactions
    (accepted only thanks to frustration), terminated, god_initial/final/max, mod_final, solved, first_solution_reaction,
    god (GOD after each reaction, first 20000), mean_frustration_final; extras.instance (N, or vertices,
    edges, colors, mean_degree), initial_assignment and final_assignment. No rate constants: CCM has none.'
  - 'v1 parameters: the LOD callable becomes the LOD fixed by the problem; catalysts (bool) becomes the
    rule enum; c keeps its meaning (FAM growth factor) with f0 added.'
  phenomena:
  - 'convergence to global optima despite purely local evaluation: 8-queens and the USA map are solved
    in every run (HICSS-27 sec. 4.2, FUZZ-IEEE''95 sec. 3)'
  - 'conflicting systems: in n-queens and colouring a reaction that raises the local IOD can lower the
    global order degree, so GOD is not monotone (HICSS-27 fig. 8, sec. 5.2)'
  - 'rules without catalysts never stop: pure random walk (HICSS-27 sec. 5.3, FUZZ-IEEE''95)'
  - 'more catalysts: fewer reactions to a solution but more matches per reaction and easier trapping (HICSS-27
    figs. 9-10, fig. 12)'
  - 'escaping local maxima: the 6-queens state of HICSS-27 fig. 12 is a GOD local maximum that the single-catalyst
    swap escapes'
  - FAM lets the variable-catalyst rule escape stationary non-solutions that trap it without frustration
    (FUZZ-IEEE'95, Kanada 1996 sec. 4)
  - 'near-lock-free parallelism: access conflicts act as harmless low-intensity noise (book 17.2.2; Kanada
    1996 sec. 5; not simulated)'
  notes: 'Kanada''s model for emergent computation: a production system whose rules test only local evaluation
    functions and fire in random order, so that global order (solutions of constraint satisfaction problems)
    emerges without a global objective. CCM* (SMC''95) adds randomized rule composition; FAM adds local
    annealing without a global temperature.

    '