algoritmo archivos - El blog de Víctor Yepes

El código secreto de la naturaleza: algoritmos metaheurísticos para resolver lo imposible.

Introducción: El genio oculto en el caos natural.

En el vasto universo de la gestión de situaciones complejas, nos enfrentamos a desafíos que cuestionan la lógica convencional: los problemas NP-difíciles.

Estos enigmas se caracterizan por que, a medida que el tamaño del problema aumenta, el tiempo necesario para resolverlo mediante fuerza bruta crece de manera exponencial. Esto hace que una búsqueda exhaustiva sea prácticamente imposible, incluso para las supercomputadoras más potentes. De este modo, cuando los métodos deterministas fallan y no hay garantía de hallar la solución perfecta, los expertos recurren a las metaheurísticas.

Al observar cómo la naturaleza optimiza los recursos para la supervivencia, hemos descubierto que el ensayo y el error no son fruto del azar, sino de un diseño refinado a lo largo de milenios de evolución. Los investigadores han dejado de mirar exclusivamente las pizarras para descifrar el genio oculto en los sistemas biológicos, físicos y químicos y han traducido procesos naturales en ecuaciones de optimización asombrosamente eficientes.

La inteligencia de enjambre: el poder de la multitud «sin inteligencia».

Uno de los pilares más fascinantes de esta disciplina es la inteligencia de enjambre (SI, por sus siglas en inglés). Este concepto se basa en el comportamiento colectivo emergente de múltiples agentes que interactúan según reglas muy sencillas. Ya sea en colonias de hormigas, enjambres de abejas o destellos de luciérnagas, el sistema logra una autorganización compleja sin necesidad de un mando central.

Lo más sorprendente es cómo la capacidad del colectivo trasciende las limitaciones del individuo. Un solo agente puede ser limitado, pero el enjambre, como unidad, exhibe una gran capacidad para resolver problemas. Como señala la literatura académica sobre este fenómeno:

«Aunque cada agente puede ser considerado como ininteligente, el sistema completo de múltiples agentes puede mostrar un comportamiento de autoorganización y, por lo tanto, puede comportarse como una suerte de inteligencia colectiva».

Más allá de la biología: la optimización se encuentra con la física y la música.

Aunque la biología es una fuente muy rica, la informática inspirada en la naturaleza trasciende mucho más. Para un especialista, la clasificación de estos algoritmos no se limita a su «musa», sino a su comportamiento matemático. Podemos categorizarlos según su trayectoria de búsqueda (como el Simulated Annealing) o según si se basan en poblaciones (como el Particle Swarm Optimization o el Firefly Algorithm).

Existen sistemas basados en leyes físicas y químicas, como los algoritmos que imitan la fuerza de la gravedad, las cargas eléctricas o la dinámica de formación de ríos. Incluso el arte tiene su lugar en el algoritmo Harmony Search (Búsqueda Armónica), que imita el proceso estético de un músico que persigue el «estado de armonía» o el acorde perfecto. Esta universalidad demuestra que los conceptos de disciplinas tan dispares pueden traducirse en reglas de actualización precisas para hallar soluciones casi óptimas en ingeniería y logística.

La trampa de las 28 000 especies: el desafío de la verdadera novedad.

A pesar del auge de estas técnicas, la comunidad científica se enfrenta a una realidad crítica: la proliferación de algoritmos que carecen de innovación real. Aunque en el mundo existen aproximadamente 28 000 especies de peces, esto no justifica la creación de 28 000 variantes algorítmicas (por ejemplo, el algoritmo del tiburón, de la trucha, etc.) que solo cambian los nombres de las variables sin aportar una mejora sustancial al motor de búsqueda.

En los últimos años, el mundo de la optimización ha experimentado una auténtica explosión de metaheurísticas. Nuevos algoritmos “inspirados en la naturaleza” están apareciendo como setas tras la lluvia. Solo en el último lustro, la comunidad científica se ha encontrado con miles de propuestas que se presentan como completamente originales.

El problema es que, en muchos casos, esas supuestas “novedades” no aportan ideas realmente nuevas. Son simplemente variantes, más o menos ingeniosas, de algoritmos ya conocidos y consolidados. Cambia el nombre, cambia la metáfora biológica o social, pero el mecanismo interno apenas difiere del de otros modelos existentes.

La situación ha llegado a tal punto que varias revistas científicas de alto impacto han decidido poner freno a esta tendencia. Muchas de ellas ya no aceptan trabajos que presenten una “nueva metaheurística” si no demuestran aportaciones metodológicas auténticas y verificables.

Esto supone una llamada a la acción para priorizar el rigor por encima de la «marca» comercial del algoritmo. Los expertos advierten sobre el peligro de la «pseudoinnovación» con fines de publicación:

No basta con bautizar un algoritmo con un nombre llamativo; tiene que resolver mejor los problemas reales.

La receta del éxito: mezcla, diversidad y paralelismo.

¿Por qué algoritmos como Cuckoo Search o el Firefly Algorithm triunfan, mientras que otros caen en el olvido? El éxito de un metaheurístico radica en su capacidad para equilibrar dos fuerzas opuestas:

Diversidad (búsqueda global/exploración): es la capacidad del algoritmo para explorar exhaustivamente el amplio espacio de búsqueda y evitar quedar atrapado en soluciones locales que parecen buenas, pero no lo son.
Mezcla (búsqueda local/explotación): es el proceso de recombinación e interacción entre soluciones que permite al algoritmo converger rápidamente hacia el punto óptimo una vez identificada una región prometedora.

Además, una ventaja competitiva de los algoritmos de inteligencia de enjambre es su facilidad de paralelización. Al basarse en múltiples agentes independientes, estos procesos pueden ejecutarse simultáneamente en hardware moderno, lo que permite optimizar problemas a gran escala en el mundo real por primera vez de forma práctica y eficiente.

