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

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

Фон

Пример различных реализаций одной и той же метаэвристической модели PSO.

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

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

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

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

Метаэвристика на основе параллельных траекторий

Метаэвристику для решения задач оптимизации можно рассматривать как прогулки по окрестностямотслеживание траекторий поиска по областям решения поставленной задачи:

Алгоритм: Общий псевдокод на основе последовательной траектории    Создать (s(0)); // Начальное решение т : = 0; // Числовой шаг пока нет Критерий прекращения (s (t)) делать        s ′ (т): = SelectMove (s (т)); // Исследование окрестностей если AcceptMove (s ′ (т)) тогда            s (т): = ApplyMove (s ′ (т));            т := т + 1;    в конце концов

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

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

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

Параллельная популяционная метаэвристика

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

Алгоритм: Последовательный метаэвристический псевдокод на основе популяции    Сгенерировать (P (0)); // Начальная популяция т : = 0; // Числовой шаг в то время как не Критерий прекращения (P (т)) делать        Оценить (P (т)); // Оценка популяции P ′ ′ (т): = Применить операторы вариации (P ′ (т)); // Генерация новых решений P (т + 1): = Заменить (P (т), П''(т)); // Создание следующей популяции т := т + 1;    в конце концов

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

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

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

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

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

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

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

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

Смотрите также

Рекомендации