Characterizing the performance of evolutionary algorithms to solve continuos optimization problems

Abstract

In the field of Evolutionary Algorithms (EA), what does constitutes a hard optimization problem?, why certain optimization problems are more difficult to solve? The answers to these questions can provide useful information, e.g., the prediction of the success of EA. In order to predict the success of EA many approaches have been developed; being the study of Fitness Landscape (FL) one of the most successful. Basically, FL is the geometric form depicted by the cost function of optimization problems; the FL can be computed by means of metrics to measure, e.g., the rate of ruggedness, neutrality, basins of attraction, among others. Fitness Landscape Analysis uses a set of metrics for the FL characterization: features of problems can be measured by descriptive metrics, while the dynamic metrics are more related to the features of the algorithm. This contribution presents a procedure called Performance Classification Models (PCM), which creates models to predict the performance exhibited by Genetic Algorithms (GA) in the solution of optimization problems in continuous domains. PCM classifies the performance in two classes (easy and difficult). The dataset has FL features as predictor variables, and the performance exhibited by GA as the target variable. The problems used in experiments are benchmark optimization functions. A product of PCM, is a procedure to Recommend Population Size (RPS): given an optimization problem, RPS recommends the minimal population size to get an acceptable level of performance. This work can be easily extended to use other metrics, it can be applied to different set of problems, or use other EA. Developing performance models for other EA, can lead to the solution of an instance of the algorithm selection problem.

En el campo de Algoritmos Evolutivos (AE), ¿qué constituye un problema de optimización difícil?, ¿por qué ciertos problemas de optimización son más difíciles de resolver? Las respuestas a estas preguntas pueden proveer información importante, por ejemplo, la predicción del éxito de los AE. Para predecir el éxito de los AE muchos enfoques han sido desarrollados; siendo el estudio de Fitness Landscape (FL) uno de los más exitosos. Básicamente, FL es la forma geométrica representada por la función de costo de los problemas de optimización; el FL puede ser calculado de métricas para medir, por ejemplo, la tasa de rugosidad, neutralidad, cuencas de atracción, entre otras. Fitness Landscape Analysis usa un conjunto de métricas para la caracterización del FL: las características de los problemas se pueden medir por medio de métricas descriptivas, mientras que las métricas dinámicas están más relacionadas a las características del algoritmo. Esta contribución presenta un procedimiento llamado Modelos de Clasificación de Rendimiento (PCM) el cual crea modelos para predecir el rendimiento exhibido por los Algoritmos Genéticos (AG) en la solución de problemas de optimización en dominios continuos. PCM clasifica el rendimiento en dos clases (fácil o difícil). El conjunto de datos tiene características del FL como variables predictoras, y el rendimiento exhibido por el AG como variable objetivo. Los problemas usados en los experimentos son funciones de optimización de referencia. Un producto de PCM, es un procedimiento para Recomendar Tamaño de Población (RPS): dado un problema de optimización, RPS recomienda la población mínima para obtener un nivel eficiente de rendimiento. Este trabajo puede ser fácilmente extendido para usar otras métricas, se puede aplicar a un conjunto diferente de problemas, o usar otro AE. El desarrollo de modelos de rendimiento para otros AE, puede llevar a la solución de una instancia del problema de selección de algoritmo.