Uso de algoritmos genéticos para la creación automática de patrones de requisitos

Resumen

Introducción Esta investigación se ha realizado dentro del grupo de investigación de la Universidad Carlos III de Madrid Knowledge Reuse Group (KR). El grupo KR investiga en las áreas de interés de representación, recuperación y reutilización del conocimiento aplicados a la Ingeniería de Software y a la Ingeniería de Sistemas en general. KR ha colaborado en el desarrollo del conjunto de productos Systems Engineering Suite (SE suite) que dan soporte entre otras actividades a todas las que tienen que ver con la Ingeniería de Requisitos, como una parte de la Ingeniería de Sistemas: autoría, verificación y validación de la calidad de los requisitos y trazabilidad de requisitos y productos finales. SE Suite utiliza patrones de texto para implementar su funcionalidad. Los patrones de texto son artefactos de conocimiento que se utilizan como plantillas para guiar a los ingenieros y analistas en el proceso de creación de requisitos; permiten la redacción de requisitos haciendo uso de lenguaje natural con ciertas restricciones sintácticas y de vocabulario que imponen los propios patrones para asegurar su calidad. Sin embargo, la generación de patrones es una actividad que requiere tiempo, es costosa y debe ser realizada por especialistas. Esta tesis propone un método de generación automática de patrones de texto utilizando algoritmos genéticos. Los algoritmos genéticos encuentran, a partir de un conjunto inicial de requisitos, patrones de texto. Motivación La principal motivación de esta investigación consiste en facilitar el trabajo de los especialistas en definición de patrones de texto para las herramientas de SE suite. Los patrones deben ser generados por expertos que necesitan conocimientos en profundidad del dominio técnico para el que se están generando y los principios de la generación de patrones sintácticos y semánticos que impone la herramienta SE suite. Es por tanto difícil formar a estos especialistas y constituyen una barrera de entrada importante para la implantación de las herramientas. Desde el punto de vista académico, la motivación consiste en la exploración de nuevas técnicas (uso de algoritmos genéticos junto con algoritmos de separación y conquista), no utilizadas hasta ahora en este contexto, que permitan avanzar en la generación automática de patrones en entornos de lenguaje natural y que pueden constituir un punto de partida para nuevas investigaciones en el ámbito de patrones, reuso del conocimiento y procesamiento de lenguaje natural. Hipótesis y objetivos Las hipótesis de partida a verificar han sido: • Es posible generar patrones de requisitos automáticamente usando algoritmos genéticos a partir de un corpus de requisitos de un mismo dominio. Estos patrones son equivalentes en calidad a los generados por expertos. • Si se añade al algoritmo anterior la técnica de separar y conquistar, entonces se puede además generar una población completa y limitada de patrones válida para que reconocer un conjunto homogéneo de requisitos de un dominio específico. • Es posible identificar e implementar parámetros en los algoritmos genéticos y de conquista que permitan ajustar su comportamiento a distintos escenarios reales de uso. En cuanto a los objetivos se ha planteado como objetivo general: • Definición de una metodología y desarrollo de una herramienta software prototipo basada en dicha metodología que genere automáticamente patrones de texto utilizando algoritmos genéticos a partir de un corpus inicial de requisitos de un dominio determinado. Otros objetivos específicos derivados han sido: • En el desarrollo de la herramienta utilizar entornos técnicos y modelos de datos compatibles con el conjunto de herramientas SE suite. • Identificar, en el desarrollo de la herramienta, parámetros con doten a la herramienta de flexibilidad para su adaptación a distintos escenario de uso reales. • Conseguir resultados en términos de tamaño de población de patrones mejores que los obtenidos en investigaciones anteriores. Definición de la metodología Procesamiento de lenguaje natural La metodología se basa en la disponibilidad de requisitos escritos en lenguaje natural. Esto significa que la primera actividad a realizar es el procesamiento de los requisitos y su normalización. Normalizar el texto significa convertirlo en una forma estructurada, más fácil de tratar por los algoritmos. Una vez normalizado se le aplican técnicas de análisis léxico, sintáctico, semántico y pragmático: • Segmentación de oraciones: el primer paso es dividir el texto a analizar en oraciones. En la Ingeniería de Requisitos un requisito suele estar constituido por una frase. • Tokenización: consiste en dividir la frase en palabras utilizando una lista de separadores. • Lematización o análisis léxico: El análisis léxico tiene como objetivo la normalización de cada palabra o token mediante un estudio que identifique y elimine las variaciones, por ejemplo, de género, número tiempos verbales verbales de las palabras candidatas, etc. • Análisis sintáctico y etiquetado gramatical: El objetivo del análisis sintáctico es encontrar las relaciones sintácticas entre las palabras. Esto permitirá el entendimiento de la semántica de los tokens en fases posteriores. • Análisis semántico y pragmático: el análisis semántico tiene como objetivo interpretar el significado de las expresiones. Se realiza después del análisis léxico y análisis sintáctico. Los problemas de implementación se deben a la ambigüedad léxica del lenguaje, ya que una palabra homónima puede tener múltiples categorías gramaticales; otros tipos de ambigüedad son la ambigüedad referencial y la ambigüedad de alcance. Patrones de texto Los patrones son una técnica de reúso de la información. Se trata de volver a utilizar soluciones ya implementadas a problemas nuevos que tienen un cierto grado de similitud con el problema anterior resuelto cuya solución se va a utilizar como “patrón”. Los patrones de texto para requisitos los podemos definir como restricciones sintáctico-semánticas que deben cumplir los requisitos para ser considerados como válidos para un patrón determinado. Son plantillas que facilitan la escritura de requisitos o que permiten validar si un requisito ya escrito cumple o no con las restricciones impuestas por patrones determinados. Los patrones se construyen con espacios contenedores o “cajas”. Cada caja contiene una restricción sintáctico-semántica de manera que los requisitos a escribir utilizando ese patrón deberán colocar en esa caja palabras que cumplan con las restricción. En esta investigación denominaremos a las cajas con el término “slot” y a las palabras permitidas en cada slot con el término “token”. Algoritmos genéticos (AG) Los Algoritmos genéticos (AG) son una aproximación a la resolución problemas inspirados en los principios de la selección natural y evolución de las especies de Darwin: diversidad genética inicial derivada de fuentes de variabilidad (mutaciones), selección natural de los individuos mejor adaptados, cruce de padres mejor adaptados, mutación, obtención de nuevas generaciones más adaptadas etc. La base es la generación de una variedad de posibles soluciones a un problema (población). Utilizando un criterio de selección (función de fitness), el algoritmo selecciona los mejores individuos a partir de los cuales genera una descendencia que hereda las características de los padres. Si los padres demuestran buen fitness, el proceso de reproducción (intercambio de genes de los padres) generará una mejor descendencia. Se trata de un proceso iterativo que, al final puede encontrar una solución óptima al problema. Los AG se han utilizado en una gran variedad de escenarios: búsqueda de la ubicación óptima de los aerogeneradores en los parques eólicos, priorización de requisitos, generación de patrones de expresiones regulares. Un ejemplo característico es la resolución del denominado “problema del viajante de comercio”. Esta es la secuencia de actividades y bucle principal de un AG genérico: A) Codificación de la solución: Definir genes, individuos y población. B) Definición de una función de fitness para evaluar la idoneidad de cada individuo como posible solución al problema. C) Generación aleatoria de una población inicial, generación 1. D) Bucle principal: Iteraciones hasta encontrar una solución final a todo el problema o hasta alcanzar un límite paramétrico de número de iteraciones. I - Evaluación la población de la generación "n" utilizando la función de fitness. II - Selección de los mejores progenitores, aquéllos con mejor fitness, para utilizarlos como padres para la siguiente generación. III - Cruce de los padres. Se desarrolla una función específica de cruce con la que se genera la generación "n+1" de población. IV - Mutación de ciertos individuos de la nueva generación. De nuevo con una función específica y con el fin de introducir aleatoriedad y explorar posibles nuevos “genes” potencialmente positivos para la resolución del problema. V - Sustitución de la generación "n" por la generación "n+1". Esta generación “n+1” tendrá un valor de fitness global mayor que la precedente, acercándose el AG a la resolución del problema. E) HASTA que se encuentre la solución o se alcance el límite paramétrico establecido de iteraciones. La implementación del AG en esta investigación ha consistido en: • Disponer de un conjunto inicial de requisitos de calidad procesados previamente con técnicas PLN. Estos requisitos se van a utilizar para encontrar patrones de texto que reconozcan estos patrones. • Los genes en el AG son los slots de los requisitos. El contenido de cada slot, cada instancia de un gen o alelo, son los tokens posibles. Los individuos, conjuntos de genes, son patrones y la población es un conjunto de patrones generados. • Existen dos características adicionales en los genes de los patrones: genes o slots opcionales y tokens comodín. Los primeros tienen la característica de que su no presencia en un requisito determinado no impide que dicho requisito sea reconocido por el patrón; los segundos tienen la capacidad de reconocer un número determinado paramétricamente de genes de requisitos independientemente del contenido de dichos genes. Estas dos características dotan de flexibilidad a los patrones para el reconocimiento. • La biblioteca de alelos, tokens disponibles para rellenar los slots de los individuos, se genera a partir de los tokens existentes en el conjunto de requisitos a tratar. • Los patrones se generan inicialmente de forma aleatoria. La longitud del cromosoma de cada individuo (número de genes), tamaño de la población, frecuencia de tokens opcionales y tokens comodín son establecidos paramétricamente en la herramienta. • La función de fitness, de selección de un mejor patrón, valora el número de requisitos que un patrón creado al azar por el AG reconoce. Un requisito es reconocido por un patrón si todos los slots del requisito coinciden con los slots del patrón. Cuantos más requisitos reconozca un patrón, mejor es ese patrón. • Las funciones de selección de mejor individuo, cruzamiento, mutación y sustitución permiten, a partir de una población generación “n” evolucionara una generación “n+1” utilizando técnicas estándar de AG para seleccionar los mejores individuos y con ellos producir una generación “n+1” con un mejor fitness global que la anterior. • Las funciones del AG se ejecutan iterativamente hasta encontrar patrones que reconocen a todos los requisitos del conjunto inicial o hasta que se llega a una solución que no evoluciona mejorando resultados. Algoritmo de conquista (AC) La estrategia de separar y conquistar se aplica cuando se requieren varias soluciones para distintos componentes de un problema. Hay un bucle general que busca una solución que explique una parte de las instancias o resuelva parcialmente el problema. Cuando encuentra una solución parcial de este tipo, la almacena y marca las instancias resueltas, esto es, las conquista. Las instancias resueltas se retiran y se continua la búsqueda con el bucle general. Herramienta Twiga Utilizando como especificación general la metodología diseñada de uso de algoritmos genéticos AG y de conquista AC para le generación automática de patrones de texto para requisitos y para la realización de los experimentos de esta investigación, se ha diseñado e implementado una herramienta software propia que hemos denominado Twiga. Twiga es por tanto un producto final resultante de esta investigación, si bien no está desarrollada con funcionalidades e interfaces de usuario que permita ser utilizada por usuarios finales, ajenos a la investigación. La versión final es un prototipo que requiere de conocimientos de diseño y de la programación realizada. Twiga se ha desarrollado en modo iterativo en tres versiones principales. Se ha utilizado el mismo modelo de datos que la herramienta SE suite ampliado para necesidades particulares, en lenguaje C# y con BBDD SQL Server. Es una prototipo plenamente compatible con SE Suite. Con el fin de dotar de flexibilidad a Twiga se han implementado 34 variables parametrizables que permiten ajustar el comportamiento de los algoritmos a distintos escenarios. Resultados de la experimentación La experimentación se realizó con un conjunto de 545 requisitos reales proporcionado por INCOSE (International Council on Systems Engineering) previamente cualificados por expertos como requisitos de calidad. Estos requisitos fueron agrupados en 10 conjuntos de requisitos o RS, por su tipología, dominio funcional etc. Con cada RS se realizaron juegos de experimentos para buscar automáticamente patrones. Los resultados muestran que se encuentran conjunto de patrones capaces de reconocer a los requisitos. Para los 545 requisitos se han obtenido 117 patrones que reconocían 472 de los 545 requisitos totales, en el mejor de los ensayos. El promedio de requisitos reconocidos por los patrones ha sido de 2,87. Los mejores patrones encontrados por cada RS son capaces de reconocer hasta 17 requisitos. Aunque no era objetivo de la experimentación, se han realizado medidas de tiempos de ejecución para disponer de un punto de partida para futuros trabajos de optimización. Se ha utilizado como métrica el tiempo medio para encontrar un patrón. En función de cada conjunto de requisitos estos tiempos varían entre 1,50 y 2,71 minutos. En experimentos previos realizados por el grupo KR utilizando otra aproximación metodológica, pero con el mismo juego de datos se obtuvieron promedios de requisitos reconocidos por patrón de 1,23. Considerando que en esta investigación este valor es de 2,87, se ha conseguido una mejora del 233%. Conclusiones Las conclusiones científicas que derivamos de la investigación llevada a cabo en esta tesis son: • Viabilidad del uso de algoritmos genéticos: Los algoritmos genéticos son una aproximación válida para la generación automática de patrones de requisitos. • Importancia de la función de evaluación: De las múltiples funciones que componen los algoritmos implementados, la función de fitness del algoritmo genético es la función clave ya que es la que permite determinar cómo de buenos son los individuos de una población y clasificarlos para continuar con el resto de funciones del AG. • Posibilidad de uso de estrategia de conquista junto con el algoritmo genético: Si se añaden iteraciones de conquista, es posible generar conjuntos de patrones para reconocer conjuntos de requisitos. Esto permite ofrecer una solución completa al problema de preparar un conjunto de patrones para un dominio determinado a partir de un subconjunto de requisitos. En cuanto a las conclusiones y resultados tecnológicos los más relevantes son: • Implementación de un prototipo funcional: Se ha desarrollado una herramienta completa, Twiga que implementa la metodología y algoritmos de esta tesis. Esta herramienta ha sido desarrollada como prototipo de un posible producto o componente a integrar en la SE suite. • Arquitectura compatible con SE suite: La arquitectura implementada permitirá en un futuro incorporar como un componente adicional o como un producto independiente la funcionalidad de generación automática de patrones dentro de la SE suite. • Prototipo con un alto nivel de parametrización: Se ha implementado un componente específico de parametrización, con un número total de 34 variables parametrizables. Este componente unifica y abstrae del resto de clases y métodos de Twiga toda la funcionalidad relacionada con el cambio de comportamiento de los algoritmos. • Capacidad de reúso del algoritmo genético AG: Se ofrece un conjunto de métodos del algoritmo genético para el problema de la generación automática de patrones que, por su diseño, permiten generar, a partir de los mismo y con un nivel de abstracción mayor, una máquina general de ejecución de algoritmos genéticos en la que se podrían definir funciones específicas (de generación de población, evaluación de la población, reproducción, etc.) distintas que se invocarían desde el algoritmo genético genérico para resolver otros posibles problemas. Principales aportaciones Esta tesis doctoral ofrece una nueva aproximación metodológica y desarrolla un prototipo plenamente funcional para la generación automática de patrones de texto aplicada al ámbito de la ingeniería de requisitos. En esta investigación hemos comprobado que la unión del uso de algoritmos genéticos y algoritmos de conquista permiten generar patrones automáticamente. Esta es una aproximación novedosa, que no había sido utilizada con anterioridad en este ámbito. Consideramos esta la principal aportación a la Comunidad Académica y a la Comunidad Industrial. La identificación de múltiples parámetros que afectan al comportamiento de los algoritmos es también una aportación importante por cuanto permite evolucionar la investigación con nuevos experimentos ante nuevos escenarios utilizando los mismos algoritmos y desarrollos y alterando el comportamiento global mediante el ajuste de estos parámetros. La propia herramienta Twiga, plenamente funcional, aunque se trate de un prototipo, y a disposición de la Comunidad, es una aportación que puede facilitar el desarrollo de nuevos componentes o productos a partir de ella.