newTSP: Generate a TSP problem environment

In xegaSelectGene: Selection of Genes and Gene Representation Independent Functions

Generate a TSP problem environment

Description

newTSP() generates the problem environment for a traveling salesman problem (TSP).

Usage

newTSP(D, Name, Cities = NA, Solution = NA, Path = NA)

Arguments

D	A n x n distance matrix.
Name	The name of the problem environment.
Cities	The names of the cities.
Solution	Solution of problem (if known). Default: NA
Path	Optimal permutation of cities (if known). As integer vector. Default: NA.

Details

newTSP() provides several local permutation improvement heuristics: a greedy path of length k starting from city i, the best greedy path of length k, a random 2-Opt-move, and a sequence of random 2-Opt moves. They help to find bounds for the TSP or to implement special purpose mutation operators.

Value

A problem environment for the TSP.

1. $name() a string with the name of the environment

2. $cities() a vector length n of city names.

3. $dist() the n x n distance matrix between n cities.

4. $genelength() the size of the permutation n. E.g. for a TSP: the number of cities.

5. $f(permutation, gene, lF, tour=TRUE) the fitness function of the TSP. If tour==FALSE, the path length is computed (without the cost from city n to city 1).

   With a permutation of size n as argument.

6. $show(p) shows tour through the cities in path p with its cost.

7. $greedy(startPosition, k) computes a k-step greedy minimal cost path beginning at the city start. For k+1=n the greedy solution gives an upper bound for the TSP.

8. $kBestGreedy(k, tour=TRUE) computes the best greedy subtour with k+1 cities. For tour=FALSE, the best greedy subpath with k+1 cities is computed.

9. $rnd2Opt(permutation, maxTries=5) returns a permutation improved by a single random 2-Opt-move after at most maxTries=5 attempts.

10. $LinKernighan(permutation, maxTries=5, show=FALSE) returns the best permutation found after several random 2-Opt-moves with at most maxTries=5 attempts. The loop stops after the first 2-Opt-move which does not improve the solution.

11. $solution() known optimal solution.

12. $path() known optimal round trip.

13. $max() FALSE.

14. $globalOptimum() a named list with the following elements:

    • $param the optimal permutation.

    • $value the known optimal solution.

    • $is.minimum TRUE.

See Also

Other Problem Environments: DeJongF4Factory(), DelayedPFactory(), Parabola2DEarlyFactory(), Parabola2DErrFactory(), Parabola2DFactory(), envXOR, lau15, newEnvXOR()

Examples

a<-matrix(0, nrow=15, ncol=15)
a[1,]<- c(0, 29, 82, 46, 68, 52, 72, 42, 51,  55,  29,  74,  23,  72,  46)
a[2,]<- c(29,  0, 55, 46, 42, 43, 43, 23, 23,  31,  41,  51,  11,  52,  21)
a[3,]<- c(82, 55,  0, 68, 46, 55, 23, 43, 41,  29,  79,  21,  64,  31,  51)
a[4,]<-c(46, 46, 68,  0, 82, 15, 72, 31, 62,  42,  21,  51,  51,  43,  64)
a[5,]<-c(68, 42, 46, 82,  0, 74, 23, 52, 21,  46,  82,  58,  46,  65,  23)
a[6,]<-c(52, 43, 55, 15, 74,  0, 61, 23, 55,  31,  33,  37,  51,  29,  59)
a[7,]<-c(72, 43, 23, 72, 23, 61,  0, 42, 23,  31,  77,  37,  51,  46,  33)
a[8,]<-c(42, 23, 43, 31, 52, 23, 42,  0, 33,  15,  37,  33,  33,  31,  37)
a[9,]<-c(51, 23, 41, 62, 21, 55, 23, 33,  0,  29,  62,  46,  29,  51,  11)
a[10,]<-c(55, 31, 29, 42, 46, 31, 31, 15, 29,  0,  51,  21,  41,  23,  37)
a[11,]<-c(29, 41, 79, 21, 82, 33, 77, 37, 62,  51,   0,  65,  42,  59,  61)
a[12,]<-c(74, 51, 21, 51, 58, 37, 37, 33, 46,  21,  65,   0,  61,  11,  55)
a[13,]<-c(23, 11, 64, 51, 46, 51, 51, 33, 29,  41,  42,  61,   0,  62,  23)
a[14,]<-c(72, 52, 31, 43, 65, 29, 46, 31, 51,  23,  59,  11,  62,   0,  59)
a[15,]<-c(46, 21, 51, 64, 23, 59, 33, 37, 11,  37,  61,  55,  23,  59,   0)
lau15<-newTSP(a, Name="lau15")
lau15$name()
lau15$genelength()
b<-sample(1:15, 15, FALSE)
lau15$f(b)
lau15$f(b, tour=TRUE)
lau15$show(b)
lau15$greedy(1, 14)
lau15$greedy(1, 1)

xegaSelectGene documentation built on April 16, 2025, 5:12 p.m.