| Title: | Instance Feature Calculation and Evolutionary Instance Generation for the Traveling Salesman Problem |
|---|---|
| Description: | Instance feature calculation and evolutionary instance generation for the traveling salesman problem. Also contains code to "morph" two TSP instances into each other. And the possibility to conveniently run a couple of solvers on TSP instances. |
| Authors: | Bernd Bischl <[email protected]>, Jakob Bossek <[email protected]>, Olaf Mersmann <[email protected]> |
| Maintainer: | Bernd Bischl <[email protected]> |
| License: | BSD_3_clause + file LICENSE |
| Version: | 1.2 |
| Built: | 2025-02-01 03:26:52 UTC |
| Source: | https://github.com/berndbischl/tspmeta |
Convert to TSP instance object of package TSP.
as_TSP(x)as_TSP(x)
x |
[ |
[TSP].
Plot TSP instance.
## S3 method for class 'tsp_instance' autoplot(object, opt_tour, ...)## S3 method for class 'tsp_instance' autoplot(object, opt_tour, ...)
object |
[ |
opt_tour |
[ |
... |
[any] |
[ggplot].
Return the center of all cities of a TSP instance.
center_of_mass(instance)center_of_mass(instance)
instance |
[ |
[numeric(2)] Center of all cities of the TSP instance.
Runs 2-Opt local search on TSP instance.
fast_two_opt(x, initial_tour)fast_two_opt(x, initial_tour)
x |
[ |
initial_tour |
[ |
[TOUR]
TOUR object from package TSP, containing order of cities, tour length and
method name that generated this solution.
Statistics of the distribution of the angle between a node and its 2 next neighbors.
feature_angle(x)feature_angle(x)
x |
[ |
[list].
Determines the ratio of cities which lie within a certain distance to the bounding box.
feature_bounding_box(x, distance_fraction = 0.1)feature_bounding_box(x, distance_fraction = 0.1)
x |
[ |
distance_fraction |
[ |
[list].
Includes the coordinates of the mean coordinates of the the point cloud and the statistics of the distances of all cities from it.
feature_centroid(x)feature_centroid(x)
x |
[ |
[list].
Determines the area of the convex hull and the ratio of the cities which lie on the convex hull in the euklidean space.
feature_chull(x)feature_chull(x)
x |
[ |
[list].
Determines the number of clusters and the mean distances from all cities in a cluster to its centroid.
feature_cluster(x, epsilon)feature_cluster(x, epsilon)
x |
[ |
epsilon |
[ |
[list].
Computes different statistics describing the distribution of pairwise distances between cities.
feature_distance(x)feature_distance(x)
x |
[ |
[list]
List of statistics describing the distribution of distances.
Includes the number of modes of the edge cost distribution.
feature_modes(x)feature_modes(x)
x |
[ |
[list]
List containing (estimated) number of modes.
Construct minimun spanning tree, then calculate the statistics of a) the distances in the MST, b) the depths of all nodes in the MST.
feature_mst(x)feature_mst(x)
x |
[ |
[list].
Statistics describing the distribution of distances of each city to its nearest neighbor.
feature_nnds(x)feature_nnds(x)
x |
[ |
[list].
Calculates list of all TSP features for an instance.
features(x, rescale = TRUE)features(x, rescale = TRUE)
x |
[ |
rescale |
[ |
[list].
feature_angle,
feature_centroid,
feature_cluster,
feature_bounding_box,
feature_chull,
feature_distance,
feature_modes,
feature_mst,
feature_nnds
x = random_instance(10) print(features(x))x = random_instance(10) print(features(x))
Returns integrated solver names.
get_solvers()get_solvers()
[character].
Pairs of cities are matched in a greedy fashion for morphing, first the closest pair w.r.t. euclidean distance, then the clostest pair of the remaining cities, and so on.
greedy_point_matching(x, y)greedy_point_matching(x, y)
x |
[ |
y |
[ |
[matrix]
Numeric matrix of point indices with shortest distance.
Get instance dimensionality (space where coords live).
instance_dim(x)instance_dim(x)
x |
[ |
[integer(1)].
Pairs of cities are matched in a greedy fashion, see greedy_point_matching.
morph_instances(x, y, alpha)morph_instances(x, y, alpha)
x |
|
y |
|
alpha |
[ |
[tsp_instance]
Morphed TSP instance.
x = random_instance(10) y = random_instance(10) z = morph_instances(x, y, 0.5) autoplot(x) autoplot(y) autoplot(z)x = random_instance(10) y = random_instance(10) z = morph_instances(x, y, 0.5) autoplot(x) autoplot(y) autoplot(z)
Calculate rotation angle such that the main axis through the cities is aligned with the X axis.
normalization_angle(instance)normalization_angle(instance)
instance |
[ |
[numeric(1)]
Normalization is performed by aligning the main axis of the cities with the X axis.
normalize_rotation(instance)normalize_rotation(instance)
instance |
[ |
A rotated tsp_instance.
Get number of cities in tsp instance.
number_of_cities(x)number_of_cities(x)
x |
[ |
[integer(1)].
E.g. computes features from distribution of distances. Computed statistics: min, median, mean, max, sd, span, coeff_of_var.
numvec_feature_statistics(x, name, na.rm = TRUE)numvec_feature_statistics(x, name, na.rm = TRUE)
x |
[ |
name |
[ |
na.rm |
[ |
[list]
Elements are named <name_statistic>.
Print TSP instance
## S3 method for class 'tsp_instance' print(x, ...)## S3 method for class 'tsp_instance' print(x, ...)
x |
[ |
... |
[any] |
Generates a random TSP instance by scattering random points in a hypercube.
random_instance(size, d = 2, lower = 0, upper = 1)random_instance(size, d = 2, lower = 0, upper = 1)
size |
[ |
d |
[ |
lower |
[ |
upper |
[ |
[tsp_instance].
The current state of the parser does not understand all variants of the TSPLIB format. Much effort has been spent making the parser as robust as possible. It will stop as soon as it sees input it cannot handle.
read_tsplib_instance(path)read_tsplib_instance(path)
path |
[ |
[tsp_instance].
Read in multiple TSPLIB style Traveling Salesman Problems from a directory.
read_tsplib_instances(path, pattern = "*.tsp", max_size = 1000, use_names = TRUE, on_no_coords = "stop")read_tsplib_instances(path, pattern = "*.tsp", max_size = 1000, use_names = TRUE, on_no_coords = "stop")
path |
[ |
pattern |
[ |
max_size |
[ |
use_names |
[ |
on_no_coords |
[ |
A list List of tsp_instance objects.
Read in a TSPLIB style Traveling Salesman Problem tour from a file
read_tsplib_tour(path)read_tsplib_tour(path)
path |
[ |
[TOUR]
TOUR object from package TSP, containing order of cities, tour length and
method name that generated this solution.
Remove any duplicate cities in a tsp instance.
remove_zero_distances(instance)remove_zero_distances(instance)
instance |
[ |
New TSP instance in which all duplicate cities have been removed.
Rescale coords of TSP instance to .
rescale_instance(x) rescale_coords(coords)rescale_instance(x) rescale_coords(coords)
x |
[ |
coords |
[ |
[matrix] for rescale_coords and tsp_instance for rescale_instance.
Numeric matrix of scaled city coordinates.
Rotate a matrix of 2D coordinates
rotate_coordinates(coords, angle, center)rotate_coordinates(coords, angle, center)
coords |
[ |
angle |
[ |
center |
[ |
A matrix of rotated coordinates.
Rotate the cities of a TSP instance around a point.
rotate_instance(instance, angle, center)rotate_instance(instance, angle, center)
instance |
[ |
angle |
[ |
center |
[ |
[tsp_instance] New TSP instance.
Currently the following solvers are supported:
nearest_insertion: See solve_TSP.
farthest_insertion : See solve_TSP.
cheapest_insertion : See solve_TSP.
arbitrary_insertion: See solve_TSP.
nn: See solve_TSP.
repetitive_nn: See solve_TSP.
concorde: See solve_TSP.
run_solver(x, method, ...)run_solver(x, method, ...)
x |
[ |
method |
[ |
... |
[any] |
[TOUR]
TOUR object from package TSP, containing order of cities, tour length and
method name that generated this solution.
x = random_instance(10) tours = sapply(c("nn", "cheapest_insertion", "arbitrary_insertion"), function(solver) { list(solver = run_solver(x, method = solver)) }) ## Not run: concorde_path(path = "/absolute/path/to/concorde/executable") concorde_tour = run_solver(x, method = "concorde") concorde_tour = run_solver(x, method = "linkern") ## End(Not run)x = random_instance(10) tours = sapply(c("nn", "cheapest_insertion", "arbitrary_insertion"), function(solver) { list(solver = run_solver(x, method = solver)) }) ## Not run: concorde_path(path = "/absolute/path/to/concorde/executable") concorde_tour = run_solver(x, method = "concorde") concorde_tour = run_solver(x, method = "linkern") ## End(Not run)
TSP generating EA.
tsp_generation_ea(fitness_function, pop_size = 30L, inst_size = 50L, generations = 100L, time_limit = 30L, uniform_mutation_rate, normal_mutation_rate, normal_mutation_sd, cells_round = 100L, rnd = TRUE, ...)tsp_generation_ea(fitness_function, pop_size = 30L, inst_size = 50L, generations = 100L, time_limit = 30L, uniform_mutation_rate, normal_mutation_rate, normal_mutation_sd, cells_round = 100L, rnd = TRUE, ...)
fitness_function |
[ |
pop_size |
[ |
inst_size |
[ |
generations |
[ |
time_limit |
[ |
uniform_mutation_rate |
[ |
normal_mutation_rate |
[ |
normal_mutation_sd |
[ |
cells_round |
[ |
rnd |
[ |
... |
[any] |
[list]
List containing best individual form the last population, its
fitness value, the genrational fitness and the last population.
Default is 50.
Generates a TSP instance S3 object either from city coordinates.
tsp_instance(coords, dists)tsp_instance(coords, dists)
coords |
[ |
dists |
[ |
[tsp_instance].