Production rules and LEFs (local evaluation functions) are used for solving problems in CCM. A combination of one production rule and one LEF is used for solving the N queens problem or sorting. The method of solving N queens problem is explained in this page. The same production rule can be used for sorting too.
A production rule changes a state of data by an application. The most simple rule used in the applet page is the ``single catalyst swapping rule.'' This rule swaps the columns of two queens. Make sure the meaning of ``column swapping'' by pushing the button in the applet in the right. (The source program of the applet.)
To find a solution using the above rule, the above simple operation is repeatedly applied to different pair of queens. A pair of queens is selected randomly (using a random number). However, whether to apply the rule to the selected queens or not is decided using the LEF shown below. The method of decision is explained later.
The rule shown in the right is the ``no catalyst swapping rule,'' used in the applet page. Actually, a solution cannot be found using this rule. To find a solution, third and maybe fourth queens must be added to the rule. The function of these queens are explained later.
The ``variable catalyst MOVING rule'' randomly changes the column of a queen. Make sure the meaning of the rule by pushing the button in the applet in the right. (You may see no change when you push the button. Then try pushing the button again and again until you see a change. Can you see the reason why there was no change?) (The source program of the applet.)
A LEF (local evaluation function) is defined between two queens. The value of the LEF o(x, y) between queens x and y is 0 when x and y can take each other, and it is 1 otherwise. Thus, the value of LEF is 0 when they are on the same row, on the same column or in the diagonal direction. (I want to create an applet that explains the definition of LEF, but I have not yet develop it because it is much more complicated than the applet for explanation of rules.)
Queens to apply rules are randomly selected when executing the prigram. Whether to apply rules to the selected queens is decided using LEFs between them. The sum of the LEFs of all the combinations of the queens is calculated. The rule is applied when the sum is increased by the application, but it is not applied when the sum is decreased. (To apply the rule or not when the sum is not changed is decided before the execution.) That is, the rule is applied when the application make the state of the chess board better locally, and it is not applied when the application make the state worse. However, the global state may become worse when the local state becomes better, and vice versa.
The above column change rule actually does not change the LEF between the two queens. The computation mechanism of CCM, thus, does not work well. So the third queen, which has nothing to do with the column swap operation itself, is added to the rule as shown in the right figure. Then, the mechanism of CCM becomes work well, because the third queen participates to the LEF calculation. This rule is the ``single catalyst swapping rule,'' which is used in the applet page. The data that does not change while the rule application is called a catalyst.
There is only one catalyst in the rule in the right figure. The number of catalysts can be two or more. You can try ``double catalyst swapping rule'' in the applet page. If more and more catalysts are added to the rule, more non-local information becomes to be used in the computation using the rule, and the number of rule applications becomes less. (The source program of the applet.)