tspgen: TSP Instance Generation
This software package accompanies the following publication accepted at the FOGA2019 conference:
Bossek, J., Kerschke, P., Neumann, A., Wagner, M., Neumann, F., & Trautmann, H. (2019). Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators. In Proceedings of the 15th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV), Potsdam, Germany. (Accepted)
What is this all about?
Usually optimization algorithms are compared by running benchmarks on test problems. For the well-known Traveling-Salesperson-Problem (TSP) diverse benchmark sets exist ranging from instances placed purely at random in the Euclidean plane (so-called Random Uniform Euclidean, RUE), placed in cluster structures (see e.g., the related netgen R package) or stemming from real-world applications (e.g., TSPlib or VLSI instances).
In the past decade due to advances in machine learning the area of per-instance Algorithm Selection (AS) gained importance significantly. Here, the primary goal is to build a decision-rule that decides for a certain algorithm from a portfolio of algorithms which will most likely perform best on a given instance. Application of AS to the TSP problem is highly encouraging (see, e.g., ). The learning process of the decision rule usually relies on a set of (computationally cheap) characteristics of problem instances, termed instance features or simply features. Another aspect closely related to AS is the understanding of working principles of algorithms: which features / feature combinations are crucial to determine the performance of a given algorithm or a pair of algorithms? Which feature values or ranges of feature values of an instance at hand pose a hard challenge for an algorithm? Recent research approaches to answer this interesting question adopt evolutionary algorithms which evolve a population of instances which are particularly hard for a given algorithm with respect to approximation quality [2, 3] or maximizing the performance gap between two competitive solvers [4, 5]. However, the latter approaches stick to simple, straight forward mutation operators which results in instances with severe structural similarity and high visual similarity to RUE instances.
One drawback of the afore-mentioned evolutionary instance generation process is the simplicity of mutation operators. In a nutshell the process is as follows: place n points uniformly at random in the Euclidean plane [0,1]x[0,1] and iteratively move points around by adding Gaussian noise or replacing selected points with new points again placed uniformly at random. Obviously, such basic operations are not able to introduce significant structural diversity and even after thousands of iterations the instance will most likely be similar to the initial solution in particular if n is large.
This package introduces a set of sophisticated, problem tailored mutation operators which allow for the generation of more diverse sets of instances. The proposed mutation operators have a much higher impact on the points than the ones mentioned before. E.g., explosion mutation generates an explosion within the points cloud leaving a hole where not points are placed at all. In contrast cluster mutation selects a random subset of points and generates a circular cluster somewhere in the plane.
 Kerschke, P., Kotthoff, L., Bossek, J., Hoos, H. H., & Trautmann, H. (2018). Leveraging TSP Solver Complementarity through Machine Learning. Evolutionary Computation, 26(4), 597–620. https://doi.org/10.1162/evco_a_00215
 Mersmann, O., Bischl, B., Bossek, J., Trautmann, H., Wagner, M., & Neumann, F. (2012). Local search and the traveling salesman problem: A feature-based characterization of problem hardness. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7219 LNCS, 115–129. https://doi.org/10.1007/978-3-642-34413-8_9
 Mersmann, O., Bischl, B., Trautmann, H., Wagner, M., Bossek, J., & Neumann, F. (2013). A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem. Annals of Mathematics and Artificial Intelligence, 69(2), 151–182. https://doi.org/10.1007/s10472-013-9341-2
 Bossek, J., & Trautmann, H. (2016). Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers. In P. Festa, M. Sellmann, & J. Vanschoren (Eds.), Proceedings of the 10th International Conference on Learning and Intelligent Optimization (LION 2016) (Vol. 10079 LNCS, pp. 48–59). Ischia, Italy: Springer International Publishing. https://doi.org/10.1007/978-3-319-50349-3_4
 Bossek, J., & Trautmann, H. (2016). Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference. In G. Adorni, S. Cagnoni, M. Gori, & M. Maratea (Eds.), AI*IA 2016 Advances in Artificial Intelligence (Vol. 10037 LNAI, pp. 3–12). Genova, Italy: Springer International Publishing. https://doi.org/10.1007/978-3-319-49130-1_1
In order to generate an instance we (1) specify a collection of mutation operators and application probabilities and (2) start the generation process.
# add mutation operators one by one set.seed(1) collection = init() collection = addMutator(collection, "doExplosionMutation") collection = addMutator(collection, "doClusterMutation", pm = 0.2) collection = addMutator(collection, "doAxisProjectionMutation", pm = 0.3) collection = addMutator(collection, "doGridMutation", box.min = 0.3, box.max = 0.5) # define probabilities collection = setProbabilities(collection, probs = c(0.3, 0.2, 0.3, 0.2)) print(collection) # generate instance x = build(n = 1000L, iters = 100L, collection = collection, bound.handling = "uniform") print(autoplot(x))
Another R package with methods for the generation of Random Uniform Euclidean instances (RUE) and heavily clustered instances is netgen. A famous RUE instance generator is provided by the DIMACS challenge and termed portgen. Further R software with methods for graph generation (not TSP specific) are igraph and grapherator.
How to Contribute
Bug reports are welcome. Please use the official issue tracker to report bugs and ask questions. You may also fix the bug by yourself by (1) forking the project and (2) fixing the bug / adding a feature and (3) generating a pull requests. However, in order to avoid useless work we encourage you to contact the authors and discuss the desired feature request first.
The package will be available at CRAN soon. Install the release version via:
If you are interested in trying out and playing around with the current github developer version use the devtools package and type the following command in R:
Please address questions and missing features about the tspgen to the author Jakob Bossek firstname.lastname@example.org. Found some nasty bugs? Please use the issue tracker for this. Pay attention to explain the problem as good as possible. At its best you provide an example, so I can reproduce your problem quickly.