Conclusión: hacia una nueva era de resolución de problemas.

Los algoritmos inspirados en la naturaleza han dejado de ser una mera curiosidad para convertirse en el estándar de oro para los problemas de alta complejidad. Es por ello que el futuro de esta disciplina no radica en buscar «más especies» que imitar, sino en profundizar en el marco matemático que permite que la diversidad y la mezcla funcionen en armonía. Solo a través de la comprensión real de estos mecanismos podremos hacer frente a los enormes desafíos de la tecnología moderna.

Al observar la elegancia con la que un enjambre encuentra su camino o un sistema físico alcanza el equilibrio, surge una pregunta inevitable: ¿existe algún límite a lo que podemos aprender sobre la eficiencia de la naturaleza o apenas estamos empezando a descifrar su código más fundamental?

En esta conversación puedes escuchar algunas de las ideas más interesantes sobre este tema.

En este vídeo se resumen algunos de los conceptos más importantes abordados.

Fister

Nature_Inspired_Optimization

Referencias:

FISTER JR, I.; YANG, X. S.; FISTER, I.; BREST, J.; FISTER, D. (2013). A brief review of nature‑inspired algorithms for optimization. arXiv preprint arXiv:1307.4186.

GARCÍA, J.; YEPES, V.; MARTÍ, J.V. (2020). A hybrid k-means cuckoo search algorithm applied to the counterfort retaining walls problem. Mathematics, 8(4), 555. DOI:10.3390/math8040555

GARCÍA, J.; MARTÍ, J.V.; YEPES, V. (2020). The buttressed walls problem: An application of a hybrid clustering particle swarm optimization algorithm. Mathematics, 8(6):862. DOI:10.3390/math8060862

GARCÍA-SEGURA, T.; YEPES, V.; ALCALÁ, J.; PÉREZ-LÓPEZ, E. (2015). Hybrid harmony search for sustainable design of post-tensioned concrete box-girder pedestrian bridges. Engineering Structures, 92:112-122. DOI:10.1016/j.engstruct.2015.03.015

GARCÍA-SEGURA, T.; YEPES, V.; MARTÍ, J.V.; ALCALÁ, J. (2014). Optimization of concrete I-beams using a new hybrid glow-worm swarm algorithm. Latin American Journal of Solids and Structures, 11(7):1190 – 1205. DOI:10.1590/S1679-78252014000700007

YEPES, V.; ALCALÁ, J.; PEREA, C.; GONZÁLEZ-VIDOSA, F. (2008). A Parametric Study of Optimum Earth Retaining Walls by Simulated Annealing. Engineering Structures, 30(3): 821-830. DOI:10.1016/j.engstruct.2007.05.023

YEPES, V. (2026). Heuristic Optimization Using Simulated Annealing. In: Kulkarni, A.J., Mezura-Montes, E., Bonakdari, H. (eds) Encyclopedia of Engineering Optimization and Heuristics. Springer, Singapore. https://doi.org/10.1007/978-981-96-8165-5_48-1

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

El algoritmo de la naturaleza: El secreto de las hormigas para resolver problemas imposibles

¿Cómo es posible que insectos con capacidades individuales sumamente limitadas resuelvan problemas geométricos y logísticos que a la humanidad le han llevado décadas de estudio formal para dominar?

En el rincón más sencillo de un jardín tiene lugar un fenómeno asombroso: una comunidad de diminutos seres encuentra, sin mapas, líderes jerárquicos ni tecnología GPS, el camino más corto entre un hormiguero y una fuente de alimento.

Este prodigio de la naturaleza no es solo una curiosidad biológica, sino la piedra angular de la optimización mediante colonias de hormigas (ACO), una potente metaheurística computacional que actúa como puente entre la eficiencia orgánica y los algoritmos más avanzados de la actualidad.

A continuación, exploramos cinco lecciones fundamentales que estos optimizadores naturales nos enseñan sobre la resolución de problemas complejos.

La inteligencia no reside en el individuo, sino en el colectivo.

En el mundo de las hormigas, la genialidad no es una cualidad de un «líder» con una visión superior, sino que surge del grupo. Así, el comportamiento inteligente surge de la masa, lo que desafía nuestras nociones tradicionales de gestión jerárquica. La ciencia ha comprobado que la brillantez del sistema no radica en sus componentes aislados, sino en la red de interacciones entre ellos.

Como se describe en los fundamentos de la inteligencia colectiva:

«En la naturaleza existen ejemplos de colectivos de individuos cuyo comportamiento es aparentemente inteligente, sin que esta característica se manifieste en sus componentes individuales».

Esta realidad nos invita a reflexionar sobre un cambio de paradigma: frente al liderazgo humano centralizado, la naturaleza propone una lógica bottom-up, en la que la suma de acciones simples y coordinadas supera la capacidad de cualquier genio individual.

El «Universo» como herramienta de comunicación dinámica.

Para que una colonia resuelva un problema, no es necesario que todas las hormigas conozcan el mapa completo del entorno. De hecho, ningún agente posee un conocimiento global. El éxito depende de la interacción con su «universo», que actúa como depositario físico de la información.

Según el contexto científico, deben cumplirse tres condiciones esenciales para que se produzca este comportamiento:

Existencia de un objetivo prioritario: una meta clara (como la locomoción o la alimentación) que proporciona un norte y, crucialmente, dicta el comportamiento de los agentes incluso en ausencia de información local.
Reglas de interacción local: si existe información local, el agente la utiliza para tomar decisiones que le permitan alcanzar el objetivo más rápidamente. Los agentes independientes depositan y modifican datos en el entorno, comunicando indirectamente los resultados de sus esfuerzos.
Un universo donde actuar: el entorno es la «geografía» por la que transitan. Es el medio que proporciona los datos necesarios y en el que se encuentra la memoria colectiva del sistema.

