Grouping harmony searchprinciples, novel adaptations and practical applications

Resumen

El objetivo principal de los problemas por agrupaciones o grouping es similar al de los problemas de hard clustering o partición no difusa, consiste en distribuir elementos de un determinado conjunto, de manera que cada elemento esté asignado a un único grupo. Sin embargo, los problemas de agrupaciones van un paso más allá respecto a los de partición no difusa, ya que la función de coste depende completamente de la composición jerárquica de los grupos; es decir, las propiedades y/o relaciones entre los elementos asignados a un determinado grupo determinan la calidad de las particiones. Orientada a la resolución de problemas de agrupaciones, Falkenauer presentó a principios de los años 90 una contribución que aunaba enfoques anteriores centrados en algoritmos genéticos por agrupaciones. Su investigación se basaba en proponer una estrategia de codificación específica para representar, con una redundancia mínima, el espacio solución de los problemas de agrupaciones, así como presentar operadores de improvisación especialmente adaptados. No obstante, la literatura relacionada aún no ha logrado reducir al mínimo la redundancia en el proceso de codificación de los citados problemas. Esta Tesis aborda, mediante una metodología práctica, dos formulaciones relacionadas de problema: se presenta primero un problema típico de agrupaciones en el que N elementos tienen que ser agrupados en M grupos, y en segundo lugar se da paso a una generalización de dicho problema en el que se asume que M es un parámetro desconocido a priori. En concreto, las contribuciones de esta Tesis son las siguientes: 1) abordar los problemas comentados, mediante la adaptación del denominado algoritmo de Búsqueda por Armonía (Harmony Search, HS), dando lugar al novedoso algoritmo de Búsqueda por Armonía por agrupaciones; y 2) diseñar operadores de improvisación especifícamente adaptados tanto a las características del problema, como a dicho algoritmo. Siguiendo la metodología práctica mencionada como base sobre la cual diseñar, implementar y validar las técnicas propuestas en esta Tesis, se han propuesto una serie de escenarios de aplicaciones dinámicas: en primer lugar se presentan una serie de problemas de despliegue de red (como las que se encuentran en las redes de telecomunicaciones) modelados como realizaciones del problema de Ubicación Óptima de Nodos de Acceso (Switch Location Problem, SLP) con restricción de costes. El problema de despliegue de redes se extiende después a su versión más general para abordar el problema de Ubicación Óptima de Nodos de Acceso Multi-tipo (Multi-Type Access Node Location Problem, MTANLP), que representa una generalización del SLP al considerar un número variable de grupos. Dado que ambas formulaciones del problema tratan el diseño de redes fijas de comunicación, la utilidad de los algoritmos derivados también se verifica a través de la resolución del problema de Planificación de Apertura de Redes de Acceso WiFi Urbanas. La viabilidad y potencialidad del algoritmo GHS propuesto quedan patentes empleando diferentes experimentos en escenarios reales de diversa complejidad. Asimismo, se ha puesto especial énfasis en analizar la escalabilidad de la herramienta en escenarios de complejidad elevada. La segunda contribución importante de la investigación presentada en esta Tesis consiste en la generalización del conocimiento adquirido a través de la metodología presentada, y abordando diversos problemas de particiones clásicos. Hasta la fecha, se han realizado avances en esta rama de la analítica descriptiva a la hora de establecer el número óptimo de agrupaciones, pero la actividad en torno al estudio de diferentes esquemas de codificación y su redundancia no se ha abordado con especial énfasis. Esta Tesis ahondará en este aspecto a través del estudio y la evaluación del rendimiento de diversas codificaciones por agrupaciones. Las conclusiones extraídas - que aplican tanto a problemas de agrupaciones como de particiones - revelan que el rendimiento del algoritmo propuesto mejora cuando se utilizan esquemas de codificación que representan unívocamente (cada solución está representada por un solo punto en el espacio solución y viceversa) el problema dado. Esta premisa se ve reforzada por el método de clasificación inteligente propuesto, que garantiza que cada solución siempre está codificada de forma unívoca. Del mismo modo, la definición de operadores de improvisación específicos es fundamental para mejorar el intercambio de información óptimo; en este sentido: 1) los operadores de improvisación están diseñados en base a la métrica utilizada para la evaluación de las soluciones, 2) se consideran las restricciones impuestas en la formulación del problema al aplicar los operadores de improvisación, y 3) se adoptan esquemas diferenciales. En esta Tesis se concluye que mediante la aplicación de las premisas citadas, no sólo se obtienen soluciones más precisas, si no que el coste computacional requerido disminuye; siendo este último aspecto clave, si se prevé extrapolar el esquema propuesto al problema del "Big Data", con los retos que éste plantea (ingente cantidad de información, análisis descriptivo y rápida respuesta, entre otros).