Algoritmos genéticos aplicados a la resolución de problemas de optimización

1

Algoritmos Genéticos aplicados a la resolución de problemas de optimización
Luis Marco Giménez lmarcogimenez@gmail.com http://www.luismarco.nom.es

R ESUMEN Los Algoritmos Genéticos, como paradigma principal de la computación evolutiva, presentan una alternativa a los procedimientos tradicionales de búsqueda y optimización como métodos sistemáticos para la resolución de estos problemas.En concreto, y en el ámbito de este trabajo, los algoritmos genéticos se han aplicado con buenos resultados en problemas de optimización en los que se desea localizar los máximos o mínimos de una función matemática determinada. La solución desarrollada en ese trabajo, SIGENOF -Sistema Genético para la Optimización de Funciones-, consiste en la implementación de un algoritmo genético para laoptimización de una amplia variedad de funciones matemáticas de las que se desea localizar sus máximos globales. Esta herramienta permite, a través de un sencillo e intuitivo interfaz gráfico de usuario, la introducción de la función a optimizar junto con los parámetros que guiarán la ejecución del algoritmo genético, representación gráfica de las mejores soluciones localizadas por la herramienta, así comola generación de ficheros con los resultados de la ejecución que permiten realizar un análisis posterior de las soluciones encontradas. PALABRAS CLAVE Algoritmo Genético, Aptitud, Búsqueda ciega, Búsqueda estocástica, Computación Evolutiva, Cromosoma, Cruce, Elitismo, Evolución biológica, Gen, Individuo, Maximización, Mutación, Optimización, Población, Reproducción, Selección, Solución. A BSTRACTGenetic Algorithms, as a major main paradigm of evolutional computation, present a good alternative to traditional procedures of searching and optimizing as systematic methods for the resolution of this kind of problems. Genetic algorithms have been applied with good results in optimizing problems where the objective is to obtain the maximus or minimus about a mathematical function. Theimplemented tool for this work, SIGENOF -Sistema Genético para la Optimización de Funciones- (Genetic System for the Optimization Functions), consists in the implementation of a genetic algorithm for the optimization of a wide variety of mathematical functions of which we want to obtain their local maximums. This tool permits, with its easy and intuitive graphical user interface allowing, among othersfunctions, the input of the function to be optimized, the parameters of the genetic algorithm that

will guide its execution, a graphical representation of the best solutions founded by the tool, and a generation of files within the execution’s results that will allow a further analysis of the found solutions.

K EYWORDS Genetic Algorithm, Fitness, Blind search, Stochastic search, EvolutionaryComputation, Chromosome, Crossover, Elitism, Biological evolution, Gen, Individual, Maximization, Mutation, Optimization, Population, Reproduction, Selection, Solution.

I.

I NTRODUCCIÓN

La Computación Evolutiva presenta un enfoque alternativo a los algoritmos tradicionales para abordar problemas complejos de búsqueda y aprendizaje a través de modelos computacionales de procesos evolutivos,cuyo principal objetivo consiste en guiar una búsqueda estocástica haciendo evolucionar a un conjunto de estructuras, y seleccionando, de modo iterativo, las más adecuadas. Son cuatro los paradigmas fundamentales de la computación evolutiva: Los Algoritmos Genéticos. Hacen evolucionar a una población, tradicionalmente de enteros binarios, sometiéndolos a transformaciones unitarias y binariasgenéricas, junto a un proceso de selección. Los Programas Evolutivos. Hacen evolucionar a una población de estructuras de datos sometiéndolas a una serie de transformaciones específicas y a un proceso de selección. Las Estrategias Evolutivas. Hacen evolucionar a una población de números reales que codifican las posibles soluciones de un problema numérico y los tamaños de salto. La selección es implícita....