Iterated Local serach – Cristian Chiquito Valencia

Taxonomía

Iterated Local Search es una Metaheurística y una técnica de Optimización Global. Es una extensión de Multi-Restar Search y puede considerarse la base de muchos enfoques de búsqueda en dos fases, como el procedimiento de Greedy Randomized Adaptive Search Procedure y Variable Neighborhood Search.

Estrategia

El objetivo de Iterated Local Search es mejorar la Multi-Restar Search mediante el muestreo en la vecindad más amplia de soluciones candidatas y el uso de una técnica de Local Search para reﬁnar las soluciones a sus óptimos locales. Iterated Local Search explora una secuencia de soluciones creadas como perturbaciones de la mejor solución actual, cuyo resultado se reﬁna mediante una heurística integrada.

Procedimiento

Heurística

Iterated Local Search se diseñó para, y se ha aplicado, predominantemente a dominios discretos, como los problemas de optimización combinatoria.

La perturbación de la mejor solución actual debe estar en un vecindario más allá del alcance de la heurística incorporada y no debe deshacerse fácilmente.

Las perturbaciones demasiado pequeñas hacen que el algoritmo sea demasiado codicioso, mientras que las perturbaciones demasiado grandes hacen que el algoritmo sea demasiado estocástico.

La heurística incrustada suele ser una técnica de búsqueda local específica del problema.

El punto de partida de la búsqueda puede ser una solución candidata construida aleatoriamente o mediante una heurística específica del problema (como el vecino más próximo).

Las perturbaciones pueden hacerse de forma determinista, aunque las más comunes son las estocásticas y probabilísticas (adaptativas basadas en el historial).

El procedimiento puede almacenar tanto o tan poco historial como sea necesario para utilizarlo durante la perturbación y los criterios de aceptación. La ausencia de historial representa un paseo aleatorio en un vecindario más amplio de la mejor solución y es la aplicación más común del enfoque.

El criterio de aceptación más simple y común es una mejora en el costo de las soluciones candidatas construidas.

Código

El algoritmo se aplica a la instancia Berlin52 del Traveling Saleman Problem (TSP), tomada de la TSPLIB. El problema busca una permutación del orden de visita de las ciudades (llamada recorrido) que minimice la distancia total recorrida. La distancia óptima del recorrido para el caso Berlín52 es de 7.542 unidades.

Iterated Local Search se ejecuta durante un número fijo de iteraciones. La implementación se basa en un algoritmo común conﬁguración para el TSP, donde un 'double-bridge move' (4-opt) se utiliza como la técnica de perturbación, y un 2-opt estocástico se utiliza como la heurística de búsqueda local incrustada. El doube-bridge move consiste en dividir una permutación en 4 partes (a,b,c,d) y volver a unirlas en un orden específico y desordenado (a,d,c,b).

# Función para calcular la distancia euclidiana entre dos puntos
euc_2d <- function(c1, c2) {
    return(round(sqrt((c1[1] - c2[1])^2 + (c1[2] - c2[2])^2)))
}

# Función para calcular el costo de una permutación de ciudades
cost <- function(permutation, cities) {
    distance <- 0
    for (i in seq_along(permutation)) {
        c1 <- permutation[i]
        c2 <- if (i == length(permutation)) permutation[1] else permutation[i + 1]
        distance <- distance + euc_2d(cities[c1, ], cities[c2, ])
    }
    return(distance)
}

# Función para generar una permutación aleatoria de las ciudades
random_permutation <- function(cities) {
    return(sample(nrow(cities)))
}

# Función para realizar una operación de dos-opt estocástica en una permutación
stochastic_two_opt <- function(permutation) {
    perm <- permutation
    c1 <- sample(length(perm), 1)
    exclude <- c(c1, if (c1 == 1) length(perm) else c1 - 1, if (c1 == length(perm)) 1 else c1 + 1)
    c2 <- sample(length(perm), 1)
    while (c2 %in% exclude) {
        c2 <- sample(length(perm), 1)
    }
    if (c2 < c1) {
        c1 <- c2
        c2 <- c1
    }
    perm[c1:c2] <- rev(perm[c1:c2])
    return(perm)
}

# Función para realizar una búsqueda local en el espacio de las permutaciones
local_search <- function(best, cities, max_no_improv) {
    count <- 0
    repeat {
        candidate <- list()
        candidate$vector <- stochastic_two_opt(best$vector)
        candidate$cost <- cost(candidate$vector, cities)
        if (candidate$cost < best$cost) {
            count <- 0
            best <- candidate
        } else {
            count <- count + 1
        }
        if (count >= max_no_improv) break
    }
    return(best)
}

