Algoritmo genetico
Un algoritmo genético (GA por el inglés Genetic Algorithm) es una técnica de busca utilizada en informática para encontrar soluciones aproximadas a problemas de optimización y búsqueda. Los algoritmos genéticos son una clase particular de algoritmos evolutivos que utilizan técnicas inspiradas por la evolución biológica cómo herencia, mutación, selección, y cruce (también denominado recombinación).
Los algoritmos genéticos se implementan típicamente como una simulación informática en la cual una población de representaciones abstractas (denominadas cromosomas) de soluciones candidatas (denominadas individuos) a un problema de optimización evoluciona hacia mejores soluciones. Tradicionalmente, las soluciones se representan como series binarias de 0s y 1s, pero las codificaciones diferentes son también posibles. La evolución empieza desde una población de individuos completamente aleatorios y pasa en diferentes generaciones. En cada generación, la adecuación de la población entera se evalúa, se seleccionan múltiples individuos de manera estocástica de la población actual (basada en su adecuación), y se modifican (haciendo mutar o recombinar) para formar una nueva población. La nueva población se utiliza en la siguiente iteración del algoritmo.
Tabla de contenidos |
Proceso de un GA
Se requieren dos cosas para definir un algoritmo genético típico: (1) una representación genética de las soluciones, (2) una función de adecuación para evaluarlas.
La representación estándar es un vector de bits. Vectores de otros tipos y estructuras diferentes se pueden utilizar esencialmente del mismo modo. La propiedad principal que hace convenientes estas representaciones genéticas es que sus partes se alinean fácilmente debido a su medida fija, que facilita la operación de cruce simple. También se utilizaban representaciones de largura variables, pero la aplicación de cruce es más compleja en este caso. Las representaciones de tipo árbol son exploradas en la programación genética y las representaciones de forma libre se exploran en algoritmos genéticos asistidos por humanos (HBGA del inglés Human-based Genetic Algorithm).
La función de adecuación se define sobre la representación genética y mide la calidad de la solución representada. La función de adecuación siempre depende del problema a tratar. Por ejemplo, en el problema de la mochila queremos maximizar el valor total de los objetos que podemos poner en una mochila de una capacidad fija. Una representación de una solución podría ser un vector de bits, dónde cada bit representa un objeto diferente, y el valor del bit (1 o 0) representa si el objeto está o no en la mochila. No cualquier representación es válida, porque la cantidad de objetos puede exceder la capacidad de la mochila. La adecuación de la solución es la suma de valores de todos los objetos a la mochila si la representación es válida, o 0 de lo contrario. En algunos problemas, es difícil o incluso imposible definir la expresión de adecuación, en estos casos se utilizan algoritmos genéticos interactivos (IGA del inglés Interactive Genetic Algorithm).
Una vez tenemos la representación genética y la función de adecuación definidas, el GA procede a inicializar la población de soluciones de manera aleatoria, entonces la mejora a través de un proceso repetitivo de mutación, cruce y selección.
Inicialitzación
Inicialmente muchas soluciones individuales se generan aleatoriamente para formar una población inicial. La medida de población depende de la naturaleza del problema, pero típicamente contiene unos cuántos centenares o miles de soluciones posibles. Tradicionalmente, la población se genera aleatoriamente, cubriendo la gama entera de soluciones posibles (el espacio de búsqueda). Ocasionalmente, las soluciones se pueden "sembrar" en áreas dónde es probable que se encuentren soluciones óptimas.
Selección
En cada sucesiva generación, una proporción de la población existente se selecciona para engendrar una nueva generación. Se seleccionan soluciones individuales a través de un proceso basado en la adecuación, dónde las soluciones más adecuadas (tal y como mide la función de adecuación) tienen típicamente más posibilidades de ser elegidas. Algunos métodos de selección evalúan la adecuación de cada solución y seleccionan de forma preferente las mejores soluciones. Otros métodos evalúan sólo una muestra de la población, porque este proceso consume mucho tiempo.
La mayoría de las funciones son estocásticas y se diseñan de forma que una proporción pequeña de soluciones menos aptas también se seleccionan. Esto ayuda a mantener la diversidad de la población grande, evitando convergencia prematura en soluciones pobres. Los métodos de selección populares y bien estudiados incluyen selección de ruleta y selección de torneo.
Reproducción
El siguiente paso es generar una segunda generación de la población de soluciones a partir de aquellas seleccionadas a través de los operadores genéticos: cruce (o recombinacion) y mutación.
Para cada solución nueva que debe ser producida, un par de soluciones "padre" se selecciona para criar desde la selección previa. Produciendo una solución "hijo" que utiliza los métodos citados de cruce y mutación, se crea una solución nueva que típicamente comparte muchas de las características de sus "padres". Los padres nuevos se seleccionan para cada hijo, y el proceso continúa hasta que una población nueva de soluciones de medida apropiada se genere.
Estos procesos generan la próxima población de generación de cromosomas que es diferente de la generación inicial. Generalmente la adecuación media habrá aumentado para la población, puesto que sólo los mejores organismos desde la primera generación se seleccionan para criar, junto con una proporción pequeña de soluciones menos aptas, por razones ya mencionadas arriba.
Finalización
Este proceso de generación se repite hasta que se llega a una condición de finalización. Condiciones de finalización comunes son
- Se ha encontrado una solución que satisface un criterio mínimo
- Se ha llegado a un número de generaciones fijados
- Se acaba el presupuesto (tiempo computacional/dinero)
- La solución con la mejor adecuación ha llegado a una meseta de tal manera que cada iteración sucesiva ya no produce mejores resultados
- Inspección manual
- Combinaciones de los anteriores
Algoritmo en pseudo-código
Escoger la población inicial Repetir Evaluar la adecuación individual de ciertas porciones de la población Seleccionar padres de individuales según la mejor adecuación para reproducir Generar una nueva generación a través del cruce y la mutación hasta la condición de finalización
Genetic algorithm. (2006, June 6). In Wikipedia, The Free Encyclopedia. Retrieved 01:36, June 13, 2006, from http://en.wikipedia.org/w/index.php?title=Genetic_algorithm&oldid=57239835.