How it works

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.

S

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 · explicit

R

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 · arity variable

A

well-stirred-multiset · none - the working memory keeps one atom per queen or vertex; a reaction rewrites atom states

Parameters

What to look for

• 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)

Implementation 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.

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

Banzhaf & Yamamoto, Artificial Chemistries (2015), §17.2.2

Preview at default parameters

64 species · 187 reactions · status observed · seed 1

q3=3 + q4=4 + q6=6 -> q3=4 + q4=3 + q6=6  (x1)
q7=7 + q0=0 + q1=1 -> q7=0 + q0=7 + q1=1  (x1)
q6=6 + q7=0 + q1=1 -> q6=0 + q7=6 + q1=1  (x1)
q5=5 + q4=3 + q0=7 -> q5=3 + q4=5 + q0=7  (x1)
q0=7 + q3=4 + q7=6 -> q0=4 + q3=7 + q7=6  (x1)
q1=1 + q4=5 + q2=2 -> q1=5 + q4=1 + q2=2  (x1)
q0=4 + q6=0 + q2=2 -> q0=0 + q6=4 + q2=2  (x1)
q3=7 + q6=4 + q2=2 -> q3=4 + q6=7 + q2=2  (x1)
q4=1 + q6=7 + q7=6 -> q4=7 + q6=1 + q7=6  (x1)
q4=7 + q6=1 + q3=4 -> q4=1 + q6=7 + q3=4  (x1)
q2=2 + q0=0 + q3=4 -> q2=0 + q0=2 + q3=4  (x1)
q6=7 + q7=6 + q2=0 -> q6=6 + q7=7 + q2=0  (x1)
q7=7 + q0=2 + q6=6 -> q7=2 + q0=7 + q6=6  (x1)
q2=0 + q1=5 + q5=3 -> q2=5 + q1=0 + q5=3  (x1)
q6=6 + q2=5 + q0=7 -> q6=5 + q2=6 + q0=7  (x1)
q6=5 + q3=4 + q1=0 -> q6=4 + q3=5 + q1=0  (x1)
q2=6 + q0=7 + q5=3 -> q2=7 + q0=6 + q5=3  (x1)
q2=7 + q5=3 + q6=4 -> q2=3 + q5=7 + q6=4  (x1)
q3=5 + q0=6 + q5=7 -> q3=6 + q0=5 + q5=7  (x1)
q3=6 + q7=2 + q6=4 -> q3=2 + q7=6 + q6=4  (x1)
q2=3 + q5=7 + q0=5 -> q2=7 + q5=3 + q0=5  (x1)
q1=0 + q2=7 + q0=5 -> q1=7 + q2=0 + q0=5  (x1)
q7=6 + q2=0 + q6=4 -> q7=0 + q2=6 + q6=4  (x1)
q1=7 + q5=3 + q6=4 -> q1=3 + q5=7 + q6=4  (x1)
q1=3 + q3=2 + q0=5 -> q1=2 + q3=3 + q0=5  (x1)
q2=6 + q4=1 + q0=5 -> q2=1 + q4=6 + q0=5  (x1)
q1=2 + q2=1 + q7=0 -> q1=1 + q2=2 + q7=0  (x1)
q4=6 + q2=2 + q6=4 -> q4=2 + q2=6 + q6=4  (x1)
q6=4 + q4=2 + q7=0 -> q6=2 + q4=4 + q7=0  (x1)
q7=0 + q3=3 + q1=1 -> q7=3 + q3=0 + q1=1  (x1)
q0=5 + q6=2 + q4=4 -> q0=2 + q6=5 + q4=4  (x1)
q4=4 + q2=6 + q1=1 -> q4=6 + q2=4 + q1=1  (x1)
q7=3 + q1=1 + q0=2 -> q7=1 + q1=3 + q0=2  (x1)
q6=5 + q2=4 + q5=7 -> q6=4 + q2=5 + q5=7  (x1)
q3=0 + q5=7 + q4=6 -> q3=7 + q5=0 + q4=6  (x1)
q0=2 + q1=3 + q3=7 -> q0=3 + q1=2 + q3=7  (x1)
q4=6 + q7=1 + q6=4 -> q4=1 + q7=6 + q6=4  (x1)
q2=5 + q4=1 + q5=0 -> q2=1 + q4=5 + q5=0  (x1)
q3=7 + q0=3 + q6=4 -> q3=3 + q0=7 + q6=4  (x1)
q2=1 + q3=3 + q7=6 -> q2=3 + q3=1 + q7=6  (x2)
… 147 more

Generated by the uploader with chemart push; the hub never runs uploaded code.