Statistical framework for terminating evolutionary algorithms at their steady state

Abstract

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.

The goal of this Thesis is assessing the quality of existing stopping conditions for terminating Evolutionary Algorithms at its steady state. An Evolutionary Algorithm (EA) is an iterative population based technique based on natural evolution rules principles to find (or explore) in a given search space the set of point that best fits a given real situation according to a cost function. When a problem is presented in practically all situations, an exploration of a set of possible solutions is needed and for each possible solution its goodness is valuable. EAs can be viewed as an optimization technique if a function is given. As any iterative technique, a stop criterion for terminating EA numeric implementation is mandatory. In the case of optimization methods, the algorithm should stop at the time it has reached a steady state so it can not improve results anymore. Assessing the reliability of termination conditions for evolutionary algorithms is of prime importance. A wrong or weak stop criterion can negatively affect both the computational effort and the final result. In this Thesis, we introduce a statistical framework for assessing whether a termination condition is able to stop EA at its steady state. In one hand a numeric approximation to steady states to detect the point in which EA population has lost its diversity has been presented for EA termination. This approximation has been applied to different EA paradigms based on diversity and a selection of functions covering the properties most relevant for EA convergence. Experiments show that our condition works regardless of the search space dimension and function landscape and Differential Evolution (DE) arises as the best EA paradigm. On the other hand, we use a regression model in order to determine the requirements ensuring that a measure derived from EA evolving population is related to the distance to the optimum in x-space. Our theoretical framework is analyzed across several benchmark test functions and two standard termination criteria based on function improvement in function space and EA population x-space distribution for the DE paradigm. Results validate our statistical framework as a powerful tool for determining the capability of a measure for terminating EA and select the x-space distribution as the best-suited for accurately stopping DE in real-world applications.