Параллельный метаэвристический

В этой статье есть несколько проблем. Помогите улучшить ее или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти сообщения ) A major contributor to this article appears to have a close connection with its subject. It may require cleanup to comply with Wikipedia's content policies, particularly neutral point of view. Please discuss further on the talk page. (June 2015) (Learn how and when to remove this message) This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (June 2015) (Learn how and when to remove this message) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Parallel metaheuristic" – news · newspapers · books · scholar · JSTOR (June 2015) (Learn how and when to remove this message) (Learn how and when to remove this message)

Параллельная метаэвристика — это класс методов, которые способны сократить как численные усилия ^{[ требуется разъяснение ]} , так и время выполнения метаэвристики . С этой целью концепции и технологии из области параллелизма в компьютерной науке используются для улучшения и даже полного изменения поведения существующих метаэвристик. Так же, как существует длинный список метаэвристик, таких как эволюционные алгоритмы , рой частиц , оптимизация колонии муравьев , имитация отжига и т. д., также существует большой набор различных методов, сильно или слабо основанных на них, поведение которых охватывает множественное параллельное выполнение компонентов алгоритма, которые каким-то образом взаимодействуют для решения проблемы на данной параллельной аппаратной платформе.

На практике задачи оптимизации (а также поиска и обучения) часто являются NP-трудными , сложными и трудоемкими. Для решения этих задач традиционно используются два основных подхода: точные методы и метаэвристики . ^{[ оспаривается – обсудить ]} Точные методы позволяют находить точные решения, но часто непрактичны, поскольку они требуют чрезвычайно много времени для реальных задач (большой размерности, с небольшими ограничениями, многомодальные, изменяющиеся во времени, эпистатические задачи). Напротив, метаэвристики обеспечивают неоптимальные (иногда оптимальные) решения за разумное время. Таким образом, метаэвристики обычно позволяют справляться с задержками разрешения, возникающими в промышленной сфере, а также позволяют изучать общие классы задач вместо конкретных экземпляров задач. В целом, многие из наиболее эффективных методов с точки зрения точности и усилий для решения сложных и реальных задач являются метаэвристиками. Их области применения варьируются от комбинаторной оптимизации, биоинформатики и телекоммуникаций до экономики, разработки программного обеспечения и т. д. Эти области полны множества задач, требующих быстрых решений высокого качества. Более подробную информацию о сложных приложениях см. в [1].

Метаэвристики делятся на две категории: метаэвристики на основе траектории и метаэвристики на основе популяции . Основное различие этих двух видов методов заключается в количестве предварительных решений, используемых на каждом шаге (итеративного) алгоритма. Метод, основанный на траектории, начинается с одного начального решения, и на каждом шаге поиска текущее решение заменяется другим (часто лучшим) решением, найденным в его окрестности. Обычно метаэвристики на основе траектории позволяют быстро находить локально оптимальное решение, и поэтому их называют методами, ориентированными на эксплуатацию, способствующими интенсификации в пространстве поиска. С другой стороны, алгоритмы, основанные на популяции, используют популяцию решений. Начальная популяция в этом случае генерируется случайным образом (или создается с помощью жадного алгоритма ), а затем улучшается с помощью итеративного процесса. На каждом этапе процесса вся популяция (или ее часть) заменяется вновь сгенерированными особями (часто лучшими). Эти методы называются методами , ориентированными на разведку , поскольку их основная способность заключается в диверсификации пространства поиска.

Большинство базовых метаэвристик являются последовательными. Хотя их использование позволяет значительно снизить временную сложность процесса поиска, эта последняя остается высокой для реальных задач, возникающих как в академических, так и в промышленных областях. Поэтому параллелизм является естественным способом не только сократить время поиска, но и улучшить качество предоставляемых решений.

Подробное обсуждение того, как параллелизм можно сочетать с метаэвристикой, см. в [2].

Метаэвристики для решения задач оптимизации можно рассматривать как обходы окрестностей , отслеживающие траектории поиска через области решений рассматриваемой задачи:

Алгоритм:  Последовательный траекторный общий псевдокод Generate( s (0)); // Начальное решение t  := 0; // Числовой шаг while  not Termination Criterion(s(t)) do s′( t ) := SelectMove(s( t )); // Исследование окрестности if AcceptMove(s′( t )) then s( t ) := ApplyMove(s′( t )); t  := t + 1; endwhile

