Algoritmos genéticos para Process Mining

Tras dos artículos seguidos dedicados a los algoritmos genéticos, uno en que simplemente me preguntaba si estaban resurgiendo y otro en que explicaba su funcionamiento, cierro hoy esa mini-serie hablando de una de las aplicaciones recientes que me ha sido dado observar de uso de este tipo de algoritmos: su empleo como una técnica de Process Mining para el descubrimiento de procesos de negocio.

Recuerdo, escuetamente, que Process Mining son un conjunto de técnicas para obtener información de procesos de negocio a partir de las trazas ('logs') dejadas por los sistemas de información en que se apoyan esos procesos de negocio.

Y recuerdo también que una de las tareas que se pueden hacer con 'Process Mining', probablemente la más representativa y también la más compleja, es el descubrimiento de procesos de negocio, es decir, a partir de esos logs, lograr deducir la estructura de actividades, conexiones y bucles que definen ese proceso de negocio.

En su libro 'Process Mining. Data science in action', Wil van der Aalst nos describe el Genetic Process Mining como una técnica avanzada para el descubrimiento de procesos. Antes de leer lo que sigue, y para el lector que no recuerde cómo funcionan los algoritmos genéticos, le recomiendo repasar mi artículo anterior '¿Cómo funcionan los algoritmos genéticos?'

Y ahora sí, pasamos a ver su aplicaciones en process mining. Y nos apoyamos en la siguiente figura procedente de la obra y autor citados: 

Los pasos serían los siguientes:

• Inicialización: Partiendo de los logs (que contienen registros con instancias de actividades correspondientes a instancias de procesos) se construye la población inicial ('initial population'). En el caso que nos ocupa, cada individuo o fenotipo sería un modelo de proceso de negocio expresado como una red de Petri, un diagrama BPMN o algo similar.


• Selección: Se realiza la evaluación obteniendo para cada cada fenotipo (modelo de negocio candidato) el valor de adecuación ('fitness value'). En el caso del process mining dicho valor de adecuación mide hasta qué punto el modelo de proceso de negocio explica los logs, es decir, su ejecución sería capaz de producir esos logs. Un ejemplo muy sencillo (aunque no muy eficaz) de esa evaluación es calcular qué proporción de las trazas pueden ser replicadas por el modelo de proceso.Las funciones reales son más sofisticadas, pero no vamos a entrar en ello aquí. En cualquier caso, tras realizar la evaluación tenemos un valor de adecuación de cada modelo de proceso de la población. Ahora seleccionamos los mejores, los que tengan un valor de adecuación más alto. Esos individuos seleccionados, serán los procesos de negocio 'padres' de la siguiente generación.


• Reproducción: Se aplican dos de los operadores genéticos de los que ya hablamos en el anterior artículo: el cruce ('crossover') y la mutación ('mutation'). El cruce, como su nombre indica, mezcla el material genético, en este caso secciones del modelo de proceso, para generar un modelo de proceso nuevo que tiene partes procedentes de cada uno de los padres. No es esta una tarea fácil pero en la obra citada se aporta algún ejemplo de cómo hacer esto. Mediante la mutación, además, se producen algunos cambios aleatorios que, en este caso, consisten en introducir alguna nueva relación causal. 


• Con esto ya hemos cerrado la primera iteración. A partir de ahí se repiten todos los pasos, con lo que la calidad de cada generación debería ir mejorando y se actúa de esta forma hasta que se alcance un umbral de adecuación de proceso prefijado. 

Lo descrito constituye el esquema general que, como se puede ver, es una aplicación bastante inmediata de la estructura general de un algoritmo genético. Sin embargo, y aunque no lo hemos explicitado mucho, su uso real implica especificidades tanto del hecho de tratar con modelos de proceso así como decisiones específicas como la forma de representar el modelo de proceso, la forma de crear la población inicial, la función de evaluación concreta a aplicar, la estrategia concreta de selección a usar, el mecanismo concreto de cruce, el mecanismo concreto de mutación, etc

Parece un poco mágico que mediante los mecanismos descritos se pueda deducir un modelo de proceso de negocio a partir de unas simples trazas pero, aparentemente, igual que en la naturaleza la genética y la selección natural han conducido a una evolución exitosa, los algoritmos genéticos aplicados a la función de descubrimiento de procesos dentro del process mining parecen haber dado frutos satisfactorios.