Feromonas: el rastro que se convierte en memoria adaptativa.

El proceso mediante el cual las hormigas optimizan sus rutas es un fascinante ciclo químico-digital. Todo comienza con una exploración aleatoria del entorno. Tan pronto como un individuo encuentra una fuente de alimento, evalúa su cantidad y calidad. Al regresar al hormiguero, deposita una sustancia química llamada feromona.

Este rastro oloroso sirve de señal para las demás hormigas. El camino más corto acaba ganando por una cuestión de frecuencia: las hormigas que viajan por la ruta más breve regresan antes y con mayor frecuencia, por lo que refuerzan ese rastro más rápido que en las rutas largas.

Sin embargo, la clave del éxito radica en la fragilidad del rastro: la feromona es dinámica y se evapora con el tiempo. Si un camino deja de usarse, la señal desaparece. Esta capacidad de «olvido» o plasticidad es vital, ya que permite que el sistema sea flexible y evita la «estagnación», impidiendo que la colonia se quede atrapada en soluciones locales, ya sean mediocres u óptimas, que ya no resultan eficientes ante un entorno cambiante.

De la biología al código: el espejo de la optimización.

La informática ha logrado traducir estos comportamientos biológicos en algoritmos de búsqueda altamente sofisticados. Para comprender esta transición del mundo natural al ámbito del procesador, es necesario observar cómo cada elemento biológico encuentra su contraparte matemática.

Esta estructura permite a los programadores utilizar la lógica de la colonia para explorar enormes espacios de soluciones, donde encontrar la respuesta perfecta sería inviable con métodos tradicionales.

No estamos solos: el club de los optimizadores naturales.

Las hormigas no son las únicas maestras del arte de la economía de recursos. La naturaleza es un club exclusivo de optimizadores en el que la eficiencia es una ley universal de supervivencia, no una invención humana. Otros ejemplos destacados son:

Los cisnes: al volar en formación de V, calculan una distribución espacial precisa para minimizar el esfuerzo total que debe realizar la bandada para desplazarse de un punto A a otro B.
Los depredadores y los peces: los patrones de ataque de los primeros y las formaciones de los segundos buscan la máxima efectividad con el mínimo riesgo energético.
Los ciclistas: apelotonándose instintivamente en una carrera para reducir la resistencia al viento, emulan estos patrones de optimización colectiva.

Conclusión: un futuro inspirado en lo pequeño.

En 1991, los investigadores Corloni, Dorigo y Maniezzo abrieron una puerta trascendental al sugerir que podíamos imitar el comportamiento de los insectos para resolver problemas de optimización combinatoria. Esa semilla científica nos permite hoy en día gestionar redes de tráfico complejas, diseñar ciudades más habitables y optimizar las cadenas logísticas globales que sustentan nuestra economía.

Si aprendiéramos a «escuchar» y a observar con mayor detenimiento los rastros y la información que fluyen en nuestro propio universo, quizá descubriríamos soluciones a problemas que hoy consideramos irresolubles.

En definitiva, nos queda una reflexión provocadora: si una hormiga no sabe que está resolviendo un algoritmo, ¿qué problemas estamos resolviendo colectivamente sin darnos cuenta?

En esta conversación puedes escuchar algunas de las ideas más interesantes sobre el tema.

Este vídeo resume bien los conceptos básicos de la optimización mediante la colonia de hormigas.

Ant_Colony_Optimization Ant_Colony_Optimization

Referencias:

COLORNI, A.; DORIGO, M.; MANIEZZO, V. (1991). Distributed optimization by ant colonies, in VARELA, F.J.; BOURGINE, P. (eds.) Proceedings of the First European Conference on Artificial Life (ECAL-91). The MIT Press: Cambrige, MA, 134-142.

MARTÍNEZ, F.; PEREA, C.; YEPES, V.; HOSPITALER, A.; GONZÁLEZ-VIDOSA, F. (2007). Optimización heurística de pilas rectangulares huecas de hormigón armado. Hormigón y Acero, 244: 67-80. ISBN: 0439-5689. (link)

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)

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.

Por qué «no existe la comida gratis» en el mundo de los algoritmos

El mito del algoritmo universal: una humillación necesaria.

Durante décadas, la comunidad científica persiguió con arrogancia el «santo grial»: el algoritmo de optimización universal. Se soñaba con una «caja negra», ya fuera basada en elegantes procesos evolutivos o en redes neuronales profundas, capaz de resolver cualquier problema, desde el diseño de un puente atirantado hasta la logística del viajante, con una eficiencia superior.

Sin embargo, esta búsqueda no solo era ambiciosa, sino que también era fundamentalmente errónea. La revelación de que no existe una inteligencia algorítmica absoluta supuso un golpe de humildad para quienes creían haber capturado la esencia del aprendizaje, cuando en realidad solo habían logrado un ajuste estadístico fortuito.

La revelación matemática: todos los algoritmos son, en promedio, iguales.

Este mito fue desmentido en 1997 por David Wolpert y William Macready. Sus teoremas «No Free Lunch» (NFL) establecieron una igualdad matemática absoluta que rompe el ego de cualquier programador: si promediamos el rendimiento sobre el conjunto de todos los problemas posibles, cualquier algoritmo sofisticado es idéntico a una búsqueda aleatoria.

Lo que un algoritmo gana en un tipo de problemas, lo paga inevitablemente con un fracaso estrepitoso en otro. No hay «comida gratis»: la superioridad de un algoritmo genético de última generación frente a un proceso de búsqueda ciega es una ilusión que solo se sostiene cuando ignoramos la inmensidad del espacio de funciones posibles.

