Metodología de optimización de los parámetros de control de un algoritmo genético

Abstract

En este trabajo se presenta una metodología para la sintonización simultánea de los parámetros de control de un algoritmo genético, enfocada a la reducción del número de generaciones empleadas por el algoritmo para encontrar un óptimo. La metodología incluye un meta-algoritmo genético en combinación con una superficie de regresión por vectores de soporte que reduce la demanda computacional inherente al método del meta-algoritmo. Cada elemento que compone la metodología fue escogido de forma que cuente con sustento suficiente para la sintonización de sus propios parámetros de control y se cumpla con el propósito principal de este trabajo que es la automatización del proceso de selección de los parámetros de control, sin generar parámetros adicionales. El algoritmo genético de alto nivel incorpora técnicas de generación de nichos para aumentar la exploración del espacio de búsqueda. El método utilizado para la definición de los nichos es uno de los principales aportes de este trabajo, así como una novedosa técnica de apareamiento restringido. La optimización de los parámetros de control del algoritmo genético de bajo nivel, es planteada como un problema de optimización sujeto a restricciones, para lo cual se plantea una nueva forma de penalización estática que no requiere el ajuste de coeficientes de penalización. Las pruebas y resultados presentados incluyen la sintonización de los tres parámetros de control fundamentales de un algoritmo genético: la probabilidad de mutación, la probabilidad de cruce y el tamaño de la población inicial. Además, se sintoniza un parámetro adicional como un ejemplo de los parámetros resultantes al incluir otros operadores especiales, en este caso, un método de escalamiento de calidad. Cada prueba fue desarrollada sobre un conjunto de ocho funciones de evaluación comparativa (benchmarking) que incluye casos continuos, discontinuos, convexos, no convexos, unimodales, multimodales, cuadráticos, no cuadráticos, de baja y de alta dimensionalidad, determinísticos y no determinísticos / Abstract: A methodology for simultaneous tuning of the control parameters of genetic algorithms is presented. This methodology is focused on reducing the number of generations the algorithm takes to find an optimal solution. The inherent computational costs due to the meta-algorithm are reduced by incorporating a support vector regression that models the interactions among genetic algorithm parameters. Each element in the methodology was selected in such a way that its theoretical background provides the sufficient basis for tuning its own parameters and thus, we can achieve the automatic tuning of control parameters in genetic algorithms, without adding new parameters, which is the main purpose of this work. The high level genetic algorithm was designed encompassing niche and speciation techniques, in order to increase exploration in the search space. The method for locating the niches and a novel restricted mating procedure are two of the mayor contributions of this work. Parameter optimization of low level genetic algorithm is viewed as a restricted optimization problem, which is solved by a novel static penalization method with no penalty coefficients. The results include tuning of the three main parameters: mutation probability, recombination probability and size of the initial population. In addition, an extra parameter for fitness scaling is included, as an example of parameters resulting from the application of special operators. Each test was developed over a set of eight benchmark functions, including continuous, discontinuous, convex, non-convex, unimodal, multimodal, quadratic, non-quadratic, low dimensional, high dimensional, deterministic and nondeterministic functions.