Categoría: transporte

Resulta fascinante comprobar cómo, aplicando los mecanismos básicos de la evolución ya descritos 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 en 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 a la teoría de Darwin son de una profundidad difícil de comprender cuando se llevan a sus últimas consecuencias. 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 quienes estén interesados, os paso en las referencias un par de artículos en los que 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 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á quitar los cimientos más profundos de sus creencias. Os paso la referencia al final.

Básicamente, los algoritmos genéticos, o “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 por su material genético. A nivel de los genes, el problema consiste en buscar adaptaciones beneficiosas en un medio hostil y cambiante. Debido, en parte, a la selección natural, cada especie gana cierta “información” que se incorpora a sus cromosomas.

Durante la reproducción sexual, un nuevo individuo, diferente de sus padres, se genera mediante 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 conservará parte de sus características. Si los hijos heredan buenos atributos de sus padres, su probabilidad de supervivencia será mayor que la de aquellos que no los tengan. De este modo, los mejores tendrán altas probabilidades de reproducirse y de transmitir 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 puede asociarse a una solución factible del problema, de modo que pueda codificarse como un vector binario “string”. Entonces, un operador de cruzamiento intercambia las 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 según 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 padres que serán reemplazados por la población.
   2. Emparejar aleatoriamente a los progenitores y cruzarlos para obtener unos vectores hijos.
   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 los individuos menos eficaces.

Normalmente este proceso finaliza después de un número determinado de generaciones o cuando la población ya no puede mejorar. La selección de los padres se realiza de forma probabilística hacia los individuos más aptos. Al igual que ocurre en la naturaleza, los sujetos con mayor aptitud difunden sus características a lo largo de toda la población.

Esta descripción de los GA se adapta a cada situación concreta, siendo habitual la codificación en números enteros en lugar de binaria. Del mismo modo, se han sofisticado los distintos operadores de cruzamiento y de 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.

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