Algoritmos Metaheurísticos la lista definitiva.

En su intento por dotar de inteligencia a los ordenares, múltiples cientificos han acudido a analogias inspiradas en la naturaleza para desarrollar algoritmos eficientes que resuelvan problemas difíciles “inteligentemente”.

Los algoritmos metaheurísticos son diseñados con el objetivo de realizar búsquedas aleatorias inteligentes que encuentren la configuración de los parámetros óptimos de un sistema o problema. Usualmente se aplican en problemas complejos o imposibles de resolver con métodos deterministas, es decir de forma matemática.

Aunque no hay garantía alguna que estos algoritmos devuelvan el valor optimo global, han comprobado ser útiles para otorgar “buenas” soluciones en tiempos razonables, aun para problemas complejos.

En la actualidad existe una gran variedad de estos algoritmos metaheurísticos y siguen agregándose más y más por cada año. En los últimos 10 años, al menos 6 nuevas estrategias han sido publicadas cada año.

Realizando un survey de algunos de estos algoritmos nos hicimos a la tarea de conseguir una lista de todos los algoritmos metaheurísticos publicados hasta el momento. Comenzando desde 1964 con el algoritmo de estrategias evolutivas, hasta el 2016 con algoritmos como Comportamiento del Grillo y el algoritmos inspirado en el Futball Americano, disponemos de esta lista para todos ustedes:

https://thesciencematrix.com/Apps/metaheuristics/

La lista puede ser fácilmente filtrada por nombre del algoritmo, autor y año de publicación, y para cada uno se otorgo el resumen incluido en la publicación y el enlace del articulo publicado.

 

Algoritmos Metaheurísticos la lista definitiva.

La genética de la optimización

Algoritmo Genético.

El algoritmo genético imita el comportamiento evolutivo descrito por Darwin, donde el individuo mejor adaptado prevalece. En ambiente limitado de recursos, lo individuos compiten entre si, y aquellos mas fuertes obtienen ventaja sobre los demás, en posibilidades de permanecer con vida, así como de aparearse y generar descendencia. Con forme pasa el tiempo y las generaciones los individuos son cada vez mas adaptados al ambiente y mantienen los “buenos” genes. Fue desarrollado en los años 1970, de la mano de John Henry Holland.

El algoritmo genético considera que cada solución del problema representa un individuo, el cual tiene un cierto nivel de adaptación a su entorno, la adaptación es un valor numérico dado por la función de desempeño (fitness). Estos individuos que forman parte de una población compiten entre si, se reproducen, e inclusive mutan, pero dado las condiciones limitadas de recursos solo un numero fijo de los mismos sobreviven en cada generación.

De la misma forma en la que las especies evolucionan en cada generación, el algoritmo evolutivo busca que el conjunto de soluciones inicial evolucione en cada iteración, hasta que los individuos sobrevivientes sean representaciones de soluciones con altos desempeños.

Este comportamiento evolutivo es imitado mediante un conjunto de operadores que trabajan sobre la población actual. Suponiendo una población inicial poco adaptada al ambiente, usualmente soluciones completamente aleatorias, y el conocimiento de su adaptación (fitness). En cada iteración del algoritmo primeramente se ejecuta un mecanismo de Selección de Padres. La descendencia es generada mediante un Operador de Cruzamiento, en el cual la información de los genes de los padres es mezclada, cada uno de los nuevos descendientes tiene una pequeña probabilidad de experimentar un proceso de Mutación, donde su información genética puede ser alterada de forma aleatoria. Finalmente la nueva población y la anterior compiten para mantenerse con vida para la siguiente generación, un operador de Remplazo.

Primero lo primero, Codificación.

Antes de poder implementar los operadores genéticos es importante definir la codificación de los individuos. Las soluciones en este algoritmo deben estar representadas por una cadena de caracteres, usualmente binaria para números, o soluciones que buscan seleccionar entre un numero de objetos la mejor combinación.