¿Cómo funcionan los algoritmos genéticos?

En el artículo anterior, me preguntaba si estaba ocurriendo algo con los algoritmos genéticos, si el hecho de que, tras años 'sin saber nada de ellos', ahora me los hubiese encontrado en muy breve plazo en dos lecturas actualizadas, significaba algún tipo de resurgimiento. Aunque en el artículo esbocé muy someramente en qué consistían, me quedé con las ganas de hacer una explicación básica pero algo más detallada sobre cómo funcionan estos algoritmos genéticos.

Y esa explicación sencilla es el objeto de este artículo. Y como apoyo tomo una de las dos lecturas que me 'avisaron' de ese posible renacimiento de los algoritmos genéticos, a saber, el libro 'Optical Character Recognition Systems for Different Languages with Soft Computing' de Arindam Chaudhuri, Krupa Mandaviya, Pratixa Badelia y Soumya K Ghosh. En el tercer capítulo de la citada obra se repasan diferentes algoritmos del campo del 'soft computing' que son aplicables al reconocimiento óptico de caracteres (OCR). Y como los algoritmos genéticos se encuadran en ese concepto, los autores hacen una breve revisión de conceptos.

Para ello, se apoyan en la siguiente figura (NOTA: la propiedad intelectual de esa figura es de los autores y la editorial Springer).

Los algoritmos genéticos fueron inicialmente propuestos por John Holland. En ellos, existe una población ('population') de soluciones candidatas al problema a resolver. Cada una de las soluciones posibles que conforman esa población se denomina individuo, criatura o fenotipo. Cada una de estos fenotipos está caracterizado por una serie de características que se denominan cromosomas y que, aunque depende del problema y algoritmo concretos, se intentan representar como cadenas digitales de unos y ceros.

Sobre cada población se aplica una función de evaluación ('evaluation') para obtener el valor de adecuación ('fitness value') de cada fenotipo como solución del problema, es decir, hasta qué punto resuelve o se acerca a resolver el problema que estamos tratando.

A su vez, cada población, una vez evaluada, y suponiendo que aún no damos por resuelto el problema,  se transforma, es decir, evoluciona, a una nueva población mediante la aplicación de los operadores genéticos ('genetic algorithm operators'). Estos operadores son reproducción ('reproduction'), cruce ('crossover') y mutación ('mutation'). Mediante la reproducción generamos individuos nuevos. Mediante el cruce se mezclan los materiales genéticos, es decir, creamos un nuevo individuo o fenotipo que usa parte de las características de uno de sus padres y parte de las características del otro. Mediante la mutación introducimos variaciones aleatorias en esos cromosomas, es decir, en las características del fenotipo, individuo o solución candidata.

¿Cómo funciona?

Para verlo nos apoyamos en la siguiente figura (NOTA: de nuevo, la propiedad intelectual de esa figura es de los autores y la editorial Springer).

• Generamos una serie de soluciones candidatas (población inicial) generalmente al azar.A partir de ahí funcionamos en bucle hasta alcanzar la solución perseguida.


• Primero aplicamos la función de evaluación a la población y encontramos el valor de adecuación de cada uno de sus individuos. Si alguna solución es suficiente, finalizaría el algoritmo. Si no, se seleccionan los individuos que tienen un mejor valor de adecuación.


• Con esos individuos seleccionados se realiza la reproducción y el cruce, para obtener nuevos individuos hijos.


• Al conjunto de individuos hijos se le aplican mutaciones aleatorias.


• Hecho esto, tenemos ya una nueva población, que pasaría a evaluarse y así continuaría el bucle.

Como se puede apreciar los algoritmos genéticos están claramente inspirados en lo que sabemos de genética y selección natural. Esa inspiración y paralelismo se refuerzan utilizando términos procedentes, en efecto, de la biología y la genética.

De todas formas, no perdamos de vista que son algoritmos matemático-informáticos, unos algoritmos no especialmente eficientes (más bien, bastante poco eficientes) pero que pueden producir soluciones que no encontraríamos mediante algoritmos más clásicos y deterministas.

¿El retorno de los algoritmos genéticos?