El teorema uno nos muestra que el uso del conocimiento del dominio puede mejorar el rendimiento, a costa de la generalidad.

La geometría del éxito: el problema de la «alineación».

Para comprender la optimización del éxito, debemos abandonar la idea de la «fuerza bruta» y abrazar la geometría. Imagine el espacio de todas las funciones posibles como una esfera gigantesca. En este espacio, cada algoritmo es un vector v y la distribución de los problemas que deseamos resolver es otro vector p.

Estar «bien adaptado» a un problema significa que el vector del algoritmo apunta en la misma dirección que el del problema.

Alineación geométrica: que el vector del algoritmo apunte en la misma dirección que el del problema. El rendimiento es, en esencia, el producto interno de ambos vectores.
Sacrificio de la generalidad: un algoritmo «generalista» apunta hacia todas partes y, por tanto, su proyección (su éxito) en un punto concreto es nula.
Curvatura del conocimiento: el éxito no reside en el código, sino en cómo este «se dobla» para encajar con la estructura lógica y física del problema.

Los investigadores del problema del viajante no han creado algoritmos «mejores» en términos absolutos, sino que han esculpido herramientas íntimamente alineadas con la geometría específica de las rutas y las distancias.

El golpe al ego: el algoritmo aleatorio como juez de paz.

Los teoremas 5 y 6 de Wolpert y Macready introducen un estándar de rigor que actúa como un «mínimo ético» para la ciencia. Si un algoritmo no consigue que el coste disminuya más rápido que con una búsqueda aleatoria, el investigador habrá fracasado.

Esta métrica es el antídoto contra el fraude intelectual del ajuste fino o manual. Muchos de los éxitos que se describen en la literatura no son más que el resultado de forzar un algoritmo a un puñado de problemas específicos sin superar el umbral de una búsqueda ciega. Superar al «juez de paz» aleatorio es la única prueba de que el algoritmo ha logrado capturar alguna estructura real del problema.

Consecuencias prácticas: el fin del experto generalista.

En ingeniería civil, las implicaciones del NFL son tajantes. No existen programas comerciales que puedan optimizar cualquier estructura de forma indiscriminada. Las herramientas generales (como las toolboxes estándar de Matlab) suelen ser ineficaces porque carecen del «conocimiento del hormigón».

Esta realidad ha provocado una «carrera armamentística» hacia la especialización.

Hibridación: La respuesta de la ingeniería moderna consiste en combinar metaheurísticas con técnicas de deep learning y redes neuronales para «aprender» la estructura del dominio.
Alineación estructural: un matemático brillante fracasará al optimizar un puente atirantado si no comprende la resistencia de los materiales. No se trata de falta de cálculo, sino de que su algoritmo no está alineado con la «curvatura» física del problema. El conocimiento experto es lo que permite al algoritmo encontrar el camino en un espacio de búsqueda que, de otro modo, sería un desierto uniforme.

El dilema del observador: la ceguera del éxito pasado.

Incluso cuando un algoritmo ha funcionado bien hasta ahora, el teorema 10 (sección VII) nos da un jarro de agua fría: observar el rendimiento pasado no garantiza el éxito futuro sin un conocimiento adicional sobre la función de coste. Sin conocer la estructura, no vemos el siguiente paso.

En este estado de «oscuridad estructural», un procedimiento de elección «irracional» (cambiar un algoritmo que ha funcionado bien por otro que ha funcionado mal) es tan válido como uno «racional». Sin suposiciones sobre la relación entre el algoritmo y la función, el comportamiento pasado es un predictor pobre. La lógica solo surge cuando el observador aporta información que no está presente en los datos.

Conclusión: hacia una optimización consciente.

Debemos aceptar una verdad incómoda: nuestra inteligencia artificial es un reflejo limitado del conocimiento que somos capaces de codificar en ella. La ciencia de la optimización ya no debe buscar el «algoritmo perfecto», sino métodos más profundos para transferir el conocimiento del dominio al proceso de búsqueda.

Si el rendimiento de nuestras máquinas depende por completo de lo que ya sabemos sobre el mundo, ¿no será que la «inteligencia artificial general» es un mito termodinámico, similar a la máquina de movimiento perpetuo? Quizás el mayor descubrimiento de Wolpert y Macready no fue matemático, sino filosófico: la inteligencia no es más que el conocimiento del problema disfrazado de código.

En esta conversación puedes escuchar las ideas más interesantes sobre este tema.

Este vídeo resume bien los conceptos más importantes tratados.

The_Universal_Algorithm_Myth

Referencias:

GARCÍA, J.; YEPES, V.; MARTÍ, J.V. (2020a). A hybrid k-means cuckoo search algorithm applied to the counterfort retaining walls problem. Mathematics, 8(4), 555.

MARTÍNEZ-MUÑOZ, D.; GARCÍA, J.; MARTÍ, J.V.; YEPES, V. (2022). Optimal design of steel-concrete composite bridge based on a transfer function discrete swarm intelligence algorithm. Structural and Multidisciplinary Optimization, 65:312. DOI:10.1007/s00158-022-03393-9

NEGRÍN, I.; CHAGOYÉN, E.; KRIPKA, M.; YEPES, V. (2025). An integrated framework for Optimization-based Robust Design to Progressive Collapse of RC skeleton buildings incorporating Soil-Structure Interaction effects. Innovative Infrastructure Solutions, 10:446. DOI:10.1007/s41062-025-02243-z

WOLPERT, D.H.; MACREADY, W.G. (1997). No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation, 1(1):67-82.

