Algoritmo genético
| ||||||
Algoritmo Genético. Durante los años 70, con el fin de abstraer y explicar los procesos de adaptación en sistemas naturales, así como diseñar un sistema artificial que por medio de softwares emulara con los mecanismos de los sistemas naturales, se conoció a esta técnica y que se hizo popular con el nombre de “algoritmos genéticos”. A partir de ese momento surge un importante grupo de investigadores que se dedicó a lo que hoy día constituye el campo de desarrollo y aplicación de los algoritmos genéticos.
Sumario
Principales elementos
Los principales elementos de un algoritmo genético son:
- Esquema de codificación, o sea la manera en que se representa una posible solución al problema.
- Función de evaluación, que indica si un individuo es apto para resolver el problema planteado.
- Tres operadores básicos: reproducción, cruce y mutación.
- Parámetros que controlan el desempeño del algoritmo genético: probabilidad de cruce, probabilidad de mutación, tamaño de la población, número de generaciones, etc.
En la práctica, la codificación más común de las soluciones es mediante cadenas binarias, aunque se han utilizado también números reales y letras o caracteres para representar los cromosomas. El primero de estos esquemas ha gozado de mucha popularidad debido a que fue el que propuso originalmente John Holland, y porque resulta fácil implementar. Operaciones sencillas de bits permiten efectuar el cruce, la mutación y otras operaciones. A pesar de que gran cantidad de investigaciones se realizaron en cadenas de longitud variable y otras estructuras, la mayor cantidad de algoritmos genéticos se ha enfocado en cadenas de caracteres de longitud fija.
Pasos a seguir
Los pasos a seguir para generar un algoritmo genético, según Coello son:
- Generar la población inicial.
- Evaluar la adaptación de todos los individuos en la población.
- Crear una nueva población efectuando operaciones como selección/ reproducción proporcional a la adaptación, cruce y mutaciones en los individuos en la que ésta acaba de ser medida.
- Reemplazar la antigua población
- Iterar utilizando la nueva población, hasta que la misma converja.
Esta implementación vista en forma de pseudocódigo sería:
generar población inicial, G(0);
evaluar G (0);
t:= 0;
repetir
t:= t + 1
generar G (t) usando
G (t-1);
evaluar G (t);
hasta encontrar una solución;
Cada iteración de este bucle es conocida como generación. La primera de este proceso es una población de individuos generados al azar. Desde ese punto, los operadores genéticos, unidos a la medida de adaptación, actúan para mejorar la población.
Principales elementos y operadores de un AG
Generación de la población inicial
La primera tarea del algoritmo genético es crear una población inicial de cadenas. Existen diversas formas de seleccionar una población inicial. Las técnicas varían desde seleccionar aleatoriamente cada carácter de una cadena hasta modificar el resultado de la búsqueda hecha previamente por el hombre.
La manera más simple de generar la población inicial es de seleccionar cada carácter de la cadena de forma totalmente aleatoria hasta completar toda la población. En caso de que el alfabeto sea binario, la probabilidad de que cada bit sea 1 es 50%.
La composición de la población inicial puede afectar dramáticamente el comportamiento del algoritmo genético.
La población debe ser lo suficientemente larga como para crear un diverso grupo de individuos con el fin de que el algoritmo genético lo explote, pero no tanto como para que no domine el tiempo de la computadora.
Esquema de codificación
Si un problema es factible de ser representado por un conjunto de parámetros (conocidos como genes), éstos pueden ser unidos para formar una cadena de valores (cromosoma), a este proceso se le llama codificación. En genética ese conjunto representado por un cromosoma en particular es referido como genotipo. Este contiene la información necesaria para construir un organismo conocido como fenotipo. Esos mismos términos se aplican en algoritmos genéticos.
Existen varias cuestiones relacionadas con la codificación de un problema que deben ser tenidas en cuenta en el momento de una ejecución:
- Utilizar el alfabeto más pequeño posible para representar los parámetros, normalmente se utilizan dígitos binarios.
- Las variables que representan los parámetros del problema deben ser discretizadas para poder representarse con cadenas de bits. Debe utilizarse suficiente resolución capaz de asegurar que la salida tenga un nivel de precisión adecuado. Se asume que la discretización es representativa de la función objetivo.
- La mayor parte de los problemas tratados con algoritmos genéticos son no lineales y muchas veces existen relaciones ocultas entre las variables que conforman la solución. Esta interacción es referida como epístasis, y es necesario tomarla en cuenta para una representación adecuada del problema.
Función de Evaluación
Dado un cromosoma, la función de evaluación consiste en asignarle un valor numérico de adaptación, el cual se supone sea proporcional a la utilidad o habilidad del individuo representado. Otras características que debe tener esta función es la de castigar las malas soluciones y premiar las buenas, de forma que sean estas últimas las que se propaguen con mayor rapidez.
Selección / reproducción
Es el proceso mediante el cual un individuo (cromosoma) es copiado proporcionalmente a su evaluación (fuerza), formando un conjunto intermedio de individuos. Tal conjunto intermedio se convierte tentativamente en una nueva población a la cual se le aplicarán los otros operadores genéticos. En la Naturaleza, la fuerza de un individuo es medida por su capacidad de sobrevivir en un cierto medio ambiente.
Existen dos formas fundamentales de realizar el procedimiento de selección/reproducción: ruleta y torneo estocástico.
Formas de trabajo de los AG
Existen varias formas de trabajo de los algoritmos genéticos, cada una basada en una metáfora distinta de la naturaleza.
Algoritmos genéticos generacionales
Es semejante a la forma de reproducción de los insectos. En la que una generación pone huevos, se aleja geográficamente o muere y es sustituida por una nueva. En tal modelo se realizan cruces en una piscina de individuos, los descendientes son colocados en otra. Al final de la fase reproductiva se elimina la generación anterior y se utiliza la nueva. Este modelo también es conocido como algoritmo genético canónico.
Algoritmos genéticos de estado fijo
Utilizan el esquema generacional de los mamíferos y otros animales de vida larga, en el cual coexisten padres y sus descendientes, lo que permite que los hijos sean educados por sus progenitores, pero también que a la larga se genere competencia entre ellos.
En este modelo, no sólo se deben seleccionar los dos individuos padres, sino también cuáles de la población anterior serán eliminados, para dar espacio a los descendientes.
Algoritmos genéticos paralelos
Parte de la metáfora biológica que motivó a utilizar la búsqueda genética consiste en que es inherentemente paralela, ya que al evolucionar se recorren de forma simultánea muchas soluciones cada una presentada por un individuo de la población. Sin embargo, es muy común en la Naturaleza que no sólo exista una población evolucionando, sino varias, normalmente aisladas de forma geográfica, que originan respuestas diferentes a la presión evolutiva. Esto trae consigo modelos que tienen en cuenta tal variación y utilizan no una población como los anteriores, sino múltiples concurrentemente.
Modelos de Islas
Si se tiene una población de individuos, ésta se divide en subpoblaciones que evolucionan independientemente como un algoritmo genético normal. En ocasiones, ocurren migraciones entre ellas, lo que les permite intercambiar material genético.
Con la migración, este modelo puede explotar las diferencias en las subpoblaciones. Tal variación representa una fuente de diversidad genética. Sin embargo, si un gran número de individuos emigran en cada generación, ocurre una mezcla global y se eliminan las diferencias locales. Si la migración no es frecuente, es probable que se produzca convergencia prematura en las subpoblaciones.
Modelo Celular
Coloca cada individuo en una matriz, donde cada uno sólo podrá buscar reproducirse con los otros que tenga a su alrededor (más cerca de casa) por lo que escoge al azar o al mejor adaptado. El descendiente pasará a ocupar un posición cercana.
No hay islas en este modelo, pero hay efectos potenciales similares. Si se asume que el cruce está restringido a individuos adyacentes, dos de ellos separados por 20 espacios estarán tan separados como si estuvieran en dos islas. Esta forma se conoce como asilamiento por distancia.
Cruce
El cruce se lleva a cabo sobre el conjunto intermedio generado por la reproducción. Primero se selecciona aleatoriamente una pareja de individuos para ser cruzados. Después, con el uso de la teoría de las probabilidades se determina si habrá cruce entre los dos individuos seleccionados o no. En caso afirmativo se alinean ambos individuos y se elige aleatoriamente una posición K entre 1 y Lc -1 (Lc es la longitud del cromosoma), en la cual se hará el cruce. Dos nuevos individuos serán creados intercambiando la información de los padres entre la posición K + 1 y la posición Lc incluso (Ver figura 1). Esto es conocido como cruce en un punto.
Cuando se usan 2 puntos de cruce, según Goldberg, se procede de manera similar. Normalmente el cruce se maneja dentro de la implementación del algoritmo genético con un porcentaje que indica con qué frecuencia se efectuará. Esto significa que no todas las parejas de cromosomas se cruzarán, sino que habrá algunas que pasarán intactas a la siguiente generación. Existe una técnica, llamada elitismo, en la que el individuo más apto a lo largo de las distintas generaciones no se cruza con nadie y se mantiene intacto hasta que surge otro mejor que lo desplazará.
Mutación
La mutación es aplicada a cada descendiente individualmente luego de cada cruce. Esta altera cada uno de los genes del cromosoma al azar, con una probabilidad pequeña. Cuando se usa una representación binaria, un bit se sustituye por su complemento (un cero se cambia por un uno y viceversa). Este operador permite la introducción del nuevo material cromosómico en la población, tal y como sucede con sus equivalentes biológicos. Al igual que el cruce, la mutación se maneja como un porcentaje que indica con qué frecuencia se efectuará, aunque se distingue de la primera por ocurrir mucho más esporádicamente (el porcentaje de cruce, normalmente es de más de 60% mientras que el de mutación es frecuente no supere 5%). Este bajo porciento en la probabilidad de mutación evita oscilaciones en el promedio de los valores objetivos de la población.
Existen dos formas de implementar una mutación: con probabilidad fija o el uso de una probabilidad variable que cambia de acuerdo con las características de la población.
La mutación busca mejorar aún más las soluciones creadas con los dos operadores anteriores. Se puede decir entonces que los algoritmos genéticos utilizan soluciones que por su evaluación han demostrado ser buenas para combinarlas y producir otras todavía mejores.
Problemas fundamentales en la implementación de un AG
Un problema de los algoritmos genéticos, dado por una mala formulación del modelo, es aquel en el cual los genes de unos pocos individuos relativamente bien adaptados, pero no óptimos, pueden dominar rápidamente la población. Una vez que esto ocurre, la habilidad del modelo para buscar mejores soluciones es eliminada completamente, mientras queda sólo la mutación como vía para hallar otras alternativas, a la vez que el algoritmo se convierte en una búsqueda al azar.
Ver además
- Algoritmo de ordenamiento
- Algoritmo de búsqueda
- Algoritmo de Kruskal
- Algoritmo de Euclides
- Algoritmo de Prim
- Algoritmo de Boruvka
- Algoritmo de Gutmann
- Algoritmo criptográfico
- Algoritmo de Ordenamiento Burbuja
- Algoritmo de Ordenamiento Shell
- Algoritmo
- Algoritmo de ordenamiento por selección
- Algoritmo de árboles de decisión de Microsoft
- Algoritmo de Búsqueda Heurística A*
- Algoritmo asimétrico
Fuente
- Irizar Mesa, MSc Ing. Mirtha, López Romeo, Ing. Vladimir, Solana Hernández, Ing. Michel: “Algoritmos Genéticos: Evolución, Genética y Computación”, en La Revista Cubana de Computación. GIGA Número 4, 1998. pág 26 – 33.