Durante los primeros años de la Inteligencia Artificial  (casi podríamos decir, incluso, que durante las primeras décadas) se intentaron diversas técnicas, estrategias y algoritmos, muy diferentes entre si, pero que buscaban encontrar la manera de crear esa inteligencia en las máquinas.

A día de hoy,  la resurgida inteligencia artificial se enfoca mucho en el Machine Learning y este, a su vez, en los enfoques conexionistas (redes neuronales, con frecuencia ampliadas con el enfoque de Deep Learning), estadísticos o de tratamiento del lenguaje natural.

Parecen  olvidados conceptos, entonces dominantes como, son la representación del conocimiento (ligada a la inteligencia artificial de orientación simbólica), los sistemas expertos (elicitación de las reglas que usan los expertos humanos para resolver problemas complejos y aplicación de esas reglas mediante un motor de inferencia), la lógica difusa ('fuzzy logic') álgebra que maneja etiquetas cualitativas, en lugar de números o valores claros de verdadero / falso)… y de lo que en este artículo hablamos: los algoritmos genéticos.

¿Qué son los algoritmos genéticos?

Debo confesar que nunca los he llegado a estudiar en profundidad, quizá porque es un enfoque que nunca estuvo del todo de moda y, probablemente, porque nunca ha obtenido grandes éxitos, al menos a nivel comercial. En cualquier caso, sí puedo decir que los algoritmos genéticos son un tipo de algoritmos que enfocan la resolución de problemas mediante una estrategia inspirada en la genética y la selección natural. 

Con esa idea, lo que hacen los algoritmos genéticos es buscar la solución a un problema generando 'mutaciones', es decir, pequeños cambios más o menos aleatorios en la soluciones posibles, y comprobando si las nuevas soluciones o el nuevo algoritmo mutado, es mejor que lo teníamos antes. Si es así, 'sobrevive' y la mutación permanece; y si no es así 'perece'

Cabe entender que los algoritmos genéticos pueden encontrar su aplicación en problemas muy complejos para los cuales somos incapaces de encontrar reglas claras sobre cómo resolverlos con lo que, de alguna forma, aplicamos una especie de 'ensayo y error' hasta acertar o, al menos, encontrar una solución satisfactoria. También cabe pensar, o al menos yo así lo entiendo, que los algoritmos genéticos son más bien una filosofía para enfocar la resolución de problemas pero que, en realidad, pueden caber dentro de esta etiqueta, una multiplicidad de algoritmos.

Sea como sea, la idea de los algoritmos genéticos tiene, al menos, 30 años y, aunque parecen haber encontrado algunos campos de aplicación, lo cierto es que nunca han alcanzado 'la fama', nunca parece haberse convertido en una tecnología 'mainstream', que se dice.

Personalmente, hace mucho que no encontraba referencia a ellos, a pesar de leer abundante literatura en tecnologías relacionadas con la inteligencia artificial o, incluso, plenamente dedicadas a ella.

Y sin embargo...

Y sin embargo, en el espacio de poco más de un mes, me he encontrado dos referencias a los algoritmos genéticos. En un caso los he visto mencionados como una de las posibles técnicas de 'soft computing' a utilizar en OCR (Optical Character Recognition). En efecto, en el libro 'Optical Character Recognition Systems for Different Languages with Soft Computing' de Arindam Chaudhuri, Krupa Mandaviya, Pratixa Badelia y Soumya K Ghosh, se menciona a los algoritmos genéticos usados como mecanismo de extracción de características.

El otro caso es en el libro 'Process Mining. Data science in action' de Wil van der Aalst en que se menciona los algoritmos genéticos para la identificación de procesos de negocio a partir de logs.

¿Es esto casual? ¿No son más que aplicaciones residuales de los algoritmos genéticos que, por azar, han llegado hasta mi de forma concurrente o hay algo más?

¿Es que los algoritmos genéticos se han perfeccionado o se ven beneficiados por el aumento de la capacidad de computación?

¿Están hallando nuevas aplicaciones o métodos? ¿Son más eficaces? O, de nuevo, estamos sólo ante una coincidencia.

¿Asistimos, en fin, al retorno de los algoritmos genéticos? ¿O es que nunca se fueron del todo?

Por si acaso, desde ya, activo las 'antenitas' de detección de tendencias...