Optimización evolutiva de los parámetros de control de un algoritmo genético

• Autores: José Ángel Fernández Prieto
• Directores de la Tesis: Juan Ramón Velasco Pérez (dir. tes.) , Luis Magdalena Layos (codir. tes.)
• Lectura: En la Universidad de Alcalá ( España ) en 2009
• Idioma: español
• Tribunal Calificador de la Tesis: Daniel Meziat Luna (presid.) , Sancho Salcedo Sanz (secret.) , Manuel Lozano Márquez (voc.) , Óscar Cordón García (voc.) , Sebastián García Galán (voc.)
• Enlaces
  • Tesis en acceso abierto en: e_Buah
• Resumen
  • español

    El comportamiento de un Algoritmo Genético viene determinado, en gran medida, por los parámetros que utiliza, como son: el tamaño de la población y las probabilidades de selección, cruce y mutación. Sin embargo, no existe una regla general mediante la cual se puedan seleccionar los parámetros apropiados para cada tipo de problema. En unos casos, se utilizan los valores recomendados en la literatura, mientras que en otros, su elección representa un problema de prueba y error. Además, distintos autores argumentan que estos valores no deben ser fijos durante la ejecución del algoritmo ya que es un proceso intrínsecamente dinámico y adaptativo.

    En esta tesis doctoral se propone un sistema de optimización de parámetros que combina dos de las técnicas recogidas en la literatura para mejorar el comportamiento de un Algoritmo Genético: la meta-evolución y la adaptación de parámetros. Con el objeto de validar el sistema propuesto, este ha sido aplicado sobre los siguientes Algoritmos Genéticos, los cuales utilizan distintos tipos de codificación:

    1.Algoritmo Genético con codificación binaria, con el objetivo de minimizar un conjunto de seis funciones representativas.

    2.Algoritmo Genético con una codificación híbrida, binaria y real, de un sistema borroso-genético basado en el enfoque de Pittsburgh.

    3.Algoritmo Genético con codificación real, el cual se encuentra integrado con un simulador de redes de comunicaciones, con el objeto de comprobar el funcionamiento en un sistema real: un protocolo de comunicaciones en una red.

    Por último, se ha comprobado el comportamiento de los distintos algoritmos al utilizar los parámetros hallados por el sistema propuesto. Los resultados se han comparado con los obtenidos por los principales métodos de adaptación de parámetros. Además, se han llevado a cabo diversos tests estadísticos para averiguar si existen diferencias significativas entre los resultados obtenidos.

  • English

    The behavior of a Genetic Algorithm is determined by the control parameter settings, such as selection probability, crossover probability, mutation probability and population size. Nevertheless, there are no standard rules for choosing appropriate values for these parameters. This decision is usually taken in terms of the most common values or experimental formulas given in literature, or by means of trial an error methods. Furthermore, any authors give arguments that any static set of parameters, having the values fixed during an Genetic Algorithm, seems to be inappropriate; a Genetic Algorithm is an intrinsically dynamic, adaptive process.

    This Ph. D. Thesis propose an approach based on a meta-level GA combined with an adaptation strategy of the GA control parameters to find and adjust the best control parameters to improve the GA performance. In order to validate the approach, it have been applied to three Genetics Algorithms which use different coding schemes to solve different types of optimization problems, such as:

    1. a binary-coded Genetic Algorithm. The objective of this algorithm is to minimize six frequently used test functions.

    2. a hybrid-coded (binary and real) Genetic Algorithm, which belong to a Genetic Fuzzy Rule-Based System based on the Pittsburgh approach.

    3. a real-coded Genetic Algorithm, which is integrated with a network simulator to verify the network protocol performance. In this case, the algorithm aims at generating the worst case traffic for the protocol under analysis.

    Finally, different comparisons are performed, aiming to assess the acceptable optimization power of the proposed system. The results have been compare with the ones obtained for other methods for changing the values of parameters. Moreover, a statiscal analysis have been done to ascertain if differences are significant between the proposed system and the other algorithms.