YEPES-BELLVER, L.; BRUN-IZQUIERDO, A.; ALCALÁ, J.; YEPES, V. (2025). Surrogate-assisted cost optimization for post-tensioned concrete slab bridges. Infrastructures, 10(2): 43. DOI:10.3390/infrastructures10020043.

A continuación os dejo el artículo original «No Free Lunch Theorems for Optimization». Se ha convertido en un clásico de optimización heurística.

Pincha aquí para descargar

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

La inteligencia de la naturaleza: cinco lecciones de los algoritmos genéticos.

Optimizar una estructura de hormigón no es solo una cuestión de cálculo, sino una batalla contra la entropía. Además, en la búsqueda de la combinación precisa entre la cantidad de acero y la resistencia del hormigón, el ingeniero se enfrenta a un océano de variables en el que la solución «perfecta» suele estar oculta bajo capas de complejidad técnica. Por tanto, el proceso exige no solo rigor analítico, sino también una comprensión profunda de cómo interactúan todos los factores que condicionan el diseño estructural.

Ante este desafío, la ingeniería moderna ha dejado de lado las calculadoras para observar el mecanismo de diseño más refinado de la historia: la selección natural.

Hace más de un siglo, Charles Darwin descubrió que la supervivencia es el resultado de un proceso en el que sobreviven los más aptos y transmiten sus rasgos. Hoy en día, aplicamos este rigor biológico a los algoritmos genéticos. Estos sistemas no solo resuelven problemas, sino que también imitan la vida misma para encontrar respuestas con una elegancia estructural que antes considerábamos inalcanzable.

Lección 1: La evolución no ocurre en el individuo, sino en su código.

Una de las distinciones más profundas de la computación evolutiva es que la mejora de un sistema no se logra manipulando el objeto final (el puente o la viga), sino su receta original. Para que un algoritmo sea verdaderamente evolutivo, debe comprender que el éxito se forja en las estructuras subyacentes, tal y como lo definió Davis en 1991:

«La evolución opera en los cromosomas, en lugar de en los individuos a los que representan».

Este enfoque resulta fascinante por lo contraintuitivo que es: para optimizar una estructura física (el fenotipo), manipulamos un vector binario o un string (el genotipo). Al trabajar con la representación abstracta, permitimos que el código explore cambios profundos sin las limitaciones del diseño inmediato, entendiendo que el cromosoma es el verdadero custodio de la adaptación global.

Lección 2: El diccionario biológico del programador.

Para resolver problemas de ingeniería como si fueran organismos vivos, debemos traducir la realidad física a un lenguaje genético preciso. Ver una solución técnica como un «ser» con ADN transforma radicalmente nuestra metodología de resolución.

Fenotipo: la solución final y detectable; la expresión física de la interacción genética.
Genotipo: la estructura o plan maestro a partir del cual se construye el organismo.
Cromosoma: vector o cadena de datos que almacena información.
Gen: Cada elemento del vector (un «vagón de tren» en la cadena de datos).
Alelo: el valor específico que adopta ese elemento (el bit o dato concreto).
Locus: posición exacta del gen, fundamental porque controla un carácter específico de la solución.
Aptitud (fitness): función objetivo que mide la capacidad de la solución para sobrevivir en su entorno técnico.

Lección 3: La «ruleta» de la supervivencia y la selección natural.

La selección natural no funciona como un sorteo, aunque tampoco actúa como una sentencia absoluta. Este principio se traslada al código mediante el método de la ruleta. En dicho procedimiento, cada solución se representa por un segmento circular cuya superficie es proporcional a su nivel de aptitud.

Esta «justicia algorítmica» garantiza que los mejores tengan mayores probabilidades de dejar descendencia. Sin embargo, no garantiza el monopolio de la reproducción, ya que los individuos menos aptos mantienen una pequeña probabilidad de transmitir sus genes. Este «caos controlado» es vital, ya que garantiza la diversidad estructural y evita que el algoritmo se estanque en óptimos locales, es decir, soluciones que parecen buenas solo porque el sistema ha perdido la capacidad de mirar más allá de lo inmediato.

Lección 4: Cruzamiento y mutación. El «sexo» de los datos.

La evolución exige novedad. Si nos limitáramos a clonar a los mejores, el progreso se detendría. Por ello, los algoritmos utilizan la recombinación o cruzamiento, mediante el cual dos progenitores intercambian información para crear descendientes con rasgos mixtos. Se destacan operadores sofisticados como el PMX (Partially-Matched Crossover), que copia un fragmento del código manteniendo las posiciones y rellena el resto con valores no utilizados, y el SEX (Strategic Edge Crossover), que busca identificar y preservar secuencias presentes en ambos progenitores.

Pero la mezcla no es suficiente. Es necesaria la mutación para introducir variaciones que no existían en la población original.

«Mutación: modificación espontánea de la información genética».

La mutación actúa como un factor de diversificación radical. Ya sea reemplazando un bit o recombinando elementos al azar sin considerar su aptitud inicial, este mecanismo introduce el «ruido» necesario para sacudir el sistema y permitirle dar el salto a fronteras de eficiencia completamente nuevas.

Lección 5: La memoria es un lastre para la evolución.

Siguiendo la lógica de Holland, uno de los conceptos más disruptivos de la evolución es su capacidad para vivir en el presente absoluto. A diferencia de otros sistemas de optimización que arrastran sesgos históricos, la evolución es un proceso sin memoria en el sentido estricto, ya que es una eficiencia de estado.

Durante la formación de nuevos cromosomas, el algoritmo solo tiene en cuenta la información del periodo inmediatamente anterior. Este enfoque «radical» permite que el sistema converja hacia la excelencia técnica basándose exclusivamente en la eficacia actual de los rasgos, sin verse frenado por configuraciones que fueron útiles en el pasado, pero ya no sirven para afrontar los desafíos del presente. Se podría decir que es una búsqueda de la perfección despojada de prejuicios históricos.