Прогулки выполняются итеративными процедурами, которые позволяют переходить от одного решения к другому в пространстве решений (см. алгоритм выше). Этот вид метаэвристик выполняет перемещения в окрестности текущего решения, т. е. они имеют пертурбативную природу. Прогулки начинаются с решения, сгенерированного случайным образом или полученного из другого алгоритма оптимизации. На каждой итерации текущее решение заменяется другим, выбранным из набора соседних кандидатов. Процесс поиска останавливается, когда выполняется заданное условие (максимальное число генераций, найти решение с целевым качеством, застрять на заданное время, . . . ).

Мощным способом достижения высокой вычислительной эффективности с помощью методов на основе траектории является использование параллелизма. Для метаэвристики на основе траектории были предложены различные параллельные модели, и три из них обычно используются в литературе: параллельная многостартовая модель, параллельное исследование и оценка соседства ( или модель параллельных перемещений) и параллельная оценка одного решения (или модель ускорения перемещения):

• Параллельная многостартовая модель : Она заключается в одновременном запуске нескольких траекторных методов для вычисления лучших и надежных решений. Они могут быть гетерогенными или гомогенными, независимыми или кооперативными, начинаться с одного и того же или разных решений и настраиваться с одинаковыми или разными параметрами.
• Модель параллельных перемещений : это низкоуровневая модель master-slave, которая не изменяет поведение эвристики. Последовательный поиск вычислил бы тот же результат, но медленнее. В начале каждой итерации мастер дублирует текущее решение между распределенными узлами. Каждый из них отдельно управляет своим кандидатом/решением, и результаты возвращаются мастеру.
• Модель ускорения перемещения : Качество каждого перемещения оценивается параллельно централизованным способом. Эта модель особенно интересна, когда функция оценки может быть сама распараллелена, поскольку она требует много времени ЦП и/или ввода-вывода. В этом случае функцию можно рассматривать как совокупность определенного количества частичных функций ^{[ необходимо разъяснение ],} которые могут выполняться параллельно.

Популяционные метаэвристики — это стохастические методы поиска, которые успешно применялись во многих реальных и сложных приложениях (эпистатические, мультимодальные, многоцелевые и сильно ограниченные задачи). Популяционный алгоритм — это итеративный метод, который применяет стохастические операторы к пулу особей: популяции (см. алгоритм ниже). Каждая особь в популяции — это закодированная версия предварительного решения. Оценочная функция связывает значение приспособленности с каждой особью, указывающее на ее пригодность для решения проблемы. Итеративно вероятностное применение операторов вариации к выбранным особям направляет популяцию к предварительным решениям более высокого качества. Наиболее известными метаэвристическими семействами, основанными на манипулировании популяцией решений, являются эволюционные алгоритмы (EA), оптимизация муравьиной колонии (ACO), оптимизация роя частиц (PSO), поиск рассеяния (SS), дифференциальная эволюция (DE) и алгоритмы распределения оценок (EDA).

Алгоритм:  Последовательный метаэвристический псевдокод на основе популяции Generate(P(0)); // Начальная популяция t  := 0; // Числовой шаг , пока не выполнен критерий завершения (P( t )) do Evaluate(P( t )); // Оценка популяции P′′( t ) := Apply Variation Operators(P′( t )); // Генерация новых решений P( t + 1) := Replace(P( t ), P′′( t )); // Создание следующей популяции t  := t + 1; endwhile

Для нетривиальных задач выполнение репродуктивного цикла простого популяционного метода на длинных особях и/или больших популяциях обычно требует больших вычислительных ресурсов. В целом, оценка функции приспособленности для каждой особи часто является наиболее затратной операцией этого алгоритма. Следовательно, изучаются различные алгоритмические вопросы для разработки эффективных методов. Эти вопросы обычно состоят из определения новых операторов, гибридных алгоритмов, параллельных моделей и т. д.

