metaheurística paralela

Las metaheurísticas paralelas son una clase de técnicas capaces de reducir tanto el esfuerzo numérico como el tiempo de ejecución de una metaheurística . Para ello, se utilizan conceptos y tecnologías del campo del paralelismo en informática para mejorar e incluso modificar por completo el comportamiento de las metaheurísticas existentes. Así como existe una larga lista de metaheurísticas como los algoritmos evolutivos , el enjambre de partículas , la optimización por colonia de hormigas , el recocido simulado , etc., también existe un amplio conjunto de técnicas diferentes, basadas en ellas de forma directa o indirecta, cuyo comportamiento abarca la ejecución paralela múltiple de componentes algorítmicos que cooperan de alguna manera para resolver un problema en una plataforma de hardware paralela determinada.

En la práctica, los problemas de optimización (y búsqueda y aprendizaje) suelen ser NP-difíciles , complejos y requieren mucho tiempo. Tradicionalmente, se utilizan dos enfoques principales para abordar estos problemas: los métodos exactos y las metaheurísticas . Los métodos exactos permiten encontrar soluciones exactas, pero a menudo resultan poco prácticos, ya que son extremadamente lentos para problemas del mundo real (problemas de gran dimensión, con pocas restricciones, multimodales, variables en el tiempo y epistáticos). Por el contrario, las metaheurísticas proporcionan soluciones subóptimas (a veces óptimas) en un tiempo razonable. Por lo tanto, las metaheurísticas suelen permitir cumplir con los plazos de resolución impuestos en el ámbito industrial, además de permitir el estudio de clases de problemas generales en lugar de instancias de problemas particulares. En general, muchas de las técnicas con mejor rendimiento en precisión y esfuerzo para resolver problemas complejos del mundo real son metaheurísticas. Sus campos de aplicación abarcan desde la optimización combinatoria, la bioinformática y las telecomunicaciones hasta la economía, la ingeniería de software, etc. Estos campos están repletos de tareas que requieren soluciones rápidas y de alta calidad. VéasePara obtener más detalles sobre aplicaciones complejas.

Las metaheurísticas se dividen en dos categorías: metaheurísticas basadas en trayectorias y metaheurísticas basadas en poblaciones . La principal diferencia entre estos dos tipos de métodos radica en la cantidad de soluciones tentativas utilizadas en cada paso del algoritmo (iterativo). Una técnica basada en trayectorias comienza con una única solución inicial y, en cada paso de la búsqueda, la solución actual se reemplaza por otra (a menudo la mejor) encontrada en su entorno. Generalmente, las metaheurísticas basadas en trayectorias permiten encontrar rápidamente una solución óptima local, por lo que se denominan métodos orientados a la explotación que promueven la intensificación en el espacio de búsqueda. Por otro lado, los algoritmos basados ​​en poblaciones utilizan una población de soluciones. En este caso, la población inicial se genera aleatoriamente (o se crea con un algoritmo voraz ) y luego se amplía mediante un proceso iterativo. En cada generación del proceso, toda la población (o una parte de ella) se reemplaza por individuos recién generados (a menudo los mejores). Estas técnicas se denominan métodos orientados a la exploración , ya que su principal capacidad reside en la diversificación del espacio de búsqueda.

La mayoría de las metaheurísticas básicas son secuenciales. Si bien su utilización permite reducir significativamente la complejidad temporal del proceso de búsqueda, esta sigue siendo elevada para problemas reales que surgen tanto en el ámbito académico como en el industrial. Por lo tanto, el paralelismo se presenta como una solución natural no solo para reducir el tiempo de búsqueda, sino también para mejorar la calidad de las soluciones obtenidas.

Para una discusión completa sobre cómo se puede combinar el paralelismo con las metaheurísticas, consulte.

Las metaheurísticas para resolver problemas de optimización podrían considerarse como recorridos por vecindarios que trazan trayectorias de búsqueda a través de los dominios de solución del problema en cuestión:

Algoritmo: Pseudocódigo general basado en trayectorias secuenciales Generar( s (0)); // Solución inicial t := 0; // Paso numérico mientras no Criterio de Terminación(s(t)) hacer s′( t ) := SeleccionarMovimiento(s( t )); // Exploración del vecindario si AceptarMovimiento(s′( t )) entonces s( t ) := AplicarMovimiento(s′( t )); t := t + 1; finmientras

