Metaheurística paralela
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 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 fuertemente o vagamente basadas en estas, cuyo comportamiento engloba la ejecución en paralelo de múltiples componentes algorítmicos que cooperan de alguna manera para resolver un problema en una determinada plataforma de hardware paralelo.
En la práctica, los problemas de optimización (y búsqueda y aprendizaje) suelen ser NP-difíciles , complejos y lentos. Dos enfoques principales se utilizan tradicionalmente 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 requieren mucho tiempo para los problemas del mundo real (problemas de gran dimensión, difícilmente 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 las 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 del software, etc. Estos campos están llenos de muchas tareas que necesitan soluciones rápidas de alta calidad. Ver[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 tentativas 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 se reemplaza por otra solución (a menudo la mejor) que se encuentra en su vecindad. Es habitual que las metaheurísticas basadas en trayectorias permitan encontrar rápidamente una solución óptima localmente, por lo que se denominan orientadas a la explotación.métodos que promueven la intensificación en el espacio de búsqueda. Por otro lado, los algoritmos basados en población 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 a través de 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, este último sigue siendo alto para los problemas del mundo real que surgen tanto en el ámbito académico como en el industrial. Por lo tanto, el paralelismo se presenta como una forma natural no solo de reducir el tiempo de búsqueda, sino también de mejorar la calidad de las soluciones proporcionadas.
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:
