We use heuristics to obtain satisfactory solutions to optimization problems in a reasonable amount of time and computer memory. The section of code most critical in terms of time and memory consumption is the problem’s fitness function.
I will illustrate some tricks to write fast fitness functions in R with the travelling salesman problem (TSP) as an example. Given a matrix of distances between nodes, the solution of the TSP is the shortest cycle that visits each city exactly once. So the inputs of the fitness function of the TSP are, in principle:
- a distance matrix
Dof dimensionn. - a cyclic permutation
solof lenghtn, always starting with the same value.
The return of the function is the total distance of solwith the matrixD`.
TSP1 is a straightforward implementation of this fitness function:
TSP1 <- function(D, sol){
n <- length(sol)
d <- 0
for(i in 1:(n-1)) d <- d + D[sol[i],sol[i+1]]
d <- d + D[sol[n],sol[1]]
return(d)
} TSP1 has some room of improvement because of:
- the need to calculate the size of the instance each time we compute the fitness function making
n <- length(sol)and - looping (we are told to loop as little as possible in R).
We can remedy the first problem calculating n only once and using the function TSP2, which takes n as an input:
TSP2 <- function(D, n, sol){
d <- 0
for(i in 1:(n-1)) d <- d + D[sol[i],sol[i+1]]
d <- d + D[sol[n],sol[1]]
return(d)
}To avoid looping we can compute distances vectorially doing:
TSP3 <- function(D, sol) sum(D[cbind(sol, c(sol[-1], sol[1]))])An alternative possible approach can be:
- turn
Dinto a vectorv. - Subset the elements of
vthat belong to the cycle defined bysol. - Use the base R function
sumto add the subseted values.
Turn a matrix into a vector in R is straightforward using c():
M <- matrix(1:12, 3, 4, byrow = TRUE)
vM <- c(M)To subset values we just consider that:
M[i, j] == vM[i + n*(j-1)]Then we can write the vectorised fitness function TSP3 as:
TSP4 <- function(v, n, sol) sum(v[sol[c(1:(n-1), 1)] + (sol[c(2:n, n)] - 1)*n])Testing the Functions
To test the functions I will use a circle_TSP instance generator that spaces the nodes evenly on a circle:
circle_TSP <- function(n, r=10){
x <- r*cos( 2 * pi * 0:(n-1) / n)
y <- r*sin( 2* pi * 0:(n-1) / n)
df <- data.frame(x=x, y=y)
D <- as.matrix(dist(df, diag = TRUE, upper = TRUE))
return(list(coords = df, distances = D))
}Let’s pick an instance of size 30:
c30 <- circle_TSP(30)$distances
v_c30 <- c(c30)First, let’s see if the four functions return the same values. I will create a list of tests of 100 random solutions:
set.seed(1111)
tests <- replicate(100, c(1, sample(2:30, 29)), simplify = FALSE)Then I will apply each function to all elements of tests:
sol_TSP1 <- sapply(tests, \(x) TSP1(c30, x))
sol_TSP2 <- sapply(tests, \(x) TSP2(c30, 30, x))
sol_TSP3 <- sapply(tests, \(x) TSP3(c30, x))
sol_TSP4 <- sapply(tests, \(x) TSP4(v_c30, 30, x))Let’s see if the results are identical. We do that checking if all solutions are equal to the first one.
sapply(list(sol_TSP2, sol_TSP3, sol_TSP4), \(x) identical(sol_TSP1, x))## [1] TRUE FALSE FALSELooks that sol_TSP3 and sol_TSP4 return values different from sol_TSP1 and sol_TSP2. Let’s use all.equal() to account for floating comma operation errors, with a low enough tolerance:
sapply(list(sol_TSP2, sol_TSP3, sol_TSP4), \(x) all.equal(sol_TSP1, x, tolerance = 1e-10))## [1] TRUE TRUE TRUENow we confirm that the four functions return similar enough values, that can account for the value of the fitness function.
Comparing Functions’ Performance
Let’s evaluate the speed of the four functions over one thousand replications of the calculation of the fitness of elements of tests:
bench <- rbenchmark::benchmark(sapply(tests, \(x) TSP1(c30, x)),
sapply(tests, \(x) TSP2(c30, 30, x)),
sapply(tests, \(x) TSP3(c30, x)),
sapply(tests, \(x) TSP4(v_c30, 30, x)),
replications = 1000,
columns = c("test", "replications", "elapsed", "relative"),
order = "test",
relative = "elapsed")
bench## test replications elapsed relative
## 1 sapply(tests, function(x) TSP1(c30, x)) 1000 2.263 5.479
## 2 sapply(tests, function(x) TSP2(c30, 30, x)) 1000 2.235 5.412
## 3 sapply(tests, function(x) TSP3(c30, x)) 1000 0.498 1.206
## 4 sapply(tests, function(x) TSP4(v_c30, 30, x)) 1000 0.413 1.000We observe that the fastest function is TSP4 and that the highest gain of speed comes from moving from TSP2 to TSP3.
The bigger gain in speed of functions TSP3 and TSP4 comes from avoiding looping. TSP3 is the simplest and most elegant optimization, although the vectorised formulation TSP4 has an edge in speed.
Session Info
## R version 4.5.3 (2026-03-11)
## Platform: x86_64-pc-linux-gnu
## Running under: Linux Mint 21.1
##
## Matrix products: default
## BLAS: /usr/lib/x86_64-linux-gnu/blas/libblas.so.3.10.0
## LAPACK: /usr/lib/x86_64-linux-gnu/lapack/liblapack.so.3.10.0 LAPACK version 3.10.0
##
## locale:
## [1] LC_CTYPE=es_ES.UTF-8 LC_NUMERIC=C
## [3] LC_TIME=es_ES.UTF-8 LC_COLLATE=es_ES.UTF-8
## [5] LC_MONETARY=es_ES.UTF-8 LC_MESSAGES=es_ES.UTF-8
## [7] LC_PAPER=es_ES.UTF-8 LC_NAME=C
## [9] LC_ADDRESS=C LC_TELEPHONE=C
## [11] LC_MEASUREMENT=es_ES.UTF-8 LC_IDENTIFICATION=C
##
## time zone: Europe/Madrid
## tzcode source: system (glibc)
##
## attached base packages:
## [1] stats graphics grDevices utils datasets methods base
##
## loaded via a namespace (and not attached):
## [1] digest_0.6.37 R6_2.6.1 bookdown_0.43 fastmap_1.2.0
## [5] xfun_0.52 blogdown_1.21 cachem_1.1.0 knitr_1.50
## [9] htmltools_0.5.8.1 rmarkdown_2.29 lifecycle_1.0.4 cli_3.6.4
## [13] sass_0.4.10 jquerylib_0.1.4 compiler_4.5.3 rstudioapi_0.17.1
## [17] tools_4.5.3 evaluate_1.0.3 bslib_0.9.0 yaml_2.3.10
## [21] jsonlite_2.0.0 rlang_1.1.6 rbenchmark_1.0.0Updated on 2026-04-15.