Параллелизм возникает естественным образом при работе с популяциями, поскольку каждая из принадлежащих ей особей является независимой единицей (по крайней мере, согласно стилю Питтсбурга , хотя существуют и другие подходы, такие как Мичиганский , которые не рассматривают особей как независимые единицы). Действительно, производительность алгоритмов, основанных на популяциях, часто улучшается при параллельном запуске. Две стратегии распараллеливания специально ориентированы на алгоритмы, основанные на популяциях:

1. Распараллеливание вычислений , при котором операции, обычно применяемые к каждому из индивидуумов, выполняются параллельно, и
2. Распараллеливание популяции , при котором популяция разделена на различные части, которые можно просто обменивать или развивать по отдельности, а затем объединять.

В начале истории распараллеливания этих алгоритмов использовался известный метод master-slave (также известный как глобальное распараллеливание или фермерство ). В этом подходе центральный процессор выполняет операции выбора, в то время как связанные с ним подчиненные процессоры (workers) выполняют оператор вариации и оценку функции пригодности. Этот алгоритм имеет то же поведение, что и последовательный, хотя его вычислительная эффективность улучшена, особенно для трудоемких целевых функций. С другой стороны, многие исследователи используют пул процессоров для ускорения выполнения последовательного алгоритма, просто потому, что независимые запуски могут быть выполнены быстрее с использованием нескольких процессоров, чем с использованием одного. В этом случае между независимыми запусками вообще не существует никакого взаимодействия.

Однако на самом деле большинство параллельных методов на основе популяции, найденных в литературе, используют некое пространственное расположение для индивидуумов, а затем распараллеливают полученные фрагменты в пуле процессоров. Среди наиболее широко известных типов структурированных метаэвристик распределенные (или крупнозернистые) и клеточные (или мелкозернистые) алгоритмы являются очень популярными процедурами оптимизации.

В случае распределенных популяция разбивается на набор субпопуляций (островов), в которых выполняются изолированные последовательные алгоритмы. Разреженные обмены особями выполняются между этими островами с целью внесения некоторого разнообразия в субпопуляции, тем самым предотвращая застревание поиска в локальных оптимумах. Чтобы разработать распределенную метаэвристику, мы ^{[ кто? ]} должны принять несколько решений. Среди них главное решение — определить политику миграции: топологию (логические связи между островами), скорость миграции (количество особей, которые подвергаются миграции при каждом обмене), частоту миграции (количество шагов в каждой субпопуляции между двумя последовательными обменами) и выбор/замену мигрантов.

В случае клеточного метода вводится концепция соседства, так что особь может взаимодействовать только со своими ближайшими соседями в цикле размножения. Перекрывающееся небольшое соседство в алгоритме помогает исследовать пространство поиска, поскольку медленное распространение решений через популяцию обеспечивает своего рода исследование, в то время как эксплуатация происходит внутри каждого соседства. См. [3] для получения дополнительной информации о клеточных генетических алгоритмах и связанных с ними моделях.

Также предлагаются гибридные модели, в которых реализуется двухуровневый подход к распараллеливанию. В общем, более высокий уровень для распараллеливания представляет собой крупнозернистую реализацию, а базовый остров выполняет клеточный, ведущий-ведомый метод или даже другой распределенный метод.

• Клеточные эволюционные алгоритмы
• Энрике Альба

• G. Luque, E. Alba, Параллельные генетические алгоритмы. Теория и применение в реальном мире, Springer-Verlag, ISBN  978-3-642-22083-8 , июль 2011 г.
• Альба Э., Блюм К., Исаси П., Леон К. Гомес Х.А. (ред.), Методы оптимизации для решения сложных проблем, Wiley, ISBN 978-0-470-29332-4 , 2009 г. 
• Э. Альба, Б. Дорронсоро, Клеточные генетические алгоритмы, Springer-Verlag, ISBN 978-0-387-77609-5 , 2008 г. 
• Н. Неджа, Э. Альба, Л. де Маседо Мурель, Параллельные эволюционные вычисления, Springer-Verlag, ISBN 3-540-32837-8 , 2006 г. 
• Э. Альба, Параллельная метаэвристика: новый класс алгоритмов, Wiley, ISBN 0-471-67806-6 , июль 2005 г. 
• МАЛЛБА
• JGDS
• ДЕМЕ
• xxGA
• ПСАЛХЕ-ЭА
• Paradiseo