# Función para realizar un movimiento de doble puente en una permutación
double_bridge_move <- function(perm) {
    pos1 <- 1 + sample(floor(length(perm) / 4), 1)
    pos2 <- pos1 + 1 + sample(floor(length(perm) / 4), 1)
    pos3 <- pos2 + 1 + sample(floor(length(perm) / 4), 1)
    return(c(perm[1:pos1], perm[(pos3 + 1):length(perm)], perm[(pos2 + 1):pos3], perm[(pos1 + 1):pos2]))
}

# Función para perturbar la mejor solución encontrada hasta ahora
perturbation <- function(cities, best) {
    candidate <- list()
    candidate$vector <- double_bridge_move(best$vector)
    candidate$cost <- cost(candidate$vector, cities)
    return(candidate)
}

# Función de búsqueda principal
search <- function(cities, max_iterations, max_no_improv) {
    best <- list()
    best$vector <- random_permutation(cities)
    best$cost <- cost(best$vector, cities)
    best <- local_search(best, cities, max_no_improv)
    # Creamos un vector para almacenar el costo del mejor vector en cada iteración
    best_costs <- numeric(max_iterations)
    for (iter in seq_len(max_iterations)) {
        candidate <- perturbation(cities, best)
        candidate <- local_search(candidate, cities, max_no_improv)
        if (candidate$cost < best$cost) {
            best <- candidate
        }
        # Almacenamos el costo del mejor vector en la iteración actual
        best_costs[iter] <- best$cost
        #print(paste(" > iteration", iter, ", best=", best$cost))
    }
    return(list(best = best, best_costs = best_costs))
}

# Configuración del problema
berlin52 <- matrix(c(565,575,25,185,345,750,945,685,845,655,
                     880,660,25,230,525,1000,580,1175,650,1130,
                     1605,620,1220,580,1465,200,1530,5,845,680,
                     725,370,145,665,415,635,510,875,560,365,300,
                     465,520,585,480,415,835,625,975,580,1215,245,
                     1320,315,1250,400,660,180,410,250,420,555,575,
                     665,1150,1160,700,580,685,595,685,610,770,610,
                     795,645,720,635,760,650,475,960,95,260,875,920,
                     700,500,555,815,830,485,1170,65,830,610,605,625,
                     595,360,1340,725,1740,245), ncol = 2, byrow = TRUE)

# Configuración del algoritmo
max_iterations <- 100
max_no_improv <- 50

# Ejecutar el algoritmo
result <- search(berlin52, max_iterations, max_no_improv)

Revisamemos el comportamiento del algoritmo para encontrar la solución óptima:

# Crear un gráfico del progreso de la función objetivo
library(ggplot2)

df <- data.frame(iteration = 1:max_iterations, cost = result$best_costs)

# Crear modificaciones al plot
crear_tema <- function() {
    theme_minimal() +
        theme(
            plot.background = element_rect(fill = "white", color = NA), 
            panel.grid.major = element_line(color = "white", size = 0.2), 
            panel.grid.minor = element_line(color = "white", size = 0.2), 
            panel.background = element_rect(fill = "white", color = NA), 
            plot.title = element_text(face = "bold", size = 14, color = "#4d6080"),
            axis.title = element_text(face = "bold", size = 12, color = "#4d6080"),
            axis.text = element_text(size = 10, color = "#4d6080"),
            axis.line = element_line(size = 1.5, colour = "#de6f41"), 
            legend.background = element_rect(fill = "#4d6080", color = NA), 
            legend.key = element_rect(fill = "grey90", color = NA),
            axis.ticks.x = element_line(color = "#de6f41", size = 1),
            axis.ticks.y = element_line(color = "#de6f41", size = 1)
        )
}


ggplot(df, aes(x = iteration, y = cost)) +
    geom_line() +
    labs(title = "Progreso del costo a lo largo de las iteraciones", x = "Iteración", y = "Costo")+
    crear_tema()

La solución óptima (con las iteraciones establecidas) es entonces:

result$best$vector

 [1] 48 47 26 13 52 14 27 28 12 11 51 43 33  9 10 41  8 45 25 46  5 24  6  4 15
[26] 19  3 31 23 21  7  2 17 42 30 20 50 29 16 44 37 38 49 35 34 40 39 36 32 18
[51] 22  1

Cómo citar

BibTeX

@online{chiquito_valencia2023,
  author = {Chiquito Valencia, Cristian},
  title = {Iterated {Local} Serach},
  date = {2023-11-18},
  url = {https://cchiquitovalencia.github.io/posts/2023-11-18-iterated_local_search/},
  langid = {en}
}

Por favor, cita este trabajo como:

Chiquito Valencia, Cristian. 2023. “Iterated Local Serach.” November 18, 2023. https://cchiquitovalencia.github.io/posts/2023-11-18-iterated_local_search/.