A. Duarte, S. Cavero, E. García Pardo
El 2D Bandwidth problem (2DBP) es un problema de optimización combinatoria que consiste en encontrar una asignación de los vértices de un grafo de entrada en los vértices de un grafo huésped tal que se optimice una función objetivo. El objetivo del 2DBP es minimizar la distancia en el grafo huésped entre cada par de vértices adyacentes del grafo de entrada. En este trabajo, se propone un algoritmo basado en la metaheurística Iterated Greedy que combina un constructivo voraz, una búsqueda local y una estrategia para la destrucción y reconstrucción parcial de una solución. El método de mejora incorpora tres estrategias avanzadas para evaluar la función objetivo, diferenciar soluciones con misma función objetivo y reducir el espacio de búsqueda. El algoritmo propuesto ha sido comparado con los métodos previos del estado del arte, resultando ser el algoritmo más competitivo tanto en tiempo como en calidad de la función objetivo.
Keywords: Graph Layout Problems, Bandwidth , Heurísticas, Metaheurísticas
Scheduled
GT09 Heuristics I. Heuristics and metaheuristics
June 8, 2022 4:00 PM
A04
