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.