Algoritmos de optimización bio-inspirados

Algoritmos de optimización bio-inspirados​ para resolver eficientemente problemas de optimización en diversas áreas de aplicación.

Los algoritmos de optimización bio-inspirados son aquellos métodos que se inspiran generalmente en principios físicos, en la teoría de la evolución y en ciertos comportamientos de los seres vivos para resolver de manera eficiente problemas de optimización en muy diversas áreas de aplicación [1].

La historia de estos algoritmos comienza en 1975 cuando John Holland et al. propusieron el primer modelo de optimización basado en la teoría de la evolución de Charles Darwin, modelo que recibió el nombre de Algoritmo Genético (GA) [2]. Gracias a las posibilidades que ofrecían los algoritmos genéticos frente a los métodos de optimización tradicionales y con el incremento de la capacidad de cómputo de la tecnología, se desarrollaron una gran cantidad de algoritmos bio-inspirados a partir del año 2000. Entre estos métodos de optimización podemos encontrar desde algoritmos que simulan el alineamiento de partículas durante el enfriamiento de materiales (Simulated Annealing) hasta algoritmos que modelan el movimiento de galaxias (Galaxy-based Search Algorithm), pasando por algoritmos basados en el comportamiento colectivo de ciertas especies de animales [1, 3]. Algunos de los algoritmos más importantes se muestran en la Fig. 1.

Ejemplos de algoritmos de optimización bio-inspirados.PNG
Fig. 1: Ejemplos de algoritmos de optimización bio-inspirados.

Aunque todo algoritmo de optimización bio-inspirado ha sido diseñado de forma genérica para tratar cualquier problema de optimización, cada algoritmo bio-inspirado tiene sus particularidades propias que le hacen ser una mejor opción frente a otros algoritmos para resolver un problema específico. Por ejemplo, los algoritmos de colonias de hormigas son una buena elección para tratar problemas de enrutamiento, los algoritmos genéticos son una buena elección de forma general siempre que no haya que desarrollar métodos de reconstrucción de solución complejos al obtener soluciones inviables tras aplicar los operadores evolutivos, y el algoritmo de colonia de abejas suele ser una buena opción para tratar problemas de optimización combinatoria. Reside, por tanto, en la pericia del experto la correcta elección del algoritmo a aplicar para cada problema, así como el diseño de las funciones de cambio y optimización de solución que mejor se ajustan a ese problema.

¿Por qué son interesantes los algoritmos de optimización bio-inspirados frente a otros métodos de optimización?

En su origen, los algoritmos de optimización bio-inspirados se propusieron como métodos para poder tratar problemas de optimización muy complejos y cuya envergadura hiciese inviable el uso de métodos de resolución exactos debido a la cantidad de tiempo necesario para obtener la solución óptima. En la literatura, estos problemas reciben el nombre de problemas NP-completos.

La idea subyacente para el uso de estos algoritmos, y que es el motivo por el que estos algoritmos son realmente interesantes, reside en aprovechar las leyes de la física y los mecanismos que la propia naturaleza ha diseñado y mejorado durante millones años para resolver los tres grandes obstáculos a los que se puede enfrentar un ser vivo: reproducción, consecución de alimento y adaptación al medio. Con estos algoritmos podemos obtener soluciones cuasi-óptimas a problemas complejos en un tiempo razonable. Además, gran cantidad de los algoritmos de optimización bio-inspirados se basan en evolucionar poblaciones de individuos, siendo cada individuo una solución concreta del problema. Esto último hace los métodos de estos algoritmos se puedan paralelizar de forma muy fácil, permitiéndonos reducir considerablemente el tiempo en obtener una solución cuasi-óptima al aprovechar los beneficios de la computación paralela en una o incluso varias máquinas.


BIBLIOGRAFÍA
[1] A. Darwish, “Bio-inspired computing: Algorithms review, deep analysis, and the scope of applications”, Future Computing and Informatics Journal, vol. 3, no. 2, pp. 231-246, 2018.
[2] Xin-She Yang, “Genetic Algorithms”, Nature-Inspired Optimization Algorithms, chapter 6, 2nd edition, Academic Press, pp. 91-100, 2021.
[3] M. A. Rahman et al., “Nature-Inspired Metaheuristic Techniques for Combinatorial Optimization Problems: Overview and Recent Advances”, Mathematics, vol. 9, no. 20, 2633, 2021.

Acerca del autor

Autor
Víctor Berrocal oga
Víctor Berrocal
Senior Optimization Consultant en