Metaheurística paralela

Las metaheurísticas paralelas son una clase de técnicas que son capaces de reducir tanto el esfuerzo numérico ^{[ aclaración necesaria ]} 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 algoritmos evolutivos , enjambre de partículas , optimización de colonias de hormigas , recocido simulado , etc., también existe un gran conjunto de diferentes técnicas basadas fuerte o débilmente en estas, cuyo comportamiento abarca la ejecución en paralelo múltiple de componentes de algoritmos que cooperan de alguna manera para resolver un problema en una plataforma de hardware paralela dada.

En la práctica, los problemas de optimización (y búsqueda y aprendizaje) suelen ser NP-hard , complejos y consumen mucho tiempo. Tradicionalmente se utilizan dos enfoques principales para abordar estos problemas: métodos exactos y metaheurísticas . ^{[ disputado – discutir ]} Los métodos exactos permiten encontrar soluciones exactas, pero a menudo son poco prácticos, ya que consumen mucho tiempo para problemas del mundo real (problemas de gran dimensión, apenas restringidos, multimodales, que varían en el tiempo, 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 generalmente permiten cumplir con los retrasos de resolución impuestos en el campo industrial, así como también permiten estudiar clases de problemas generales en lugar de instancias de problemas particulares. En general, muchas de las técnicas con mejor desempeño en precisión y esfuerzo para resolver problemas complejos y del mundo real son metaheurísticas. Sus campos de aplicación van 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 llenos de muchas tareas que necesitan soluciones rápidas de alta calidad. Consulte [1] para 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 reside en el número 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 sustituye por otra (a menudo la mejor) solución que se encuentra en su entorno. Es habitual que las metaheurísticas basadas en trayectorias permitan encontrar rápidamente una solución localmente óptima, 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 hacen uso de una población de soluciones. La población inicial se genera en este caso de forma aleatoria (o se crea con un algoritmo voraz ) y luego se mejora a través de un proceso iterativo. En cada generación del proceso, toda la población (o una parte de ella) se sustituye 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 en el 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 última sigue siendo alta para los problemas del mundo real que surgen tanto en el ámbito académico como en el industrial. Por lo tanto, el paralelismo surge como una forma natural no solo de reducir el tiempo de búsqueda, sino también de mejorar la calidad de las soluciones proporcionadas.

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

Las metaheurísticas para resolver problemas de optimización podrían verse como paseos por los 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 trayectoria secuencial 
    Generate( s (0)); // Solución inicial
     t  := 0; // Paso numérico
     while  not Termination Criterion(s(t)) do 
        s′( t ) := SelectMove(s( t )); // Exploración del vecindario
         if AcceptMove(s′( t )) then 
            s( t ) := ApplyMove(s′( t ));
             t  := t + 1;
     endwhile

Los paseos se realizan mediante procedimientos iterativos que permiten pasar de una solución a otra en el espacio de soluciones (ver el algoritmo anterior). Este tipo de metaheurísticas realizan los movimientos en la vecindad de la solución actual, es decir, tienen una naturaleza perturbativa. Los paseos parten de una solución generada aleatoriamente u obtenida a partir 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 dada (un número máximo de generaciones, encontrar una solución con una calidad objetivo, quedarse estancado durante un tiempo dado, . . . ).

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 de inicio múltiple paralelo , 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 de arranque múltiple paralelo : consiste en el lanzamiento simultáneo de varios métodos basados ​​en trayectorias para calcular soluciones mejores y más robustas. Pueden ser heterogéneos u homogéneos, independientes o cooperativos, partir de la misma solución o de soluciones diferentes y estar configurados con los mismos parámetros o con parámetros diferentes.
• Modelo de movimientos paralelos : Es 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 lento. Al comienzo de cada iteración, el maestro duplica la solución actual entre los nodos distribuidos. Cada uno administra por separado 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 es particularmente interesante cuando la función de evaluación puede paralelizarse, ya que consume mucho tiempo de CPU y/o hace un uso intensivo de E/S. En ese caso, la función puede verse como una agregación de una cierta cantidad de funciones parciales ^{[ aclaración necesaria ]} 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 muchas aplicaciones reales y complejas (problemas epistáticos, multimodales, multiobjetivo y altamente restringidos). Un algoritmo basado en poblaciones es una técnica iterativa que aplica operadores estocásticos a un grupo de individuos: la población (ver 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 manera iterativa, la aplicación probabilística de operadores de variación en individuos seleccionados guía a la población a soluciones tentativas de mayor calidad. Las familias metaheurísticas más conocidas basadas en la manipulación de una población de soluciones son los algoritmos evolutivos (EA), la optimización de colonias de hormigas (ACO), la optimización de enjambre de partículas (PSO), la búsqueda dispersa (SS), la evolución diferencial (DE) y los algoritmos de distribución de estimación (EDA).

Algoritmo:  pseudocódigo metaheurístico basado en población secuencial
    Generar(P(0)); // Población inicial
    t  := 0; // Paso numérico
     while not Termination Criterion(P( t )) do 
        Evaluate(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) := Replace(P( t ), P′′( t )); // Construyendo la siguiente población
         t  := t + 1;
     endwhile

En el caso de problemas no triviales, la ejecución del ciclo reproductivo de un método poblacional simple en individuos largos y/o poblaciones grandes suele requerir recursos computacionales elevados. En general, evaluar una función de aptitud para cada individuo es con frecuencia la operación más costosa de este algoritmo. En consecuencia, se están estudiando diversos problemas algorítmicos para diseñar técnicas eficientes. Estos problemas suelen consistir en definir nuevos operadores, algoritmos híbridos, modelos paralelos, etc.

El paralelismo surge de forma natural cuando se trabaja 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 cuando se ejecutan en paralelo. Dos estrategias de paralelización están especialmente enfocadas en 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 simplemente intercambiarse o evolucionar por separado, y luego unirse más tarde.

En los inicios de la historia de la paralelización de estos algoritmos se utilizó el conocido método maestro-esclavo (también conocido como paralelización global o farming ). En este enfoque, un procesador central realiza las operaciones de selección mientras los procesadores esclavos asociados (workers) ejecutan el operador de variación y la evaluación de la función de aptitud. Este algoritmo tiene el mismo comportamiento que el secuencial, aunque su eficiencia computacional es mejorada, especialmente para funciones objetivo que consumen mucho tiempo. Por otro lado, muchos investigadores utilizan un pool de procesadores para acelerar la ejecución de un algoritmo secuencial, simplemente porque se pueden realizar ejecuciones independientes más rápidamente utilizando varios procesadores que utilizando uno solo. En este caso, no existe interacción alguna entre las ejecuciones independientes.

Sin embargo, la mayoría de las técnicas basadas en poblaciones paralelas 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 grupo de procesadores. Entre los tipos de metaheurísticas estructuradas más conocidos, 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 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 cierta diversidad en las subpoblaciones, evitando así que la búsqueda se quede estancada en óptimos locales. Para diseñar una metaheurística distribuida, ^{debemos tomar varias decisiones. Entre ellas} , una decisión principal es determinar la política de migración: topología (enlaces 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 vecindad, de modo que un individuo solo puede interactuar con sus vecinos cercanos en el ciclo de reproducción. La pequeña vecindad superpuesta 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 vecindad. Consulte [3] para obtener más información sobre algoritmos genéticos celulares y modelos relacionados.

También se están proponiendo modelos híbridos en los que se adopta un enfoque de paralelización de dos niveles. En general, el nivel superior de paralelización es una implementación de grano grueso y la isla básica realiza un método celular, un método maestro-esclavo o incluso otro 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-8 , julio 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ísticas paralelas: una nueva clase de algoritmos, Wiley, ISBN 0-471-67806-6 , julio de 2005 
• MALBA
• JGDS
• DEMO
• xxGA
• SALMO-EA
• Paraíso