Los algoritmos genéticos

Charles Darwin en una fotografía tomada por J.M. Cameron en 1869.

Resulta fascinante comprobar cómo aplicando los mecanismos básicos de la evolución ya descrita por Darwin en su obra fundamental, El origen de las especies por medio de la selección natural, o la preservación de las razas preferidas en la lucha por la vida, publicada en 1859, se pueden generar algoritmos capaces de optimizar problemas complejos. Este tipo de metaheurísticas inspiradas en la Naturaleza ya se comentaron en artículos anteriores cuando hablamos de la optimización por colonias de hormigas o de la cristalización simulada. Aunque es un algoritmo ampliamente conocido por la comunidad científica, voy a intentar dar un par de pinceladas con el único afán de divulgar esta técnica. La verdad es que las implicaciones filosóficas que subyacen tras la teoría de Darwin son de una profundidad difícil de entender cuando se lleva a sus últimos extremos. Pero el caso es que estos algoritmos funcionan perfectamente en la optimización de estructuras de hormigón, problemas de transporte y otros problemas difíciles de optimización combinatoria.

Para aquellos interesados, os paso en las referencias un par de artículos donde hemos aplicado los algoritmos genéticos para optimizar rutas de transporte aéreo o pilas de puente huecas de hormigón armado.

Sin embargo, para aquellos otros que queráis un buen libro para pensar, os recomiendo “La peligrosa idea de Darwin”, de Daniel C. Dennett. A más de uno le hará remover los cimientos más profundos de sus creencias. Os paso la referencia al final.

Básicamente, los algoritmos genéticos “Genetic Algorithms, GA”, simulan el proceso de evolución de las especies que se reproducen sexualmente. De manera muy general, se puede decir que en la evolución de los seres vivos, el problema al que cada individuo se enfrenta diariamente es el de la supervivencia. Para ello cuenta, entre otras, con las habilidades innatas provistas en su material genético. A nivel de los genes, el problema consiste en la búsqueda de aquellas adaptaciones beneficiosas en un medio hostil y cambiante. Debido en parte a la selección natural, cada especie gana cierta “información” que es incorporada a sus cromosomas.

Durante la reproducción sexual, un nuevo individuo, diferente de sus padres, se genera a través de la acción de dos mecanismos fundamentales: El primero es el cruzamiento, que combina parte del patrimonio genético de cada progenitor para elaborar el del nuevo individuo; el segundo es la mutación, que supone una modificación espontánea de esta información genética. La descendencia será diferente de los progenitores, pero mantendrá parte de sus características. Si los hijos heredan buenos atributos de sus padres, su probabilidad de supervivencia será mayor que aquellos otros que no las tengan. De este modo, los mejores tendrán altas probabilidades de reproducirse y diseminar su información genética a sus descendientes.

Holland (1975) estableció por primera vez una metaheurística basada en la analogía genética. Un individuo se puede asociar a una solución factible del problema, de modo que se pueda codificar en forma de un vector binario “string”. Entonces un operador de cruzamiento intercambia cadenas de los padres para producir un hijo. La mutación se configura como un operador secundario que cambia, con una probabilidad pequeña, algunos elementos del vector hijo. La aptitud del nuevo vector creado se evalúa de acuerdo con una función objetivo.

Los pasos a seguir con esta metaheurística serían los siguientes:

  1. Generar una población de vectores (individuos).
  2. Mientras no se encuentre un criterio de parada:
    1. Seleccionar un conjunto de vectores padre, que serán reemplazados de la población.
    2. Emparejar aleatoriamente a los progenitores y cruzarlos para obtener unos vectores hijo.
    3. Aplicar una mutación a cada descendiente.
    4. Evaluar a los hijos.
    5. Introducir a los hijos en la población.
    6. Eliminar a aquellos individuos menos eficaces.

Normalmente este proceso finaliza después de un numero determinado de generaciones o cuando la población ya no puede mejorar. La selección de los padres se elige probabilísticamente hacia los individuos más aptos. Al igual que ocurre con en la Naturaleza, los sujetos con mayor aptitud diseminan sus características en toda la población.

Esta descripción de los GA se adapta a cada situación concreta, siendo habitual la codificación de números enteros en vez de binarios. Del mismo modo se han sofisticado los distintos operadores de cruzamiento y mutación.

