Genetic Algorithm: qué son y dónde se utilizan los algoritmos genéticos

Un algoritmo genético, también conocido por su término en inglés genetic algorithm, es un método de optimización que se basa en los principios de la selección natural. Su objetivo es mejorar progresivamente un conjunto de soluciones potenciales, generación tras generación, hasta encontrar la más adecuada para resolver un problema. Los algoritmos genéticos se utilizan en una amplia variedad de áreas, que van desde la optimización de sistemas técnicos hasta el aprendizaje automático.

¿Qué son los algoritmos genéticos?

Los algoritmos genéticos, conocidos también como genetic algorithms (GAs), representan un enfoque global para resolver problemas de toma de decisiones, inspirado en los principios de la selección natural y la genética. Estos algoritmos pertenecen a la categoría de los algoritmos evolutivos y utilizan mecanismos que emulan los procesos de selección natural para mejorar gradualmente las soluciones a problemas complejos. En definitiva, simulan el principio de la “ley del más fuerte”, basado en las siguientes premisas:

1. Los individuos compiten por recursos y por oportunidades de reproducción.
2. Los individuos más fuertes o exitosos tienen más descendencia que los demás.
3. Los genes de los progenitores más aptos se transmiten a través de las generaciones, generando descendientes que, de media, poseen combinaciones genéticas más favorables.
4. A largo plazo, los mejores genes prevalecen, y cada generación se adapta mejor a su entorno que la anterior.

Los algoritmos genéticos generan una población de individuos, donde cada uno representa una posible solución al problema planteado. Aquellos individuos que mejor se adapten a su entorno sobreviven y se reproducen. Los individuos se representan mediante cromosomas, que se codifican en forma de cadenas de caracteres (caracteres, bits, flotantes o enteros). Los cromosomas se dividen a su vez en genes, que especifican características individuales, como podría ser el color del cabello. Las diferentes versiones de un gen (por ejemplo, rubio, castaño o moreno) se denominan alelos.

Para aproximarse cada vez más a la solución óptima, los algoritmos genéticos utilizan un proceso de varios pasos que combina cálculos y reproducción. Los cromosomas se modifican y combinan a lo largo de varias generaciones o iteraciones mediante operadores genéticos, como la selección, la recombinación (o cruce) y la mutación. Así, los algoritmos genéticos avanzan hacia una solución global óptima al combinar las mejores soluciones parciales.

¿Cómo funcionan los algoritmos genéticos?

El proceso de iteración en los algoritmos genéticos generalmente se divide en las siguientes etapas:

1. El problema de optimización se codifica o se mapea a un cromosoma codificado en formato binario.
2. El algoritmo genético genera una población de individuos y la inicializa aleatoriamente. La población inicial también se conoce como Generación 0.
3. A cada individuo se le asigna una puntuación de aptitud (o fitnesscore) en forma de un número real.
4. Utilizando una variante de selección predefinida, el algoritmo genético selecciona progenitores de la población.
5. Basándose en la información genética de ambos progenitores, se generan descendientes.
6. Es posible que los rasgos genéticos (o alelos) de los descendientes muten, lo que provoca que sus valores se inviertan.
7. La población se amplía con los nuevos descendientes. Si el tamaño de la población supera el límite establecido, un esquema de reemplazo define qué individuos dejarán de formar parte del conjunto de soluciones.
8. Mientras no se cumpla un criterio de parada, el algoritmo genético repite los pasos 3 a 7 para acercarse cada vez más a la solución óptima del problema. Sin embargo, los criterios de parada pueden variar ampliamente. Algunos algoritmos se detienen después de un número fijo de generaciones, mientras que otros siguen activos hasta que ya no se detecten mejoras en comparación con la generación anterior.

Fitnessscore

El fitness es un sinónimo de la capacidad de adaptación de cada individuo. La puntuación de fitness de un individuo indica su nivel de competitividad. El objetivo del algoritmo genético es identificar al individuo con la capacidad ideal (o casi ideal). Los individuos con mejores puntuaciones tienen una mayor probabilidad de ser seleccionados para reproducirse. Esto provoca que las nuevas generaciones presenten, de media, soluciones más avanzadas que las anteriores.

¿Qué operadores utilizan los algoritmos genéticos?

Los algoritmos genéticos utilizan diversos operadores para desarrollar la población inicial. Los mecanismos fundamentales que hacen posible la evolución son la selección, la recombinación y la mutación. A continuación, se describen con más detalle los operadores individuales de los algoritmos genéticos.

Selección (Selection-Operator)

La selección determina qué individuos tienen permitido reproducirse y cuántos descendientes pueden generar. La selección de los progenitores se basa en la puntuación de fitness o aptitud, donde el algoritmo genético da preferencia a los individuos con puntuaciones altas.

Recombinación (Crossover-Operator)

Mediante la recombinación, se generan nuevos individuos. El algoritmo genético selecciona al azar los puntos de cruce. En estos puntos, los genes se intercambian, dando lugar a descendientes con nuevas características. La siguiente ilustración muestra un ejemplo de recombinación o cruce:

• genes del progenitor 1: A|B|C|D|E|F
• genes del progenitor 2: G|H|I|J|K|L
• genes del descendiente: A|B|I|J|K|F

Mutación (Mutation-Operator)

La idea principal de las mutaciones consiste en introducir cambios aleatorios en los genes de los descendientes, es decir, modificar la solución potencial de un problema. Esto ayuda a mantener la diversidad genética entre la población y a evitar una convergencia prematura. A continuación, se muestra un ejemplo de mutación:

• antes de la mutación: A|B|C|D|E|F
• después de la mutación: A|B|L|D|T|F

¿Dónde se utilizan los algoritmos genéticos?

Los algoritmos genéticos se utilizan principalmente en áreas donde los métodos analíticos tradicionales alcanzan sus límites. Esto se aplica especialmente a problemas con un espacio de solución amplio y complejo. Un campo clave donde se utiliza es en el deep learning o aprendizaje profundo, donde los algoritmos genéticos se emplean para optimizar los pesos de las redes neuronales.

Además, los algoritmos genéticos se utilizan con frecuencia en la planificación de la producción, donde ayudan a encontrar horarios óptimos y asignaciones de recursos. En el ámbito empresarial y financiero, se aplican tanto para la optimización de carteras como para el desarrollo de estrategias de trading complejas. Otro campo de aplicación es el ajuste de hiperparámetros de modelos del aprendizaje automático o machine learning. Aunque no siempre son el método más eficiente, los algoritmos genéticos son considerados una técnica de optimización muy versátil debido a su flexibilidad.

Ejemplo práctico de aplicación de los algoritmos genéticos

Supongamos que la tarea de un algoritmo genético consiste en generar una cadena objetivo, como por ejemplo “The fittest survive” (los más aptos sobreviven), partiendo de una cadena aleatoria de la misma longitud. En este caso, los caracteres individuales (de A a Z, de a a z, de 0 a 9 y otros caracteres especiales) representan los genes. La cadena de caracteres puede considerarse como un cromosoma o solución. La puntuación de fitness representa la cantidad de caracteres que difieren de la cadena objetivo. Por lo tanto, se da preferencia a los individuos con una puntuación baja. La siguiente tabla muestra cómo podría ser el resultado en este caso:

Cabe destacar, no obstante, que el resultado puede variar. Esto se debe a que el algoritmo genético comienza con cadenas de caracteres generadas de manera aleatoria.