نبذة مختصرة : El objetivo de esta tesis es de determinar la calidad de las condiciones de parada existentes para terminar un Algoritmo Evolutivo cuando llegue a su un estado estacionario. Un Algoritmo Evolutivo es una técnica iterativa basada en poblaciones de individuos e inspirada en las reglas de la evolución natural para encontrar (o explorar) el conjunto de puntos, en un espacio de búsqueda, que mejor se ajustan a una situación dada de acuerdo con una función de coste. Delante de cualquier problema, en prácticamente todas las situaciones, se necesita explorar un conjunto de posibles soluciones donde cada una de ellas se puede evaluar. Por tanto, los Algoritmos Evolutivos se pueden entender como una técnica de optimización si tenemos una función de coste que determine la bondad del ajuste. Como para cualquier técnica iterativa, es esencial disponer de un criterio de parada. En el caso de los métodos de optimización, el algoritmo habría de parase en el momento en el que ha llegado a su estado estacionario y por tanto ya no se podrán mejorar los resultados. Determinar la fiabilidad de las condiciones de parada de un algoritmo evolutivo es de gran importancia. Un criterio de parada débil o equivocado puede afectar negativamente tanto al esfuerzo computacional como al resultado final. En esta tesis introducimos un marco estadístico para determinar cuándo una condición de parada es capaz de parar el Algoritmo Evolutivo en el momento en el que llegue a su estado estacionario. Por una parte, se presenta una aproximación numérica a los estados estacionarios para detectar el momento en el cual la población de individuos del algoritmo evolutivo ha perdido su diversidad. Esta aproximación se ha aplicado a diferentes métodos de computación evolutiva que están basados en la diversidad y a una selección de funciones que cubren las propiedades más relevantes respecto a la convergencia de los algoritmos evolutivos. Los experimentos muestran que la condición presentada funciona independientemente de la dimensión del espacio de búsqueda y del perfil de la función de coste. También muestran que el método Differential Evolution (DE) figura como el mejor paradigma entre los algoritmos evolutivos para aplicar el método de parada. Por otra parte, utilizamos un modelo de regresión lineal para determinar los requisitos que aseguran que una medida derivada de la población evolutiva del algoritmo evolutivo está relacionada con la distancia al óptimo en el espacio de búsqueda. El marco teórico presentado se analiza para diferentes funciones de un conjunto de funciones marco y para dos criterios de parada estándar basados en la mejora del valor de la función de coste y en la distribución en el espacio de búsqueda de la población de individuos para cada método de los algoritmos evolutivos. Los resultados validan el marco estadístico presentado como una buena herramienta para determinar la capacidad de una medida para parar el algoritmo evolutivo y selecciona la medida basada en la distribución de la población como la más conveniente para aplicaciones en casos reales.
Processing Request
No Comments.