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á.