Búsquedas genéticasmétodos de optimización global y optimización combinatoria

Résumé

Esta tesis se enmarca en la aplicación de algoritmos genéticos a la optimización de funciones tanto en el ámbito de variables continuas como en los problemas de optimización combinatoria, En particular, se establecerán diversas estrategias basadas en sucesivas búsquedas acotadas, que permitan evolucionar al algoritmo hacia el óptimo de la función a optimizar, tomando como base los algoritmos genéticos. En concreto, se han diseñado las siguientes estrategias: 1) En el ámbito de variables continuas: a) Búsqueda Lineal Genética trata de extender los tradicionales métodos de optimización que usan Búsqueda Lineal, permitiendo explorar la dirección de búsqueda en un intervalo mucho más amplio y que incluye incluso la rama de valores negativos. Dicha Búsqueda Lineal Extendida se realiza mediante un sencillo AG unidimensional. b) Búsqueda Genética en Cajas corresponde a una estrategia de resolución de sucesivos problemas acotados, centrados en torno a óptimos locales obtenidos mediante un AG multidimensional y que usa una función de evaluación con memoria. 2) En el ámbito de variables discretas: a) Búsqueda Genética en Vecindades es una adaptación de la Búsqueda Genética en Cajas al problema combinatorio. De modo que, se desarrollarían sucesivos problemas acotados, centrándonos en torno a la búsqueda de un óptimo local dentro de la vecindad del punto inicial. b) Búsqueda Genética de Mutantes permite generar de forma automática mutantes de programas originales en el ámbito de las pruebas del software, y más en concreto en la técnica de mutaciones. Este algoritmo se integra dentro de la herramienta GAmera que permite automatizar el proceso de pruebas de mutaciones para composiciones de servicios en WS-BPEL 2.0 mediante el empleo de un AG. Una de las características de esta propuesta es la optimización del número de mutantes a generar, de manera que no se generarán todos los posibles mutantes, sin pérdida significativa de información. También permite etectar mutantes potencialmente equivalentes, así como medir la calidad de los casos de prueba. Para evaluar la calidad de las estrategias desarrolladas, no sólo se aplicarán a funciones clásicas en la optimización de funciones, sino que se emplearán en la búsqueda de soluciones en problemas actuales. Así, en el ámbito de la optimización de variables continuas las estrategias desarrolladas se aplicarán al entrenamiento de redes neuronales. En el caso de optimiza ción combinatoria se resolverá, por un lado el problema del viajante que engloba a numerosos problemas de producción, y por otro lado, en el ámbito de las pruebas del software, y más en concreto en la prueba de mutaciones, se desarrollará una estrategia para la generación automática de mutantes.