Búsquedas Genéticas: Métodos de optimización global y optimización combinatoria

Abstract

Esta tesis se enmarca en la aplicación de AGs 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. Por tanto, los objetivos a conseguir en esta tesis son diseñar y validar diversas estrategias de resolución de problemas de optimización continua, por un lado, y de optimización combinatoria, por otro, mediante métodos evolutivos diversos, que toman como base los AGs. Las aportaciones de la tesis consiste en el desarrollo de cuatro estrategias de optimización: En el ámbito de variables continuas: 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ú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. En el ámbito de variables combinatorias: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úsqueda Genética deMutantes 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 enWS-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.