Algoritmo metaheurístico basado en el enfoque MOS para resolver el problema 0-1 de la mochila cuadrática en instancias de alta dimensionalidad

Abstract

El problema de la mochila cuadrática (QKP) es una generalización del clásico pro-blema de la mochila (KP), su diferencia radica en que ahora los elementos a ingresar en la mochila tienen aparte de su beneficio propio un beneficio asociado a los demás elementos a ingresar en la mochila, y su propósito es encontrar la mejor combinación posible con el fin de maximizar la función objetivo sujeto a una restricción de capa-cidad. Este problema de optimización combinatoria tiene complejidad NP-Hard y en los últimos años se han intensificado las investigaciones debido la gran cantidad de aplicaciones que puede tener como son: el trafico global entre estaciones satelitales, la localización de aeropuertos, terminales o estaciones de ferrocarril, el diseño de compiladores, la gestión de redes VLCI, el problema del clique, entre otros. En este proyecto de investigación se diseñó, implementó y evaluó un algoritmo hibrido que combina las adaptaciones de los algoritmos SGVNS [1] y GRASPr [2] bajo un gestor de técnicas denominado MOS para resolver el problema 0-1 QKP. La primera técni-ca, SGVNS, cuenta con un algoritmo de búsqueda local VND con dos vecindarios, un componente de sacudida para escapar de estancamientos en el espacio de soluciones y se incorpora una fase de construcción tipo GRASP para añadir una funcionalidad de inicio múltiple, que es precedida por otra fase de construcción por peso para la exploración de diferentes espacios de soluciones. La segunda técnica denominada GRASPr cuenta también con una fase de pre-construcción por peso, construcción por densidad con una lista reducida de candidatos (RCL), la búsqueda local de selección de estructura de vecindad aleatoria, moviendo la fase de actualización de la solución con que contaba el algoritmo original a MOS, el cual actualiza la solución al final de cada iteración y sirve como coordinador de la participación de las metaheuristicas como técnicas subordinadas a las cuales se les provee una participación dinámica de acuerdo a su desempeño en cada iteración, competencia que inicia equitativamente. El algoritmo metaheuristico MOS fue probado en 80 instancias de prueba para (1000 y 2000 elementos) y fue comparado con el estado del arte IHEA y GRASP+Tabu, y se reportan los resultados y un análisis comparativo de estos.