As Table 5.1 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.
When using the GA to solve TSPs, the location of a city in a string is not important. For example, for the 3 cities TSP, (1 2 0) and (0 1 2) mean the same tour. However, pairs of cities, that is edges, are now important. We believe the reason we can always get good performance during early generations after injecting individuals and running NRGAs with previous information is that those injected individuals contain good edges from similar problems.
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 [Goldberg 89]. We believe edges are the building blocks of the traveling salesman problems. After we inject individuals from the modified similar problems, which contain good edges for the original problem, the NRGA can combine these good edges and get good performance quickly. This may explain why running GAs with previous information can get better performance than running GAs with random initialization.
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. This is expected because in the first two cases, we use information from all cities and the length of each edge is still the same. This implies that a 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.