Evolución Genética aplicada al Transporte por Carretera

Sí, has leído bien: Teorías de Evolución Genética aplicadas al común y complejo problema del Transporte por Carretera, más bien a su organización.

  • Introducción

En 1965, Ingo Rechenberg -Universidad Técnica de Berlín- ideó una técnica a la que llamó estrategia evolutiva, que conseguía por primera vez resultados exitosos en un sistema de optimización y aprendizaje automáticos. Si bien ésta no fue la primera aproximación a los Algoritmos Genéticos (AG), ni tampoco la definitiva (más bien un embrión), sí dio pié a que muchos otros científicos se empezaran a interesar y trabajar en ella.

De esta forma, veinte años más tarde -mediados de los 80- y en un mundo mucho más computerizado, ésta técnica funcionaba y no sólo eso si no que se utilizaba. Bueno, rectifico en esto último, se utilizaba y se utiliza por que, aunque con ciertas "modificaciones genéticas" (broma fácil), hoy en día los Algoritmos Genéticos están ahí, a pié de cañón.

Computación Inteligente - Taxonomía

-Fuente-

Al tratarse de un algoritmo general -aplicable a multitud de problemas- su ámbito de aplicación es muy extenso. Por poner algunos ejemplos, los podemos encontrar detrás de: Ingeniería Aeroespacial, Química, Mercados Financieros, Matemáticas y Algoritmia, Ejército y Cumplimiento de la Ley, Diseño de Rutas y Horarios, Robótica y, como no, Juegos.

  • ¿Pero, como funciona, qué hace exactamente para que sea tan útil?

Veamos una definición: Técnica de programación que imita a la evolución biológica
como estrategia para resolver problemas. Dado un problema específico
a resolver, la entrada del AG es un conjunto de soluciones potenciales
a ese problema, codificadas de alguna manera, y una métrica llamada
función de aptitud que permite evaluar cuantitativamente a cada candidata.
Estas candidatas pueden ser soluciones que ya se sabe que funcionan,
con el objetivo de que el AG las mejore, pero se suelen generar aleatoriamente.

Como vemos, una vez más, el hombre se ha aprovechado de la naturaleza, copiando un método que funciona y adaptándolo a sus necesidades. ¿Para qué reinventar la rueda, si tienes los planos delante mismos?

Si nos ponemos más técnicos, el pseudocódigo que define un AG puede verse como este:

Evolutionary Algorithm

1. [i] Choose initial population
2. [f(X)] Evaluate the fitness of each individual in the population
3. [?] Repeat until termination: (time limit or sufficient fitness achieved)
a. [Se] Select best-ranking individuals to reproduce
b. [Cr]&[Mu] Breed new generation through crossover and/or mutation
(genetic operations) and give birth to offspring
c. [f(X)] Evaluate the individual fitnesses of the offspring
d. [Re] Replace worst ranked part of population with offspring

Lo que se consigue con esta especificación es asegurar un sistema en el que sus individuos mejoren, iteración a iteración, de forma automática. El "truco" para conseguir un buen AG está en definir una buena codificación de la población y una función de fitness competente, que se adecue a las necesidades del problema que se trate, para que escoja a los mejores individuos para la tarea dada.

Si bien esto no se ha comentado aún, los AG forman parte de los Algoritmos Metaheurísticos (AM), y estos se especifican, entre otras cosas, por el hecho de no asegurarnos la mejor solución pero sí una solución subóptima. La idea es dejar trabajando el algoritmo y pararlo cuando lo consideremos adecuado (¡el tiempo es oro!), cuanto más tiempo (minutos ... horas) pase, mejor - aunque, como es de sentido común, los resultados tenderán a estancarse pasado un cierto número de iteraciones.

Quizás con un caso práctico se vea más claro.

  •  Caso práctico

Dado que, últimamente, en la UDT-IA se ha trabajado en un proyecto (Speed) en el cual se ha trabajado la parte de planificación de recursos, podemos ver un caso actual y sencillo (de concepto, no de solución):

Supongamos una empresa con N camiones (recursos) y M puntos donde pasar a entregar o recoger paquetes (servicios). Podría ser tanto una empresa de transporte internacional como nacional, así como empresas de reparto e incluso camiones de la basura (la solución es adaptable).

Si esta empresa quiere ser eficiente en sus transportes -ahorro en combustible, tiempo, horarios de sus trabajadores; y un largo etcétera posible- debe planificar periódicamente los viajes -rutas a escoger, horarios, camiones adecuados, etc.- y, en ocasiones introducir modificaciones (replanificar).

Pues bien, lo más común sería tener una persona en la empresa, dedicada parcial o completamente a hacer esa planificación. Los problemas que presenta esta opción son: coste económico permanente para pagar a la persona, tendencia a repetir rutas sin valorar "todos" los factores, eficiencia relativa de las soluciones dadas, dificultad para replanificar, etc. Llegados a este punto del caso, es aquí donde entran en juego los Algoritmos Genéticos.

¡Es para volverse loco!

¡Para volverse loco!

Con la solución basada en los AG, nos encontramos con un panorama totalmente distinto y favorable. Tras una inversión económica y de tiempo inicial, que quedará sobradamente amortizada en cuanto se empiece a utilizar, dispondremos de un sistema al cual le introduciremos los datos necesarios (recursos disponibles, servicios a cumplir, posibles cambios o preferencias en rutas) cuando queramos nuevas planificaciones y, en cuestión de horas, nos ofrecerá soluciones subóptimas que, en la mayoría de casos, supondrán mejoras respecto al "método de la persona".

Lo más común es introducir esos datos por la tarde-noche y dejar trabajando el sistema durante la noche. En muchos casos tendremos una buena solución a las pocas horas (3-4), pero como esto sigue trabajando, cuando se llegue por la mañana a la empresa, se dispondrá de una solución para que los camiones empiecen a trabajar, ahorrando. Sin ir más lejos, hace un par de años leí el caso de una compañía de transporte nacional, con unos treinta camiones, que pasó a ahorrar hasta 3.000eur/mes en carburante (lástima que no tenga la fuente).

Solución mostrada sobre mapa

Una ruta simple, mostrada sobre mapa, automáticamente.

Como te habrás dado cuenta, este sistema es mejorable y es que, además de necesitar mucho tiempo de cálculo, tiene una baja tolerancia a la replanificación -¡Replanificar no puede ser planificar de nuevo!-. Y es ahí en lo que se está trabajando des de la UDT-IA, tratando de mejorar ese AG a través de una fuerte modificación y simbiosis con otros métodos de la Inteligencia Artificial (IA).

Conoce mejor lo que hacemos en la Unidad de Desarrollo Tecnológico en Inteligencia Artificial (UDT-IA) y en el Instituto de Investigación en Inteligencia Artificial (IIIA), del cual formamos parte, aquí: UDT-IA i IIIA (CSIC).

  • Fuentes básicas y conocer más:
  1. AG | Wikipedia
  2. AG y CE | Adam Marczyk
  3. AM | Wikipedia
  4. Soft Computing | IIIA
  5. Proyecto Speed | UDT-IA

Reply

The content of this field is kept private and will not be shown publicly.
CAPTCHA
This question is for testing whether you are a human visitor and to prevent automated spam submissions.
Image CAPTCHA
Copy the characters (respecting upper/lower case) from the image.