Metaheurísticas bioinspiradas: resolviendo problemas como la naturaleza lo haría

Consejo Consultivo de Ciencias

— Éste es el siglo de las metaheurísticas, pues en él su uso se popularizará todavía más y se les utilizará para problemas cada vez más complejos y desafiantes—

 

La palabra “heurística” se deriva del griego heuriskein, que significa “encontrar” o “descubrir”. La heurística es antónimo de algoritmo, que es una serie de pasos sistemáticos que se siguen para resolver una tarea.

El término “metaheurística” lo acuñó Fred Glover en 1986, definiéndola como un procedimiento de búsqueda de alto nivel que aplica alguna regla o conjunto de reglas basado en una fuente de conocimiento, a fin de explorar el espacio de búsqueda de manera más eficiente que los algoritmos exactos.

Las metaheurísticas han sumado popularidad en los últimos 25 años, toda vez que existen limitantes de los métodos exactos, como conocer poco del problema o que el espacio de búsqueda sea demasiado grande o muy accidentado. Una particularidad de las metaheurísticas es su flexibilidad y facilidad de uso, además de constituir la última línea de defensa en optimización.

Existe una clase particular de metaheurísticas que se ha vuelto muy popular en los últimos años, a las que se denomina “metaheurísticas bioinspiradas”, esto debido a que sus reglas para elegir soluciones se basan en conceptos biológicos. Entre ellas se encuentran: los algoritmos evolutivos, los cúmulos de partículas, los sistemas inmunes artificiales y la colonia de hormigas.

Los Algoritmos evolutivos, basados en el principio de supervivencia del más apto, de la teoría evolutiva de Charles Darwin. Surgen en los años 60 y parten de un conjunto de soluciones (población) que se genera aleatoriamente. En cada iteración (o generación), la búsqueda se guía por el valor de la función objetivo que queremos optimizar (la función de aptitud). Por ejemplo, si queremos minimizar una función, las soluciones que representen los valores más pequeños son más aptas que las que representen los valores más grandes, por lo tanto, tienen mayor probabilidad de sobrevivir; dichas soluciones se reproducen (mediante una cruza sexual) y los resultados obtenidos son denominados hijos, quienes posteriormente serán mutados (o sea, se les realizarán pequeños cambios). Estos nuevos individuos constituyen una nueva población que reemplazará parcial o totalmente a la anterior.

Existen 3 tipos de algoritmos evolutivos:

1) Programación Evolutiva. Surge en Estados Unidos en los años 60 y simula la evolución natural a nivel de las especies, se caracteriza por no existir en ella la cruza sexual, debido que especies diferentes no pueden recombinarse. Por tanto, sólo utiliza mutación.

2) Estrategias Evolutivas. Surgen en Alemania en los años 60, cuando Ingo Rechenberg, al realizar su tesis doctoral en torno a la optimización de una boquilla hidrodinámica, se ve obligado a desarrollar un algoritmo que denominó “la estrategia evolutiva 1+1”, en la que se genera aleatoriamente (siguiendo una cierta distribución de probabilidad) un vector de números reales (el padre), al cual se le modifica uno de sus valores, para producir un hijo. Si el hijo tiene mejor valor de la función objetivo que su padre, entonces este hijo se vuelve el nuevo padre; de lo contrario, el padre se mantiene y su hijo se elimina.

3) Algoritmos Genéticos. Desarrollado por John H. Holland en los años 60. Su algoritmo originalmente se llamó “planes reproductivos y “adaptativos” pero en 1975, tras la publicación de su libro sobre el tema, se popularizan bajo el nombre de “algoritmo genético”. En este caso, todas las soluciones tienen que convertirse a binario, sin importar el valor que tengan (a esto se le llama codificación).  Utilizan tanto cruza sexual como mutación, siendo la primera el operador principal. Éste es sin duda el algoritmo evolutivo más popular de la actualidad.

