Redes bayesianas para el ajuste de parámetros de algoritmos genéticos basados en problemas de satisfacción de restricciones geométricas

Resum

Dentro del Diseño Asistido por Computador, uno de los paradigmas que más desarrollo ha experimentado es el diseño basado en restricciones geométricas, En el núcleo de dicho paradigma se encuentra el Problema de la Satisfacción de Restricciones Geométricas (PSRG). El PSRG 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.) definen o no, un objeto rígido. La solución del PSRG, si existe, en general no es un único objeto, sino una familia de objetos, cada uno de los cuales es una instancia diferente construida con valores diferentes de los parámetros sobre los mismos elementos geométricos. Resulta que, cuando hay solución, el usuario espera que el sistema de resolución le proporcione una determinada distancia y no cualquier instancia del espacio de soluciones. Este problema se conoce como el Problema de Selección de la Solución Deseada. En su tesis doctoral, Luzón desarrolló diversos métodos novedosos para la selección de la solución deseada. Uno de ellos se basa en la aplicación de algoritmos genéricos para la búsqueda en el espacio de soluciones, espacio cuya cardinalidad es exponencial en relación con el número de elementos geométricos que componen el problema. Demostrada la idoneidad y efectividad de los algoritmos genéticos aplicados al problema de la selección de la solución deseada, sería interesante identificar como los diferentes parámetros de control que gobiernan el comportamiento de esta clase de algoritmos, afectan al problema que nos ocupa. El conocimiento de dichos efectos permitiría definir estrategias automáticas o semiautomáticas tales que, para un problema de satisfacción de restricciones geométricas dado, se fijasen las condiciones de operación del algoritmo genético, con la consiguiente aplicación práctica al Diseño Asistido por Computador. En este trabajo se pretende diseñar un sistema que proporcione valores óptimos de los parámetros que controlan la ejecución de un algoritmo genético y que, al mismo tiempo, tenga capacidad de adaptación conforme al sistema vaya recopilando más información sobre ejecuciones completadas de diversos algoritmos genéticos, aplicados a diferentes problemas de satisfacción de restricciones geométricas. Para alcanzar este objetivo se plantean dos fases bien diferenciadas. En una primera fase, se debe construir un modelo básico para el ajuste de parámetros de control de un algoritmo genético y un problema geométrico prefijados. Para alcanzar este objetivo, las Redes Bayesianas constituyen un formalismo adecuado puesto que, permiten expresar de forma gráfica el conocimiento explícito, permiten almacenar eficientemente los parámetros del modelo y permiten realizar tareas de inferencia. Asimismo, el mecanismo de aprendizaje Bayesiano permie adaptar el modelo de acuerdo con la experiencia adquirida. En una segunda fase, y dado que la interacción de los parámetros de control del algoritmo genético puede variar según se trate de un problema geométrico u otro, o también según se trate de un algoritmo genético u otro, se supone necesario integrar el sistema básico de ajuste automático de parámetros con una base de casos. Cada caso viene determinado por las características del problema geométrico y del algoritmo genético utilizado y de forma que, cada situación diferente pueda tratarse con un modelo (red Bayesiana) específico. En este sentido, la utilización de la metodología CBR (Case Base Reasoning) parece ser el mecanismo adecuado para llevar a cabo esta integración.