RESULTS AND ANALYSIS

We applied the IGA to eight (8) different TSPs (eil51, eil76, ch150, bier127, a280, d657, lin318, vm1084) from the TSPLIB [Reinelt, 1996] that span a wide range of sizes. These TSPs have been used by others and are considered benchmarks with optimal or best known tour lengths available. We follow the steps outlined in section 2 for each problem and compare our results with an identical GA running on the complete problem. For every problem, we ensure that both the IGA and the GA complete the same number of evaluations. For the IGA the number of evaluations is given by

$$\mbox{evaluations} = P \times IGA_g \times IGA_p$$

where P is the number of clusters, IGA_g is the number of generations run, and IGA_p is the populations size (identical for each cluster). Since we tried to decompose the problem into equal sized clusters, we used the same population size across all clusters on a particular TSP instance. The number of evaluations for the GA on the complete TSP is $GA_g \times GA_p$ and

$$P \times IGA_g \times IGA_p = GA_g \times GA_p$$

for all problems. We ran all problems on the same unloaded ULTRA5 Sun workstations. The GA code used by the IGA was the same as the code run on complete problems.

 

Table: Results from the IGA and the GA for different size TSPs

		IGA		GA
No. of	No. of	1 run		10 runs
Cities	Sets	Time	% Over	Time	% over
		(min)	optimal	(min)	optimal
51	2	0.25	0.7	0.96	7.0
76	2	0.60	5.9	2.95	13.0
127	2	2.70	11.7	16	13.1
150	5	2.70	9.1	26.4	13.1
280	7	6.16	12.2	145.9	22.0
318	7	5.45	14.2	181.6	33.9
657	12	11.55	32.2	296.2	44.0
1084	12	40.1	26.0	684.5	72.0

 

Table 1 compares the performance of the IGA with the GA. Column one shows the size of the problem, the next three columns deal with the IGA and the last two columns provide results from the GA. Column two lists the number of clusters used. Since we found that the GA is able to competently solve TSPs with less than one hundred cities, we chose a number of clusters that would result in subproblems with less than one hundred cities. Column three shows the time in minutes from the start of interaction until obtaining a complete tour with the IGA. The difference in time is more than clear at the wristwatch level of resolution. Column four lists the quality of solution in percentage over optimal. The last two columns provide time in minutes and the quality of solution obtained by the GA.

If N is the number of cities, we let small TSPs be categorized as those with $N \leq 100$, medium TSPs are those with $(100 < N \leq 200)$ and large TSPs have N > 200. From the table, we can see that the IGA easily outperforms the GA on large problems.