Optimización Multiobjetivo para la Detección de Comunidades en Redes Complejas

Resumen

A raíz de las bases de la teoría de grafos que surgieron en el siglo XVIII, es posible estudiar las relaciones o vínculos existentes en un conjunto de elementos y determinar las características y propiedades de dichas relaciones. En las últimas décadas, los continuos avances en el ámbito de las ciencias de la computación han permitido modelar y analizar grafos de cualquier escala y tipología correspondientes a sistemas reales de alta complejidad que proceden de multitud de áreas de conocimiento como ingeniería, física, ciencias sociales, etc. En la actualidad, gracias al modelado y análisis de grafos por computador, es posible obtener información valiosa sobre las relaciones funcionales o las características de un determinado sistema, por complejo que éste sea. Ello ha dado lugar a que investigadores de todo el mundo muestren un gran interés por resolver una amplia variedad de problemas relacionados con grafos, como pueden ser: partición de grafos, coloreado de grafos, problemas de enrutado, problemas de flujos en redes, etc. Todos estos problemas han sido considerados en la categoría de problemas NP-completos, lo que implica que instancias lo suficientemente grandes de dichos problemas no pueden ser resueltos en un tiempo limitado. En los últimos años, un problema relativamente nuevo que puede ser abordado mediante las técnicas de análisis basadas en grafos y que ha sido incluido en la categoría de problemas NP-Completos, ha despertado un gran interés dentro de la comunidad científica debido al potencial de analizar sistemas complejos que éste ofrece. Este problema, llamado detección de comunidades, nace a raíz de una característica común inherente a todos los sistemas complejos, la presencia de patrones de nodos más densamente conectados entre sí que con el resto de nodos de la red. De los nodos que muestran estos patrones de conexión, llamados comunidades, se espera que compartan ciertas propiedades que permitirán detectar nuevas características o relaciones funcionales de la red. Cómo encontrar la estructura de comunidades óptima que mejor representa las características de una red, se ha convertido en todo un hándicap, pues se han propuesto multitud de algoritmos y funciones objetivo para resolver el problema. Entre ellos, destacan los algoritmos evolutivos y el índice de Modularidad como las principales soluciones aceptadas por la comunidad científica. Además de la importancia de la búsqueda de un algoritmo capaz de resolver el problema de la detección de comunidades eficientemente, el análisis de redes complejas a menudo se encuentra limitado a estudiar las características de una red desde una única perspectiva debido al enfoque propuesto por la mayoría de los algoritmos que encontramos en la literatura científica. Para superar este inconveniente, esta tesis doctoral propone un enfoque novedoso, flexible y adaptativo que permitirá un análisis de comunidades más completo y detallado sobre redes de cualquier complejidad y tipología. En particular, se analizan redes de diferente topología y extensión comúnmente utilizadas en la literatura científica, y, además, se lleva a cabo un estudio pionero en el ámbito de ingeniería eléctrica sobre redes de transmisión de alta tensión. La importancia de este estudio radica en que estamos tratando con una de las mayores infraestructuras creadas por el hombre, con cientos de miles de kilómetros de líneas de alta tensión que interconectan regiones, países, e incluso áreas continentales. Además, debido a la creciente demanda de electricidad y a la aparición de nuevos formatos de generación eléctrica, resulta imprescindible abordar el estudio sobre la ampliación y modificación de redes eléctricas mediante nuevos procedimientos complementarios a las técnicas tradicionales utilizadas en el estudio de sistemas eléctricos de potencia. La incorporación de estos nuevos formatos de generación de energía eléctrica renovables, está provocando que el diseño clásico de las redes eléctricas pase de un modelo centralizado, basado en disponer de un número relativamente acotado de centrales térmicas, nucleares e hidroeléctricas, a un modelo distribuido con un peso creciente en energías renovables, originando así un aumento de la conectividad en las redes y, por consiguiente, un incremento de su complejidad. En este sentido, se hace indispensable la necesidad de aplicar estrategias de control más robustas, así como nuevas técnicas de optimización para gestionar sistemas a gran escala. Actualmente, aunque existen procedimientos de análisis y diseño de redes eléctricas, como es el caso de la resolución de flujos de potencia, el inmenso abanico de posibles configuraciones existentes provoca que sea necesario aplicar nuevos procedimientos complementarios de cara a hacer factible la búsqueda de soluciones. En este sentido, en la presente tesis doctoral se aplica la detección de comunidades en el estudio y análisis de redes eléctricas de gran tamaño a fin de ampliar las conclusiones obtenidas por los procedimientos tradicionales, además de analizar los resultados como posibles mejoras de control de la red, que supondrían de una mayor fiabilidad y capacidad de restauración ante graves perturbaciones como desastres naturales (tormentas, terremotos, etc.) mediante el desarrollo de nuevos planes de conmutación para proteger islas o desconexiones parciales de la red, evitando así una mayor degradación durante los incidentes. En resumen, el objetivo de esta tesis se centra en afrontar el problema de la detección de comunidades en ámbitos que precisan de la aparición de nuevas técnicas de diseño y control, a través del desarrollo de nuevos algoritmos evolutivos (mono-objetivo y multiobjetivo) que permitan analizar las características topológicas de una red desde distintas perspectivas, con mayor o menor nivel de detalle en función de las necesidades del analista. Para lograr este objetivo, en primer lugar, se han diseñado métodos de inicialización poblacional eficientes y operadores evolutivos avanzados basados en intercambios entre comunidades, que han sido incorporados al algoritmo genético mono-objetivo propuesto en esta tesis, el cual optimiza el popular Índice de Modularidad como función objetivo. Dicho algoritmo, denominado “Generational Genetic Algorithm” (GGA+), ha sido analizado sobre multitud de benchmarks populares basados en redes sociales, además de sobre grafos de gran escala con miles de nodos y aristas que representan redes reales de transmisión de alta tensión de escala nacional y continental. Tras el éxito de los resultados logrados por la implementación del algoritmo mono-objetivo, con el objetivo de evaluar el rendimiento que los métodos de detección de comunidades evolutivos pueden ofrecer en el ámbito de ingeniería, distintos algoritmos como el mencionado GGA+ y otros algoritmos evolutivos referenciados en la literatura, como “Modularity and Improved Genetic Algorithm” (MIGA) o el bien conocido método de “Louvain”, se han aplicado sobre múltiples redes eléctricas, demostrando que los resultados obtenidos avalan su utilidad y buen rendimiento. Actualmente, la mayoría de métodos destinados a resolver el problema de la detección de comunidades, utilizan un enfoque mono-objetivo, siendo el índice Modularidad la función objetivo más extendida. Sin embargo, debido a la propia definición de comunidad en la que ésta puede ser vista desde un enfoque multiobjetivo, donde un objetivo puede ser maximizar el número de conexiones dentro de una comunidad y otro objetivo minimizar el número de conexiones con nodos externos a la comunidad, y, debido a que algunos estudios recientes han demostrado que al considerar Modularidad como único objetivo pueden surgir inconvenientes relacionados con el límite de resolución y desbalanceo de las soluciones, parece adecuado plantear el problema de la detección de comunidad desde un punto de vista multiobjetivo. Por estos motivos, en segundo lugar, basándonos en el buen rendimiento demostrado por GGA+, se ha diseñado una nueva versión multiobjetivo llamada MOGGA+, la cual incluye nuevos objetivos a optimizar en la detección de comunidades, abriendo de esta manera una nueva vía de investigación mediante la aplicación de algoritmos evolutivos multiobjetivo que optimizan simultáneamente diferentes objetivos. Más concretamente, MOGGA+ se ha sido diseñado con nuevos métodos de inicialización avanzados y operadores evolutivos. Además, utiliza un conjunto de soluciones no dominadas basado en la dominancia de Pareto, y una estructura adicional para modificar dinámicamente la probabilidad de aplicar distintos operadores evolutivos en tiempo de ejecución. En cuanto a los diferentes objetivos optimizados, se ha analizado la combinación del índice de Modularidad con un novedoso objetivo propuesto en esta tesis, “Desbalanceo” de comunidades, propiedad a tener en cuenta a la hora de diseñar redes eléctricas resistentes a contingencias, donde es importante que la red pueda ser separada en islas (subredes) de escala aproximadamente similar, para evitar una mayor degradación de la red. También, se ha analizado otro conocido objetivo Conductancia (como alternativa a Modularidad) junto con Desbalanceo.