Uno de los desafíos centrales de la informática es lograr que una computadora haga lo que debe hacerse, sin decirle cómo hacerlo. La programación genética aborda este desafío proporcionando un método para crear automáticamente un programa de computadora que funcione a partir de una declaración de alto nivel del problema.
La programación genética logra este objetivo de la programación automática (también llamada a veces síntesis de programas o inducción de programas ) mediante la reproducción genética de una población de programas de computadora utilizando los principios de la selección natural darwiniana y las operaciones de inspiración biológica. Las operaciones incluyen operaciones de reproducción, cruzamiento (recombinación sexual), mutación y alteración de la arquitectura siguiendo el patrón de la duplicación y eliminación de genes en la naturaleza.
Un algoritmo genético es una heurística de búsqueda que se inspira en la teoría de la evolución natural de Charles Darwin. Este algoritmo refleja el proceso de selección natural en el que los individuos más aptos son seleccionados para su reproducción con el fin de producir la descendencia de la siguiente generación.
Noción de selección natural
El proceso de selección natural comienza con la selección de los individuos más aptos de una población. Éstos producen una descendencia que hereda las características de los padres y que se incorporará a la siguiente generación. Si los padres tienen una mejor aptitud, su descendencia será mejor que los padres y tendrá más posibilidades de sobrevivir. Este proceso sigue iterando y al final se encontrará una generación con los individuos más aptos.
Esta noción puede aplicarse a un problema de búsqueda. Se considera un conjunto de soluciones para un problema y se selecciona el conjunto de las mejores de entre ellas.
En un algoritmo genético se consideran cinco fases.
- Población inicial
- Función de aptitud
- Selección
- Cruce
- Mutación
- Población inicial
El proceso comienza con un conjunto de individuos que se llama Población. Cada individuo es una solución al problema que se quiere resolver.
Un individuo se caracteriza por un conjunto de parámetros (variables) conocidos como Genes. Los genes se unen en una cadena para formar un Cromosoma (solución).
En un algoritmo genético, el conjunto de genes de un individuo se representa mediante una cadena, en términos de un alfabeto. Normalmente se utilizan valores binarios (cadena de 1s y 0s). Decimos que codificamos los genes en un cromosoma.
Función de aptitud
La función de aptitud determina la aptitud de un individuo (la capacidad de un individuo para competir con otros individuos). Da una puntuación de aptitud a cada individuo. La probabilidad de que un individuo sea seleccionado para la reproducción se basa en su puntuación de aptitud.
Selección
La idea de la fase de selección es seleccionar a los individuos más aptos y dejar que pasen sus genes a la siguiente generación.
Se seleccionan dos pares de individuos (padres) en función de su puntuación de aptitud. Los individuos con alta aptitud tienen más posibilidades de ser seleccionados para la reproducción.
Cruzamiento
El cruce es la fase más importante de un algoritmo genético. Para cada par de progenitores que se van a aparear, se elige un punto de cruce al azar dentro de los genes.
Por ejemplo, consideremos que el punto de cruce es el 3, como se muestra a continuación.
Punto de cruce
La descendencia se crea intercambiando los genes de los padres entre sí hasta alcanzar el punto de cruce.
Intercambio de genes entre los padres
Los nuevos descendientes se añaden a la población.
Mutación
En algunos de los nuevos descendientes formados, algunos de sus genes pueden sufrir una mutación con una probabilidad aleatoria baja. Esto implica que algunos de los bits de la cadena de bits pueden invertirse.
Mutación: Antes y después
La mutación se produce para mantener la diversidad en la población y evitar la convergencia prematura.
Finalización
El algoritmo termina si la población ha convergido (no produce descendientes que sean significativamente diferentes de la generación anterior). Entonces se dice que el algoritmo genético ha proporcionado un conjunto de soluciones a nuestro problema.
Comentarios
La población tiene un tamaño fijo. A medida que se forman nuevas generaciones, los individuos con menor aptitud mueren, lo que proporciona espacio para nuevos descendientes.
La secuencia de fases se repite para producir individuos en cada nueva generación que sean mejores que la anterior.
