Academia Mexicana de Ciencias
Boletín AMC/159/18
Ciudad de México, 6 de julio de 2018

• Las metaheurísticas se usan para la solución de problemas en sistemas de control (robótica, estructuras), programación de horarios (scheduling), bioinformática (clasificación y optimización), minería de datos (sobre todo con grandes volúmenes de datos), hidráulica (calibración de modelos, redes hidráulicas), ingeniería aeronáutica (diseño de aviones, perfiles aerodinámicos), clasificación y reconocimiento de patrones y problemas de transporte.

Por la flexibilidad y facilidad de uso que ofrecen, las metaheurísticas se han vuelto una opción recurrente para resolver problemas de alta complejidad, sobre todo de optimización, destaca Carlos Coello Coello, investigador del Cinvestav y miembro de la Academia Mexicana de Ciencias.
Foto: Elizabeth Ruiz Jaimes/AMC.
Imagen en alta resolución

El rápido crecimiento de los procesadores, el incremento de la velocidad con la que operan y el abaratamiento de las memorias de las computadoras hacia finales del siglo XX contribuyó a popularizar el uso de las metaheurísticas, técnicas que buscan soluciones buenas donde bueno no necesariamente significa óptimo —lo cual no es problema porque los problemas que se resuelven con metaheurísticas son de alta complejidad—, y tienen un costo computacional razonable.

Para comprender qué es una metaheurística, antes es necesario definir qué es una heurística, palabra que deriva del griego heuresis, que significa hallar o inventar (etimología que comparte con eureka). “En los orígenes de la inteligencia artificial, en los años cincuenta del siglo pasado, se decía que una heurística era el antónimo de algoritmo. La mayor parte de los procesos que se realizan en una computadora se reducen a un algoritmo, que indica una serie de pasos sistemáticos que se siguen para resolver una tarea”, dijo Carlos Coello Coello, investigador del Departamento de Computación del Centro de Investigación de Estudios Avanzados (Cinvestav).

Hoy en día se usa este término como un adjetivo, por tanto, una metaheurística es cualquier técnica que mejore el desempeño en promedio de la solución de un problema. Por ejemplo: se tiene un problema de optimización de búsqueda muy complicado y quizá el mejor algoritmo que se conoce tardaría 50 años en resolverlo, lo que lleva a encontrar una manera de hacer la búsqueda un poco más eficiente con una solución de un algoritmo que lleve horas o días, pero no años. “Las metaheurísticas son esas reglas que llevan a resolver de manera más eficiente los problemas, aunque no se garantiza que la solución sea óptima ni siquiera válida, eso es lo que se sacrifica cuando se usan”, explicó el doctor en ciencias de la computación.

Hay metaheurísticas de diferentes tipos: las deterministas, las cuales siempre siguen el mismo tipo de reglas, y las bioinspiradas, que en general no son deterministas, son probabilísticas o estocásticas porque se basan en números aleatorios, lo que las hace interesantes, pues cada vez que se ejecutan el resultado puede ser diferente con una pequeña variable.

Ventajas y desventajas
Por la flexibilidad y facilidad de uso que ofrecen, las metaheurísticas se han vuelto una opción recurrente para resolver problemas (sobre todo de optimización) de alta complejidad, sin embargo, se recomienda su uso prudente al no ser adecuadas para todo tipo de problemas.

El investigador consideró también que, por su utilidad, este es el siglo de las metaheurísticas, ya que su uso se popularizará aún más y se les utilizará para problemas cada vez más complejos y desafiantes como el diseño de fármacos.

Carlos Coello Coello trabaja desde el año 2001 en el Cinvestav, es pionero en la optimización evolutiva multiobjetivo, área que se enfoca en la solución de problemas utilizando algoritmos con inspiración biológica; con sus diseños de algoritmos ha ayudado a resolver problemas en Estados Unidos, Colombia, Chile y Cuba.

Las metaheurísticas constituyen la última línea de defensa en optimización. No obstante, además de no poder garantizar que encontrarán la solución óptima al problema, su costo computacional hace prohibitivo su uso en algunos problemas, reconoció el experto.

Metaheurísticas bioinspiradas
En optimización, una metaheurística puede verse como un método numérico que utiliza cierta información del problema para hacer una búsqueda relativamente eficiente, sin garantizar que se obtendrá el óptimo global. Pese a sus aparentes limitantes, las metaheurísticas se han vuelto muy populares en los últimos 25 años, ya que los métodos exactos solo pueden aplicarse a ciertas clases de problemas de optimización, mientras que los diseñados para problemas discretos se basan en el uso de búsquedas exhaustivas.

