A Statistical Framework for Terminating Evolutionary Algorithms at their Steady State
David Roche Valles · 2015
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 tecnica iterativa basada en poblaciones de individuos e inspirada en las reglas de la evolucion natural para encontrar (o explorar) el conjunto de puntos, en un espacio de busqueda, que mejor se ajustan a una situacion dada de acuerdo con una funcion de coste. Delante de cualquier problema, en practicamente 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 tecnica de optimizacion si tenemos una funcion de coste que determine la bondad del ajuste. Como para cualquier tecnica iterativa, es esencial disponer de un criterio de parada. En el caso de los metodos de optimizacion, el algoritmo habria de parase en el momento en el que ha llegado a su estado estacionario y por tanto ya no se podran mejorar los resultados. Determinar la fiabilidad de las condiciones de parada de un algoritmo evolutivo es de gran importancia. Un criterio de parada debil o equivocado puede afectar negativamente tanto al esfuerzo computacional como al resultado final. En esta tesis introducimos un marco estadistico para determinar cuando una condicion 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 aproximacion numerica a los estados estacionarios para detectar el momento en el cual la poblacion de individuos del algoritmo evolutivo ha perdido su diversidad. Esta aproximacion se ha aplicado a diferentes metodos de computacion evolutiva que estan basados en la diversidad y a una seleccion de funciones que cubren las propiedades mas relevantes respecto a la convergencia de los algoritmos evolutivos. Los experimentos muestran que la condicion presentada funciona independientemente de la dimension del espacio de busqueda y del perfil de la funcion de coste. Tambien muestran que el metodo Differential Evolution (DE) figura como el mejor paradigma entre los algoritmos evolutivos para aplicar el metodo de parada. Por otra parte, utilizamos un modelo de regresion lineal para determinar los requisitos que aseguran que una medida derivada de la poblacion evolutiva del algoritmo evolutivo esta relacionada con la distancia al optimo en el espacio de busqueda. El marco teorico presentado se analiza para diferentes funciones de un conjunto de funciones marco y para dos criterios de parada estandar basados en la mejora del valor de la funcion de coste y en la distribucion en el espacio de busqueda de la poblacion de individuos para cada metodo de los algoritmos evolutivos. Los resultados validan el marco estadistico presentado como una buena herramienta para determinar la capacidad de una medida para parar el algoritmo evolutivo y selecciona la medida basada en la distribucion de la poblacion como la mas conveniente para aplicaciones en casos reales.