Greedy Randomized Adaptative Search – Cristian Chiquito Valencia

Taxonomía

El Procedimiento de Greedy Randomized Adaptative Search es un algoritmo Metaheurístico y de Optimización Global, originalmente propuesto para los practicantes de la Investigación de Operaciones. La aplicación iterativa de una técnica de Local Search incrustada relaciona el enfoque con Iterated Local Search y las técnicas de Multi-Start.

Estrategia

El objetivo del Greedy Randomized Adaptative Search es muestrear repetidamente soluciones codiciosas y, a continuación, utilizar un procedimiento de Local Search para refinarlas hasta alcanzar un óptimo local. La estrategia del procedimiento se centra en el mecanismo de construcción por pasos estocásticos y codiciosos que restringe la selección y el orden de inclusión de los componentes de una solución en función del valor que se espera que aporten.

Procedimiento

Se presenta un pseudocódigo del Greedy Randomized Adaptative Search para minimizar una función de costo.

Pseudocódigo Greedy Randomized Adaptative Search

Además, el pseudocódigo de la función de construcción aleatoria codiciosa. La función consiste en la construcción paso a paso de una solución candidata utilizando un proceso de construcción estocástico. La función trabaja construyendo una Lista Restringida de Candidatos (RCL por sus siglas en inglés) que restringe los componentes de una solución (características) que pueden seleccionarse en cada ciclo. La RCL puede limitarse mediante un tamaño explícito o utilizando un umbral \((⍺ ∈ [0,1])\) en el costo de añadir cada característica a la solución candidata actual.

Heurística

El umbral \(⍺\) define el grado de avaricia del mecanismo de construcción, donde valores cercanos a 0 pueden ser demasiado codiciosos, y valores cercanos a 1 pueden ser demasiado generalizados.

Como alternativa al uso del umbral \(⍺\), el RCL se puede puede limitarse al top \(n%\) de las características candidatas que pueden seleccionarse en cada ciclo de construcción.

La técnica se diseñó para clases de problemas discretos, como los problemas de optimización combinatoria.

Código

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

La construcción estocástica y codiciosa por pasos de un recorrido implica la evaluación de las ciudades candidatas por el costo que aportan por ser la siguiente ciudad del recorrido. El algoritmo utiliza un procedimiento estocástico 2-opt para Local Search con un número fijo de iteraciones no mejoradas como como condición de parada.

# 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(perm, cities) {
    distance <- 0
    for (i in seq_along(perm)) {
        c1 <- perm[i]
        c2 <- if (i == length(perm)) perm[1] else perm[i + 1]
        distance <- distance + euc_2d(cities[c1, ], cities[c2, ])
    }
    return(distance)
}

# 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) {
        temp <- c1
        c1 <- c2
        c2 <- temp
    }
    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 construir una solución codiciosa aleatorizada
construct_randomized_greedy_solution <- function(cities, alpha) {
    candidate <- list()
    candidate$vector <- sample(1:nrow(cities), 1)
    allCities <- 1:nrow(cities)
    while (length(candidate$vector) < nrow(cities)) {
        candidates <- setdiff(allCities, candidate$vector)
        costs <- sapply(candidates, function(i) euc_2d(cities[candidate$vector[length(candidate$vector)], ], cities[i, ]))
        rcl <- candidates[which(costs <= min(costs) + alpha * (max(costs) - min(costs)))]
        candidate$vector <- c(candidate$vector, sample(rcl, 1))
    }
    candidate$cost <- cost(candidate$vector, cities)
    return(candidate)
}

# Función de búsqueda principal
search <- function(cities, max_iter, max_no_improv, alpha) {
    best <- NULL
    cost_progress <- list()  # Lista para registrar el progreso del costo
    for (iter in seq_len(max_iter)) {
        candidate <- construct_randomized_greedy_solution(cities, alpha)
        candidate <- local_search(candidate, cities, max_no_improv)
        if (is.null(best) || candidate$cost < best$cost) {
            best <- candidate
        }
        cost_progress[[iter]] <- best$cost  # Registrar el costo en la lista
        cat(" > iteration", iter, ", best=", best$cost, "\n")
    }
    return(list(best = best, cost_progress = cost_progress))  # Devolver la mejor solución y el progreso del costo
}

# 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_iter <- 50
max_no_improv <- 50
greediness_factor <- 0.3

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

 > iteration 1 , best= 11976 
 > iteration 2 , best= 11434 
 > iteration 3 , best= 9936 
 > iteration 4 , best= 9936 
 > iteration 5 , best= 9936 
 > iteration 6 , best= 9461 
 > iteration 7 , best= 9461 
 > iteration 8 , best= 9461 
 > iteration 9 , best= 9461 
 > iteration 10 , best= 9461 
 > iteration 11 , best= 9461 
 > iteration 12 , best= 9461 
 > iteration 13 , best= 9461 
 > iteration 14 , best= 9461 
 > iteration 15 , best= 9461 
 > iteration 16 , best= 9461 
 > iteration 17 , best= 9461 
 > iteration 18 , best= 9461 
 > iteration 19 , best= 9461 
 > iteration 20 , best= 9461 
 > iteration 21 , best= 9461 
 > iteration 22 , best= 9461 
 > iteration 23 , best= 9461 
 > iteration 24 , best= 9461 
 > iteration 25 , best= 9461 
 > iteration 26 , best= 9461 
 > iteration 27 , best= 9461 
 > iteration 28 , best= 9461 
 > iteration 29 , best= 9461 
 > iteration 30 , best= 9461 
 > iteration 31 , best= 9461 
 > iteration 32 , best= 9461 
 > iteration 33 , best= 9461 
 > iteration 34 , best= 9461 
 > iteration 35 , best= 9461 
 > iteration 36 , best= 9461 
 > iteration 37 , best= 9461 
 > iteration 38 , best= 9461 
 > iteration 39 , best= 9461 
 > iteration 40 , best= 9461 
 > iteration 41 , best= 9461 
 > iteration 42 , best= 9461 
 > iteration 43 , best= 9461 
 > iteration 44 , best= 9461 
 > iteration 45 , best= 9461 
 > iteration 46 , best= 9461 
 > iteration 47 , best= 9461 
 > iteration 48 , best= 9461 
 > iteration 49 , best= 9461 
 > iteration 50 , best= 9461

best <- result$best
cost_progress <- result$cost_progress

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

library(ggplot2)

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)
        )
}

df <- data.frame(iteration = 1:max_iter, cost = unlist(cost_progress))
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()

Cómo citar

BibTeX

@online{chiquito_valencia2023,
  author = {Chiquito Valencia, Cristian},
  title = {Greedy {Randomized} {Adaptative} {Search}},
  date = {2023-12-08},
  url = {https://cchiquitovalencia.github.io/posts/2023-12-08-greedy_randomized_adaptative_search/},
  langid = {en}
}

Por favor, cita este trabajo como:

Chiquito Valencia, Cristian. 2023. “Greedy Randomized Adaptative Search.” December 8, 2023. https://cchiquitovalencia.github.io/posts/2023-12-08-greedy_randomized_adaptative_search/.