¿Cómo se podrían optimizar, en tiempos de cálculo razonables, problemas complejos de redes de transporte, estructuras de hormigón (puentes, pórticos de edificación, túneles, etc.) y otros tipos de problemas de decisión empresarial cuando la dimensión del problema es de tal calibre que resulta imposible resolverlos con métodos matemáticos exactos? La respuesta consiste en métodos aproximados, también denominados heurísticos. Este artículo divulgativo trata de ampliar otros anteriores en los que ya hablamos de los algoritmos, de la optimización combinatoria, de los modelos matemáticos y otros temas similares. Más adelante explicaremos otros temas relacionados específicamente con aplicaciones a problemas reales. Aunque para los más curiosos, os paso en abierto una publicación donde se han optimizado con éxito algunas estructuras de hormigón como muros, pórticos o marcos de carretera: (González et al., 2008).
Desde los primeros años de la década de los 80, la investigación sobre los problemas de optimización combinatoria se centra en el diseño de estrategias generales que guíen las heurísticas. Se les ha llamado metaheurísticas. Se trata de combinar inteligentemente diversas técnicas para explorar el espacio de soluciones. Osman y Kelly (1996) nos aportan la siguiente definición: “Los procedimientos metaheurísticos son una clase de métodos aproximados diseñados para resolver problemas de optimización combinatoria difíciles, en los que los heurísticos clásicos no son ni efectivos ni eficientes. Los metaheurísticos proporcionan un marco general para crear nuevos algoritmos híbridos que combinan diferentes conceptos derivados de la inteligencia artificial, la evolución biológica y la mecánica estadística”.
Aunque existen diferencias apreciables entre los distintos métodos desarrollados hasta el momento, todos ellos tratan de conjugar en mayor o menor medida la intensificación en la búsqueda –seleccionando movimientos que mejoren la valoración de la función objetivo-, y la diversificación –aceptando aquellas otras soluciones que, aun siendo peores, permiten la evasión de los óptimos locales-.
Las metaheurísticas pueden agruparse de varias formas. Algunas clasificaciones recurren a cambios sucesivos de una solución a otra en la búsqueda del óptimo, mientras otras se sirven de los movimientos aplicados a toda una población de soluciones. El empleo, en su caso, de la memoria que guíe la exploración del espacio de posibles elecciones permite otro tipo de agrupamiento. En otras circunstancias, se emplean perturbaciones en las opciones, en la topología del espacio de soluciones o en la función objetivo. En la Figura se presenta una propuesta de clasificación de las heurísticas y metaheurísticas empleadas en la optimización combinatoria (Yepes, 2002), que comparten todas ellas la necesidad de contar con soluciones iniciales que permitan cambios para alcanzar otras mejores. Es evidente que en este momento existen muchas más técnicas de optimización, pero dicha clasificación puede ser un punto de partida para una mejor taxonomía de dichas técnicas.
Las metaheurísticas empleadas en la optimización combinatoria podrían clasificarse en tres grandes conjuntos. Las primeras generalizan la búsqueda secuencial por entornos de modo que, una vez se ha emprendido el proceso, se recorre una trayectoria de una solución a otra vecina hasta que este concluye. En el segundo grupo se incluyen los procedimientos que actúan sobre poblaciones de soluciones, evolucionando hacia generaciones de mayor calidad. El tercero lo constituyen las redes neuronales artificiales. Esta clasificación sería insuficiente para aquellas metaheurísticas híbridas que emplean, en mayor o menor medida, estrategias de unos grupos y otros. Esta eventualidad genera un enriquecimiento deseable de posibilidades adaptables, en su caso, a los distintos problemas de optimización combinatoria.
Referencias
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)
OSMAN, I.H.; KELLY, J.P. (Eds.) (1996). Meta-Heuristics: Theory & Applications. Kluwer Academic Publishers.
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)
Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.