Por ejemplo:
Si una de las variables del problema tiene que seleccionar entre 127 objetos, entonces la codificación de dicho gen seria la cadena binaria del valor propuesto por la solución.

127 = 1111111
83 = 1010011
1 = 0000001

En el caso que alguna variable del problema tiene que elegir un grupo de objetos que serán incluidos y el resto no, entonces el gen adquiere un valor de 1 en los indices de los objetos que considera para dicha solución y 0 en los demás.

Obj1 Obj2 Obj3 ... ObjN
   1    0    1 ...    1
   0    0    1 ...    0
   1    1    0 ...    1

Aunque la representación binaria es muy utilizada en este algoritmo no es estrictamente necesaria ya que si una solución busca escoger para cada gen entre un numero N de opciones, la cadena podría ser de la forma:

Suponiendo N como 5.
Gen1 Gen2 Gen3 Gen4
   2    5    3    1
   4    2    1    1
   5    5    2    1

O alguna mezcla de estas.

El siguiente ejemplo muestra la codificación utilizada en para resolver el problema de optimización discreta conocido como problema de la mochila. En este problema se busca escoger entre todos los objetos el conjunto de ellos que represente el mayor valor económico, teniendo como limitante un peso máximo posible de escoger. Prueba entre las diferentes combinaciones, y observa la codificación de la solución para cada una.

Este problema es desarrollado mas extensamente en esta entrada

Operaciones Evolutivas.

Estos cuatro operadores manipulan la información obtenida de una población aleatoria de forma que iterativa, simulando un comportamiento evolutivo, mejorando las soluciones, mediante la explotación de la información conocida por los individuos que constituyen a la población actual.

Selección de Padres.

En la selección se considera un balance entre aleatoriedad y elitismo, para dar preferencia a individuos con mejor adaptación, pero también permitir la diversificación evitando convergencia prematura.
La selección de padres se lleva a cabo mediante un proceso de torneo, donde dos individuos distintos de la población son seleccionados aleatoriamente, y el que tenga mejor desempeño es seleccionado. Este proceso se realiza tantas veces como numero de individuos hay en la población.

Desde 1 hasta el numero de individuos en la población:
  P1 = selecciona un individuo aleatoriamente
  P2 = selecciona un individuo aleatoriamente
  seleccionados = selecciona entre P1 y P2 al que tiene mejor fitness.

Cruzamiento.

Con los pares de padres seleccionados, entonces un torneo probabilistico evalúa si estos producirán descendencia entre ellos. La descendencia es generada mediante un Operador de Cruzamiento, en el cual la información de los genes de los padres es mezclada al rededor de un punto de cruce, aunque existen otras formas de realizar esta operación.

Este operador es el que mezcla la información de los individuos seleccionados. Cada par de individuos generan dos descendientes, por lo que al final una nueva población de mismo tamaño que la anterior es generada.