Los algoritmos genéticos demuestran que la naturaleza ya había resuelto los problemas de optimización más difíciles hace millones de años. Al adoptar estas leyes biológicas, la ingeniería no solo encuentra mejores soluciones para sus puentes y edificios, sino que lo hace con una elegancia que solo la evolución puede dictar.

Si principios tan elementales como la herencia y la mutación pueden dar lugar a estructuras de hormigón de una eficiencia asombrosa, ¿qué otros procesos naturales esconden hoy la clave para el próximo gran avance en la inteligencia de nuestro software?

En esta conversación puedes escuchar las ideas más interesantes sobre este tema.

Este vídeo resume bien los conceptos básicos de los algoritmos genéticos.

Aquí tenéis un vídeo en el que explico este algoritmo. Espero que os interese.

Genetic_Algorithms

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.

Algoritmia, heurísticas y optimización computacional

En el corazón de nuestra civilización digital late un motor invisible que solemos dar por sentado. Lo que en el siglo IX nació como una serie de reglas rígidas para el cálculo algebraico —el legado de Al-Juarismi— ha evolucionado hasta convertirse en el concepto moderno de algoritmo: una sofisticada «receta» diseñada para manipular información mediante operaciones elementales. En la actualidad, los algoritmos no son solo curiosidades matemáticas, sino la infraestructura lógica que decide desde la ruta de un camión de reparto hasta la resistencia de un viaducto de hormigón. Sin embargo, ¿comprendemos realmente las leyes que rigen su eficiencia o somos ciegos ante las reglas que separan lo posible de lo imposible?

El concepto de algoritmo ha evolucionado desde una acepción antigua, centrada en reglas para operaciones algebraicas, hacia una visión moderna: un conjunto prescrito de reglas o instrucciones bien definidas para resolver un problema específico en un número finito de pasos. En esencia, se trata de un método para manipular información mediante operaciones elementales.

A continuación, desvelamos cinco realidades esenciales para navegar por este universo de precisión y complejidad.

1. Los pilares del rigor: más allá del simple «paso a paso».

A menudo se define el algoritmo como una lista de instrucciones, pero para la ciencia de la computación esta definición es insuficiente. Un algoritmo debe ser un baluarte contra la ambigüedad, ese «fantasma en la máquina» que detiene en seco cualquier proceso lógico. Un método solo alcanza la categoría de algoritmo si cumple cuatro condiciones necesarias, pero no suficientes.

Precisión: cada instrucción debe indicar exactamente qué acción realizar, sin margen de interpretación.
Finitud: el proceso debe tener un final garantizado tras un número determinado de pasos.
Efectividad: cada operación debe poder ser ejecutada por el ejecutor (humano o máquina) en un tiempo finito.
Entrada y salida: debe existir un punto de partida de datos y un resultado concreto.

La finitud no es solo una exigencia teórica, sino también una restricción física. En un mundo de recursos limitados, un proceso que no termina nunca no es una solución, sino un abismo de consumo de energía.

2. El enigma de P vs. NP

Existe una frontera que divide los problemas en dos grandes categorías. Por un lado, la clase P, que agrupa los problemas que podemos resolver rápidamente (de forma eficiente). Por otro lado, está la clase NP, que incluye problemas cuya solución, aunque difícil de encontrar, puede verificarse con rapidez una vez que la tenemos. La gran pregunta que obsesiona a los genios desde 1971 es si resolver es intrínsecamente más difícil que verificar.

«¡Hoy en día no se ha podido demostrar que P = NP!»

Científicamente, sabemos que P ⊂ NP, pero el gran misterio radica en el «empate». Si se demostrara que P = NP, significaría que para la mayoría de los retos complejos de nuestra era —desde la criptografía hasta el diseño estructural— existen algoritmos de una eficiencia asombrosa que aún no hemos logrado ver.

3. La tiranía del tiempo: el análisis del «peor caso».

En ingeniería y computación, el rendimiento no es cuestión de suerte. Para medirlo, recurrimos a la teoría del análisis asintótico de funciones, que nos permite predecir cómo crecerá el esfuerzo de cálculo a medida que aumenta la dimensión del problema (n). Para un especialista, no basta con saber cuánto tarda un algoritmo de media; lo vital es el análisis del peor caso. Este define el coste máximo de aplicar el algoritmo a cualquier problema de tamaño n.

Aquí es donde la matemática se vuelve tangible. Imagine que n representa el número de ciudades que un camión debe visitar.

Complejidad polinómica (O(n^k)): El tiempo crece de forma controlada. Estos problemas se consideran «resolubles eficientemente».
Complejidad exponencial: El tiempo de cálculo aumenta de forma exponencial. Un ligero aumento en el número de ciudades puede hacer que el ordenador necesite más tiempo que la edad del universo para hallar la respuesta.

4. El drama de los problemas NP-completos.

Dentro del vasto territorio de la clase NP, existe una «aristocracia» del caos: los problemas NP-completos (NPC). El ejemplo más célebre es el problema del viajante (O(n² 2^n)). Estos problemas son fascinantes porque están interconectados: si alguien lograra encontrar un algoritmo polinómico para resolver un problema NPC, automáticamente todos los problemas NP pasarían a ser resolubles de manera eficiente.

Mientras ese día no llegue, los problemas NPC representan el muro contra el que choca la potencia bruta. En ellos, añadir un solo dato más a la entrada no solo implica trabajo, sino que multiplica la dificultad hasta el punto de que la realidad física se vuelve incapaz de soportar el cálculo.

5. El arte de la heurística: la sabiduría de lo «suficientemente bueno».

