A GOD is a function of time. It may change when an instance is reacted. The time can be measured by the number of reactions since the system began to work. An example of the GOD transitions in the eight queens system, measured using SOOC with an MR strategy, is shown by the unshaded line in Figure 8. The solution was found in 88 reactions in this trial. The rule used in this measurement computes the GOD explicitly. The shaded line in this figure is explained in Section 5.3.
Computation can be regarded as a stochastic process in CCM even when an S strategy is used. Figure 8 illustrates the meaning of this statement. The following three states occur in this order in the computation process of CCM, if appropriate rules and LODs are given.
The N queens system and the graph coloring system mentioned in Section 4.3 are conflicting systems, unless the IOD is the same as the GOD. Thus the GOD does not increase monotonically as shown in Figure 8. Some systems have little conflict while others have considerably more. However, the definition of the degree of conflict is a task for the future. On the contrary, the GOD monotonically increases in a cooperative system. Examples of cooperative systems are the TSP system, the 0-1 Knapsack system and the sorting systems mentioned in Section 4.3.
In a cooperative system, the local maxima of the GOD can partially be avoided by reducing the locality by composing rules. This property is explained in the next section.
In a conflicting system, to add catalysts to a rule makes the system less conflictive and decreases the average number of reactions required to find a solution. If more catalysts are added, the rule refers to a more global state. For example, the rule in the N queens system contains a catalyst. If this catalyst is removed, the system does not stop even when a solution is found. However, this system performs a random search. An example of GOD transition in a random search is shown by the shaded line in Figure 8. On the contrary, more catalysts may be added to the rule. However, if more catalysts are added, the execution time for the rule matching increases, thus the efficiency of the system is reduced.
Figures 9 and 10 shows the effect of adding or removing catalysts in the N queens system. The average and standard deviation of GOD in the quasi-stationary state as functions of the number of catalysts, Nc, are shown in Figure 9. The average becomes higher and the standard deviation becomes lower when Nc increases. This means that catalysts bias the search: a system with more catalysts searches among the states where the GOD is higher, thus the computation is more efficient. The performance as a function of Nc, measured on a Macintosh IIX computer, is shown in Figure 10. The data are not given for Nc = 0 because the execution does not stop in this case. Although the number of reactions decreases when Nc increases, the execution time, which is approximately proportional to the number of matches, increases when Nc > 2.
Adding catalysts decreases the possibility of escaping from local maxima. This property is explained in the next subsection. Adding catalysts also makes it impossible to solve the problem for small N in the N queens problem, because the rule cannot produce a solution if the number of matching patterns in the LHS is greater than N. Thus, there is an optimum number of catalysts.
The rule with catalysts can sometimes be generated not only by adding catalysts to the rule, but also by composing a rule with no catalyst, and thus rule composition can be used for controlling rule locality. Figure 11 shows the composition of a rule with a catalyst using a rule without a catalyst in the N queens system. An application of the rule with a catalyst, shown in Figure 4, moves the current state from State 0 to 3. The three contiguous applications of a rule without a catalyst also move the current state from State 0 to 3. In the first step, the columns of Q1 and Q2 are swapped. The columns of Q2 and Q3, and the columns of Q1 and Q2 are swapped in the following steps. Rules with two or more catalysts can be composed in the same way.
A conflicting system, such as the N queens system but not all conflicting systems, never falls into the local maxima of the GOD and can reach the global maxima, i.e., reach solutions, even when using an S strategy. This behavior can be regarded as emergent.
Here, a local maxima of GOD means that a state S such that GOD(S) >= GOD(S') holds for any state S' derived from S by a reaction. An example of a local maximum in the six queens system is shown in Figure 12.[*5.2?] The maximum value of the GOD is 15, and that of the state shown is 14.
If a hill-climbing method is used for finding the maximum value of the GOD, the search may fall into a local maximum. However, the CCM-based system can escape from local maxima because there is always an instance that can be reacted even when the system is in a local maximum.[*5.3?] For example, in Figure 12, if the queens in the sixth, fifth and fourth columns are matched to Queen1, 2 and 3 of the rule in Figure 4 respectively, the reaction occurs and the system escapes from this local maximum.
Reducing the locality by adding catalysts decreases the possibility of escaping from local maxima. For example, the state shown in Figure 12 is a local maximum if a rule with four catalysts, i.e., a rule with six patterns, is used, because the IOD computed in this rule is equal to the GOD. On the contrary, in cooperative systems, reducing the locality by adding (but not replacing) rules that are compositions of the original rule usually increases the possibility of escaping from local maxima. This happens, for example, in optimization problems such as the TSP system or the 0-1 Knapsack system.
Figure 9. Relation between number of catalysts and global order
Figure 10. Relation between number of catalysts and performance
Figure 11. Composition of a rule with a catalyst using a rule without a catalyst
5.4 Escaping from Local Maxima
Conflicting and cooperative systems behave differently in regards to local maxima. Thus, the behavior of conflicting systems is explained first, and then that of cooperative systems is explained.
Figure 12. An example of a local maximum in the six queens system
Go to: Next section, Parent node