Параллельная метаэвристика

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

Фон

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

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

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

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

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

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

Algorithm: Sequential trajectory-based general pseudo-code
    Generate(s(0));        // Initial solution
    t := 0;                // Numerical step
    while not Termination Criterion(s(t)) do
        s′(t) := SelectMove(s(t)); // Exploration of the neighborhood
        if AcceptMove(s′(t)) then
            s(t) := ApplyMove(s′(t));
            t := t + 1;
    endwhile

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

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

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

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

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

Algorithm: Sequential population-based metaheuristic pseudo-code
    Generate(P(0)); // Initial population
    t := 0;          // Numerical step
    while not Termination Criterion(P(t)) do
        Evaluate(P(t)); // Evaluation of the population
        P′′(t) := Apply Variation Operators(P′(t)); // Generation of new solutions
        P(t + 1) := Replace(P(t), P′′(t)); // Building the next population
        t := t + 1;
    endwhile

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

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

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

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

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

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

В случае клеточного метода вводится понятие соседства, так что отдельный может взаимодействовать только со своими ближайшими соседями в цикле размножения. Перекрывающаяся небольшая окрестность в алгоритме помогает исследовать пространство поиска, поскольку медленное распространение решений среди совокупности обеспечивает своего рода исследование, в то время как эксплуатация происходит внутри каждой окрестности. См . [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 г.
Альба Э. Параллельная метаэвристика: новый класс алгоритмов . ISBN 0-471-67806-6 , июль 2005 г.
МАЛЬБА
ЯГДС
НЕ ГОВОРИ
xxGA
ПСАЛХЕ-ЕА
Райо