Tecnologías Específicas

Computación

Descripcion y Objetivos

La agregación de rankings es un problema fundamental en áreas como la teoría de la decisión, la economía, y la ciencia de datos. En muchos casos, los rankings no son estrictos y pueden contener empates, dando lugar a los rankings conocidos como bucket orders. Uno de los enfoques más estudiados en la agregación de rankings con empates es el Optimal Bucket Order Problem (OBOP), que busca encontrar un ranking (bucket order) de consenso que minimice la distancia a los rankings originales de los individuos. Sin embargo, en poblaciones heterogéneas, un único ranking de consenso puede no ser representativo, ya que existen subgrupos dentro de la población con preferencias diferentes. Para abordar esta situación, surge una extensión del OBOP, denominada Optimal Set Bucket Order Problem (OSBOP).

En OSBOP, el objetivo no es solo encontrar un único ranking de consenso, sino identificar múltiples rankings representativos (con empates) que describan diferentes subgrupos dentro de la población, junto con un peso asociado a cada ranking, que refleje la importancia relativa de cada subgrupo. Debido a la complejidad del problema, se requiere el uso de técnicas avanzadas de optimización como algoritmos metaheurísticos para encontrar soluciones aproximadas.

 

Objetivos

1. Definir formalmente el problema OSBOP, identificando las relaciones entre los rankings individuales, los buckets, y los subgrupos dentro de la población.
2. Diseñar algoritmos metaheurísticos (como Algoritmos Genéticos, Búsqueda local, PSO, etc.) para encontrar soluciones aproximadas al problema OSBOP, determinando los rankings (bucket orders) de consenso y su peso asociado a cada ranking que refleje la proporción de la población a la que pertenece.
3. Evaluar el rendimiento de los algoritmos metaheurísticos en diferentes escenarios, considerando tanto la calidad de las soluciones como la eficiencia computacional.
4. Desarrollar un framework experimental que permita la simulación y análisis del OSBOP en conjuntos de datos generados o reales.

Escribir la memoria del TFG documentando el desarrollo del proyecto, los resultados obtenidos y las conclusiones.

 

Metodología y Competencias

Metodología

1. Análisis del Problema OSBOP:
   • Definir formalmente el problema de agregación de rankings con empates y su extensión a OSBOP, donde el resultado no es un único ranking de consenso, sino varios rankings con su peso asociado.
   • Estudiar la métrica de distancia adecuada para generalizar la métrica de OSBOP a un conjunto de rankings con pesos.
   • Obtención de la matriz de precedencia a partir de conjuntos (poblaciones) de rankings con y sin empates.
2. Diseño de Algoritmos Metaheurísticos:
   • Implementar diferentes algoritmos metaheurísticos, como Algoritmos Genéticos, búsqueda local, algoritmos de enjambre, adaptados para optimizar tanto los rankings de consenso como los pesos asociados a cada bucket order.
   • Explorar operadores específicos para el problema, como cruces o mutaciones diseñadas para rankings, y técnicas de clustering para identificar los subgrupos de rankings.
3. Implementación del Algoritmo:
   • Desarrollar una implementación eficiente en un lenguaje como Python, desde cero o utilizando librerías especializadas en optimización (por ejemplo, DEAP o Pymoo para algoritmos evolutivos).
   • Introducir restricciones y criterios de convergencia para asegurar que el algoritmo encuentre múltiples rankings de consenso representativos y asigne de manera adecuada los pesos.
4. Evaluación del Rendimiento:
   • Aplicar los algoritmos a conjuntos de datos sintéticos y reales, midiendo tanto la calidad de los rankings de consenso obtenidos como el tiempo de ejecución.
   • Realizar experimentos con diferentes parámetros, como el número de rankings y subgrupos, para estudiar el comportamiento del algoritmo en situaciones de alta complejidad.
5. Desarrollo de un Framework Experimental:
   • Desarrollar un software o framework que permita la fácil configuración y ejecución de experimentos sobre OSBOP, incluyendo la posibilidad de cargar diferentes conjuntos de datos y visualizar los rankings de consenso obtenidos.
6. Escritura de la Memoria:
   • Documentar el proceso completo, desde la definición del problema hasta la implementación y experimentación, detallando los resultados y las conclusiones derivadas del estudio.

 

Competencias

Este proyecto permitirá el desarrollo de competencias clave en la intensificación de computación:

• [CM1] Capacidad para tener un conocimiento profundo de los principios fundamentales y modelos de la computación y saberlos aplicar para interpretar, seleccionar, valorar, modelar, y crear nuevos conceptos, teorías, usos y desarrollos tecnológicos relacionados con la informática.
• [CM3] Capacidad para evaluar la complejidad computacional de un problema, conocer estrategias algorítmicas que puedan conducir a su resolución y recomendar, desarrollar e implementar aquella que garantice el mejor rendimiento de acuerdo con los requisitos establecidos.
• [CM7] Capacidad para conocer y desarrollar técnicas de aprendizaje computacional y diseñar e implementar aplicaciones y sistemas que las utilicen, incluyendo las dedicadas a extracción automática de información y conocimiento a partir de grandes volúmenes de datos.

 

Medios a utilizar

• Lenguajes de programación como Python o C++, junto con librerías especializadas en algoritmos evolutivos y metaheurísticas, como DEAP (Distributed Evolutionary Algorithms in Python) o Pymoo.
• Herramientas de visualización de datos como Matplotlib o Plotly para representar los rankings y sus pesos asociados.
• Computadoras con recursos suficientes para la experimentación, disponibles en la universidad o mediante servicios de computación en la nube.

 

Bibliografía

• Artículos y libros sobre algoritmos metaheurísticos y su aplicación en problemas de optimización combinatoria.
• Literatura sobre agregación de rankings y problemas de consenso, incluyendo extensiones a rankings con empates.
• Artículos científicos recientes sobre aplicaciones de metaheurísticas en problemas similares al OBOP y su generalización a OSBOP.