Exploiting HPC Capabilities For Combinatorial Optimization In Computational Systems Biology

Abstract

[Resumo] A optimización combinatoria é esencial para resolver problemas complexos nunha ampla gama de campos, incluíndo a programación, o enrutamento, o deseño en enxe ñaría e os sistemas de control. En bioloxía de sistemas, a optimización combinatoria é importante porque permite a identificación eficiente de solucións ´optimas ou case óptimas en sistemas e redes biolóxicas complexas con espazos de solucións grandes e discretos. Dada a complexidade e a escala destes problemas, os métodos exactos adoitan ser pouco prácticos, o que fai que as metaheurísticas sexan unha alternativa necesaria. Os algoritmos metaheurísticos, en particular os deseñados para a optimización combinatoria, demostraron a súa eficacia á hora de producir solucións case óptimas en períodos de tempo razoables. Aproveitar o paralelismo pode servir para mellorar significativamente tanto a eficiencia como a precisión do proceso de busca. Os rápidos avances na computación de alto rendemento permiten hoxe en día un acceso xeneralizado a grandes capacidades computacionais, facilitando a aplicación de metaheurísticas paralelas a tarefas de optimización a gran escala. Esta tese presenta BiPCACO, unha variante binaria, paralela e cooperativa da coñecida metaheurística Optimización da Colonia de Formigas (ACO), adaptada especificamente a problemas de optimización combinatoria. BiPCACO integra varias melloras, como mecanismos de cooperación optimizados, patróns de comunicación máis eficientes, unha hibridación con outro algoritmo e unha innovadora estratexia de axuste automático de parámetros en tempo de execución. Estes axustes melloran a robustez do algoritmo, converténdoo nunha ferramenta poderosa non só en bioloxía de sistemas, senón tamén en problemas xerais de optimización combinatoria binaria.[Resumen] La optimización combinatoria es esencial para resolver problemas complejos en una amplia gama de campos, como la programación, el enrutamiento, el diseño en ingeniería y los sistemas de control. En biología de sistemas, la optimización combinatoria es importante porque permite la identificación eficiente de soluciones óptimas o casi óptimas en redes y sistemas biológicos complejos con espacios de soluciones amplios y discretos. Dada la complejidad y escala de estos problemas, los métodos exactos suelen ser poco prácticos, lo que convierte a las metaheurísticas en una alternativa necesaria. Los algoritmos metaheurísticos, en particular los diseñados para la optimización combinatoria, han demostrado su eficacia a la hora de producir soluciones casi óptimas en periodos de tiempo razonables. Aprovechar el paralelismo puede servir para mejorar significativamente tanto la eficiencia como la precisión del proceso de búsqueda. Los avances rápidos en computación de alto rendimiento permiten hoy en día un acceso generalizado a grandes capacidades computacionales, facilitando la aplicación de metaheurísticas paralelas en tareas de optimización a gran escala. Esta tesis presenta BiPCACO, una variante binaria, paralela y cooperativa de la conocida metaheurística Optimización de la Colonia de Hormigas (ACO), adaptada específicamente a problemas de optimización combinatoria. BiPCACO integra varias mejoras, como mecanismos de cooperación perfeccionados, patrones de comunicación más eficientes, una hibridación con otro algoritmo y un enfoque innovador para el ajuste automático de parámetros durante el tiempo de ejecución. Estos ajustes mejoran la robustez del algoritmo, convirtiéndolo en una potente herramienta no solo en biología de sistemas, sino también en problemas generales de optimización combinatoria binaria.[Abstract] Combinatorial optimization is essential for solving complex problems across a wide range of fields, including scheduling, routing, engineering design, and control systems. In Computational Systems Biology (CSB), combinatorial optimization is important because it enables the efficient identification of optimal or near-optimal solutions in complex biological networks and systems with vast and discrete solution spaces. Given the complexity and scale of such problems, exact methods are often impractical, making advanced metaheuristics a necessary alternative. Metaheuristic algorithms, particularly those designed for combinatorial optimization, have demonstrated their effectiveness in producing near-optimal solutions within reasonable time constraints. Leveraging parallelism significantly enhances both efficiency and accuracy in the search process. The rapid advancements in high-performance computing (HPC) now enable widespread access to sophisticated computational capabilities, facilitating the application of parallelized metaheuristics in large-scale optimization tasks. This thesis introduces BiPCACO, a binary, parallel, and cooperative variant of the well-known Ant Colony Optimization (ACO) metaheuristic, specifically tailored for combinatorial optimization problems. BiPCACO integrates several enhancements, including improved cooperation mechanisms, more efficient communication patterns, hybridization with complementary algorithms, and an innovative approach for automatic parameter tuning during runtime. These refinements enhance the algorithm’s robustness, making it a powerful tool not only in CSB but also in broader binary combinatorial optimization challenges.