Mejora de algoritmos evolutivos en problemas de búsqueda de árboles óptimosnuevos operadores sobre la codificación dandelion

Résumé

Esta tesis doctoral aborda la optimización de grafos con forma de árbol, ampliamente utilizados actualmente para modelar diferentes tipos de estructuras, dada la utilidad que presentan sus características. Concretamente, recurriremos al empleo de métodos evolutivos como herramienta clave para afrontar la resolución de distintos tipos de problemas de optimización que en este contexto se plantean. Actualmente existen varios procedimientos que permiten una adecuada representación de esta clase de grafos, permitiendo a dichos algoritmos manejarlos adecuadamente durante el proceso de optimización que desarrollan. Algunos ejemplos de estas codificaciones son Prüfer, Blob, Neville y en especial Dandelion, cuyas valiosas propiedades han convertido dicho método en el más empleado con este fin. A pesar de la significativa capacidad que estas representaciones poseen para alcanzar buenos resultados ante la mayoría de escenarios, existen problemas especialmente difíciles en que su comportamiento no resulta tan satisfactorio como cabría esperar. Ante estas situaciones, la mejora de las codificaciones anteriormente mencionadas resulta necesaria a fin de proveer a estos métodos evolutivos de representaciones suficientemente versátiles, y consecuentemente, obtener los resultados deseados. Dependiendo del problema concreto que deba abordarse, los mencionados métodos deberán resultar modificados en un grado diferente. Un primer ejemplo de estos problemas especialmente difíciles de resolver se puede encontrar en el diseño de sistemas de respuesta de voz interactiva, que se han convertido en un componente fundamental de los centros de llamadas. Este tipo de sistemas son ampliamente utilizados por un gran número de empresas como medio para gestionar las relaciones con sus clientes. El fin de estos sistemas es proporcionar diferentes servicios y recursos, dependiendo de las preferencias expresadas por los usuarios a través de una serie de opciones. Teniendo en cuenta el funcionamiento de estos sistemas, se puede demostrar cómo la navegación guiada de cada cliente a través de los sucesivos menús puede ser descrita mediante un grafo con forma de árbol de servicios, cuyas hojas representan los recursos proporcionados. Dada la amplia variedad de servicios que este tipo de sistemas pueden ofrecer, la cantidad de hojas consideradas puede resultar significativamente alta (y equivalente al tamaño del árbol). Específicamente, es posible demostrar que dado un conjunto de L hojas en el sistema es suficiente considerar 2L-1 nodos en el árbol para modelar cualquier sistema coherente de este tipo. Entre los diferentes parámetros a optimizar que pueden abordarse en un sistema interactivo, el tiempo promedio de servicio es probablemente el más significativo. Consecuentemente, esta magnitud es la que se decidió emplear como medida de la calidad que cada sistema considerado exhibe. Efectuando ciertas suposiciones acerca de la duración de los mensajes que los usuarios de estos sistemas deberán escuchar, una primera formulación del problema a resolver es propuesta. Posteriores desarrollos sobre esta formulación matemática muestran la estrecha relación que dicho problema mantiene con la teoría de codificación de fuente, resultando equivalentes el diseño de un sistemas de respuesta de voz interactiva y el de un código fuente hasta cierto punto. Esta equivalencia permite aplicar en el diseño de centros de llamadas algunas importantes herramientas pertenecientes a la teoría de la información, como son el algoritmo de Huffman y el teorema de codificación de fuente, que respectivamente permitirán obtener un buen método determinista capaz de optimizar estos sistemas y un límite inferior para el tiempo de servicio promedio que cualquier centro considero podrá proporcionar. Comparando la estructura del problema con el tipo de árboles representados mediante cualquiera de las codificaciones anteriormente mencionadas se puede apreciar la existencia de un gran número de árboles equivalentes: aquellos codificados empleando cromosomas diferentes, pero asociados a una misma solución. La existencia de semejante cantidad de redundancia responde al hecho de que cualquiera de los métodos indicados contiene información acerca de qué posición concreta ocupa cada nodo. Sin embargo, desde el punto de vista de este problema, existen ciertos nodos cuya ubicación no resulta relevante, sino que los mismos se pueden intercambiar sin necesidad de modificar la solución global. En estas condiciones, ciertas mejoras pueden acometerse con el fin de reducir en la medida de lo posible las dimensiones del espacio de búsqueda correspondiente. Específicamente se han diseñado dos procedimientos diferentes de búsqueda local, capaces de mejorar considerablemente los resultados obtenidos. La utilidad de los procedimientos diseñados se comprueba sobre una amplia gama de experimentos diseñados artificialmente, consistentes en centros de llamadas provistos de diversas cantidades de servicios a ofrecer, cuyas probabilidades de demanda muestran distribuciones diferentes. Además, estos ejemplos permiten comparar distintas configuraciones del algoritmo evolutivo propuesto, relacionadas con la codificación de la solución, los operadores de cruce y mutación y el procedimiento de selección. A continuación, la mejor de dichas configuraciones se emplea en la optimización de sistemas de respuesta de voz interactiva reales, pudiéndose además considerar en nuestro algoritmo ciertas restricciones impuestas sobre dichos sistemas por parte de sus respectivos administradores, con el fin de agrupar algunos de los servicios ofrecidos de acuerdo a ciertos criterios. Respecto el segundo objetivo contemplado, éste aborda de modo aún más evidente el tratamiento de la información aportada por la apariencia que los diferentes árboles considerados muestran. Específicamente aquellos problemas de optimización orientados a la obtención de ciertos árboles que exhiban topologías concretas ocuparán los estudios contenidos en este segundo escenario, cuyo objetivo precisamente consistirá en el diseño de diferentes alternativas que permitan la correcta representación de las mencionadas topologías en la forma de cromosomas, sin que los mismos contengan información alguna acerca de las identidades concretas de aquellos nodos que ocupen ciertas ubicaciones en el árbol. Debido a la considerable dificultad que la simple enumeración de las diferentes topologías que a partir de cierto número de nodos pueden ser creadas, resultará imprescindible restringir el ámbito de estudio sobre un conjunto concreto de árboles, considerando únicamente aquellos de apariencia binaria dadas las particulares propiedades que los mismos poseen, las cuales les dota de enorme utilidad en diversas aplicaciones. Tras definir rigurosamente el concepto de topología que durante el mencionado estudio se empleará, se procede a evaluar la cantidad de diferentes topologías que empleando cierto número dado de nodos pueden ser construidas. Primeramente se presenta un método capaz de representar la totalidad de estas topologías de un modo considerablemente sencillo, a costa de introducir cierta redundancia en el espacio de búsqueda. Con el objetivo de subsanar dicho inconveniente se propone un segundo procedimiento, que si bien no resulta excesivamente laborioso en su utilización, requiere un detenido análisis que permita comprobar su validez. La correspondiente demostración acerca de la capacidad que dicho método muestra para representar correctamente la totalidad de topologías existentes, evitando la inclusión de redundancia en el espacio de búsqueda, completa dicho estudio.