¿Qué debe hacer un ingeniero ante un problema cuya solución perfecta tardaría milenios en aparecer? La respuesta está en las heurísticas y las metaheurísticas. Se trata de algoritmos aproximados que actúan como un «Plan B» inteligente cuando la perfección se convierte en el enemigo de lo posible.

Sin embargo, el orden de los factores sí altera el producto. Si un problema de optimización se presenta en forma algebraica, es imperativo intentar primero las técnicas clásicas. No tiene sentido utilizar una heurística si los métodos Simplex (para problemas lineales) o de gradiente (para problemas no lineales) pueden proporcionarnos la respuesta exacta. Solo cuando estas herramientas fallan o su lentitud resulta inasumible, recurrimos a la intuición algorítmica.

Conclusión: Hacia una nueva frontera de optimización.

El viaje desde las antiguas reglas de cálculo hasta la optimización de las estructuras de hormigón modernas nos enseña que el límite de la ingeniería no está en la potencia de los procesadores, sino en la elegancia de nuestros métodos. El éxito consiste en saber navegar entre el rigor asintótico y la flexibilidad heurística.

En última instancia, nos enfrentamos a una pregunta que definirá el futuro de nuestra capacidad técnica: ¿residirá el progreso en la búsqueda incansable del algoritmo perfecto que demuestre que P = NP o en perfeccionar nuestra capacidad para utilizar la intuición heurística y construir un mundo «suficientemente bueno» antes de que se agote el tiempo?

En esta conversación podéis escuchar las ideas más interesantes sobre este tema.

El vídeo resume bien los conceptos más importantes de la algoritmia y la complejidad computacional.

Aquí os dejo un resumen de este asunto.

Algorithmic_Complexity_and_Structural_Optimization

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

Fórmula del área de Gauss para la cubicación en movimiento de tierras

Figura 1. El cruce de productos de coordenadas empleado en el algoritmo de la lazada. Wikipedia.

El Algoritmo de la Lazada, también llamado Fórmula del área de Gauss, es una técnica matemática utilizada para calcular el área de un polígono simple a partir de sus vértices, los cuales son representados por pares de coordenadas en un plano.

La fórmula recibe su nombre por la forma en que se cruzan los productos de las coordenadas correspondientes de cada par de vértices, que recuerda el proceso de atar una lazada. Este método es ampliamente empleado en la cubicación de movimiento de tierras, entre otras áreas. Además, se le llama Fórmula del área de Gauss en homenaje a Carl Friedrich Gauss.

La fórmula puede expresarse de la siguiente forma:

Como se puede observar en la Figura 1, el algoritmo es muy sencillo de aplicar, pues basta realizar la diferencia de los productos cruzados. Para que veáis un ejemplo resuelto, os paso un problema que espero que sea de vuestro interés. En este caso, se calcula el área de un polígono irregular (Figura 2). El cálculo del área puede ejecutarse de distintas formas, como por ejemplo, dividiéndola en sucesivos triángulos. Pero se va a utilizar la fórmula del área de Gauss, pues es muy útil su programación en el cálculo mediante ordenador en la cubicación en tierras.

Figura 2. Polígono irregular formado por siete puntos.

A continuación os dejo un vídeo explicativo y un problema resueltos que, espero, sean de vuestro interés. Se trata de uno de los muchos casos que explicamos en el Curso de gestión de costes y producción de la maquinaria empleada en la construcción. Os animo a que, si estáis interesados, os informéis de este curso en línea.

Pincha aquí para descargar

Referencias:

YEPES, V. (1995). Maquinaria de movimiento de tierras. Servicio de Publicaciones de la Universidad Politécnica de Valencia. SP.UPV-264. 144 pp.

YEPES, V. (1997). Equipos de movimiento de tierras y compactación. Problemas resueltos. Colección Libro Docente n.º 97.439. Ed. Universitat Politècnica de València. 256 pág. Depósito Legal: V-4598-1997. ISBN: 84-7721-551-0.

YEPES, V. (2022). Gestión de costes y producción de maquinaria de construcción. Colección Manual de Referencia, serie Ingeniería Civil. Editorial Universitat Politècnica de València, 243 pp. Ref. 442. ISBN: 978-84-1396-046-3

YEPES, V. (2023). Maquinaria y procedimientos de construcción. Problemas resueltos. Colección Académica. Editorial Universitat Politècnica de València, 562 pp. Ref. 376. ISBN 978-84-1396-174-3

Curso:

Curso de gestión de costes y producción de la maquinaria empleada en la construcción.

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

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 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:

Generar una población de vectores (individuos).
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.

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)

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.

La revolución de la digitalización en la ingeniería civil

En una entrada anterior que denominé «La ingeniería de caminos en el siglo XXI, ¿quo vadis?«, puse de manifiesto la incertidumbre que suponía la desaparición de la titulación de ingeniero de caminos, canales y puertos con motivo de la reestructuración de las enseñanzas universitarias en grado y máster. Las preguntas que dejaban en el aire adquirían un tinte dramático cuando se contextualizaban en una situación de profunda crisis económica, especialmente fuerte en el sector de la construcción.

Otra reflexión sobre el futuro de la profesión la dejé en la entrada «¿Qué entendemos por «Smart Construction»? ¿Una nueva moda?«. Allí dejé constancia de las modas que igual que aparecen, desaparecen, pero que suponen cambios sustanciales en una profesión como la de ingeniero civil. Allí expresé mi esperanza de que el término de “construcción inteligente” tuviera algo más de recorrido y pudiera suponer un punto de inflexión en nuestro sector. Este término presenta, como no podía ser de otra forma, numerosas interpretaciones y tantas más aplicaciones. Es un concepto que se asocia al diseño digital, a las tecnologías de la información y de la comunicación, la inteligencia artificial, al BIM, al Lean Construction, la prefabricación, los drones, la robotización y automatización, a la innovación y a la sostenibilidad, entre otros muchos conceptos. Entre estos conceptos, uno que me interesa especialmente es la asociación con el de los nuevos métodos constructivos (término que incluye nuevos productos y nuevos procedimientos constructivos). Su objetivo es mejorar la eficiencia del negocio, la calidad, la satisfacción del cliente, el desempeño medioambiental, la sostenibilidad y la previsibilidad de los plazos de entrega. Por lo tanto, los métodos modernos de construcción son algo más que un enfoque particular en el producto. Involucran a la gente a buscar mejoras, a través de mejores procesos, en la entrega y ejecución de la construcción.

