Tres heurísticas basadas en inteligencia de partículas adaptadas al problema de asignación generalizada

Abstract

El presente trabajo desarrolla la adaptación de tres técnicas heurísticas pertenecientes a la rama de las metaheurísticas denominada inteligencia de partículas (IP) para su adaptación al problema de asignación generalizada (PAG). Las heurísticas adaptadas al problema de asignación generalizada son las siguientes: Algoritmo de luciérnagas (AL); Búsqueda Gravitacional (ABG) Método de composición musical (MCM) Se propone una codificación para representar una solución, que permita visualizar de una manera fácil las características de la misma. A diferencia de los algoritmos originales que comienzan con soluciones aleatorias, aquí se plantea una estrategia para generar soluciones de buena calidad aprovechando las características del problema lo cual genera una adaptación en los métodos antes mencionados, ya que se agregan dos parámetros los cuales permitirán generar soluciones por tres estrategias diferentes los cuales serán representados de la siguiente manera: Pg (% soluciones realizadas por un algoritmo glotón) y Pa (% de soluciones realizadas de manera aleatoria ) el restante de la población será generada por una relajación del problema con fijación de variables y generación aleatoria. Para la estrategia AL se realizaron las siguientes adaptaciones: la función objetivo no solo es representada por el valor del individuo, sino que en base a su aptitud a través de las reglas de manejo de restricciones de Coello 2002 [14]. La distancia entre dos individuos no es determinada solamente por la distancia euclidiana, sino que también contempla la distancia de Hamming la cual permite encontrar soluciones de buena calidad; se generaron seis versiones del algoritmo de luciérnagas las cuales se basan en 4 vecindarios diferentes. Para la estrategia ABG se realizaron las siguientes adaptaciones: la masa de inercia es calculada por las reglas de manejo de restricciones de Coello 2002 la cual genera una función de pesos; la función de distancia propuesta contempla al igual que en el AL la distancia euclidiana y la distancia de Hamming, para este algoritmo tanto la mejor como la peor solución el movimiento lo realiza con una búsqueda local; para el resto de las soluciones el movimiento lo realiza con base a las características de la estrategia orinal. Para la estrategia MCM se realizaron las siguientes adaptaciones: la función objetivo utiliza las reglas de manejo de restricciones de Coello 2002 para determinar la aptitud de la solución; la función de distancia propuesta contempla al igual que en las estrategias AL y ABG la distancia euclidiana y la distancia de Hamming. Se tomaron instancias de prueba utilizadas en Chu y Beasley 1997[13], las cuales se encuentran disponibles en Or-Library. Se realizó una calibración de parámetros para las estrategias adaptadas al PAG con la estrategia de búsqueda armónica (BA) para cien mil llamadas a la función objetivo. Se llevó a cabo una serie de experimentos y una comparación con base en algunas de las estrategias del estado del arte del problema. Los resultados obtenidos permiten afirmar que se obtienen soluciones de buena calidad.