Results and Analysis

Results

  
Table 3: Average distance from optimal for all problems

Table 3 shows the average performance across different sized problems for running the NRGA with different degrees of similarity. Column one shows the modified problem, while column two and three show the percentage distance of the first and the last generation tour length from the optimal tour length. From this table, we can see that after injecting individuals and running GAs with previous information, we can always get better results than when running GAs with random initialization on our problems. We provide details on each modified problem below:

1. Same problem (same): We do not change the problem letting be the original problem and solve the original problem twice. Figure 1 shows the optimal solution, the average performance from running the RGA 10 times and the average performance from running the NRGA 10 times for the 76 cities TSP. As expected, injecting solutions from the same problem can help NRGAs get better performance especially in early generations.

     
   Figure 1: Performance on 76 cities problem with injection from solutions to the same problem
   

2. Change one city (diff1): We slightly change the original problem by randomly selecting one city and changing its location by randomly changing its x and y coordinates by to . Note that the problem size remains the same. Now, since and the original problem are different, the performance during early generations is not as good as the performance when injecting solutions from the same problem but the performance is still better than with random initialization.
3. Change two cities (diff2): We randomly select two cities and change their locations by randomly changing their x and y coordinates by to . The performance graph (not shown here) indicates that the performance is still better than that of an RGA. When changing two cities instead of changing one, the two problems are less similar which leads to the difference in performance between diff1 and diff2. During earlier generations, the performance of diff1 is always better than that of diff2. However, during later generations, this is not always true and diff2 actually results in better performance on some of our benchmarks.
4. Add one city (add1): To modify the original problem, we not only change the location of cities, we also change the size of the problems. We do this by adding or deleting one city. When adding one city, we generate a new city and let its coordinates be (randomly) between the maximal and minimal coordinates of all cities. We run the RGA to solve the modified problem and save the best individuals. For each of these individuals, we delete the added city so the changed individuals are legal tours for the original problem. Then we inject these changed individuals to solve the original problem. The average performance graphs show that adding one city can help GAs get performance similar to that obtained when injecting solutions from the same problem.
5. Delete one city (del1): We also randomly delete one city, run GAs to solve the modified problem and save the best individuals. For each one of these individuals, we randomly select one site and insert the deleted city, so that the changed individuals become legal tours for the original problem. We then inject these new individuals to solve the original problem. Because we randomly insert the deleted city, the performance during the first few generations is not as good as when injecting solutions from other similar problems but the performance is better than an RGA.

Analysis

As Table  3 shows, after injecting solutions of previous similar problems, the performance is always better than running the GA with random initialization. This may imply that injecting individuals from previous solved similar problems is a good way to help the GA get better results for TSPs. This may also mean that if most cities of the two TSPs are the same, we can use solutions from one TSP to solve the other one.

Short, highly fit subsets of strings (building blocks) play an important role in the action of genetic algorithms because they combine to form better strings  [3]. We believe edges are the building blocks for traveling salesman problems. After we inject individuals containing good edges from similar problems, the NRGA can combine these good edges and get good performance quickly.

Our results show that injecting individuals from the same problem and the add1 problem can help the NRGA get better performance than when injecting individuals from other problems. In these two cases, we use information from all cities and the length of each edge is still the same. This implies that problems can be similar enough to be useful even if they are of different size. In other words, different sized problem with information from all cities and all edges can help the NRGA get better performance than a same sized problem with some different edges.