Genética y computación. ¿Qué son los algoritmos genéticos?

Existe un tipo de computación que basa su forma de trabajar en analogías con sistemas biológicos. ¿Si la naturaleza tiene mecanismos para resolver problemas, por qué no inspirarnos en ellos? A este tipo de computación, inspirada en lo biológico, la denominamos: computación bio-inspirada.

La forma en la que la naturaleza ha llegado a resolver los problemas ha sido mediante la evolución biológica, la cual posee unos mecanismos muy potentes, que son los responsables de la biodevirsidad en todos los niveles. Por lo tanto, era cuestión de tiempo aplicar esto a la computación para la resolución de problemas.

Por lo tanto tiene sentido aprovechar los mecanismos de la evolución, de una forma simplificada, para resolver problemas. Como una gran simplificación, la naturaleza se encarga de optimizar individuos a su entorno natural y esta optimización se reduce a la combinación de genes de los individuos. En la década de los 60 se comenzó a investigar en ello (mediante estrategias evolutivas), dando como resultado en 1975 la propuesta de los algoritmos genéticos por parte de John Henry Holland. La computación evolutiva aprovecha los mecanismos de la evolución biológica para resolver problemas de optimización.

¿Cómo funcionan los algoritmos genéticos?

Los algoritmos genéticos se encuentran inspirados en la evolución y su base genética. Aplicando la combinación de elementos o características, cromosomas, se obtienen individuos (cada individuo representa una solución al problema). Los cuales a partir de una función conocida (función de fitness) obtienes lo “valioso” que es un individuo, lo bien que resuelve el problema, asemejándose a lo bien que se adaptan al medio.

Los genes actúan a un nivel más bajo. Siendo una unidad individual de información, cobrando esta sentido en el cromosoma.

Partiendo de una población inicial de individuos, el algoritmo se encarga de seleccionar a los individuos “supervivientes” a partir de la función de fitness, sobreviven los mejores. Estos individuos se “reproducirán” entre sí intercambiando cromosomas, para dar como resultado una nueva población del mismo tamaño que la inicial. En este cruce de cromosomas existe la posibilidad de mutación (en genes o cromosomas), haciendo que alguno/s cromosomas no vengan de ninguno de los progenitores. Esto se repetirá hasta que se cumpla un criterio de parada (puede ser manual, en el momento en el que un individuo supera umbral de fitness, etc).

Por ejemplo: imagina un juego en 2 dimensiones en el cuál necesitas un coche que recorra el máximo de distancia posible sobre un terreno que se genera automáticamente. Este coche estará compuesto por un cuerpo, para simplificar rectangular y 2 ruedas. Las ruedas pueden ser configurables en tamaño y peso. Por lo que el problema a resolver consiste en maximizar la distancia que recorre el coche a partir del tamaño de las ruedas y su peso. Por lo tanto, la función que marca lo bueno que es un coche será la distancia que recorre y los cromosomas serán el tamaño de las ruedas y el material. Puedes ver algo un poco más complicado con coches de 2 dimensiones en http://rednuht.org/genetic_cars_2/

Estos algoritmos son muy intuitivos debido a que están basados en la forma de trabajar de la naturaleza. Además, es posible que encuentres soluciones inesperadas lo que lo convierten en una posible solución a problemas no resueltos por otros algoritmos de aprendizaje automático. Sin embargo, tiene la desventaja de que a priori no sabes si existe un individuo óptimo que resuelva tu problema y además es un algoritmo más lento que otros algoritmos de optimización.

En resumen, los algoritmo genéticos son una solución a problemas computacionales a partir de una técnica inspirada en la evolución de los seres vivos. Lo que pone de manifiesto como se pueden abordar diferentes problemas de una forma diferente y original. Además pone de manifiesto como algo puramente biológico puede ser llevado a la práctica mediante computadores, aunque de una forma simplificada.

*Otro ejemplo en el que podemos ver un algoritmo genético en funcionamiento http://rednuht.org/genetic_walkers/

Entrevista a un investigador

Tengo el placer de poder hablar con un estudiante de doctorado que se encuentra utilizando algoritmos evolutivos y que así pueda arrojar un poco de luz acerca de qué se hace o puede hacerse con estos algoritmos.

P: ¿En qué consiste tu investigación con los algoritmos genéticos?
R: Consiste en el uso de aprendizaje automático para la predicción de energía solar, a grandes rasgos. Una de las herramientas con las que he trabajado son algoritmos genéticos, en concreto programación genética aplicada a la detección automática de tipos de cielo.

P: ¿Qué te hizo decantarte por utilizar los algoritmos genéticos en clasificación de nubes?
R: Los algoritmos genéticos siempre me han parecido una opción muy potente. Me resulta muy elegante resolver problemas con las herramientas que ha utilizado la evolución a lo largo de años y reducirlo a ciclos de reloj.

P: ¿A qué se aplican algoritmos genéticos actualmente?
R: La cruda realidad es que la mayor parte de desarrollo en algoritmos genéticos se produce en el terreno de la investigación. Por mi parte no conozco aplicaciones comerciales que lo utilicen. Son técnicas que requieren muchos recursos, más que otras de uso mas extendido como las redes de neuronas o árboles de decisión.

P: ¿Cuál crees que es la mayor ventaja y cual el peor handicap de estos algoritmos?
R: En mi opinión la mayor ventaja que tienen los algoritmos genéticos es que generalizando tienen mayor capacidad de descubrimiento, encontrando soluciones inesperadas a problemas muy difíciles. La mayor desventaja es la otra cara de la moneda ya que, al igual que hay soluciones inesperadas, es posible que nunca se encuentre una solución.

P: ¿Cómo definirías la evolución ?
R: “Survival of the fittest”

P: ¿Cuál crees que sería la función de fittest de la naturaleza y cómo lo relacionarías con el algoritmo?
R: La naturaleza tiene una función de fitness que decide quien se reproduce y quien no, está optimizando individuos al entorno natural. La genética, el código del adn es lo que se está optimizando y este a su vez no es mas que una combinación muy larga de 1s y 0s. Entonces, los algoritmos genéticos exploran un espacio combinatorio para optimizar una función de adecuación arbitraria.

P: ¿Qué le dirías a alguien que niega la evolución?
R: Puedes creer en la evolución o no, pero seguirá haciendo su trabajo sin importar lo que opines.

Me encantaría mucho agradecerte tu colaboración y revisión de lo que he escrito. Muchas gracias por todo =)

Show your support

Clapping shows how much you appreciated Fernando Cortés’s story.