Os dejo a continuación un vídeo explicativo que he elaborado para mis clases de “Modelos predictivos y de optimización heurística de estructuras de hormigón“, del Máster Universitario en Ingeniería del Hormigón, de la Universitat Politècnica de València.

Referencias:

DENNETT, D.C. (1999). La peligrosa idea de Darwin. Galaxia Gutenberg. Círculo de Lectores, Barcelona.

HOLLAND, J.H. (1975). Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor.

MARTÍNEZ, F.J.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A.; YEPES, V. (2010). Heuristic Optimization of RC Bridge Piers with Rectangular Hollow Sections. Computers & Structures, 88: 375-386. ISSN: 0045-7949.  (link)

MEDINA, J.R.; YEPES, V. (2003). Optimization of touristic distribution networks using genetic algorithms. Statistics and Operations Research Transactions, 27(1): 95-112.  ISSN: 1696-2281.  (pdf)

PONZ-TIENDA, J.L.; YEPES, V.; PELLICER, E.; MORENO-FLORES, J. (2013). The resource leveling problem with multiple resources using an adaptive genetic algorithm. Automation in Construction, 29(1):161-172. DOI:http://dx.doi.org/10.1016/j.autcon.2012.10.003. (link)

YEPES, V. (2003). Apuntes de optimización heurística en ingeniería. Editorial de la Universidad Politécnica de Valencia. Ref. 2003.249. Valencia, 266 pp. Depósito Legal: V-2720-2003.

Licencia de Creative Commons
Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.

¿Qué es la optimización combinatoria?

Los problemas de optimización en los que las variables de decisión son enteras, es decir, donde el espacio de soluciones está formado por ordenaciones o subconjuntos de números naturales, reciben el nombre de problemas de optimización combinatoria. En este caso, se trata de hallar el mejor valor de entre un número finito o numerable de soluciones viables. Sin embargo la enumeración de este conjunto resulta prácticamente imposible, aún para problemas de tamaño moderado.

Las raíces históricas de la optimización combinatoria subyacen en ciertos problemas económicos: la planificación y gestión de operaciones y el uso eficiente de los recursos. Pronto comenzaron a modelizarse de esta manera aplicaciones más técnicas, y hoy vemos problemas de optimización discreta en diversas áreas: informática, gestión logística (rutas, almacenaje), telecomunicaciones, ingeniería, etc., así como para tareas variadas como el diseño de campañas de marketing, la planificación de inversiones, la división de áreas en distritos políticos, la secuenciación de genes, la clasificación de plantas y animales, el diseño de nuevas moléculas, el trazado de redes de comunicaciones, el posicionamiento de satélites, la determinación del tamaño de vehículos y las rutas de medios de transporte, la asignación de trabajadores a tareas, la construcción de códigos seguros, el diseño de circuitos electrónicos, etc. (Yepes, 2002). La trascendencia de estos modelos, además del elevado número de aplicaciones, estriba en el hecho de que “contiene los dos elementos que hacen atractivo un problema a los matemáticos: planteamiento sencillo y dificultad de resolución” (Garfinkel, 1985). En Grötschel y Lobas (1993) se enumeran otros campos en los cuales pueden utilizarse las técnicas de optimización combinatoria.

REFERENCIAS

GARFINKEL, R.S. (1985). Motivation and Modeling, in LAWLER, E.L.; LENSTRA, J.K.; RINNOOY KAN, A.H.G.; SHMOYS, D.B. (eds.) The Traveling Salesman Problem: A Guide Tour of Combinatorial Optimization. Wiley. Chichester.

GRÖTSCHEL, M.; LÓVASZ, L. (1993). Combinatorial Optimization: A Survey. Technical Report 93-29. DIMACS, May.

YEPES, V. (2002). Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW. Tesis Doctoral. Escuela Técnica Superior de Ingenieros de Caminos, Canales y Puertos. Universitat Politècnica de València. 352 pp. ISBN: 0-493-91360-2. (pdf)

¿Por qué son tan complicados los problemas de distribución física?

Aspecto de diversas soluciones al problema de rutas
Aspecto de diversas soluciones al problema de rutas

