Un modelo de rendimiento de algoritmos evolutivos aplicados a la selección de la solución deseada

Resumo

Uno de los paradigmas más recientes y prometedores en el campo del Diseño Asistido por Computador es el denominado diseño basado en restricciones geométricas, El aspecto clave de este paradigma es el problema de satisfacción de restricciones geométricas, que consiste en decidir si un conjunto de elementos geométricos (puntos, segmentos de recta, etc.) relacionados mediante un conjunto de restricciones (distancias, ángulos, tangencias, etc.) define o no un objeto rígido. Por lo general la solución de este problema, si existe, no consiste en un único objeto sino en una familia de objetos, cada uno de los cuales es una instancia diferente construida sobre los mismos elementos. Todas y cada una de las instancias verifican las restricciones impuestas. Surge aquí un nuevo problema, el problema de la selección de la solución deseada, que puede ser definido como problema de optimización combinatoria y cuya resolución reviste gran complejidad debido a su NP-completitud. Entre los métodos efectivos para abordar la solución de los problemas de optimización combinatoria con mayores requerimientos computacionales destacan las Metaheurísticas. La obtención de un modelo para representar el rendimiento de las Metaheurísticas cuando son aplicadas para resolver problemas de grandes requerimientos computacionales es fundamental para determinar las garantías de calidad de solución frente al tiempo de ejecución disponible. La disponibilidad de este modelo es aún mas importante para tamaños considerables del problema. Presentación y marco del trabajo En el diseño basado en restricciones el usuario describe un objeto mediante la definición de un conjunto de elementos geométricos tales como puntos, segmentos de línea y segmentos circulares, y un conjunto de restricciones geométricas relativas a dichos elementos. La principal tarea de los sistemas de Diseño Asistido por Computador es comprobar si el conjunto de restricciones geométricas define de forma precisa el objeto y, en ese caso, determinar la posición y orientación de los elementos geométricos. Dado un problema geométrico bien definido y dada una asignación de valores a los parámetros de las restricciones, resolver el problema geométrico consiste en calcular las coordenadas de todos los puntos del objeto. Si se analiza desde una perspectiva matemática, cada restricción geométrica es una ecuación. Por lo tanto, resolver un sistema de restricciones geométricas consiste en resolver el correspondiente sistema de ecuaciones. Sin embargo, se obtienen sistemas de ecuaciones no lineales muy grandes, con múltiples soluciones, que por lo general resultan difíciles de tratar. Dado que se trata de un problema geométrico, resulta natural utilizar métodos geométricos para resolverlo. Los sistemas de resolución de restricciones geométricas constructivos permiten resolver el problema para una clase razonablemente grande de problemas geométricos. Estos sistemas transforman las restricciones originales en las coordenadas de los puntos usando únicamente un conjunto de herramientas, como por ejemplo regla y compás. Como resultado generan una secuencia simbólica de pasos constructivos básicos que, ejecutados adecuadamente, sitúan uno a uno todos y cada uno de los puntos del objeto. La realización de este algoritmo geométrico se denomina problema de contrucción geométrico. Cuando existe una solución, el usuario espera que el sistema de resolución de restricciones geométricas le proporcione una determinada instancia con unas características concretas, y no cualquier instancia del espacio de posibles soluciones. El problema de generar automáticamente la instancia esperada es conocido como el problema de la selección de la solución deseada. Uno de los métodos propuestos para abordar el problema de la selección de la solución deseada consiste en la definición de un conjunto de restricciones adicionales que el usuario desea que cumpla la solución a seleccionar. De esta forma, el problema puede ser formulado como un problema de optimización combinatoria cuya solución supone la maximización del número de restricciones adicionales. Sin embargo, tal problema presenta gran dificultad para su resolución debido a su NP-completitud y a la naturaleza interactiva subyacente a los sistemas de resolución de restricciones geométricas. Entre los métodos para abordar la solución de los problemas de optimización combinatoria con mayores requerimientos computacionales destacan las Metaheurísticas. En trabajos anteriores se aplicaron Algoritmos Genéticos para la resolución del problema de la selección de la solución deseada. Los algoritmos aplicados fueron tanto el Algoritmo Genético básico como Algoritmos Genéticos multimodales. Se demostró tanto la eficiencia como la efectividad de la aplicación de los Algoritmos Genéticos al problema. Por otra parte, el estudio de la optimización estadística de los parámetros que dirigen la evolución de los Algoritmos Genéticos, concretamente del Algoritmo Genético básico, en su aplicación al problema es descrita en. Se propone y contrasta una configuración óptima para cada tamaño del problema. En ambos estudios, los tamaños del problema analizados correspondían a espacios de búsqueda conocidos y que pueden ser generados para su estudio sin limitaciones temporales importantes. Con objeto de ampliar el abanico de Metaheurísticas a aplicar, estudios preliminares demostraron que los algoritmos más prometedores para el problema que tratamos correspondían claramente a las Metaheurísticas basadas en población: concretamente a los algoritmos CHC (Cross generational elitist selection Heterogeneous recombination and Cataclismic mutation) y PBIL (Population-Based Incremental Learning). Por otra parte, es importante analizar la capacidad de los algoritmos para enfrentarse a instancias del problema para las que el espacio de búsqueda sea desconocido y cuya resolución, en principio, supone un coste computacional inabordable. La obtención de un modelo para representar el rendimiento de las Metaheurísticas cuando son aplicadas para resolver problemas de grandes requerimientos computacionales es fundamental para determinar las garantías de calidad de solución frente al tiempo de ejecución disponible. La disponibilidad de este modelo es aún mas importante para tamaños considerables del problema. La caracterización previa del comportamiento de un algoritmo puede proporcionar una idea del efecto de su aplicación. Ello ayudará a decidir cuál será su utilidad, de modo parcial o completo, en la resolución del problema de la selección de la solución deseada en función de los requerimientos del usuario.