A Statistical Framework for Terminating Evolutionary Algorithms at their Steady State

July 24, 2015 at 12:00 pm by

Thesis Supervisor: Dr. Debroa Gil

Place: Computer Vision Centre at Lecture Room.

Dr. Daniela Zaharie. Faculty of Mathematics and Computer Science. West University of Timisoara Timisoara, Romania.
Dr. Oriol Ramos Terrades. Departament Ciències de la Computació and Computer Vision Centre, UAB. Bellaterra. Catalunya. Spain.
Dr. José Ignacio Fernández de Trocóniz Fernández. Departamento de Farmacia y Tecnología Farmacéutica. Universidad de Navarra. Pamplona. Navarra. Spain.

As any iterative technique, it is a necessary condition a stop criterion for terminating Evolutionary Algorithms (EA). 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 EAs is of prime importance. A wrong or weak stop criterion can negatively a ect both the computational e ort and the nal 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 di erent 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 Di erential Evolution (DE) arises as the best 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 xspace.
Our theoretical framework is analyzed across several benchmark test functions and two standard termination criteria based on function improvement in f-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.


Watch the Video Presentation