Los problemas de distribución física consisten básicamente en asignar una ruta a cada vehículo de una flota para repartir o recoger mercancías. Los clientes se localizan en puntos o arcos y a su vez pueden presentar horarios de servicio determinados; el problema consiste en establecer secuencias de clientes y programar los horarios de los vehículos de manera óptima. Los problemas reales de transporte son extraordinariamente variados. Yepes (2002) propone una clasificación que contiene un mínimo de 8,8·109 combinaciones posibles de modelos de distribución. Si alguien fuese capaz de describir en un segundo cada uno de ellos, tardaría cerca de 280 años en enunciarlos todos. La investigación científica se ha centrado, por tanto, en un grupo muy reducido de modelos teóricos que además tienden a simplificar excesivamente los problemas reales. Son típicos problemas de optimización matemática combinatoria. Continue reading “¿Por qué son tan complicados los problemas de distribución física?”

Optimización económica de redes de transporte

Trascendencia del transporte

La trascendencia económica del sector del transporte genera costos sociales y medioambientales de gran envergadura. Esta actividad supone aproximadamente un sexto del Producto Interno Bruto (PIB) de los países industrializados (ver Yepes, 2002). Un estudio del National Council of Physical Distribution (ver Ballou, 1991) estima que el transporte sumó un 15% del PIB de Estados Unidos en 1978, constituyendo más del 45% de todos los costos logísticos de las organizaciones. En España, según datos del Ministerio de Fomento (ver CTCICCP, 2001), la participación del sector en el valor añadido bruto del año 1997 se situó en un 4.6%. En cuanto al empleo, 613,400 personas se encontraban ocupadas en el año 1999 en el sector de transportes en España, lo cual representa el 3.69% de la población activa. La distribución física representa para las empresas entre la sexta y la cuarta parte de las ventas y entre uno y dos tercios del total de los costos logísticos (Ballou, 1991). Continue reading “Optimización económica de redes de transporte”

La logística y los problemas de distribución física

Empezamos una serie de artículos que van a tratar aspectos relacionados con el transporte, la logística, la distribución de mercancías, la investigación de las operaciones y, en definitiva, la toma de decisiones en las empresas. Como siempre, el objeto es divulgativo, abriendo puertas a la reflexión y no pretendiendo, ni mucho menos, abarcar todos los aspectos relativos a un tema determinado. Empezamos, pues.

El National Council of Physical Distribution Management definió, en 1979 (ver Ballou, 1991) la gestión de la distribución física como “todas aquellas actividades encaminadas a la planificación, implementación y control de un flujo creciente de materias primas, recursos de producción y productos finales desde el punto de origen al de consumo”. Entre estas tareas se encuentran el servicio al cliente, la previsión de la demanda, el control de inventarios, los servicios de reparación, el manejo de mercancías, el procesamiento de pedidos, la selección de la ubicación geográfica de las fábricas y los almacenes, las compras, el empaquetado de productos, el tratamiento de las mercancías devueltas, la recuperación y tratamiento de desperdicios, la distribución y el transporte, y el almacenamiento. Sin embargo, otros autores prefieren emplear el término de logística empresarial.

La importancia de la eficacia y la eficiencia de la gestión de la distribución adquiere su verdadera magnitud cuando se consideran los costes. Kotler (1991) indica que los principales elementos de los costes de la distribución física son el transporte (37%), el control de existencias (22%), el almacenamiento (21%) y otros como la recepción de órdenes, el servicio al cliente, la distribución y la administración (20%). El mismo autor cree, al igual que otros expertos, que pueden conseguirse ahorros sustanciales en el área de la distribución física, la cual ha sido descrita como “la última frontera para obtener economías en los costes” y “el continente oscuro de la economía”. Drucker (1962) describió las actividades logísticas que se llevaban a cabo tras la fabricación como las “áreas peor realizadas y a la vez más prometedoras dentro del mundo industrial”.

Muchas empresas sostienen que el objetivo último de la distribución física es obtener las mercancías necesarias, llevarlas a los lugares oportunos a su debido tiempo y al coste más bajo posible. Sin embargo, y tal como afirma Kotler (1991), no existe ningún sistema de distribución que pueda, simultáneamente, maximizar el servicio al cliente y minimizar los costes de distribución, puesto que lo primero supone un elevado coste de existencias, un transporte rápido y múltiples almacenes, factores que incrementan los costes. Se trata de buscar un equilibrio que contemporice los intereses contrapuestos.