Para cada par de individuos seleccionados: %(NoIndividuos / 2)
  Si (numero aleatorio > Probabilidad de cruce):
    indiceCruce = NumeroAleatorio entre 1 y el numero de bits de la solución.
    Hijo1 = [Padre1[desde 1 hasta indice de cruce] , Padre2[desde indice de cruce al final]
    Hijo2 = [Padre2[desde 1 hasta indice de cruce] , Padre1[desde indice de cruce al final]
  sino
    Hijo1 = Padre1
    Hijo2 = Padre2
  Descendencia.agregar([Hijo1, Hijo2])

La información de la descendencia es resultado de una mezcla de la información de los padres en un punto de cruce, el cual es seleccionado de manera aleatoria. Por ejemplo si tenemos los siguientes padres: $P1 = 01010101$ y $P2 = 11111111$, y el punto de cruce resulto ser 4 entonces:

Punto de cruce aleatorio PC, suponemos que sea 4
P1_1 = P1(1:4) %que sería 0101
P1_2 = P1(5:8) %que sería 0101
P2_1 = P2(1:4) %que sería 1111
P2_2 = P2(5:8) %que sería 1111

Ch1 = [P1_1 P2_2] %01011111
Ch2 = [P2_1 P1_2] %11110101

Mutación.

Cada uno de los nuevos descendientes tiene una pequeña probabilidad de experimentar un proceso de Mutación, donde su información genética puede ser alterada de forma aleatoria. Esta posibilidad es evaluada en cada bit de la solución de la siguiente forma:

Para cada nuevo individuo generado:
  Para cada bit i:
    Si (numero aleatorio > Probabilidad de mutación):
      individuo[i] = inverso(individuo[i]) %si era 1 -> 0 o el inverso.

Remplazo.

Finalmente la nueva población y la anterior compiten para mantenerse con vida para la siguiente generación, un operador de Remplazo selecciona los individuos tomando en cuenta su adaptación al medio.

Añadir la nueva población con la anterior
Ordenar la población de acuerdo al desempeño
Población = Seleccionar los NumeroIndividuos mejores de la población.

De esta forma la siguiente iteración tendrá de inicio los mejores individuos encontrados hasta el momento. Esta estrategia es elitista y suele tener problemas de convergencia prematura. Existen múltiples variantes para estos operadores. En otra entrada hablaremos sobre algunas de estas variantes y sus características.

Clasificación.

Este algoritmo pertenece a la clasificación de:

  • algoritmos evolutivos,
  • metaheurísticos,
  • optimización global,
  • algoritmo poblaciónal,
  • para un solo objetivo, aunque tiene sus variantes multiobjetivo
  • optimización de parámetros reales, o en problemas de combinatoria, incluso mixtos.

Este algoritmo es uno de los pioneros en el área, y abrió el paso a muchas versiones que utilizan está misma inspiración de la evolución.

Pseudocodigo

P = PoblaciónInicial(NoPoblación)
F = FunciónDesempeño(P)
mientras (i < NoIteraciones):
  Padres = SeleccionaPadres(P)
  Hijos = Cruzamiento(Padres, ProbCruz)
  Hijos = Mutación(Hijos)
  FH = FunciónDesempeño(Hijos)
  P = Remplazo(P, Hijos)

Implementaciones.

Este algoritmo esta implementado en javascript con el modulo AISearch, desarrollado por nosotros, y disponible en el área de pruebas.

La genética de la optimización

Algoritmos que van mas allá.

Algoritmos metaheurísticos.

En muchas ocasiones en la investigación científica se busca encontrar formas eficientes de realizar procesos. Usualmente estos problemas terminan siendo representados mediante un proceso de optimización, donde el objetivo es encontrar una configuración de parámetros (variables) que mejor resuelvan el problema dada una métrica que los clasifica.

Cuando estos problemas son muy complejos (NP Hard) no pueden encontrarse soluciones de forma determinista, o bien es imposible enumerar todas las configuraciones posibles en un tiempo aceptable. Este tipo de problemas se conocen también como intratables o altamente intratables. Usualmente en este tipo de problemas suelen utilizarse métodos heurísticos, que son diseñados especificamente para el problema a tratar.

Las heuristicas son métodos desarrollados para ofrecer soluciones de forma mas rápida o para encontrar una solución aproximada donde los métodos clásicos son lentos o fallan en encontrar una solución.
https://en.wikipedia.org/wiki/Heuristic_(computer_science)

Algunos problemas comunes en estos métodos es que suelen atorarse en óptimos locales o bien si la naturaleza del problema cambia un poco puede que estos no funcionen de forma correcta ya que están diseñados especificamente para el problema en cuestión.

Con estas restricciones en mente surgen un nuevo conjunto de métodos denominados metaheurísticos. Estos algoritmos están diseñados para dar una respuesta rápida, esquivando óptimos locales, y para trabajar independientemente del problema, lo que cual les brinda robustes al enfrentar cambios en la naturaleza del mismo.

La palabra “meta” quiere decir que va mas allá.

La forma en la que están diseñados estos algoritmos es muy variada, pueden ser resultado de imitar un fenómeno natural (bioinspirados) o basarse en una trayectoria, tener una única solución o un conjunto de ellas (poblacionales), buscar el optimo global o también un conjunto de óptimos locales (unimodal – multimodal), tener un único objetivo o múltiples, entre otras clasificaciones.

Blum y Roli remarcan algunas características de los algoritmos metaheurísticos:
+ Son estrategias que “guían” el proceso de búsqueda.
+ Buscan eficientizar la exploración por el espacio de búsqueda.
+ Se componen de técnicas que van desde búsqueda local hasta complejos procesos de aprendizaje.
+ Son métodos aproximados y usualmente no determinísticos.
+ Incorporan mecanismos que evitan quedar atrapados en óptimos locales prematuramente.
+ No son diseñados para un problema en especifico.
+ Los mas avanzados utilizan la experiencia obtenida en la búsqueda (mediante algún tipo de memoria) que los dirige.

Clever Algoritms

Dada su naturaleza de diseño independiente del problema, son aplicados en a los problemas de la forma “black box”, es decir, pueden ser implementados sin tener que tener ningún (o muy poco) conocimiento del problema que buscan resolver. Esto permite que sean muy flexibles en su uso sin tener que realizar muchas modificaciones. Generalmente las técnicas que requieren menos información sobre el problema que resuelven son mas flexibles, aunque menos eficientes. El mejor ejemplo de este comportamiento sería la búsqueda aleatoria, que simplemente genera soluciones aleatorias.

Este tipo de algoritmos también son denominados como Algoritmos de Optimización Estocasticos. Esto debido a que utilizan aleatoriedad en sus operaciones, lo cual los convierte en no deterministas. Esto no significa que sean algoritmos aleatorios, si no que explotan la aleatoriedad al explorar de manera probabilística, enfocandose en áreas de interés.

J. Brownlee utiliza la siguiente clasificación:

  • Algoritmos Estocásticos.
  • Algoritmos Evolutivos.
  • Algoritmos Físicos.
  • Algoritmos Probabilisticos.
  • Algoritmos Basados en Partículas.
  • Algoritmos Inmunes.
  • Algoritmos Neuronales.

La mayoría de estos algoritmos presentan un comportamiento de aprendizaje inductivo, es decir que van aprendiendo de la experiencia, comienzan de manera aleatoria y mediante generación, selección y prueba van mejorando las soluciones a través de la iteraciones.

En este espacio publicaremos un análisis de algunos de estos algoritmos, con su explicación, clasificación, bondades y posibles problemas, y el pseudocodigo y código en Matlab. La lista de algoritmos que tenemos contemplados por el momento son:

  • Algoritmo Genético.
  • Evolución Diferencial.
  • PSO (Optimización por enjambre de partículas).
  • Algoritmo inspirado en los estados de la materia.
  • Optimización por colonia de hormigas.
  • Búsqueda del Cuckoo
  • (coloca aquí el algoritmo en el que estés interesado)

Algunos problemas que estarán contemplados mas adelante y que utilizan un proceso de optimización son:

  • Segmentación inteligente de imágenes:
    Este proceso busca separar el fondo de uno o varios objetos en una imagen, para ello utiliza el histograma de la imagen, y busca representar esta información estadística mediante una sumatoria de gaussianas parametrizadas.
  • Asignación dinámica de canal en comunicaciones inalámbricas:
    Busca vincular a cada usuario con un conjunto de entre los canales disponibles del sistema, de forma que el sistema incremente su eficiencia en el uso espectral.
  • Entre otros.

Dejanos saber en los comentarios si tienes un problema en especifico que utiliza estos algoritmos o bien que consideres implementarlos para su solución. Dinos también si te interesa que incluyamos una revisión de alguno en especifico.

Si estas interesado en escribir sobre alguna implementación propia o compartir tu experiencia escribiendo para el blog, estamos buscando gente como tu. Dejanos saber que estas ahí.

Algoritmos que van mas allá.