Genetic Algorithm: qué son y dónde se utilizan los al­go­ri­t­mos genéticos

Un algoritmo genético, también conocido por su término en inglés genetic algorithm, es un método de op­ti­mi­za­ción que se basa en los pri­n­ci­pios de la selección natural. Su objetivo es mejorar pro­gre­si­va­me­n­te un conjunto de so­lu­cio­nes po­te­n­cia­les, ge­ne­ra­ción tras ge­ne­ra­ción, hasta encontrar la más adecuada para resolver un problema. Los al­go­ri­t­mos genéticos se utilizan en una amplia variedad de áreas, que van desde la op­ti­mi­za­ción de sistemas técnicos hasta el apre­n­di­za­je au­to­má­ti­co.

¿Qué son los al­go­ri­t­mos genéticos?

Los al­go­ri­t­mos genéticos, conocidos también como genetic al­go­ri­th­ms (GAs), re­pre­se­n­tan un enfoque global para resolver problemas de toma de de­ci­sio­nes, inspirado en los pri­n­ci­pios de la selección natural y la genética. Estos al­go­ri­t­mos pe­r­te­ne­cen a la categoría de los al­go­ri­t­mos evo­lu­ti­vos y utilizan me­ca­ni­s­mos que emulan los procesos de selección natural para mejorar gra­dua­l­me­n­te las so­lu­cio­nes a problemas complejos. En de­fi­ni­ti­va, simulan el principio de la “ley del más fuerte”, basado en las si­guie­n­tes premisas:

1. Los in­di­vi­duos compiten por recursos y por opo­r­tu­ni­da­des de re­pro­du­c­ción.
2. Los in­di­vi­duos más fuertes o exitosos tienen más de­s­ce­n­de­n­cia que los demás.
3. Los genes de los pro­ge­ni­to­res más aptos se tra­n­s­mi­ten a través de las ge­ne­ra­cio­nes, generando de­s­ce­n­die­n­tes que, de media, poseen co­m­bi­na­cio­nes genéticas más fa­vo­ra­bles.
4. A largo plazo, los mejores genes pre­va­le­cen, y cada ge­ne­ra­ción se adapta mejor a su entorno que la anterior.

Los al­go­ri­t­mos genéticos generan una población de in­di­vi­duos, donde cada uno re­pre­se­n­ta una posible solución al problema planteado. Aquellos in­di­vi­duos que mejor se adapten a su entorno so­bre­vi­ven y se re­pro­du­cen. Los in­di­vi­duos se re­pre­se­n­tan mediante cro­mo­so­mas, que se codifican en forma de cadenas de ca­ra­c­te­res (ca­ra­c­te­res, bits, flotantes o enteros). Los cro­mo­so­mas se dividen a su vez en genes, que es­pe­ci­fi­can ca­ra­c­te­rí­s­ti­cas in­di­vi­dua­les, como podría ser el color del cabello. Las di­fe­re­n­tes versiones de un gen (por ejemplo, rubio, castaño o moreno) se denominan alelos.

Para apro­xi­mar­se cada vez más a la solución óptima, los al­go­ri­t­mos genéticos utilizan un proceso de varios pasos que combina cálculos y re­pro­du­c­ción. Los cro­mo­so­mas se modifican y combinan a lo largo de varias ge­ne­ra­cio­nes o ite­ra­cio­nes mediante ope­ra­do­res genéticos, como la selección, la re­co­m­bi­na­ción (o cruce) y la mutación. Así, los al­go­ri­t­mos genéticos avanzan hacia una solución global óptima al combinar las mejores so­lu­cio­nes parciales.

¿Cómo funcionan los al­go­ri­t­mos genéticos?

El proceso de iteración en los al­go­ri­t­mos genéticos ge­ne­ra­l­me­n­te se divide en las si­guie­n­tes etapas:

1. El problema de op­ti­mi­za­ción se codifica o se mapea a un cromosoma co­di­fi­ca­do en formato binario.
2. El algoritmo genético genera una población de in­di­vi­duos y la ini­cia­li­za alea­to­ria­me­n­te. La población inicial también se conoce como Ge­ne­ra­ción 0.
3. A cada individuo se le asigna una pu­n­tua­ción de aptitud (o fi­t­ne­s­s­co­re) en forma de un número real.
4. Uti­li­za­n­do una variante de selección pre­de­fi­ni­da, el algoritmo genético se­le­c­cio­na pro­ge­ni­to­res de la población.
5. Basándose en la in­fo­r­ma­ción genética de ambos pro­ge­ni­to­res, se generan de­s­ce­n­die­n­tes.
6. Es posible que los rasgos genéticos (o alelos) de los de­s­ce­n­die­n­tes muten, lo que provoca que sus valores se inviertan.
7. La población se amplía con los nuevos de­s­ce­n­die­n­tes. Si el tamaño de la población supera el límite es­ta­ble­ci­do, un esquema de reemplazo define qué in­di­vi­duos dejarán de formar parte del conjunto de so­lu­cio­nes.
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 am­plia­me­n­te. Algunos al­go­ri­t­mos se detienen después de un número fijo de ge­ne­ra­cio­nes, mientras que otros siguen activos hasta que ya no se detecten mejoras en co­m­pa­ra­ción con la ge­ne­ra­ción anterior.

