martes, 27 de marzo de 2012 0 comentarios

Algoritmos Voraces Iterativos para el Problema de Agrupación de Máxima Diversidad

Jonathan David González Barrera
 
Aula 22 (Facultad de Matemáticas), 13.30 h.

 



En ciencias de la computación, el problema de partición es un problema complejo que, desde la perspectiva de la decisión, consiste en decidir si, dado un conjunto de elementos, puede éste ser particionado en dos mitades, de tal manera que sumando los elementos de cada una ambas den como resultado la misma suma. Asimismo, en lugar de dividir dicho conjunto en dos partes, podemos dividirlo en un número k fijo de ellas, sin que compartan elementos y cuya unión forme el conjunto total. Por otra parte, los elementos pueden formar relaciones equivalentes que midan la repartición de los mismos entre las partes.

Tanto la formación de múltiples particiones como el establecimiento de una relación de equidad entre elementos conforman el soporte de nuestro problema. El Problema de Agrupación de Diversidad Máxima (en inglés, Maximally Diverse Grouping Problem, MDGP) parte de estas premisas para construir una colección de grupos, a partir de un conjunto de elementos, que maximice, en la medida de lo posible, la relación entre los elementos que componen a cada grupo.

Para abordar este problema, consideramos oportuno utilizar la metaheurística voraz iterativa (en inglés, iterated greedy, IG) por dos razones fundamentales: 1) por su flexibilidad y simpleza; y 2) por la eficiencia mostrada en otros problemas de combinatoria similares al MDGP. 


Jonathan David González Barrera se licenció en Ciencias y Técnicas Estadísticas por la Universidad de La Laguna en 2010. Cursó el máster "Soft Computing y Sistemas Inteligentes" en la Universidad de Granada. En la actualidad, es alumno de doctorado en el Departamento de Estadística, Investigación Operativa y Computación de la ULL. Trabaja en el campo de la "metaheurística poblacionales" aplicada a problemas de optimización.



 
;