Computational Intelligence - August 2014 - 51

O (n 2)-scan of the solution can result in mulThe TSP Suite, including its source code, extensive
tiple improvements. With ranks 24.5 (seeded)
and 56 (not seeded), it outperformed all pure
documentation, example data, and example reports,
and seeded EC methods as well as most of
can be downloaded from http://www.logisticPlanning.
their hybrids.
org/tsp/.
Although ffa appears to be a slightly better
convergence prevention strategy for the hMA
Fourth, with the experiments we have shown that the
than fuss or rs, the hMA using neither of them can perform
TSP Suite is an efficient tool for answering both general and
even better. While the always seeded DEA was able to outperspecific research questions. This also validates the experimenform the non-seeded EA and TEHBSA variants, it was infetal procedure (which is not limited to TSPs). We confirmed
rior to a simple seeded HC. Edge Crossover is better than the
that local search can outperform pure global search methods
new Savings Crossover.
on the TSP, but that EC methods hybridized with local search
To sum up, the best local search (MNS) together with the
can be even better. PACO and the new MNS have been
best pure global search (PACO) produces the best hybrid
found to be the best global and local optimization algorithms
search. Pure PACO performs better than the pure EA. Their
in the tests, respectively.
hybridized versions with MNS show the same behavior. One
There are five major strands of future work, which will be
may thus assume that hybridization would have an almost addifollowed by the authors.
tive effect. However, this is not always true, since all tested
First, we are working to set up a centralized website that
hybrid algorithms are seeded and the (seeded) hEA is better
provides the TSP Suite and its documentation as well as all the
than the (seeded) hPACO.
generated benchmarking results for download. This site will
Based on the results presented, we hope that our experiallow other researchers to upload their results and maintain an
mental approach can lead to the development of better algoup-to-date list of the best TSP solvers.
rithms through identifying behaviors and trends of different
Second, the collection of algorithms in our TSP Suite is far
algorithms. Prior to these experiments using the TSP Suite,
from complete. We are currently implementing Branch and
some of us would expect an MA to be the best hybrid EC
Bound methods and Lin-Kernighan local search [48]. Compremethod for the TSP. The results, however, tell us that PACO is
hensive experiments with these two methods will be performed.
the method of choice.
Third, the experimentation approach described in Section
II-B will be extended to other well-known optimization tasks
V. Conclusions and Future Work
such as Knapsack or Set Covering problems. We plan to repeat
This paper has made four contributions to the research on
our initial analysis for viable time measures (Section II-A3) and
combinatorial optimization with metaheuristics in general and
then re-use existing code from the TSP Suite.
the TSP in particular.
Fourth, at present the TSP Suite can compare different
First, we proposed an experimentation procedure that
experiments, but it cannot automatically analyze what influences
allows for analyzing and comparing optimization algorithms
their parameters may have. For example, in Section IV-C, we had
from several different points of view. This procedure marks a
to manually conclude that Edge Crossover is better than our
step forward between the traditional experimental analysis and
new Savings Crossover. It would be more convenient if the
data mining applied to performance data from optimization
TSP Suite could automatically derive such conclusions (instead
processes. It is not limited to the TSP and may be useful in
of treating each algorithm setup as a different algorithm).
other domains as well.
Fifth, there are several limitations with the current version
Second, this experimentation procedure is realized in a genof the experimental procedure that need to be addressed, some
eral open source framework for the implementation, unit testof which are 1) The global ranking of algorithms depends
ing, experimentation, and analysis of TSP algorithms. The TSP
strongly on the mixture of statistics it is based on, so this mixSuite, including its source code, extensive documentation,
ture needs to be further discussed and analyzed; 2) The comexample data, and example reports, can be downloaded from
parison of the areas under performance curves is our first forhttp://www.logisticPlanning.org/tsp/. With the TSP Suite,
mal idea to compare dynamic behaviors, but probably not
experiments can be run in a parallel or distributed fashion and
statistically robust; 3) The best discovered solution must be preevaluation reports containing high-level, human-readable conserved by the TSP Suite in the log files, which entails performclusions can be produced.
ing an O (n) copy operation whenever the running algorithm
Third, the TSP Suite has been used to obtain a baseline set
of data generated from several local search methods as well as
registers an improvement. This may potentially skew the meamembers of the main EC algorithm families (EAs, MAs, ACO,
sured CPU times. Since a running algorithm can query the
EDAs) in pure, seeded, and hybridized versions. This allows
system for the best solution it has found so far, it is relieved
users of the TSP Suite to acquire data from algorithms that are
from making this copy itself, which may offset this expense; 4)
related and suitable for comparison purposes. All of these
Additionally, we are looking for better methods to mine the
implementations and collected data will be made available.
data gathered during the experimental runs.

august 2014 | IEEE ComputatIonal IntEllIgEnCE magazInE

http://www.logisticPlanning http://www.logisticPlanning.org/tsp/

Table of Contents for the Digital Edition of Computational Intelligence - August 2014