Majalah Ilmiah UNIKOM

Vol.8, No. 1

9

H a l a m a n

DATA SETS

TSP225

PCB442

GR666

PR1002

Total generations needed

72

68

88

120

Best solution found by us

4159.67

56923

3470.81

294945

Known optimum

3854

50783

3952.54

259067

Quality of our solution

92.65%

89.21%

113.88%

87.84%

Table 3. Overall Performance of Our Problem

DATA SETS

Quality of our solution

TSP225

PCB442

PR1002

Minimum

91.51%

90.02%

85.79%

Maximum

94.00%

90.84%

87.84%

Average

92.60%

90.49%

86.72%

Deviation

0.012776

0.004241

0.010334

Table 4. Stability Analysis of Our Algorithm

AG

SA

GA

Time computation (milliseconds)

1921.9

296.9

1468.8

Memory usage (kilo bytes)

13.88

10.67

31.11

Table 5. Profile Comparison

results showed that AG improves the dis-

tance 2.25% over SA and 3.09% over GA.

But for the larger sets of data, GA improves

the distance 3.19% over SA and 4.66% over

GA. For the first small sets of data, our algo-

rithm can find all optimal solutions in less

than aminute. For the other larger sets of

data, we can reach reasonably good quality

solutions.

Next, we test the algorithm for 4 large sets

of data : TSP225 (225 city), PCB442 (442

city), GR666 (666 city) and PR1002 (1002

city). We tested 10 runs (using different

seeds) on each of the 3 sets of data. The

best results from each data are summarized

in Table 3. The first rows in Table 3 show the

computation effort, and the next 3 rows

show how good the solution is. The equation

quality

optimum solution/best solution

found) x 100%

centage the solution exceeds the optimal

solution. Figure 7 and Figure 8 show the

example problem and our solution for

TSP225 and PR1002.

Another important measure is the stability

of the algorithm. The Table 4 shows the sta-

bility analysis of our algorithm. The results

are taken from 10 random runs for each set

of data. Each column corresponds to one

data instance and gives the best quality, the

worst quality, the average quality, and the

standard deviation. The results show that

our algorithm is very stable. The standard

deviations are relative small, so we can ex-

pect to achieve average performance easily.

But computation type of AG is more

complex than SA and GA algorithm, so for