5. Characteristics of CCM-based Computation

This section explains the characteristics of CCM-based computation after defining the global order degree.

5.1 Global Order Degree and its Stochastic Process

The global order degree (GOD) of an CCM-based system is the sum of the LODs.2, 3 If the LOD is defined as the self order degree, the GOD is the sum of the LODs of all atoms. If the LOD is defined as a mutual order degree, the GOD is the sum of the LODs of all pairs of atoms in working memory. In the case of the N queens system, there are combination(N, 2) (= N(N-1)/2) pairs of queens. Because each LOD is 0 or 1, the minimum and maximum values of the GOD are 0 and combination(N, 2). The GOD is at a maximum at the solutions and only in these states, because the GOD is equal to the number of satisfied unit constraints in this system.[*5.1] The GOD is at a minimum when all the queens are on a diagonal.

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.

Figure 8. An example of GOD transition in the eight queens computation

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.

In Figure 8, the quasi-stationary state is estimated to begin when t (number of reactions) is around 10. The above states can be modeled by a Markov chain [Kan 92b].

5.2 Conflict and Cooperation in CCM

CCM-based systems can be put into two categories. Cooperative systems are called such because reactions cooperate toward the local or global maximum of the GOD. Conflicting systems are called such because reactions does not cooperate toward that.

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.

5.3 Variability of Locality

The locality of computation can be controlled by adding catalysts to rules or composing two or more rules. Rules with less or more locality work differently because the value of IOD is used at reaction. This characteristic of CCM-based systems is called the variability of locality. The effects of controlling the locality in cooperative and conflicting systems are explained below.

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.

Figure 9. Relation between number of catalysts and global order

Figure 10. Relation between number of catalysts and performance

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.

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.

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.

Figure 12. An example of a local maximum in the six queens system

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.

Go to: Next section, Parent node
(C) Copyright 1994 by Yasusi Kanada and IEEE
Y. Kanada