Los recorridos se realizan mediante procedimientos iterativos que permiten pasar de una solución a otra en el espacio de soluciones (véase el algoritmo anterior). Este tipo de metaheurísticas realiza los movimientos en la vecindad de la solución actual, es decir, tienen un carácter perturbativo. Los recorridos parten de una solución generada aleatoriamente u obtenida de otro algoritmo de optimización. En cada iteración, la solución actual se reemplaza por otra seleccionada del conjunto de sus candidatas vecinas. El proceso de búsqueda se detiene cuando se cumple una condición determinada (un número máximo de generaciones, encontrar una solución con una calidad objetivo, quedarse atascado durante un tiempo determinado, etc.).

Una forma eficaz de lograr una alta eficiencia computacional con métodos basados ​​en trayectorias es el uso del paralelismo. Se han propuesto diferentes modelos paralelos para metaheurísticas basadas en trayectorias, y tres de ellos se utilizan comúnmente en la literatura: el modelo paralelo de múltiples inicios , la exploración y evaluación paralela del vecindario (o modelo de movimientos paralelos) y la evaluación paralela de una única solución (o modelo de aceleración de movimientos):

• Modelo paralelo de arranque múltiple : Consiste en lanzar simultáneamente varios métodos basados ​​en trayectorias para calcular soluciones mejores y más robustas. Estos métodos pueden ser heterogéneos u homogéneos, independientes o cooperativos, partir de la misma o de diferentes soluciones y estar configurados con los mismos o diferentes parámetros.
• Modelo de movimientos paralelos : Se trata de un modelo maestro-esclavo de bajo nivel que no altera el comportamiento de la heurística. Una búsqueda secuencial calcularía el mismo resultado, pero más lentamente. Al inicio de cada iteración, el maestro duplica la solución actual entre los nodos distribuidos. Cada nodo gestiona de forma independiente su candidato/solución y los resultados se devuelven al maestro.
• Modelo de aceleración de movimientos : La calidad de cada movimiento se evalúa de forma centralizada y paralela. Este modelo resulta especialmente interesante cuando la función de evaluación puede paralelizarse, dado que consume mucho tiempo de CPU y/o recursos de entrada/salida. En ese caso, la función puede considerarse como una agregación de varias funciones parciales que pueden ejecutarse en paralelo.

Las metaheurísticas basadas en poblaciones son técnicas de búsqueda estocástica que se han aplicado con éxito en numerosas aplicaciones reales y complejas (problemas epistáticos, multimodales, multiobjetivo y con muchas restricciones). Un algoritmo basado en poblaciones es una técnica iterativa que aplica operadores estocásticos a un conjunto de individuos: la población (véase el algoritmo a continuación). Cada individuo de la población es la versión codificada de una solución tentativa. Una función de evaluación asocia un valor de aptitud a cada individuo, indicando su idoneidad para el problema. De forma iterativa, la aplicación probabilística de operadores de variación a los individuos seleccionados guía a la población hacia soluciones tentativas de mayor calidad. Las familias de metaheurísticas más conocidas, basadas en la manipulación de una población de soluciones, son los algoritmos evolutivos (AE), la optimización por colonia de hormigas (ACH), la optimización por enjambre de partículas (PSO), la búsqueda dispersa (SS), la evolución diferencial (ED) y los algoritmos de distribución de estimación (EDA).

Algoritmo: Pseudocódigo metaheurístico secuencial basado en población Generar(P(0)); // Población inicial t := 0; // Paso numérico mientras no se cumpla el Criterio de Terminación(P( t )) hacer Evaluar(P( t )); // Evaluación de la población P′′( t ) := Aplicar operadores de variación(P′( t )); // Generación de nuevas soluciones P( t + 1) := Reemplazar(P( t ), P′′( t )); // Construyendo la siguiente población t := t + 1; fin del bucle

Para problemas complejos, ejecutar el ciclo reproductivo de un método poblacional simple en individuos de gran tamaño o poblaciones numerosas suele requerir elevados recursos computacionales. En general, evaluar la función de aptitud para cada individuo suele ser la operación más costosa de este algoritmo. Por consiguiente, se están estudiando diversas cuestiones algorítmicas para diseñar técnicas eficientes. Estas cuestiones suelen consistir en la definición de nuevos operadores, algoritmos híbridos, modelos paralelos, etc.

