Acceso

Ciencia

Computación

Cuando las máquinas evolucionan solas

Encontrar la ruta más corta entre Lugo y Murcia no es fácil, ni siquiera para un ordenador. Pero la teoría de la evolución da una herramienta: los algoritmos genéticos, que eligen la ruta que mejor se adapta al entorno.

GPS en un coche
El GPS es un gran aliado para salir de una ciudad desconocida en un tiempo razonableAls33120Creative Commons
Patricia Contreras
Creada:
Última actualización:

Cuando una empresa de alquiler de coches baja los precios, lo hace para atraer a más clientes y así aumentar sus beneficios. Si una fábrica cambia el diseño de los recipientes que produce, es para ahorrar en material. O bien, cuando tu GPS te propone seguir un camino distinto cada vez que viajas desde Lugo hasta Murcia, pretende que tardes menos tiempo.

Son tres problemas diferentes, pero tienen algo en común: en cada uno de estos casos se pretende optimizar algo. Sea maximizar ganancias, o minimizar materiales o tiempo, en cada situación hay que hallar la solución óptima para ahorrar costes y sumar beneficios.

Para resolver algunos problemas bastan una serie de cálculos que apenas llevan tiempo en un ordenador (en ocasiones, se pueden hacer incluso a mano). Pero cuando el problema es demasiado complejo, ¿cómo se puede abordar? La teoría de la evolución nos da la clave.

No siempre hay un método infalible

Es cierto que algunos problemas de optimización están tan estudiados que tienen asociado un método infalible para resolverlos. Encontrar el recipiente que utilice menos material para contener un volumen dado es un problema típico de la asignatura de matemáticas en la educación secundaria, y los cálculos para resolverlo se pueden hacer a mano.

Otros problemas son algo más complejos, y requieren la ayuda de un ordenador. El precio ideal de un alquiler de coches depende de muchos factores, pero se puede simplificar la situación lo suficiente para que un ordenador pueda calcularlo.

Pero encontrar la ruta más corta entre Lugo y Murcia no es nada fácil, ni siquiera para un ordenador. No se trata solo de minimizar la distancia: debemos tener en cuenta también cuánto tráfico hay en cada momento, la velocidad permitida en cada calle o carretera…

Desde luego, probar todas las rutas posibles y seleccionar la más corta no es una opción. Aunque este método garantizaría que tendríamos la mejor ruta, se tardaría demasiado en encontrarla. Precisamente para un GPS es crítico que la solución se halle rápidamente, puesto que el tiempo de cálculo se añade a lo que tardemos en recorrer nuestra ruta.

En vez, es mucho más rápido utilizar un algoritmo genético. Así se llaman los algoritmos de inteligencia artificial que se inspiran en la teoría de la evolución para resolver algunos problemas de optimización. La clave está en la idea de que los individuos que sobreviven son los que están mejor adaptados al medio.

Soluciones al azar

El punto de partida de estos algoritmos es un conjunto de posibles soluciones al problema, elegidas al azar. Por ejemplo, para calcular la ruta más corta entre Lugo y Murcia, podemos empezar con muchas rutas posibles: una pasa por Barcelona, otra por Cádiz, otra por Logroño… Está claro que algunas se alejarán mucho de la solución óptima, mientras que otras serán más adecuadas.

Estas posibles soluciones serán los individuos de nuestro escenario evolutivo. Para medir la adaptación al entorno, simplemente se calcula el tiempo de recorrido de cada ruta, teniendo en cuenta todos los factores que puedan influir: el tráfico, la velocidad permitida en cada vía, si hay lluvia o nieve…

Así, se clasifican las posibles soluciones de peor a mejor. Las peores acabarán descartándose, al igual que los individuos peor adaptados a su entorno acaban muriendo. Pero no se descartan de golpe: en vez, se fomenta que las soluciones mejores se reproduzcan más que las peores.

Sí, las soluciones se pueden reproducir. Para imitar el proceso de reproducción sexual que es clave para la evolución, se combinan unas soluciones con otras. Por ejemplo, se coge la primera mitad de la ruta que pasa por Logroño y se combina con otra ruta que pasaba por Cádiz (asegurándose de que el resultado final también es una ruta válida entre Lugo y Murcia). Así se llega a un nuevo conjunto de posibles soluciones para el problema.

Si continuáramos combinando y reproduciendo sin añadir ningún ingrediente más, a lo mejor conseguiríamos tener soluciones cada vez mejores. Pero si el conjunto inicial de soluciones fuera muy malo (es decir, si todas las rutas fueran bastante largas), nunca obtendríamos una ruta muy corta.

Para evitar este problema, se introducen modificaciones aleatorias en algunas soluciones. Es el paso correspondiente a las mutaciones, un ingrediente clave en la teoría de la evolución. Para provocar una mutación en una de las rutas, se cambia una ciudad por otra (el análogo a mutar un gen en un individuo). Por ejemplo, se modifica la ruta que pasaba por Barcelona para que pase, en vez, por Santander.

Antes de volver a reproducir las soluciones, es necesario evaluarlas de nuevo. Se calcula el tiempo de cada ruta y se favorece que las mejores se reproduzcan más que las peores. A cada paso, algunas rutas pasan a durar menos mientras que otras se vuelven más largas.

Pero, al aplicar el mecanismo muchas veces, las rutas más largas se van eliminando, y solo las más cortas sobreviven. Mediante la reproducción, la combinación y la mutación, el algoritmo genético va seleccionando las rutas mejor adaptadas al entorno dado por el tráfico, el tiempo o los límites de velocidad.

Cerrando el círculo

¿Cuándo dar por terminada la búsqueda? Dependerá del error que podamos tolerar. Si queremos asegurarnos de que tenemos una ruta muy similar a la ruta verdaderamente óptima, deberemos invertir más tiempo para reproducir, combinar y mutar más veces. Pero si nos conformamos con una ruta un poco peor, bastará con menos tiempo de cálculo.

Para ir de vacaciones a Murcia partiendo de Lugo, probablemente no seamos muy exigentes en cuanto al tiempo de recorrido. Pero para las empresas de reparto que hacen envíos a domicilio, una pequeña diferencia de tiempo puede suponer un gran ahorro económico.

Y no se trata solo de calcular rutas. Los algoritmos genéticos también se utilizan para diseñar horarios, para modelizar los cambios en la temperatura global, para crear filtros de spam en el correo electrónico… E, incluso, para conocer cómo se doblan las proteínas. Se cierra el círculo: la biología inspira a la computación para resolver problemas de la propia biología.

QUE NO TE LA CUELEN:

  • Aunque los algoritmos genéticos se asocian con la teoría de la evolución de Darwin, en realidad van más allá del darwinismo. Aunque Darwin sentó las bases de la selección natural (que es clave en los algoritmos genéticos), las variaciones en los individuos que él describía venían motivadas por el entorno. Es decir, según él, los individuos adquieren atributos en función de sus necesidades para sobrevivir. Pero ahora sabemos que estas variaciones se deben a las mutaciones, que ocurren de manera aleatoria. De igual forma, en los algoritmos genéticos, las soluciones mutan al azar, no necesariamente para acercarse más a la solución óptima.

REFERENCIAS (MLA):

Accede a tu cuenta para comentar

Ahora en Portada