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
51
http://www.logisticPlanning
http://www.logisticPlanning.org/tsp/
Table of Contents for the Digital Edition of Computational Intelligence - August 2014
Computational Intelligence - August 2014 - Cover1
Computational Intelligence - August 2014 - Cover2
Computational Intelligence - August 2014 - 1
Computational Intelligence - August 2014 - 2
Computational Intelligence - August 2014 - 3
Computational Intelligence - August 2014 - 4
Computational Intelligence - August 2014 - 5
Computational Intelligence - August 2014 - 6
Computational Intelligence - August 2014 - 7
Computational Intelligence - August 2014 - 8
Computational Intelligence - August 2014 - 9
Computational Intelligence - August 2014 - 10
Computational Intelligence - August 2014 - 11
Computational Intelligence - August 2014 - 12
Computational Intelligence - August 2014 - 13
Computational Intelligence - August 2014 - 14
Computational Intelligence - August 2014 - 15
Computational Intelligence - August 2014 - 16
Computational Intelligence - August 2014 - 17
Computational Intelligence - August 2014 - 18
Computational Intelligence - August 2014 - 19
Computational Intelligence - August 2014 - 20
Computational Intelligence - August 2014 - 21
Computational Intelligence - August 2014 - 22
Computational Intelligence - August 2014 - 23
Computational Intelligence - August 2014 - 24
Computational Intelligence - August 2014 - 25
Computational Intelligence - August 2014 - 26
Computational Intelligence - August 2014 - 27
Computational Intelligence - August 2014 - 28
Computational Intelligence - August 2014 - 29
Computational Intelligence - August 2014 - 30
Computational Intelligence - August 2014 - 31
Computational Intelligence - August 2014 - 32
Computational Intelligence - August 2014 - 33
Computational Intelligence - August 2014 - 34
Computational Intelligence - August 2014 - 35
Computational Intelligence - August 2014 - 36
Computational Intelligence - August 2014 - 37
Computational Intelligence - August 2014 - 38
Computational Intelligence - August 2014 - 39
Computational Intelligence - August 2014 - 40
Computational Intelligence - August 2014 - 41
Computational Intelligence - August 2014 - 42
Computational Intelligence - August 2014 - 43
Computational Intelligence - August 2014 - 44
Computational Intelligence - August 2014 - 45
Computational Intelligence - August 2014 - 46
Computational Intelligence - August 2014 - 47
Computational Intelligence - August 2014 - 48
Computational Intelligence - August 2014 - 49
Computational Intelligence - August 2014 - 50
Computational Intelligence - August 2014 - 51
Computational Intelligence - August 2014 - 52
Computational Intelligence - August 2014 - 53
Computational Intelligence - August 2014 - 54
Computational Intelligence - August 2014 - 55
Computational Intelligence - August 2014 - 56
Computational Intelligence - August 2014 - 57
Computational Intelligence - August 2014 - 58
Computational Intelligence - August 2014 - 59
Computational Intelligence - August 2014 - 60
Computational Intelligence - August 2014 - 61
Computational Intelligence - August 2014 - 62
Computational Intelligence - August 2014 - 63
Computational Intelligence - August 2014 - 64
Computational Intelligence - August 2014 - 65
Computational Intelligence - August 2014 - 66
Computational Intelligence - August 2014 - 67
Computational Intelligence - August 2014 - 68
Computational Intelligence - August 2014 - 69
Computational Intelligence - August 2014 - 70
Computational Intelligence - August 2014 - 71
Computational Intelligence - August 2014 - 72
Computational Intelligence - August 2014 - 73
Computational Intelligence - August 2014 - 74
Computational Intelligence - August 2014 - 75
Computational Intelligence - August 2014 - 76
Computational Intelligence - August 2014 - 77
Computational Intelligence - August 2014 - 78
Computational Intelligence - August 2014 - 79
Computational Intelligence - August 2014 - 80
Computational Intelligence - August 2014 - 81
Computational Intelligence - August 2014 - 82
Computational Intelligence - August 2014 - 83
Computational Intelligence - August 2014 - 84
Computational Intelligence - August 2014 - 85
Computational Intelligence - August 2014 - 86
Computational Intelligence - August 2014 - 87
Computational Intelligence - August 2014 - 88
Computational Intelligence - August 2014 - Cover3
Computational Intelligence - August 2014 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202311
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202308
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202305
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202302
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202211
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202208
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202205
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202202
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202111
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202108
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202105
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202102
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202011
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202008
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202005
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202002
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201911
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201908
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201905
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201902
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201811
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201808
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201805
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201802
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter12
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall12
https://www.nxtbookmedia.com