Production rules and local evaluation functions are used to solve problems in CCM. One production rule and one local evaluation function are used to color a graph or a set of graph vertices.
The rule selects a color from a set of given colors, and the rule changes the color of an area, in the case of a map, or the color of a vertex, in the case of a graph. The area or vertex is randomly selected (using a random number). However, whether to apply the rule or not is decided using a local evaluation function explained in the next section. Try selecting the area and color by pushing the button in the applet in the right. (the source program of the applet.)
The local evaluation function is defined between two areas or two vertices. In the case of map coloring, o(x, y), the value of the local evaluation function between x, y is 1 when the color of x and y are different, and the value is 0 when the color of them are the same. That means that the value is higher when the state is better.
An area or vertex for the rule application is randomly selected. In the case of a map, whether to apply the rule on the selected areas is decided using local evaluation functions between the area and the neighbor areas. If the sum of all the local evaluation functions between any combination of two areas selected by the rule is increased by the rule application, the rule is actually applied. Otherwise, the rule is not actually applied. This means that the rule is applied when the application locally improves the state of coloring, and is is not applied otherwise. The global state of coloring may be disproved even when the local state is improved, and vice versa.
The above basic production rule selects only one area, and the sum of local evaluation function is actually zero. So, the rule cannot find a solution. To make the rule solvable (??), the rule must be changed to select several more areas neighbor to the area to change the color. Then the neighbor areas are counted when computing the sum of local evaluation functions, and the mechanism of CCM works well for finding a solution. The data that are selected but not changed by applying the rule are called catalysts. The rule that selects only one neighbor area is called the ``Single catalyst swapping rule,'' which is used in the applet page.
The number of catalysts can be increased. ``Double catalyst swapping rule'' is also appeared in the applet page. The number of neighbor areas depends on the area. So, a rule that selects all the neighbor areas of the area to change color can be described. This is the ``variable catalyst rule.'' If more and more catalysts are used in the rule, more non-local information is used, and the number of application of the rule until the solution is found becomes less.