La metaheurística paralela es 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 potenciar 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 técnicas diferentes basadas fuerte o libremente en estas, cuyo comportamiento engloba la ejecución en paralelo múltiple de componentes de algoritmos que cooperan de alguna manera para resolver un problema en una plataforma hardware paralela dada.
Fondo
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: métodos exactos y metaheurísticas . [ disputado ] Los métodos exactos permiten encontrar soluciones exactas pero a menudo no son prácticos ya que consumen mucho tiempo para problemas del mundo real (problemas epistáticos de gran dimensión, difícilmente restringidos, multimodales, variables en el tiempo). 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 casos de problemas particulares. En general, muchas de las técnicas de mejor rendimiento 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 y 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 la trayectoria y metaheurísticas basadas en la población . La principal diferencia de estos dos tipos de métodos radica en el número de soluciones provisionales utilizadas en cada paso del algoritmo (iterativo). Una técnica basada en la trayectoria comienza con una única solución inicial y, en cada paso de la búsqueda, la solución actual es reemplazada por otra solución (a menudo la mejor) que se encuentra en su vecindario. 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. En este caso, la población inicial se genera aleatoriamente (o se crea con un algoritmo codicioso ) y luego se mejora mediante un proceso iterativo. En cada generación del proceso, toda la población (o una parte de ella) es reemplazada 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 habilidad reside en la diversificación en el espacio de búsqueda.
La mayoría de las metaheurísticas básicas son secuenciales. Aunque 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 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 completa sobre cómo se puede mezclar el paralelismo con las metaheurísticas, ver [2] .
Metaheurísticas basadas en trayectorias paralelas
Las metaheurísticas para resolver problemas de optimización podrían verse 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: Generar pseudocódigo general basado en trayectorias secuenciales ( s (0)); // Solución inicial t : = 0; // paso numérico mientras no criterio de terminación (s (t)) hacer s '( t ): = SelectMove (s ( t )); // Exploración de la vecindad si AcceptMove (s ′ ( t )) luego s ( t ): = ApplyMove (s ′ ( t )); t : = t + 1; terminar mientras
Las caminatas se realizan mediante procedimientos iterativos que permiten pasar de una solución a otra en el espacio de la solución (ver el algoritmo anterior). Este tipo de metaheurísticas realizan los movimientos en las proximidades de la solución actual, es decir, tienen un carácter perturbativo. Las caminatas parten de una solución generada aleatoriamente u obtenida de otro algoritmo de optimización. En cada iteración, la solución actual es reemplazada por otra seleccionada del conjunto de sus candidatos vecinos. El proceso de búsqueda se detiene cuando se cumple una condición determinada (un número máximo de generación, encontrar una solución con una calidad objetivo, atascado durante un tiempo determinado, ...).
Una forma poderosa 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 sola solución (o modelo de aceleración de movimiento):
- Modelo de arranque múltiple paralelo : Consiste en el lanzamiento simultáneo de varios métodos basados en trayectorias para computar soluciones mejores y robustas. Pueden ser heterogéneos u homogéneos, independientes o cooperativos, partir de la misma o diferentes soluciones, y configurarse con los mismos o diferentes parámetros.
- 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 nodos distribuidos. Cada uno gestiona 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 paralela y centralizada. Ese modelo es particularmente interesante cuando la función de evaluación se puede paralelizar en sí misma, ya que consume mucho tiempo de la CPU y / o hace una gran cantidad de E / S. En ese caso, la función puede verse como una agregación de un cierto número de funciones parciales [ aclaración necesaria ] que se pueden ejecutar en paralelo.
Metaheurísticas paralelas basadas en poblaciones
Las metaheurísticas basadas en la población son técnicas de búsqueda estocástica que se han aplicado con éxito en muchas aplicaciones reales y complejas (problemas epistáticos, multimodales, multiobjetivos y muy restringidos). Un algoritmo basado en la población es una técnica iterativa que aplica operadores estocásticos en un grupo de individuos: la población (consulte 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 hacia soluciones tentativas de mayor calidad. Las familias metaheurísticas más conocidas basadas en la manipulación de una población de soluciones son algoritmos evolutivos (EA), optimización de colonias de hormigas (ACO), optimización de enjambres de partículas (PSO), búsqueda de dispersión (SS), evolución diferencial (DE) y algoritmos de distribución de estimación (EDA).
Algoritmo: pseudocódigo metaheurístico secuencial basado en la población Generar (P (0)); // Población inicial t : = 0; // paso numérico mientras no Terminación Criterion (P ( t )) no 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; terminar mientras
Para problemas no triviales, la ejecución del ciclo reproductivo de un método simple basado en poblaciones en individuos largos y / o grandes poblaciones generalmente requiere altos recursos computacionales. 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 una variedad de 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 trata de poblaciones, ya que cada uno de los individuos que lo integran es una unidad independiente (al menos según el estilo de Pittsburg , aunque existen otros enfoques como el de Michigan que no consideran al individuo como unidades independientes). De hecho, el rendimiento de los algoritmos basados en poblaciones a menudo mejora cuando se ejecutan en paralelo. Dos estrategias de paralelización se centran especialmente en algoritmos basados en poblaciones:
- Paralelización de cálculos , en la que las operaciones comúnmente aplicadas a cada uno de los individuos se realizan en paralelo, y
- 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.
Al comienzo 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 agricultura ). En este enfoque, un procesador central realiza las operaciones de selección mientras los procesadores esclavos asociados (trabajadores) 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 se mejora su eficiencia computacional, especialmente para funciones objetivas que consumen mucho tiempo. Por otro lado, muchos investigadores usan un grupo de procesadores para acelerar la ejecución de un algoritmo secuencial, simplemente porque las ejecuciones independientes se pueden realizar más rápidamente usando varios procesadores que usando uno solo. En este caso, no existe interacción alguna entre las ejecuciones independientes.
Sin embargo, en realidad, 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 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 los distribuidos, la población se particiona en un conjunto de subpoblaciones (islas) en las que se ejecutan algoritmos seriales aislados. Entre estas islas se realizan escasos intercambios de individuos con el objetivo de introducir cierta diversidad en las subpoblaciones, evitando así que la búsqueda se atasque en óptimos locales. Para diseñar una metaheurística distribuida, nosotros [ ¿quién? ] debe tomar varias decisiones. Entre ellos, una decisión principal es determinar la política migratoria: 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 circuito de reproducción. El pequeño vecindario superpuesto en el algoritmo ayuda a explorar el espacio de búsqueda porque una lenta difusión 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. Consulte [3] para obtener más información sobre algoritmos genéticos celulares y modelos relacionados.
Además, se están proponiendo modelos híbridos en los que se emprende un enfoque de paralelización de dos niveles. En general, el nivel más alto para la paralelización es una implementación de grano grueso y la isla básica realiza un método celular, maestro-esclavo o incluso otro distribuido.
Ver también
Referencias
- G. Luque, E. Alba, Algoritmos genéticos paralelos. Teoría y aplicaciones del 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ística paralela: una nueva clase de algoritmos, Wiley , ISBN 0-471-67806-6 , julio de 2005
- MALLBA
- JGDS
- DEME
- xxGA
- PSALHE-EA
- Paradiseo