- Programación Genética, es una variante de los algoritmos genéticos, propuesta por John Koza en los 80, que utiliza árboles capaces de codificar un programa de computadora. Esta técnica se caracteriza por requerir de una cantidad considerable de recursos de cómputo pues las poblaciones que utiliza típicamente son muy grandes.  Su propósito es evolucionar programas de computadora de cualquier tipo, y se ha usado para evolucionar, entre otras cosas, algoritmos de ordenamiento, para diseñar circuitos, filtros digitales y antenas, entre muchas otras cosas.

Cúmulos de partículas. Es una técnica propuesta en 1995 por James Kennedy y Russell C. Eberhart en la que se simula el movimiento de una partícula en un ­fluido, definido a partir de su posición y velocidad, siguiendo la mejor posición que ha tenido la partícula en el tiempo y la mejor del cúmulo, tal como lo hacen, por ejemplo, las aves que siguen a un líder. Aunque es una metaheurística muy eficiente (computacionalmente hablando), tiene algunas limitantes teóricas, como el no poder garantizar, aun en condiciones ideales, convergencia al óptimo global. Esta metaheurística ha sido muy popular como optimizador.

Sistemas inmunes artificiales. Son un modelo computacional de nuestro sistema inmune, el cual comenzó a desarrollarse en los años de la década  de 1980. Esta metaheurística simula el ataque de un antígeno a nuestro sistema inmune y la respuesta de dicho sistema, mediante la producción de anticuerpos, los cuales son hipermutados hasta lograr la máxima afinidad posible con los antígenos. Dichos anticuerpos de afinidad máxima son clonados para anular los antígenos. Esta metaheurística se ha usado sobre todo para problemas de clasificación.

Colonia de hormigas. Es un modelo computacional (basado en agentes) de las colonias reales de hormigas que fue propuesto a principios de los 90 por Marco Dorigo. Se usaron inicialmente para resolver un solo tipo de problema de optimización (el problema del viajero), pero con el tiempo se ha extendido a diversos tipos de problemas combinatorios e incluso a problemas en los que las variables son números reales.

Algunas de las muchas aplicaciones de las metaheurísticas son las siguientes:

l Diseño y optimización estructural (p.ej., diseño del marco de una motocicleta).

l Inferencia de modelos de redes reguladoras de genes.

l Detección de microcalcificaciones con el objetivo de identificar cáncer de mama de manera automatizada (sin intervención humana).

l Diseño de nuevos materiales y optimización del perfil aerodinámico de los automóviles.

l Optimización del diseño del tren bala que se usa en Japón.

l Diseño de un avión que sobrevolará la superficie de Marte en 2020 para realizar un mapa de la misma.

Algunas de las principales áreas de investigación que se exploran actualmente son, por ejemplo: el diseño de nuevos algoritmos o variantes de los existentes; solución de problemas de optimización con dos o más funciones objetivo en conflicto (llamados multiobjetivo), optimización con restricciones (geométricas, físicas, de costo, etc.), optimización dinámica (en la que el óptimo se mueve de lugar en el tiempo), optimización combinatoria, etc.; el diseño de nuevos operadores y de esquemas para mantener diversidad.

Concluyendo:

El rápido crecimiento de la velocidad de los procesadores y el abaratamiento de las memorias de las computadoras que hemos venido experimentando desde finales del siglo XX ha contribuido a popularizar el uso de las metaheurísticas.

La flexibilidad y facilidad de uso que ofrecen las metaheurísticas las han vuelto una opción recurrente para resolver problemas (sobre todo de optimización) de alta complejidad. Sin embargo, debe evitarse su uso indiscriminado, pues su uso debe reservarse precisamente para problemas complejos y no para aquellos que pueden resolverse eficientemente usando algoritmos exactos.

 

 

Dr. Carlos A. Coello Coello
Investigador del Departamento de Computación del Cinvestav-IPN y miembro del Consejo Consultivo de Ciencias.

 

Imprimir

Comentarios