META-EVOLUCIÓN PARALELA PARA LA ASIGNACIÓN DE PARÁMETROS Y OPERADORES EN ALGORITMOS EVOLUTIVOS
Resumen
Se presenta una herramienta diseñada para seleccionar operadores (cruce y mutación) y entonar parámetros de control de algoritmos evolutivos (tamaño de la población, probabilidad de cruce y probabilidad de mutación). Esta herramienta fue concebida con un enfoque de meta-evolución: en el nivel superior, un algoritmo genético optimiza a un programa evolutivo, ubicado en el nivel inferior. Dado el volumen de cómputo que esto puede implicar, se implementó una configuración paralela maestro-esclavo, utilizando MPICH2. Los resultados experimentales confirman la validez y generalidad de esta herramienta.
Descargas
Citas
Asensio-Cuesta, S.; Diego, J. y Alcaide-Marzal, J. (2009). Metodología para la generación de agendas de rotación de puestos de trabajo desde un enfoque ergonómico mediante algoritmos evolutivos. Tesis Doctoral no publicada, Universidad Politécnica de Valencia. España.
Back, T. (1994,). Parallel Optimization of Evolutionary Algorithms. InParallel Problem Solving from Nature-PPSN III: International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature, Jerusalem, Israel, Octubre.
Back, T. y Schwefel, H. (1993). An overview of Evolutionary Algorithms for Parameter Optimization. Evolutionary Computation, Vol. 1, Núm. 1, Pp. 1-23.
Bäck, T.; Fogel, D. y Michalewicz, Z. (1997). Handbook of evolutionary computation. USA. Institute of Physics Publishing and Oxford. University Press, Bristol and New York.
Caballero, R.; Molina, J.; Luque, M.; Torrico, A. y Gomez, T. (2002). Algoritmos genéticos para la resolución de problemas de programación por metas entera. Aplicación a la Economía de la Educación. Documento en línea. Disponible en: http://www.uv.es/asepuma/X/J01C.pdf. Consulta: 12-01-2013.
Candidato Nro. 73390, (2002). Measuring the effect of population size in the efficiency of a genetic algorithm. Curso de Vida Artificial, En: Cognitive and Computing Sciences, Universidad de Sussex.
De Jong, K. (1975). An Analysis of the behaviour of a class of genetic adaptative systems. PhD thesis. Universidad de Michigan. USA.
Djordjalian, A. (s.f.). Programas de Evolución y Algoritmos Genéticos. Documento en línea. Disponible en: http://indicart.com.ar/ga/epyga.htm . Consulta: 05/01/2012.
Dorigo, M. y Gambardella, L. (1996). Ant colonies for the traveling salesman problem. Documento en línea. Disponible en: http://www.idsia.ch/~luca/acs-bio97.pdf. Consulta: 20/07/2012.
Eilon, S.; Watson-Gandy C. y Christofides, N. (1969). Distribution management: mathematical modeling and practical analysis. Operational Research Quarterly, Núm. 20, Pp. 37–53.
Fogel, D. (1988). An evolutionary approach to the travelling salesman problem. Biological Cybernetics, Vol. 60, Núm. 2, Pp. 139-144.
Freisleben, B. (1997). Handbook of Evolutionary Computation. USA. Oxford University Press.
Goldberg, D. (1989). Genetic algorithms in search, optimization and machine learning. Documento en línea. Disponible: http://download.springer.com/static/pdf/580/art%253A10.1023%252FA%253A1022602019183.pdf?auth66=1387123803_d485244feb91867e1b8197d84878d365&ext=.pdf. Consulta: 20/07/2012.
Gómez, J. y Cantor, G. (2008). Asignación de parámetros en los algoritmos evolutivos. Revista RE´TAKVN de la Facultad de Ingeniería de la Universidad del Magdalena, Vol. 1, Núm. 1, Pp. 60-67.
Grefenstette, J. (1986). Optimization of control parameters for genetic algorithms. IEEE Transactions on Systems, Man and Cybernetics, Vol. 16, Núm. 1, Pp. 122-128.
Hart, W. y Bellew, R. (1991). Optimizing an arbitrary function is hard for the genetic algorithm. Proceedings of the 4th conference on Genetic Algorithms, Pp. 190-195.
Hernández, J.; Ramírez, M. y Ferri, C. (2008). Introducción a la minería de datos, España. Pearson Prentice Hall.
Herrera, F.; Lozano, M. y Verdegay, J. (1994). Algoritmos genéticos: fundamentos, extensiones y aplicaciones, ARBOR CLII 597, Pp. 9-40.
Holland, J. (1975). Adaptation in natural and artificial systems. USA. University of Michigan Press.
Jaramillo, J. (2007). Metodología de optimización de los parámetros de control de un algoritmo genético. Documento en línea. Disponible en: http://www.bdigital.unal.edu.co/3348/. Consulta: 20/07/2012.
Koza J. (1992). Genetic programming: on the programming of Computers by means of natural selection, MIT Press, Cambridge, Massachusetts, London.
Mernik, M.; Crepinsek, M. y Zumer, V. (2000). A meta evolutionary approach in searching of the best combination of crossover operators for the tsp. Neural Networks Nn'2000: Proceedings of the lasted International Conference. Pittsburgh, Pennsylvania. USA.
Michalewicz, Z. (1992). Genetic Algorithms + Data Structures = Evolution Programs. USA. Springer-Verlag.
Nesmachnow, S. (2002). Evolución en el diseño y la clasificación de Algoritmos Genéticos Paralelos. XXVIII Conferencia Latinoamericana de Informática. Montevideo, Uruguay.
Oliver, I.; Smith, D. y Holland, J. (1987). A study of permutation crossover operators on the travelling salesman problem. Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application. Cambridge, Reino Unido.
Orozco, M. (2004). Optimización de los parámetros de control del algoritmo genético simple usando regresión de vectores soporte. IX Simposio de Tratamiento de Señales, Imágenes y Visión Artificial. Colombia.
Rivas, J.; Perozo, F.; Rodríguez, R. y Tineo L. (2012). Una herramienta de meta-evolución paralela para la entonación de programas evolutivos. Revista Tekhné, Vol. 15, Pp. 15-19.
Rodríguez, C. y Díaz, I. (2009). Los Algoritmos Genéticos. Introducción a la inteligencia artificial. E.U.I.T. Informática de Gijón. Universidad de Oviedo, Principado de Asturias, España.
Schwefel, H. (1995). Evolution and Optimum Seeking. Documento en línea. Disponible en: http://ls11-www.cs.uni-dortmund.de/lehre/wiley/preface.pdf. Consulta: 20/07/2012.
