Optimizadores de clave aleatoria

Este minicurso presenta metaheurísticas independientes del problema utilizando el paradigma del optimizador de clave aleatoria (RKO). SA (recocido simulado), GRASP (procedimiento de búsqueda adaptativa aleatoria codicioso), VNS (búsqueda de vecindad variable), ILS (búsqueda local iterada) y PSO (optimización de enjambre de partículas) son metaheurísticas clásicas para la optimización combinatoria. Un optimizador de claves aleatorias (RKO) utiliza un vector de claves aleatorias para codificar una solución a un problema de optimización combinatoria. Utiliza un decodificador para evaluar una solución codificada por el vector de claves aleatorias.  Un RKO es una metaheurística en la que los puntos del hipercubo unitario se evalúan mediante un decodificador. Describimos RKO como un componente independiente del problema y un decodificador dependiente del problema. Como prueba de concepto, el RKO con diferentes metaheurísticas se prueba en cinco problemas de optimización combinatoria NP-hard: problema del vendedor viajero, problema de ubicación del árbol de cubos, problema de cobertura triple de Steiner, problema de partición de grafos capacitados por nodos y problema de secuenciación de trabajos y cambio de herramientas.