Simulation Graph Legends

For each of the simulation graphs results that are shown in the following sections, the following legend applies, representing the average fitness, best fitness and the solution for each run:

Fitness Function Simulation Results

Three different fitness functions (F1, F2, and F3), as described previously in the section, “Fitness function,” were investigated. The results of each fitness function simulation are discussed below.

F1 Fitness Function Simulations

Each F1 fitness function simulation was run with the crossover, mutation, and genetic algorithm parameters as noted in the simulation test matrix.

Simulation 1 was run with database configuration 1, which is a database consisting of 100 transactions and an embedded relationship between items 11, 22, 33, 44. Of the 100 transactions, 51 contained all four of the items. As can been seen from Figure 9.2, the item combination of interest entered the population in less than fifteen generations, and the entire population average temporarily converged on the solution around generation 160.

Figure 9.2  Simulation 1 results

Simulation 2 was run with database configuration 2, which is a database consisting of 100 transactions and an embedded relationship between items 11, 22, 33, 44. Of the 100 transactions, 11 contained all four of the items. Thus, this database represented more of a challenge to the genetic algorithm than that of database configuration 1 since there were fewer occurrences of the four item combination. As can be seen from Figure 9.3, the simulation prematurely converged on an incorrect solution and did not locate the item combination of interest.

Figure 9.3  Simulation 2 results

Simulation 3 was run with database configuration 3, which is a database consisting of 500 transactions and two embedded relationships; the first between items 11, 22, 33, 44 and the second between items 55, 66, 77, and 88. Of the 500 transactions, 290 contained all four of the items 11, 22, 33, and 44, and 85 contained all four of the items 55, 66, 77, and 88. Thus, this database, while it has many of the first item combination occurrences to guide the simulation, there are also many of the second item combination occurrences to provide a “distraction” to the genetic algorithm. As can be seen from Figure 9.4, the optimum solution (item combination 11, 22, 33, 44) was not located. The simulation, instead, prematurely converged on a solution consisting of members from each of the embedded item combinations (11, 33, 44, 88).

Figure 9.4  Simulation 3 results

F1 Fitness Function Simulation Conclusions

Simulation 1, the easiest of the database configurations, converged on the correct solution but only temporarily. Simulations 2 and 3, on the other hand, prematurely converged on an incorrect solution. Therefore, in an effort to resolve this premature convergence, a second fitness function (F2) involving fitness scaling was implemented and is discussed in the next section.

F2 Fitness Function Simulations

Each F2 fitness function simulation was run with the crossover, mutation, and genetic algorithm parameters as noted in the simulation test matrix.

Simulation 4 was run with database configuration 1 (previously described). As can be seen from Figure 9.5, the simulation average increased much more gradually than in the corresponding unscaled simulation (simulation 1) which suggests that the scaling mechanism was preventing premature convergence, as intended. The item combination of interest entered the population around generation 110 but the simulation did not completely converge on the solution.

Figure 9.5  Simulation 4 results

Simulation 5 was run with database configuration 2 (previously described). As can be seen from Figure 9.6, the simulation average did not converge as quickly as it had in the corresponding unscaled simulation (simulation 2) which suggests that the scaling was operating, as intended, to a certain degree. However, the simulation prematurely converged on an incorrect solution.

Figure 9.6  Simulation 5 results

Simulation 6 was run with database configuration 3 (previously described). As can be seen from Figure 9.7, the item combination of interest never entered the population and the average fitness remained fairly constant throughout the simulation.

Figure 9.7  Simulation 6 results

F2 Fitness Function Simulation Conclusions

None of the F2 fitness function simulations performed better than the corresponding F1 (unscaled) simulations. Thus, the fitness scaling mechanism did not improve simulation results as anticipated.

F3 Fitness Function Simulations

Each F3 fitness function simulation was run with the crossover, mutation, and genetic algorithm parameters as noted in the simulation test matrix.

Simulation 7 was run with database configuration 1 (previously described). As can be seen from Figure 9.8, the item combination of interest entered the population around generation 7 and the simulation quickly converged on the solution around generation 17.

Figure 9.8  Simulation 7 results

Simulation 8 was run with database configuration 2 (previously described). As can be seen from Figure 9.9, the item combination of interest entered the population around generation 5 and the simulation quickly converged on the solution around generation 20.

Figure 9.9  Simulation 8 results

Simulation 9 was run with database configuration 3 (previously described). As can be seen from Figure 9.10, the item combination of interest entered the population around generation 15. While the population did not completely converge on the solution, there were a majority of solution strings within the population such that I would consider the solution to have been determined.

Figure 9.10  Simulation 9 results