7.3.1 Coding

At first glance, the addition of two new choices for the actions has not changed anything that should make us reconsider our use of the concatenated, mapped, unsigned binary coding described above. However, upon further consideration, perhaps we should make some adjustments. Consider the use of binary strings of length two to represent the nine choices we have for each rule. If we use binary strings of length two, we can without duplication directly represent four choices; with binary strings of length three we can represent eight choices; with binary strings of length four we can represent sixteen choices. Thus, binary coding requires binary strings of length four be used to represent the nine choices for the linguistic variables describing force to be associated with each rule. We will have seven “unused” bits that will be filled with duplicate selections. Recall we faced this situation in the previous section in which we duplicated one linguistic descriptor of force. However, all of the problems associated with duplication of solutions are now magnified. Consider for instance the size of the search space. With the declaration of nine choices for the rules, there exist approximately 2*10¹⁸ possible rule sets. However, with the binary coding being discussed, the GA would be faced with a search space consisting of 2^108*4 = 1.109*10¹³⁰ possible solutions (certainly some of them are duplicates, but they are still possibilities). Thus, it is prudent to consider an alternative coding scheme.

With nine rule actions to choose from, a tertiary coding is natural. Consider a coding scheme in which base three representations are used instead of binary or base two representations. If such an alphabet is used, then the following table lists the mapping from base three space to rule value space:

Notice in the above representation no duplication of solutions is required; each string of characters maps directly and uniquely to a single choice of action. Thus, the problems associated with duplication in the coding scheme discussed in the previous section are no longer relevant. Additionally, a GA is now faced with a search space of size 3^108*2 = 1.143*10¹⁰³ which is far smaller than that created using a binary representation. Aside from the leverage gained by reducing the size of the search space, it is generally better to avoid duplication when possible because of the bias introduced; strings that are represented with more than one substring represent a larger percentage of the possible solutions. Thus, they are more likely to exist in the population, whether they are quality solutions or not. This bias can cause the GA to converge to sub-optimal answers or to take longer to converge to the best answers.

Given the expansion of our coding scheme from binary representation to a ternary alphabet, we must ensure that the operators employed by the GA can still be used. Reproduction biases successive populations of strings toward highly fit strings. It employs the fitness function values to drive its choice of strings to copy in the mating pool with our tournament selection. Reproduction is not affected by the extension to a base three representation. Crossover still involves the combining of strings. It selects two strings from the mating pool, cuts the strings at a randomly selected site, and exchanges the tails of the strings to form two new strings. Like reproduction, crossover is not affected by the use of a ternary alphabet. Mutation, however, is a different story. Mutation involves the random alteration of string values. In our binary strings, it meant changing a 0 to 1, and a 1 to a 0. In our current coding, we must accommodate not only the familiar 1 and 0 characters, but also the newly introduced two character. Thus, a simple expansion of mutation (and others are presented in the reference by Goldberg, 1989) is to change a 0 to a 1, change a 1 to a 2, and change a 2 to a 0. With this modification of the mutation operator, the GA is fully capable of working with the ternary coding scheme which results in 108, two-character substrings concatenated to form strings of length 216.

7.3.2 Fitness Function

The changes in the coding scheme have in no way altered the desired goal of the controller. Therefore, it is reasonable to assume that the fitness function defined in the previous section is again applicable. The fitness function of Equation (7.1) is employed here.

7.3.3 Results

In the previous section we demonstrated the ability to locate an already defined optimum rule-set in less time than needed by a human developer (at least in less time than it took us). The results of this section should provide a little something different. First of all, we do not know what the optimum controller for the cart-pole system is when we have nine values available from which to choose an action. Thus, the performance of the nine-action term GA-FC is directly compared to the performance of the seven-action term GA-FC developed in the previous section. As can be seen from Figure 7.4, the nine-action GA-FC is more robust. As a note, the initial conditions depicted in Figure 7.4 were not one of the four initial condition cases appearing in the fitness function. Thus, this figure represents the performance of the GA-FC on an initial condition case for which it was not specifically trained.

Figure 7.4  The optimized nine-action GA-FC is more efficient than the optimized seven-action GA-FC. Thus, it is apparent that expanding the values from which an action can be chosen gives a more effective controller. However, without an effective search technique such as a GA, determining optimum rule values is a daunting task.