Methodology

A genetic algorithm uses little knowledge to search large problem spaces. During the course of a search, a genetic algorithm extracts and uses information about the space, however, this information is usually discarded at the end of a GA's run. Past work [Louis 93] shows that previous information, if properly used, helps GAs to get better performance. We use non-random initialization of the initial population to provide GAs with useful previously learned information.

A traditional GA randomly initializes the population (RGA). We use the following four steps to run GAs with non-random initialization (NRGA) and compare the performance of an RGA versus an NRGA.

Step1: Modify the original problem into .

Step2: Run the RGA to solve .

a) Randomly initialize the population.

b) Run the GA 10 times with 10 different random seeds.

c) Save the best individuals from generation 5, 10, 20, 40, 80, 160, 320 and the last generation for each run of the GA (except for the 52 cities TSP, where we save the best individuals from generation 1, 5, 10, 20, 40, 80, 160, and 300).

Step3: Run the GA to solve the original problem.

a) Inject 8 chosen individuals from the saved solutions to into the initial population of the GA solving the original problem.

b) Run the GA 10 times with 10 random seeds.

Step4: Compare the average performance over 10 runs.

For all the problems, we use the same crossover and mutation probabilities of 0.85 and 0.05 respectively but use different population sizes and various number of generations for different problems. Table  4 shows the population sizes and the number of generations we use.

We used standard TSP benchmarks whose optimal solutions (or the current best solutions) are known  [Reinelt 96]. To implement step 1 of our methodology we modified each of these benchmarks in several different ways as shown in Table  4. For each modified problem, we run the RGA 10 times with 10 different random seeds and save the individuals identified in step 2c of our methodology. Running the GA 10 times means that we will have 10 saved individuals for generation 5, 10 saved individuals for generation 10 and so on. We randomly select one of the ten saved individuals for generation 5, one of the ten saved individuals for generation 10 and so on and inject these eight chosen individuals into the initial population of the GA being used to solve the original problem.

  
Table 1: Population and generation size for different problems

  
Table 2: Different ways of modifying TSPs