Discrete/Binary Approach - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 156

on overall average. In other words, it indicates that the DDE algorithm has a tendency of
yielding consistent solutions across a wide variety of problem instances. To highlight
its consistency more, the range between the best and worst case was only 0.02% on
overall average, thus indicating a very robust algorithm.

6.4.2 Computation Time

Table 6.19 also gives necessary information about CPU time requirement for each of the
problem instances. The DDE algorithm is very fast in terms of CPU time requirement
due to the mean CPU time of less than 12 seconds for all instances. In addition, its
maximum CPU time was no more than 18 seconds for all instances. The DDE algorithm
was able to find its best solution in the first 4.03 generations on overall average and
spent most of the time waiting for the termination condition. It took 2.11 generations
at minimum and only 8.22 generations at maximum on overall average to find its best
solution for each problem instance. Since the local search heuristics are applied to each
problem instance at each generation, most of the running times have been devoted to
the local search improvement heuristics, which indicates the impact of the them on the
solution quality. It implies the fact that with some better local search heuristics such
as Renaud and Boctor's G2-opt or G3-opt, as well as with some speed-up methods for
2-opt heuristic, its CPU time performance may be further improved.

6.4.3 Comparison to Other Algorithms

We compare the DDE algorithm to two genetic algorithms, namely, RKGA by Sny-
der & Daskin [30] and mrOXGA by Silberholz & Golden [29], where RKGA is
re-implemented under the same machine environment. Table 6.20 summarizes the so-
lution quality in terms of relative percent deviations from the optimal values and CPU
time requirements for all three algorithms. Note that our machine has a similar speed
as Silberholz & Golden [29]. A two-sided paired t -test which compares the results on
Table 6.20 with a null hypothesis that the algorithms were identical generated p-values
of 0.175 and 0.016 for DDE vs. mrOXGA and DDE vs. RKGA,respectively, suggesting
near-identical results between DDE and mrOXGA. On the other hand, the paired t -test
confirms that the differences between DDE and RKGA were significant on the behalf of
DDE subject to the fact that DDE was computationally less expensive than both RKGA
and mrOXGA since p -values were 0.001 for DDE vs. mrOXGA and 0.008 for DDE vs.
RKGA.
In addition to above, Silberholz & Golden [29] provided larger problem instances
ranging from 493 (99) to 1084 (217) nodes (clusters) where no optimal solutions are
available. However, they provided the results of mrOXGA and RKGA. We compare the
DDE results to those presented in Silberholz & Golden [29]. As seen in Table 6.21, DDE
generated consistently better results than both RKGA and mrOXGA in terms of both
solution quality and CPU time requirement even if the larger instances are considered.
In particular, 8 out 9 larger instances are further improved by the DDE algorithm. The
paired t -test on the objective function values on Table 6.21 confirms that the differences
between DDE and RKGA were significant since p -value was 0.033 (null hypothesis
is rejected), whereas DDE was equivalent to mrOXGA since p -value was 0.237. In