Industrial Applications of Genetic Algorithms:Data Mining Using Genetic Algorithms

Previous | Table of Contents | Next

Crossover Operator

Crossover is used to improve the population fitness by introducing new strings into the population. Thus, the crossover operator for this problem had to introduce new item combination strings into the population. Due to the fact that the sub-strings (item numbers) within a coded string must be preserved, possible cross sites exist at the item boundaries within a string, as shown by points A, B, and C below:

In determining a crossover operator for this application, it was important to consider the fact that duplicate item numbers cannot exist within a string since this would represent an invalid combination of items. For example, if the following two strings were crossed using simple crossover and a cross site as noted by A,

strings 1′ and 2′ would result, as shown:

Note that the resulting string 1′ only contains three different item numbers (04, 21, and 24) instead of four.

Given this consideration, it was obvious that a simple single point crossover operator would not be adequate. Crossover operators such as partially matched crossover, or PMX [7], and ordered crossover [7] ensure that duplicates do not occur in children strings. However, these crossover operators require that each parent string contain the same characters. The situation in the data mining problem, however, is slightly different in that every item in the first string may, or may not, be in the second string. Considering this fact, two different crossover operators were developed for examination: aligned single-point crossover (ASPX) and unmatched crossover with single child offspring (UXSCO), each of which is described below. The results of simulations run with each of these crossover operators are discussed in the section, “Crossover Operator Simulation Results.” Those results show that the ASPX crossover operator provided very good performance, better than the UXSCO operator.

Aligned Single-Point Crossover (ASPX)

Recall that the main goal of our crossover operator is that it produces children strings which do not contain duplicate item numbers. This goal can be achieved with aligned single point crossover as follows: Two parent strings, such as those shown below, are chosen at random from the current population.

Next, since the order of the item numbers within a string is not important, a string can be rearranged without affecting its fitness value. Thus, the item numbers in string 2 are rearranged such that each item number that has a corresponding match in string 1 is aligned with that item number. In this example, the 10 and 20 in string 2 are matched in string 1 and would thus be aligned, as follows:

Now, since all matching item numbers are aligned between the two strings, basic single-point crossover can be performed and guarantees that no duplicates occur in either child string. For example, if a cross site is chosen at point A,

the following children strings will result and no duplicates will be present.

Unmatched Crossover with Single Child Offspring (UXSCO)

As with aligned single-point crossover, unmatched crossover with single child offspring operates with the main goal of producing children strings which do not contain duplicate item numbers. In unmatched crossover with single child offspring, this is achieved as follows: Again, two parent strings are chosen, at random, from the current population. Next, it is determined if there are any matching items between the two strings. As part of this determination, the item numbers that are matched between the two strings are saved. In addition, the item numbers in string 2 that do not match any items in string 1 are saved. Next, a random number, X, between one and the number of items that are unmatched is generated. If there are zero unmatched items (the parent strings are identical) then X will be zero and no crossover will take place. If there are greater than zero unmatched items (the parent strings are not identical), then X unmatched item numbers from parent 2 are copied to random locations in child 1. Following the copy of X items to child 1, child 2 will be equal to parent 2 (there is a single new offspring, child 1). The following example demonstrates the operation of unmatched crossover with single child offspring:

Assume the following two strings, which possess two matched items (10 and 20) and two unmatched items, were chosen:

Next, assume that choosing a random number between 1 and the number of unmatched items (two) results in X equal to two. Then, two unmatched items from string 2 (88 and 99) are copied to two random locations in string 1. Assuming the random locations are one and three, the following children strings will result:

By performing crossover in this manner, it is guaranteed that no duplicate item numbers will appear in a string.

Crossover Operator Support of Coding Scheme

Both the ASPX and UXSCO operators supported the choice of a decimal coding over a binary coding. Since the goal of crossover is to create strings with new item number combinations, there would be no advantage to allowing crossover to occur at sites other than between item number boundaries. Given this, there would be no advantage to having a string coded in binary form since no additional “useful” schemata would be processed. Using a binary coding, more schemata would be available for processing by the genetic algorithm, however, the additional available schemata would represent strings that are not possible solutions to the problem.

Mutation Operator

With the use of a base-10 coding as previously described, an alternate method of mutation was required. In a typical binary coding, mutation is simple in that if it is determined that mutation should take place, a 1 is mutated to a 0, and a 0 is mutated to a 1. In a base-10 coding, however, a method to mutate a decimal value between 0 and 99 must be determined. The following alternatives were considered:

  1) generate a random number between 0 and 99 (“random” mutation)
  2) generate a new number within some ±δ of the number being mutated (“window” mutation)

In an effort to determine if there was an advantage of one mutation operator over the other, each was examined through simulations and the results are discussed in the section, “Mutation Operator Simulation Results.” For the most part, each mutation operator performed equally well.

Previous | Table of Contents | Next

Copyright © CRC Press LLC