La gestión de la distribución física presenta una gran variedad de problemas de decisión que afectan a la planificación en el ámbito estratégico, táctico y operativo. La localización de plantas y almacenes, o la reconfiguración de la red de transporte son decisiones estratégicas, mientras que los problemas relacionados con la dimensión de la flota, o si ésta debe ser propia o alquilada pertenecen al ámbito de las decisiones tácticas. Los problemas habituales en las operaciones son: (a) el establecimiento de rutas para vehículos que, con cierta limitación de capacidad, deben distribuir o recoger mercancías a un grupo de clientes; y (b) la programación de horarios o precedencias entre destinos para satisfacer estos recorridos.

Un estudio del National Council of Physical Distribution (ver Ballou, 1991) estima que el transporte sumó un 15% del Producto Interior Bruto de Estados Unidos en 1978, constituyendo más del 45% de todos los costes logísticos de las organizaciones. El sector de las empresas de servicios públicos y transportes estadounidenses movió en 1991 aproximadamente 506 millardos de dólares, según el Informe del Presidente de 1994 (ver Fisher, 1997). King y Mast (1997) señalan que la valoración anual que implican los excesos de coste en los viajes en Estados Unidos ascienden a 45 millardos de dólares. En Reino Unido, Francia y Dinamarca, por ejemplo, el transporte representa cerca del 15%, 9% y 15% del gasto nacional respectivamente (Crainic y Laporte, 1997; Larsen, 1999). En Japón, los costes logísticos suponen un 26,5% de las ventas, y los de transporte, un 13,5% (Kobayashi, 1973). Estas mismas cifras son del 14,1% y 2,5% en Australia (Stephenson, 1975), y del 16% y 5,5% en Reino Unido (Murphy, 1972). En España, según datos del Ministerio de Fomento (ver CTCICCP, 2001), la participación del sector transporte en el valor añadido bruto del año 1997 se situó en un 4,6%. En cuanto al empleo, 613.400 personas se encontraban ocupadas en el año 1999 en el sector del transporte público en nuestro país, lo cual supone el 3,69% de la población activa.

Existe una gran variación entre los costes logísticos de las distintas empresas. Ballou (1991) indica que estas cifras oscilan entre menos del 4% sobre las ventas en aquellas empresas que producen y distribuyen mercancías de alto valor, hasta más de un 32% en aquellas otras que lo hacen en las de bajo valor. El mismo autor apunta que los costes de transporte representan entre una tercera y dos terceras partes del total de costes logísticos. Se estima que los costes de distribución suponen casi la mitad del total de los costes logísticos en algunas industrias, y que en las de alimentación y bebidas pueden incrementar un 70% el coste de las mercancías (De Backer et al., 1997; Golden y Wasil, 1987). Además, la importancia de la programación de rutas se manifiesta claramente con el dato aportado por Halse (1992) informando que en 1989, el 76,5% de todo el transporte de mercancías se realizó con vehículos.

Así, las actividades que conforman la planificación operativa de la distribución física implican un gran número de pequeñas decisiones interrelacionadas entre sí. Además, la cifra de planes posibles crece exponencialmente con la dimensión del problema. Incluso para flotas pequeñas y con un número moderado de peticiones de transporte, la planificación es una tarea altamente compleja. Por tanto, no es de extrañar que los responsables de estos asuntos simplifiquen al máximo los problemas y utilicen procedimientos particulares para despachar sus vehículos basándose, en multitud de ocasiones en la experiencia de errores anteriores. Existe un amplio potencial de mejora claramente rentable para las unidades de negocio.