Al hilo de estas reflexiones, me ha gustado especialmente el vídeo ganador del concurso de la Asociación de Ingenieros de Caminos, Canales y Puertos, ingeniería en 200 segundos, que presenta Juan Antonio Martínez Ortega, y que trata del impacto de la digitalización en la ingeniería civil. Atento al «diablillo de Laplace«. ¡Enhorabuena para Juan Antonio!

Optimización heurística mediante aceptación por umbrales

En algunos posts anteriores hemos comentado lo que es un modelo matemático de optimización, qué son las metaheurísticas, o cómo poder optimizar las estructuras de hormigón. A continuación os presentamos un Polimedia donde se explica brevemente cómo podemos optimizar siguiendo la técnica de optimización heurística mediante aceptación por umbrales. Podréis comprobar cómo se trata de un caso similar a la famosa técnica de la cristalización simulada. Espero que os sea útil.

Podéis consultar, a modo de ejemplo, algunos artículos científicos que hemos escrito a ese respecto en las siguientes publicaciones:

CARBONELL, A.; GONZÁLEZ-VIDOSA, F.; YEPES, V. (2011). Heuristic optimization of reinforced concrete road vault underpasses. Advances in Engineering Software, 42(4): 151-159. ISSN: 0965-9978. (link)
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)
YEPES, V.; MEDINA, J.R. (2006). Economic Heuristic Optimization for Heterogeneous Fleet VRPHESTW. Journal of Transportation Engineering, ASCE, 132(4): 303-311. (link)

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

¿Qué es la optimización por cristalización simulada?

La cristalización simulada (también llamado recocido simulado) “Simulated Annealing, SA” constituye una de las estrategias a las que se recurre en la resolución de los problemas de optimización combinatoria. Kirkpatrick, Gelatt y Vecchi la propusieron por primera vez en 1983, y Cerny la propuso de forma independiente en 1985. Estos autores se inspiraron en los trabajos de Metrópolis et al. (1953) sobre Mecánica Estadística. La metaheurística despliega una estructura que se inserta cómodamente en la programación y, además, muestra una considerable habilidad para escapar de los óptimos locales. Fue una técnica que experimentó un auge considerable en la década de los 80 para resolver problemas de optimización mediante modelos matemáticos.

La energía de un sistema termodinámico se compara con la función de coste evaluada para una solución admisible de un problema de optimización combinatoria. En ambos casos se trata de evolucionar de un estado a otro de menor energía o coste. El acceso de un estado metaestable a otro se alcanza introduciendo “ruido” mediante un parámetro de control, denominado temperatura. Su reducción adecuada permite, con una probabilidad elevada, que un sistema termodinámico adquiera un mínimo global de energía. Conceptualmente, es un algoritmo de búsqueda por entornos que selecciona candidatos de forma aleatoria. La alternativa se aprueba si perfecciona la solución actual (D ≤ 0); en caso contrario, será aceptada con una probabilidad e^(-D/T), donde T es el parámetro de temperatura, si D > 0. El proceso se repite cuando la propuesta no es admitida. La selección aleatoria de soluciones degradadas permite eludir los mínimos locales. La cristalización simulada se codifica fácilmente, incluso en problemas complejos y con funciones objetivo arbitrarias. Además, independientemente de la solución inicial, el algoritmo converge estadísticamente a la solución óptima (Lundy y Mees, 1986). En cualquier caso, SA suele ofrecer soluciones valiosas, aunque no informa si ha alcanzado el óptimo absoluto. Por contra, al ser un procedimiento general, en ocasiones no resulta competitivo, aunque sí comparable, frente a otros específicos que aprovechan información adicional del problema. El algoritmo es lento, especialmente si la función objetivo es costosa en términos de tiempo de computación. Además, la cristalización simulada pierde terreno frente a otros métodos más simples y rápidos, como el descenso local, cuando el espacio de las soluciones es poco abrupto o escasean los mínimos locales.

Os dejo un vídeo explicativo:

Referencias

CERNY, V. (1985). Thermodynamical approach to the traveling salesman problem: an efficient simulated algorithm. Journal of Optimization Theory and Applications, 45: 41-51.

KIRKPATRICHK, S.; GELATT, C.D.; VECCHI, M.P. (1983). Optimization by simulated annealing. Science, 220(4598): 671-680.

LUNDY, M.; MEES, A. (1986). Convergence of an Annealing Algorithm. Mathematical programming, 34:111-124.

METROPOLIS, N.; ROSENBLUTH, A.W.; ROSENBLUTH, M.N.; TELLER, A.H.; TELER, E. (1953). Equation of State Calculation by Fast Computing Machines. Journal of Chemical Physics, 21:1087-1092.

GONZÁLEZ-VIDOSA-VIDOSA, F.; YEPES, V.; ALCALÁ, J.; CARRERA, M.; PEREA, C.; PAYÁ-ZAFORTEZA, I. (2008) Optimization of Reinforced Concrete Structures by Simulated Annealing. TAN, C.M. (ed): Simulated Annealing. I-Tech Education and Publishing, Vienna, pp. 307-320. (link)