IEEE Computational Intelligence Magazine - August 2023 - 23

and IV-E), and NCO solvers suffered from far more severe
performance degradation.
B. Exp_1: Small-Size Testing Instances With the Same
Problem Characteristics as Training Instances
The testing results ofExp_1 in terms of average optimum gap
(Gap), standard deviation (std), total computation time, and
energy are reported in Table III. In Exp_1, for DACT with
the instance augmentation mechanism (denoted by aug.), its
results on the rue-100 and clu-100 testing instances are missing
because it ran for prohibitively long periods of time to solve
these instances. Besides, the tuned variant of LKH, i.e., LKH
(tuned), was not included in Exp_1 because the original LKH
has already achieved nearly optimal solution quality. In addition,
the medians and variance of the optimum gaps across all
the testing instances are visualized by box plots in Figure 2.
For brevity, the name ofthe NCO approach is used to denote
the solvers learned by it.
The first observation from these results is that traditional
solvers still achieved much better solution quality than the
learned solvers. For example, EAX and MAOS could notably
solve all the testing instances to optimality. Among all
the randomized solvers, i.e., DACT, NeuroLKH, LKH,
EAX, and MAOS, EAX and MAOS also exhibited the best
stability. They achieved the smallest standard deviation over
10 repeated runs.
The second observation is that, after EAX and MAOS,
NeuroLKH was the third best-performing solver. Compared to
LKH, NeuroLKH reduced the average optimum gap by one
order ofmagnitude on three out ofthe four testing sets. Based
on Figure 2, one can also observe that NeuroLKH achieved
more stable performance than LKH across the testing instances.
Compared to the other two NCO solvers POMO and DACT,
the performance advantages ofNeuroLKH in terms ofsolution
quality were much more significant. In general, NeuroLKH
could reduce the average optimum gaps by at least two orders
ofmagnitude on all four testing sets. Although the performance
of POMO and DACT could be improved when equipped
with the instance augmentation mechanism, they still performed
worse than NeuroLKH.
The third observation is that NCO solvers could generally
achieve better solution quality on the rue instances than on the
clu instances. For example, the average optimum gap achieved
by POMO on the clu-50 testing instances was 14.18% greater
than that obtained on the rue-50 testing instances, and the corresponding
numbers for DACT and NeuroLKH were 9.60
times and 33.33%, respectively. Moreover, as the problem size
grows, such performance gaps became larger. These results
show that current NCO approaches are less adept at learning
solvers for structural problem instances (i.e., clustered TSP
instances) than for uniformly and randomly generated instances,
indicating that the learning models adopted by them may have
limitations in handling structural data. This could be an important
direction for improving NCO approaches.
The fourth observation is that in Figure 2, as the problem
size grows, the performance of POMO and DACT significantly
deteriorated, while the performance ofNeuroLKH was
still stable. These results indicate that currently the scalability
ofLCH approaches and LIH approaches is still quite limited.
The last observation is that regarding efficiency, POMO
exhibited excellent performance in terms of both runtime and
energy. Notably, it usually consumed at most one-tenth ofthe
resources consumed by other solvers, which could be very useful
in resource-limited environments. This is also true when
EAX and LKH were terminated at the solution quality
achieved by POMO solver (marked by LKH and EAX in
FIGURE 2 Visual comparison in box plots of the optimum gaps achieved by the tested solvers in Exp_1.
FIGURE 3 Visual comparison in box plots of the optimum gaps achieved by the tested solvers in Exp_2.
AUGUST 2023 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE 23

IEEE Computational Intelligence Magazine - August 2023

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - August 2023