El doctor Coello, secretario de la Academia Mexicana de Ciencias, señaló en la charla que impartió sobre el tema en el Foro de Química de Universum, Museo de las Ciencias, que dentro de las diferentes metaheurísticas que se conocen hay una clase en particular que se ha vuelto muy popular en los últimos años y están basadas en conceptos biológicos, las cuales se conocen como metaheurísticas bioinspiradas, y aunque solo se refirió a cuatro de ellas —algoritmos evolutivos, cúmulos de partículas, sistemas inmunes artificiales y colonias hormigas—, apuntó que existen muchas más.

Los algoritmos evolutivos se basan en simular en una computadora el principio de la supervivencia del más apto, de la teoría evolutiva de Charles Darwin. Se inventó en los años sesenta del siglo XX, y lo que se realiza en la computadora es crear un conjunto de soluciones que en computación se les llaman individuos. Estos individuos son la población que va a evolucionar, cada interacción que hacen del algoritmo es una generación que está evolucionando, así, la búsqueda se guía por algo denominado la función de aptitud.

“Si estoy tratando de minimizar un problema, las soluciones que representen los valores más pequeños son más aptas que las que representen valores más grandes, lo que indica que los más aptos tienen mayor posibilidad de sobrevivir, y los que lo hacen se reproducen, se dice que se usa la cruza sexual: dos padres generan dos hijos y éstos son mutados, se les hace un pequeño cambio en la solución y van evolucionando. Es una simulación muy burda de lo que ocurre en la naturaleza, el mecanismo de selección que usamos está basado en la selección natural de Darwin, sin embargo, esta técnica, a pesar de lo simple que es, ha logrado resolver problemas de muy alta complejidad”, destacó.

En la actualidad existen tres tipos de algoritmos evolutivos principales: programación evolutiva, estrategias evolutivas y algoritmos genéticos (que están relacionados con programación genética).

Algunas aplicaciones
Las metaheurísticas se aplican para la solución de problemas en sistemas de control (robótica, estructuras), programación de horarios (scheduling), bioinformática (clasificación y optimización), minería de datos (sobre todo con grandes volúmenes de datos), hidráulica (calibración de modelos, redes hidráulicas), ingeniería aeronáutica (diseño de aviones, perfiles aerodinámicos), clasificación y reconocimiento de patrones y problemas de transporte.

En su trabajo de investigación, Coello Coello ha logrado que sus algoritmos se apliquen en diferentes casos: “Hace algunos años tuvimos una colaboración en Valparaíso, Chile, donde usaron un algoritmo que nosotros desarrollamos para obtener configuraciones óptimas de redes de distribución de potencia eléctrica; ellos querían minimizar las pérdidas del sistema de potencia y aumentar los índices de confiabilidad”, comentó.

Pero el trabajo del científico mexicano también llegó a Colombia, en este caso se desarrolló un algoritmo para diseñar el marco de una motocicleta, lo cual significó un problema costoso, “porque la estructura del marco se modela con elemento finito, las simulaciones se resuelven con un sistema de ecuaciones diferenciales y ello, en términos computacionales, era muy alto puesto que cada evaluación podía tomar entre 10 a 15 minutos – por una sola evaluación de la función objetivo—, por lo que se usaron técnicas de neuro-aceleración, con redes neuronales se hicieron las predicciones para no tener que hacer demasiadas evaluaciones”.

Carlos Coello subrayó, por otro lado, que también se han formado nuevos investigadores en el área. Recordó que un estudiante que tuvo hace varios años y ahora está en el Instituto Max Planck, en Alemania, donde es doctorando en informática, usó un algoritmo evolutivo para realizar la diferencia de modelos de redes reguladoras de genes, “es un programa interesante en bioinformática y esto lo implementó en procesadores GPUs, como los que tienen las consolas de juegos en la actualidad, pero para resolver problemas de optimización”.

Igualmente, se refirió al proyecto en el que participó hace algún tiempo con el investigador Akira Oyama, de la Agencia Aeroespacial Japonesa (JAXA), quien requería un algoritmo que sirviera para el diseño de un vehículo aéreo no tripulado para explorar Marte en 2020.

El avión pesa un kilogramo y tiene integrada una cámara. Se empezó a diseñar en 2006 y el objetivo es que realice un mapa del planeta rojo, el proyecto fue optimizado con algoritmos evolutivos. “Logramos que un joven investigador estuviera en JAXA en su estancia posdoctoral y Akira ha hecho un gran esfuerzo por involucrar a colegas de la JAXA en el uso de algoritmos evolutivos en sus aplicaciones”, expuso el especialista del Cinvestav.

Elizabeth Ruiz Jaimes.