Búsqueda de vecindad variable para el problema de la minimización del número de errores en ordenaciones líneales

Resumen

El problema de la minimizaci´on del n´umero de errores en ordenaciones lineales se define como un problema sobre un grafo con signos, donde las aristas est´an etiquetadas con signos positivos y negativos. De manera general, el objetivo del problema consiste en encontrar una ordenaci´on lineal, que sit´ue a cada v´ertice lo m´as cerca posible de sus v´ertices adyacentes con conexiones positivas y lo m´as lejos posible de sus v´ertices adyacentes con conexiones negativas. Espec´ıficamente, la funci´on objetivo tratar´a de minimizar el n´umero de conexiones negativas situadas antes que una conexi´on positiva. En este trabajo, se propone un algoritmo basado en la metodolog´ıa B´usqueda de Vecindad Variable, particularmente en la variante B´asica, para abordar el problema. El algoritmo propuesto ha sido comparado sobre diversos conjuntos de instancias y resulta competitivo con m´etodos previos en el estado del arte.

Abraham Duarte

Catedrático de Universidad

Mi carrera investigadora se ha centrado en el desarrollo de nuevos algoritmos y técnicas de Inteligencia Computacional (metaheurísticas) y su aplicación a diferentes problemas en Ciencia e Ingeniería desde que me incorporé a la Universidad Rey Juan Carlos (URJC) en el octubre del año 2000.