El paralelismo surge de forma natural al trabajar con poblaciones, ya que cada uno de los individuos que la componen es una unidad independiente (al menos según el estilo de Pittsburg , aunque existen otros enfoques, como el de Michigan , que no consideran a los individuos como unidades independientes). De hecho, el rendimiento de los algoritmos basados ​​en poblaciones suele mejorar al ejecutarse en paralelo. Dos estrategias de paralelización se centran especialmente en los algoritmos basados ​​en poblaciones:

1. Paralelización de cálculos , en la que las operaciones comúnmente aplicadas a cada uno de los individuos se realizan en paralelo, y
2. Paralelización de la población , en la que la población se divide en diferentes partes que pueden intercambiarse o evolucionar por separado, y luego unirse posteriormente.

Al inicio de la historia de la paralelización de estos algoritmos, se utilizó el conocido método maestro-esclavo (también llamado paralelización global o en clúster ). En este enfoque, un procesador central realiza las operaciones de selección, mientras que los procesadores esclavos asociados (trabajadores) ejecutan el operador de variación y la evaluación de la función de aptitud. Este algoritmo se comporta de forma similar al secuencial, aunque su eficiencia computacional mejora, especialmente para funciones objetivo que consumen mucho tiempo. Por otro lado, muchos investigadores utilizan un conjunto de procesadores para acelerar la ejecución de un algoritmo secuencial, ya que las ejecuciones independientes se pueden realizar más rápidamente utilizando varios procesadores que uno solo. En este caso, no existe interacción alguna entre las ejecuciones independientes.

Sin embargo, la mayoría de las técnicas paralelas basadas en poblaciones que se encuentran en la literatura utilizan algún tipo de disposición espacial para los individuos y luego paralelizan los fragmentos resultantes en un conjunto de procesadores. Entre los tipos más conocidos de metaheurísticas estructuradas, los algoritmos distribuidos (o de grano grueso) y celulares (o de grano fino) son procedimientos de optimización muy populares.

En el caso de las metaheurísticas distribuidas, la población se divide en un conjunto de subpoblaciones (islas) en las que se ejecutan algoritmos seriales aislados. Se realizan intercambios dispersos de individuos entre estas islas con el objetivo de introducir diversidad en las subpoblaciones, evitando así que la búsqueda se estanque en óptimos locales. Para diseñar una metaheurística distribuida, debemos tomar varias decisiones. Entre ellas, una decisión fundamental es determinar la política de migración: topología (vínculos lógicos entre las islas), tasa de migración (número de individuos que migran en cada intercambio), frecuencia de migración (número de pasos en cada subpoblación entre dos intercambios sucesivos) y la selección/reemplazo de los migrantes.

En el caso de un método celular, se introduce el concepto de vecindario, de modo que un individuo solo puede interactuar con sus vecinos cercanos en el ciclo de reproducción. El vecindario pequeño superpuesto en el algoritmo ayuda a explorar el espacio de búsqueda porque una difusión lenta de soluciones a través de la población proporciona una especie de exploración, mientras que la explotación tiene lugar dentro de cada vecindario. VerPara obtener más información sobre algoritmos genéticos celulares y modelos relacionados.

Asimismo, se están proponiendo modelos híbridos que emplean un enfoque de paralelización de dos niveles. En general, el nivel superior de paralelización consiste en una implementación de grano grueso, mientras que la isla básica utiliza un método celular, maestro-esclavo o incluso otro método distribuido.

• Algoritmos evolutivos celulares
• Enrique Alba

• G. Luque, E. Alba, Algoritmos genéticos paralelos. Teoría y aplicaciones en el mundo real, Springer-Verlag, ISBN 978-3-642-22083-8Julio de 2011
• Alba E., Blum C., Isasi P., León C. Gómez JA (eds.), Técnicas de optimización para la resolución de problemas complejos, Wiley , ISBN 978-0-470-29332-4, 2009
• E. Alba, B. Dorronsoro, Algoritmos genéticos celulares, Springer-Verlag , ISBN 978-0-387-77609-5, 2008
• N. Nedjah, E. Alba, L. de Macedo Mourelle, Computaciones evolutivas paralelas, Springer-Verlag , ISBN 3-540-32837-8, 2006
• E. Alba, Metaheurística paralela: una nueva clase de algoritmos, Wiley , ISBN 0-471-67806-6Julio de 2005
• MALLBA
• JGDS
• DEME
• xxGA
• PSALHE-EA
• Paraíso