Algoritmos genéticos: Funcionamiento, Pasos y Aplicaciones

Algoritmos genéticos: Definición y Pasos

Un algoritmo genético es una búsqueda heurística que está inspirada en la teoría de la evolución natural de Charles Darwin.

Este algoritmo refleja el proceso de selección natural donde los individuos más aptos son seleccionados para la reproducción con el fin de producir descendencia de la próxima generación.

Como tal, representa una explotación inteligente de una búsqueda aleatoria utilizada para resolver problemas de optimización. Aunque son aleatorios, los AG no son aleatorios, sino que explotan la información histórica para dirigir la búsqueda a la región de mejor desempeño dentro del espacio de búsqueda.

Las técnicas básicas de los GA están diseñadas para simular los procesos en los sistemas naturales necesarios para la evolución, especialmente aquellos que siguen los principios establecidos por primera vez por Charles Darwin de "la supervivencia del más apto".

Como en la naturaleza, la competencia entre individuos por recursos escasos resulta en que las personas más aptas dominen a las más débiles.

Selección natural

"No es la especie más fuerte que sobrevive, ni la más inteligente, sino la que más responde al cambio."

Vamos a entender con un ejemplo básico:

Tomemos una situación hipotética en la que, usted es el presidente de un país, y para mantener su país productivo, implemente una política como esta.

  • Seleccionas a las personas más trabajadoras y les pides que extiendan su generación teniendo hijos.
  • Esto se repite por algunas generaciones.
  • Notará que ahora tienes toda una población de gente productiva.

Ahora, eso puede no ser del todo posible, ni ético, pero este ejemplo fue solo para ayudarlo a comprender el concepto.

El concepto de algoritmo genético está relacionado de alguna manera con la biología. Así que vamos a comprender rápidamente algunos pequeños conceptos, de modo que podamos trazar una línea paralela entre ellos.

El proceso de selección natural comienza con la selección de individuos más aptos de una población. Producen descendientes que heredan las características de los padres y se agregarán a la generación siguiente.

Si los padres tienen una mejor condición física, sus hijos serán mejores que los padres y tendrán más posibilidades de sobrevivir. Este proceso continúa iterando y, al final, se encontrará una generación con las personas más aptas.

Esta noción se puede aplicar a un problema de búsqueda. Consideramos un conjunto de soluciones para un problema y seleccionamos el conjunto de las mejores.

Cinco fases en un algoritmo genético:

  • Población inicial
  • Función de aptitud
  • Selección
  • Cruzamiento
  • Mutación

 

Pasos de un algoritmo genético

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 cuerda para formar un cromosoma (solución).

En un algoritmo genético, el conjunto de genes de un individuo se representa utilizando una cuerda, 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 buena es una persona (la capacidad de una persona para competir con otras personas). 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 las personas más aptas y dejarles pasar sus genes a la próxima generación.

Se seleccionan dos pares de individuos en función de sus puntajes de aptitud.

Las personas con una buena aptitud tienen más posibilidades de ser seleccionadas para la reproducción.

Cruzamiento

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.

Terminación

El algoritmo finaliza si la población ha convergido (no produce descendencia que sea significativamente diferente de la generación anterior).

Luego se dice que el algoritmo genético ha proporcionado una serie de soluciones a nuestro problema.

¿Por qué usar algoritmos genéticos?

Es mejor que la IA convencional porque es más robusta. A diferencia de los sistemas de IA más antiguos, no se rompen fácilmente incluso si las entradas cambiaban levemente o en presencia de ruido razonable.

Además, 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)

Aplicaciones en el mundo real

El algoritmo genético tiene muchas aplicaciones en el mundo real. 

Diseño de ingeniería

El diseño de ingeniería se ha basado en gran medida en la simulación y el modelado de computadoras para que el proceso del ciclo de diseño sea rápido y económico.

El algoritmo genético se ha utilizado para optimizar y proporcionar una solución robusta.

Enrutamiento de tráfico y envío (Problema del vendedor ambulante)

Este es un problema famoso y ha sido adoptado de manera eficiente por muchas compañías basadas en ventas ya que ahorra tiempo y es económico. También se puede solucionar usando un algoritmo genético.

Robótica

El uso del algoritmo genético en el campo de la robótica es bastante grande. En la actualidad, el algoritmo genético se utiliza para crear robots de aprendizaje que se comportarán como humanos y realizarán tareas más humanas y no tan automatizables.