Parallel implementation of estimation of distribution algorithms based on probabilistic graphical models. Application to chemical calibration models

Resumen

Los Algoritmos de Estimación de Distribuciones (Estimation of Distribution Algorithms, EDAs) son una clase de Algoritmos Evolutivos cuya principal característica es el uso de modelos probabilísticos para detectar las posibles dependencias entre variables, Los EDAs han demostrado su potencial para resolver problemas de optimización de tamaño pequeño-mediano, pero su uso para problemas medianos-grandes es actualmente inviable, dado su gran coste computacional. El objetivo principal de esta tesis es el diseño de versiones rápidas de un subconjunto de los EDAs (los basados en modelos gráficos probabilítiscos), utilizando programación paralela, de tal forma que se explote la potencia de cálculo de varios procesadores trabajando simultáneamente. Para ello se han utilizado los dos paradigmas más habituales de programación paralela: hilos (POSIX threads) y paso de mensajes (Message Passing Interface, MPI). Los programas obtenidos mantienen la funcionalidad de los originales secuenciales, al mismo tiempo que utilizan eficientemente sistemas multiprocesador y multicomputador (incluyendo clusters), de tal manera que el tiempo de ejecución se reduce de forma proporcional al número de procesadores utilizados. La disponibilidad de versiones paralelas rápidas de los EDAs permite ampliar el ámbito de aplicación de estos algoritmos. Desde el punto de vista práctica, se ha utilizado la versión paralela de un EDA, en concreto EBNABIC, para obtener modelos de calibración en el área de la química analítica. El proceso exige en primer lugar la creación de un modelo a partir de datos de reacciones conocidas: concentraciones iniciales de los analitos que forman parte d lea reacción, y una colección de medidas espectrales tomadas a lo largo del tiempo durante la reacción. Una vez obtenido el modelo, se pueden dar medidas espectrales de una reacción desconocida para predecir las concentraciones iniciales de los analitos. La utilización de EBNABOC en el