 | Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) ( Узнайте, как и когда удалить этот шаблон сообщения )
|
Параллельная метаэвристика - это класс методов, которые способны уменьшить как числовые затраты [ требуется пояснение ], так и время выполнения метаэвристики . С этой целью концепции и технологии из области параллелизма в информатике используются для улучшения и даже полного изменения поведения существующей метаэвристики. Так же, как существует длинный список метаэвристик, таких как эволюционные алгоритмы , рой частиц , оптимизация муравьиной колонии , имитация отжига.и т. д. также существует большой набор различных методов, сильно или слабо основанных на этих методах, поведение которых включает в себя множественное параллельное выполнение компонентов алгоритма, которые каким-либо образом взаимодействуют для решения проблемы на данной параллельной аппаратной платформе.
Фон [ править ]
На практике задачи оптимизации (поиска и обучения) часто являются NP-трудными , сложными и требуют много времени. Для решения этих проблем традиционно используются два основных подхода: точные методы и метаэвристика . [ оспаривается ]Точные методы позволяют находить точные решения, но часто непрактичны, поскольку они требуют очень много времени для реальных проблем (большие размерные, почти не ограниченные, мультимодальные, изменяющиеся во времени, эпистатические задачи). И наоборот, метаэвристика предоставляет неоптимальные (иногда оптимальные) решения за разумное время. Таким образом, метаэвристика обычно позволяет встретить задержки разрешения, налагаемые в промышленной области, а также они позволяют изучать общие классы проблем, а не конкретные экземпляры проблем. В общем, многие из наиболее эффективных методов с точки зрения точности и усилий по решению сложных и реальных проблем - это метаэвристика. Сферы их применения варьируются от комбинаторной оптимизации, биоинформатики и телекоммуникаций до экономики, разработки программного обеспечения и т. Д.В этих сферах множество задач, требующих быстрого и качественного решения. Видеть[1] для получения более подробной информации о сложных приложениях.
Метаэвристика делится на две категории: метаэвристика, основанная на траекториях, и метаэвристика, основанная на популяциях. Основное различие этих двух типов методов заключается в количестве предварительных решений, используемых на каждом этапе (итерационного) алгоритма. Метод, основанный на траектории, начинается с единственного начального решения, и на каждом шаге поиска текущее решение заменяется другим (часто лучшим) решением, найденным в его окрестности. Обычно метаэвристика на основе траекторий позволяет быстро находить локально оптимальное решение, поэтому они называются ориентированными на эксплуатацию.методы, способствующие интенсификации поискового пространства. С другой стороны, алгоритмы, основанные на популяциях, используют совокупность решений. В этом случае начальная популяция генерируется случайным образом (или создается с помощью жадного алгоритма ), а затем улучшается с помощью итеративного процесса. В каждом поколении процесса вся популяция (или ее часть) заменяется вновь созданными особями (часто лучшими). Эти методы называются методами, ориентированными на исследование, поскольку их основная способность заключается в диверсификации пространства поиска.
Большинство основных метаэвристик последовательны. Хотя их использование позволяет значительно снизить временную сложность процесса поиска, последняя остается высокой для реальных проблем, возникающих как в академической, так и в промышленной областях. Таким образом, параллелизм - это естественный способ не только сократить время поиска, но и улучшить качество предоставляемых решений.
Подробное обсуждение того, как параллелизм может быть смешан с метаэвристикой, см. В [2] .
Метаэвристика на основе параллельных траекторий [ править ]
Метаэвристику для решения задач оптимизации можно рассматривать как прогулки по окрестностям, отслеживающие траектории поиска через области решения рассматриваемой проблемы:
Алгоритм: Генерация общего псевдокода на основе последовательной траектории ( s (0)); // Начальное решение t : = 0; // Численный шаг , пока не Клеммная Критерий (ы (т)) сделать S '( т ): = SelectMove (с ( т )); // Исследование окрестностей if AcceptMove (s ′ ( t )) then s ( t ): = ApplyMove (s ′ ( t )); т : = т + 1; в конце концов
Прогулки выполняются итерационными процедурами, позволяющими переходить от одного решения к другому в пространстве решений (см. Описанный выше алгоритм). Этот вид метаэвристики выполняет действия в окрестности текущего решения, т. Е. Они имеют пертурбативный характер. Прогулки начинаются с решения, случайно сгенерированного или полученного из другого алгоритма оптимизации. На каждой итерации текущее решение заменяется другим, выбранным из набора соседних кандидатов. Процесс поиска останавливается, когда выполняется заданное условие (максимальное количество генераций, поиск решения с заданным качеством, застревание на заданное время, ...).
Мощным способом достижения высокой вычислительной эффективности с помощью методов, основанных на траекториях, является использование параллелизма. Различные модели параллельных были предложены для траекторной на основе метаэвристики, и три из них широко используются в литературе: параллельная многозаходная модель, параллельное исследование и оценка окрестностей (или параллельной модели двигается), и параллельная оценка в единственное решение (или модель ускорения движения):
- Параллельная модель с несколькими запусками: она заключается в одновременном запуске нескольких методов, основанных на траектории, для вычисления лучших и надежных решений. Они могут быть неоднородными или однородными, независимыми или кооперативными, начинаться с одного или разных решений и конфигурироваться с одинаковыми или разными параметрами.
- Модель параллельных перемещений : это низкоуровневая модель «ведущий-ведомый», которая не изменяет поведение эвристики. Последовательный поиск даст тот же результат, но медленнее. В начале каждой итерации мастер дублирует текущее решение между распределенными узлами. Каждый отдельно управляет своим кандидатом / решением, и результаты возвращаются мастеру.
- Модель ускорения движения: качество каждого движения оценивается параллельно централизованно. Эта модель особенно интересна, когда функцию оценки можно распараллелить, поскольку она требует много времени процессора и / или ввода-вывода. В этом случае функцию можно рассматривать как совокупность определенного количества частичных функций [ требуется пояснение ], которые могут выполняться параллельно.
Параллельная популяционная метаэвристика [ править ]
Метаэвристика на основе популяции - это методы стохастического поиска, которые успешно применялись во многих реальных и сложных приложениях (эпистатические, мультимодальные, многоцелевые и сильно ограниченные задачи). Алгоритм на основе популяции - это итеративный метод, который применяет стохастические операторы к пулу индивидов: популяции (см. Алгоритм ниже). Каждый человек в популяции - это закодированная версия предварительного решения. Функция оценки связывает значение пригодности с каждым человеком, указывая на его пригодность к проблеме. Итеративно вероятностное применение операторов вариации к выбранным индивидам приводит популяцию к предварительным решениям более высокого качества. Наиболее известные метаэвристические семейства, основанные на манипулировании совокупностью решений:эволюционные алгоритмы (EAs), оптимизация муравьиных колоний (ACO), оптимизация роя частиц (PSO), поиск по разбросу (SS), дифференциальная эволюция (DE) и алгоритмы распределения оценок (EDA).
Алгоритм: последовательный метаэвристический псевдокод на основе популяции Сгенерировать (P (0)); // Начальная популяция t : = 0; // Числовой шаг без критерия завершения (P ( t )) do Evaluate (P ( t )); // Оценка населения P ′ ′ ( t ): = Применить операторы вариации (P ′ ( t )); // Генерация новых решений P ( t + 1): = Заменить (P ( t ), P ′ ′ ( t )); // Создание следующей популяции t : = t + 1; в конце концов
Для нетривиальных задач выполнение репродуктивного цикла простого популяционного метода на длинных особях и / или больших популяциях обычно требует больших вычислительных ресурсов. В общем, оценка функции приспособленности для каждого человека часто является самой затратной операцией этого алгоритма. Следовательно, для разработки эффективных методов изучается множество алгоритмических проблем. Эти вопросы обычно заключаются в определении новых операторов, гибридных алгоритмов, параллельных моделей и так далее.
Параллелизм возникает естественным образом при работе с популяциями, поскольку каждый из принадлежащих к нему индивидов является независимой единицей (по крайней мере, в соответствии с питтсбургским стилем, хотя есть и другие подходы, такие как мичиганский подход, которые не рассматривают индивида как независимые единицы). Действительно, производительность алгоритмов на основе популяции часто повышается при параллельной работе. Две стратегии распараллеливания специально ориентированы на алгоритмы, основанные на популяциях:
- Распараллеливание вычислений , при котором операции, обычно применяемые к каждому из индивидов, выполняются параллельно, и
- Распараллеливание популяции , при которой популяция делится на разные части, которые можно просто обменивать или развивать отдельно, а затем присоединять позже.
В начале истории распараллеливания этих алгоритмов хорошо известный главный-подчиненный (также известный как глобальное распараллеливание или сельское хозяйство) был использован метод. В этом подходе центральный процессор выполняет операции выбора, в то время как связанные подчиненные процессоры (рабочие) запускают оператор изменения и оценку функции пригодности. Этот алгоритм имеет то же поведение, что и последовательный, хотя его вычислительная эффективность улучшена, особенно для трудоемких целевых функций. С другой стороны, многие исследователи используют пул процессоров для ускорения выполнения последовательного алгоритма просто потому, что независимые запуски могут выполняться быстрее при использовании нескольких процессоров, чем при использовании одного. В этом случае никакого взаимодействия между независимыми прогонами не существует.
Однако на самом деле большинство параллельных популяционных методов, встречающихся в литературе, используют какое-то пространственное расположение индивидов, а затем распараллеливают полученные фрагменты в пуле процессоров. Среди наиболее широко известных типов структурированной метаэвристики очень популярными процедурами оптимизации являются распределенный (или крупнозернистый) и ячеистый (или мелкозернистый) алгоритмы.
В случае распределенных популяция разбивается на набор субпопуляций (островов), в которых выполняются изолированные последовательные алгоритмы. Между этими островами производятся редкие обмены особями с целью внесения некоторого разнообразия в субпопуляции, что предотвращает поиск застревания в локальных оптимумах. Чтобы разработать распределенную метаэвристику, мы [ кто? ] должен принять несколько решений. Среди них главное решение - определить миграционную политику: топологию (логические связи между островами), скорость миграции (количество людей, которые подвергаются миграции при каждом обмене), частоту миграции (количество шагов в каждой субпопуляции между двумя последовательными обменами). , и отбор / замена мигрантов.
В случае клеточного метода вводится понятие соседства, так что особь может взаимодействовать только со своими ближайшими соседями в цикле размножения. Перекрывающееся небольшое соседство в алгоритме помогает исследовать пространство поиска, потому что медленное распространение решений среди населения обеспечивает своего рода исследование, в то время как эксплуатация происходит внутри каждого района. См. [3] для получения дополнительной информации о клеточных генетических алгоритмах и родственных моделях.
Также предлагаются гибридные модели, в которых применяется двухуровневый подход к распараллеливанию. В общем, более высокий уровень распараллеливания является крупномасштабной реализацией, а базовый остров выполняет сотовый метод, метод «ведущий-ведомый» или даже другой распределенный.
См. Также [ править ]
- Клеточные эволюционные алгоритмы
- Энрике Альба
Ссылки [ править ]
- Дж. Луке, Э. Альба, Параллельные генетические алгоритмы. Теория и приложения реального мира, 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
- DEME
- xxGA
- PSALHE-EA
- Paradiseo
