Un algoritmo genético es una búsqueda heurística, que se basa en la teoría de la selección natural propuesta por Charles Darwin. Este tipo de algoritmos reflejan el proceso de selección natural, donde los más aptos son los que son seleccionados para la reproducirse y así generar una generación aún más apta.
¿Por qué usar algoritmos genéticos?
Al buscar en un gran espacio de estado multimodal o superficie n-dimensional, un algoritmo genético puede ofrecer beneficios significativos sobre una búsqueda más típica de técnicas de optimización. (programación lineal, heurística, búsqueda en profundidad y praxis)
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. Estos producen descendientes que heredan las características de los padres y se agregarán a la próxima generación. Si los padres tienen una mejor condición física, sus hijos serán mejores que los padres y tendrán una mejor oportunidad de sobrevivir. Este proceso continúa iterando y, al final, se encontrará una generación con los individuos más aptos.
Esta noción se puede aplicar para un problema de búsqueda. Consideramos un conjunto de soluciones para un problema y seleccionamos el conjunto de las mejores entre ellas.
Se pueden definir cinco fases en un algoritmo genético.
1. Población inicial
2. Función de aptitud
3. Selección
4. Cruce
5. 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 desea 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 usando una cadena, en términos de un alfabeto. Por lo general, 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 qué tan bueno es un individuo (la capacidad de un individuo para competir con otros). Le da un puntaje de aptitud a cada individuo.
La probabilidad de que un individuo sea seleccionado para la reproducción se basa en su puntaje de aptitud.
Selección
La idea de la fase de selección es seleccionar a los individuos más aptos y dejarles pasar sus genes a la próxima generación.
Se seleccionan los pares de individuos en función de sus puntajes de aptitud.
Los individuos con una buena aptitud tienen más posibilidades de ser seleccionados para la reproducción.
Cruce
El cruzamiento es la fase más importante en un algoritmo genético. Para cada par de padres que se aparearán, se elige al azar un punto de cruce dentro de los genes.
Los descendientes se crean intercambiando los genes de los padres entre ellos hasta que se alcanza el punto de cruce.
Mutación
En ciertos descendientes nuevos, algunos de sus genes pueden ser sometidos a una mutación con una baja probabilidad aleatoria. Esto implica que algunos de los bits en la cadena de bits se pueden voltear.
La mutación ocurre para mantener la diversidad dentro de la población y prevenir la convergencia prematura.
Referencias
Algoritmos genéticos: Funcionamiento, Pasos y Aplicaciones. Recuperado 25 Julio 2020, de https://www.tecnologias-informacion.com/algoritmosgeneticos.html
Introduction to Genetic Algorithms — Including Example Code. Recuperado 25 Julio 2020, de https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3#:~:text=Example%20Implementation%20in%20Java,1s%20present%20in%20the%20genome.