Fi­t­ne­s­s­s­co­re

El fitness es un sinónimo de la capacidad de ada­p­ta­ción de cada individuo. La pu­n­tua­ción de fitness de un individuo indica su nivel de co­m­pe­ti­ti­vi­dad. El objetivo del algoritmo genético es ide­n­ti­fi­car al individuo con la capacidad ideal (o casi ideal). Los in­di­vi­duos con mejores pu­n­tua­cio­nes tienen una mayor pro­ba­bi­li­dad de ser se­le­c­cio­na­dos para re­pro­du­ci­r­se. Esto provoca que las nuevas ge­ne­ra­cio­nes presenten, de media, so­lu­cio­nes más avanzadas que las an­te­rio­res.

¿Qué ope­ra­do­res utilizan los al­go­ri­t­mos genéticos?

Los al­go­ri­t­mos genéticos utilizan diversos ope­ra­do­res para de­sa­rro­llar la población inicial. Los me­ca­ni­s­mos fu­n­da­me­n­ta­les que hacen posible la evolución son la selección, la re­co­m­bi­na­ción y la mutación. A co­n­ti­nua­ción, se describen con más detalle los ope­ra­do­res in­di­vi­dua­les de los al­go­ri­t­mos genéticos.

Selección (Selection-Operator)

La selección determina qué in­di­vi­duos tienen permitido re­pro­du­ci­r­se y cuántos de­s­ce­n­die­n­tes pueden generar. La selección de los pro­ge­ni­to­res se basa en la pu­n­tua­ción de fitness o aptitud, donde el algoritmo genético da pre­fe­re­n­cia a los in­di­vi­duos con pu­n­tua­cio­nes altas.

Re­co­m­bi­na­ción (Crossover-Operator)

Mediante la re­co­m­bi­na­ción, se generan nuevos in­di­vi­duos. El algoritmo genético se­le­c­cio­na al azar los puntos de cruce. En estos puntos, los genes se in­te­r­ca­m­bian, dando lugar a de­s­ce­n­die­n­tes con nuevas ca­ra­c­te­rí­s­ti­cas. La siguiente ilu­s­tra­ción muestra un ejemplo de re­co­m­bi­na­ción o cruce:

• genes del pro­ge­ni­tor 1: A|B|C|D|E|F
• genes del pro­ge­ni­tor 2: G|H|I|J|K|L
• genes del de­s­ce­n­die­n­te: A|B|I|J|K|F

Mutación (Mutation-Operator)

La idea principal de las mu­ta­cio­nes consiste en in­tro­du­cir cambios alea­to­rios en los genes de los de­s­ce­n­die­n­tes, es decir, modificar la solución potencial de un problema. Esto ayuda a mantener la di­ve­r­si­dad genética entre la población y a evitar una co­n­ve­r­ge­n­cia prematura. A co­n­ti­nua­ció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 al­go­ri­t­mos genéticos?

Los al­go­ri­t­mos genéticos se utilizan pri­n­ci­pa­l­me­n­te en áreas donde los métodos ana­lí­ti­cos tra­di­cio­na­les alcanzan sus límites. Esto se aplica es­pe­cia­l­me­n­te a problemas con un espacio de solución amplio y complejo. Un campo clave donde se utiliza es en el deep learning o apre­n­di­za­je profundo, donde los al­go­ri­t­mos genéticos se emplean para optimizar los pesos de las redes neu­ro­na­les.

Además, los al­go­ri­t­mos genéticos se utilizan con fre­cue­n­cia en la pla­ni­fi­ca­ción de la pro­du­c­ción, donde ayudan a encontrar horarios óptimos y asi­g­na­cio­nes de recursos. En el ámbito em­pre­sa­rial y fi­na­n­cie­ro, se aplican tanto para la op­ti­mi­za­ción de carteras como para el de­sa­rro­llo de es­tra­te­gias de trading complejas. Otro campo de apli­ca­ción es el ajuste de hi­pe­r­pa­rá­me­tros de modelos del apre­n­di­za­je au­to­má­ti­co o machine learning. Aunque no siempre son el método más eficiente, los al­go­ri­t­mos genéticos son co­n­si­de­ra­dos una técnica de op­ti­mi­za­ción muy versátil debido a su fle­xi­bi­li­dad.

Ejemplo práctico de apli­ca­ción de los al­go­ri­t­mos genéticos

Su­po­n­ga­mos que la tarea de un algoritmo genético consiste en generar una cadena objetivo, como por ejemplo “The fittest survive” (los más aptos so­bre­vi­ven), partiendo de una cadena aleatoria de la misma longitud. En este caso, los ca­ra­c­te­res in­di­vi­dua­les (de A a Z, de a a z, de 0 a 9 y otros ca­ra­c­te­res es­pe­cia­les) re­pre­se­n­tan los genes. La cadena de ca­ra­c­te­res puede co­n­si­de­rar­se como un cromosoma o solución. La pu­n­tua­ción de fitness re­pre­se­n­ta la cantidad de ca­ra­c­te­res que difieren de la cadena objetivo. Por lo tanto, se da pre­fe­re­n­cia a los in­di­vi­duos con una pu­n­tua­ció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 ca­ra­c­te­res generadas de manera aleatoria.