La planificación y la gestión de las redes de distribución exige la disposición de técnicas eficientes de optimización de rutas, puesto que no sólo afecta al desarrollo de las operaciones, sino que también incide en las decisiones tácticas y estratégicas (tamaño óptimo de flota, estimación de costes, políticas de publicidad y rotura de servicio, etc.

Medina y Yepes (2000) proporcionan un ejemplo práctico que muestra cómo la aplicación de técnicas de optimización condiciona críticamente el desarrollo de ciertas operaciones de distribución. Se trata de un negocio de venta de paquetes turísticos con transporte incluido; donde los precios se fijan mucho antes de que la demanda sea conocida, y donde son frecuentes las cancelaciones de última hora así como la llegada de nuevos clientes. Si el número de pasajeros es pequeño, en comparación con la máxima capacidad de carga del vehículo, los beneficios o las pérdidas generadas por el transporte dependen fuertemente de la eficiencia del sistema de optimización de rutas. La figura que sigue describe la influencia de la optimización de operaciones en la planificación y gestión de redes de distribución de baja demanda.

Planificación y gestión de redes de distribución. Fuente: Medina y Yepes (2000).
Planificación y gestión de redes de distribución. Fuente: Medina y Yepes (2000).

En apretada síntesis, la planificación y la gestión de las redes de distribución genera una gran variedad de problemas de decisión, cuyo éxito depende críticamente de la optimización de las operaciones, donde el espectro de soluciones posibles es enorme y además creciente exponencialmente con el número de destinos y el tamaño de la flota. Esta explosión combinatoria de soluciones y la complejidad de las variables impiden que la optimización sea, en muchas situaciones reales, abordable con técnicas de resolución exactas. Afortunadamente, existen procedimientos alternativos que, si bien no garantizan la solución óptima, sí proporcionan soluciones de calidad a los problemas cotidianos.

De esta forma, la resolución de los problemas de distribución se convierte en una de las parcelas notables de la Investigación Operativa. Incluso el recorte de una pequeña fracción de los costes puede aflorar enormes ahorros económicos y una reducción de los impactos medioambientales ocasionados por la polución y el ruido, además de incrementar significativamente la satisfacción de los requerimientos de los clientes.

Referencias

BACKER DE, B.; FURNON, V.; PROSSER, P.; KILBY, P.; SHAW, P.(1997). Local Search in Constraint Programming: Application to the Vehicle Routing Problem. Presented at the CP-97 Workshop on Industrial Constraint-based Scheduling, Schloss Hagenberg, Austria.

BALLOU, R.H. (1991). Logística empresarial. Control y planificación. Ed. Díaz de Santos, Madrid. 655 pp.

COMISIÓN DE TRANSPORTES DEL COLEGIO DE INGENIEROS DE CAMINOS, CANALES Y PUERTOS (2001). Libro Verde del Transporte en España. Disponible en internet. 111 pp.

CRAINIC, T.G.; LAPORTE, G. (1997). Planning Models for Freight Transportation. European Journal of Operational Research, 97: 409-438.

DRUCKER, P. (1962). The Economy’s Dark Continent. Fortune, april: 265-270.

GOLDEN, B.L.; WASIL, E.A. (1987). Computerized Vehicle Routing in the Soft Drink Industry. Operations Research, 35: 6-17.

HALSE, K. (1992). Modeling and Solving complex Vehicle Routing Problems. Ph.D. thesis, Department for Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark.

KING, G.F.; MAST, C.F. (1997). Excess Travel: Causes, Extent and Consequences. Transportation Research Record, 1111: 126-134.

KOBAYASHI, I. (1973). Management of Physical Distribution Cost. Proceedings of International Distribution Conference, Tokyo.

KOTLER, P. (1991). Marketing Management. Analysis, Planning, Implementation, and Control. Prentice Hall International. United Kingdom.

FISHER, M.L. (1997). Vehicle routing. In BALL, M.O.; MAGNANTI, T.L.; MONMA, C.L.; NEMHAUSER, G.L. (Eds.), Network Routing, volume 8 of Handbooks in Operations Research and Management Science, chapter 1, 1-79. North-Holland.

MEDINA, J.R.; YEPES, V. (2000). Optimización de redes de distribución con algoritmos genéticos, en Colomer, J.V. y García, A. (Eds.): Calidad e innovación en los transportes. Actas del IV Congreso de Ingeniería del Transporte. Vol. 1, pp. 205-213. Valencia.

MURPHY, G.J. (1972). Transport and Distribution. Business Books. London.

STEPHENSON, A.R. (1975).  Productivity Promotion Council of Australia: 7-10.

YEPES, V. (2002). Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW. Tesis Doctoral. Escuela Técnica Superior de Ingenieros de Caminos, Canales y Puertos. Universidad Politécnica de Valencia. 352 pp.

Licencia de Creative Commons
Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.