Использование шаблонного метапрограммирования при реализации параллельных гибридных метаэвристических алгоритмов оптимизации

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Уфа: УГАТУ, 2010
'-Be& amp-тн, и, к,
Т. 14, № 4 (39). С. 221−228
УПРАВЛЕНИЕ, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И ИНФОРМАТИКА
УДК 004. 8
О. И. Булычов
ИСПОЛЬЗОВАНИЕ ШАБЛОННОГО МЕТАПРОГРАММИРОВАНИЯ ПРИ РЕАЛИЗАЦИИ ПАРАЛЛЕЛЬНЫХ ГИБРИДНЫХ МЕТАЭВРИСТИЧЕСКИХ АЛГОРИТМОВ ОПТИМИЗАЦИИ
Рассматривается подход к разработке параллельных метаэвристических алгоритмов оптимизации, реализованный в библиотеке параллельных метаэвристик НеО. Подход основан на использовании шаблонов проектирования, что позволяет получать универсальные и гибкие алгоритмы с возможностью гибридизации. Обсуждаются вопросы реализации параллельного генетического алгоритма, алгоритма имитационной нормализации и их гибридов. Приводятся результаты вычислительных экспериментов. Метаэвристики- параллелизм- гибридные алгоритмы- шаблоны проектирования
ВВЕДЕНИЕ
Оптимизационные задачи возникают в различных областях науки и техники, и для их решения разработан богатый арсенал методов. Однако нахождение точного решения многих задач на практике оказывается невозможным. Это может быть вызвано разными причинами: сложностью решаемой задачи, погрешностями входных данных, временными и аппаратными ограничениями и др. В связи с этим актуальным остается вопрос разработки эффективных приближенных методов решения таких задач.
Благодаря интенсивному развитию компьютерной техники вот уже несколько десятилетий для нахождения приближенного решения многих трудных оптимизационных задач (прежде всего задач дискретной оптимизации) с успехом применяются метаэвристические алгоритмы (см., например, [1]). Популярность данных алгоритмов обусловлена целым рядом факторов, из которых можно отметить следующие два:
• простота и ясность концепций, лежащих в их основе-
• высокий уровень абстракции.
Первый фактор обуславливает относительную простоту реализации метаэвристических алгоритмов на различных программно-
аппаратных платформах, а второй позволяет применять данные алгоритмы к широкому кругу оптимизационных задач (как дискретных, так и непрерывных).
Бурное развитие параллельных вычислительных технологий в последние годы способ-
Контактная информация: (9510) 97−04−61 Статья рекомендована к публикации программным комитетом Международной научной конференции «Параллельные вычислительные технологии-2010»
ствовало возрождению интереса к метаэвристи-ческим алгоритмам, что обусловлено возможностью их эффективного распараллеливания. Используя различные модели параллельных вычислений в метаэвристических алгоритмах, можно либо улучшать качество получаемых решений, либо ускорять процесс их поиска. На сегодняшний день разработано большое количество программных средств, в которых реализованы те или иные параллельные метаэвристи-ческие алгоритмы для решения конкретных задач. Одной из тенденций последнего десятилетия является создание универсальных библиотек (frameworks) параллельных метаэвристиче-ских алгоритмов, которые можно применять для решения широкого круга оптимизационных задач.
Кроме того, в последние годы большое внимание уделяется гибридизации метаэвристик, что позволяет на основе базовых алгоритмов получать новые, более эффективные методы оптимизации. Вопросы гибридизации метаэври-стических алгоритмов в разных программных продуктах решаются по-разному. Учитывая большое разнообразие метаэвристических алгоритмов, универсального метода их гибридизации просто не существует, однако можно выделить некоторые общие подходы к гибридизации, применяемые на практике. Хороший обзор методов гибридизации метаэвристик приведен
в [2].
В настоящей статье рассматриваются практические вопросы программной реализации и гибридизации параллельных метаэвристиче-ских алгоритмов в библиотеке HeO, разработанной с использованием современных технологий программирования, метапрограммирования и параллельных вычислений на языке C++. Подробное описание библиотеки можно найти
в [3]. В следующем разделе будут приведены наиболее важные сведения об этой библиотеке.
1. БИБЛИОТЕКА HEO
Библиотека HeO (Heuristic Optimization) является проектом с открытым исходным кодом и распространяется на основе лицензии MIT. Цель проекта — обеспечить исследователей современными и простыми в использовании средствами для решения широкого круга оптимизационных задач.
Ключевыми особенностями библиотеки являются:
• кроссплатформенность, поддержка архитектур x86 и x64-
• реализация методов оптимизации в виде проблемно-независимых алгоритмических каркасов-
• реализация каждого метода оптимизации с использованием двух технологий параллельного программирования: MPI и OpenMP-
• использование оригинальной обертки (wrapper) для функций MPI-
• наличие мастеров (wizards), облегчающих создание пользовательских проектов-
• прозрачность параллелизма для пользователей библиотеки.
Официальная страница проекта располагается по адресу: http: //www. code. google. eom/p/ heo1.
Библиотека представляет собой набор классов, которые можно разделить на две большие группы: основные классы и вспомогательные классы.
Основные классы участвуют в непосредственной реализации того или иного метода оптимизации. Ядро основных классов библиотеки составляют так называемые решатели (solvers). Каждый решатель реализует определенный метод оптимизации в соответствии с определенной технологией параллельного программирования (MPI или OpenMP).
Решатели выполнены в виде шаблонов языка C++ в соответствии с идеологией алгоритмических каркасов. Это означает, что в них:
• реализована только проблемно-независимая часть алгоритма-
• скрыты все аспекты параллельной реализации.
1 В настоящий момент для скачивания (в разделе Downloads или через SVN-клиент) доступна версия 1.1 библиотеки.
Эти особенности позволяют применять решатели к широкому кругу задач и делают параллелизм прозрачным для пользователя библиотеки. Для использования решателей пользователем должны быть реализованы проблемнозависимые классы, описывающие конкретную задачу оптимизации и ее решения. Кроме того, в проблемно-зависимых классах обязательно должны быть реализованы методы, специфические для того или иного алгоритма оптимизации.
Вспомогательные классы библиотеки выполняют всевозможные служебные функции (работа с конфигурационными файлами, запуск решателей, передача данных по сети, генерация псевдослучайных чисел и т. п.).
Для демонстрации возможностей библиотеки разработаны несколько проектов, в которых реализованы проблемно-зависимые классы для нескольких задач дискретной и непрерывной оптимизации:
• ONE-MAX — максимизация числа единиц в двоичной строке (тестовая задача для ме-таэвристических алгоритмов) —
• MAX-SAT — задача максимальной выполнимости-
• GridMin — задача минимизации числа покрывающих блоков в #-отношениях недетерминированных конечных автоматов-
• Rastrigin — минимизация функции Рас-тригина-
• Rosenbrock — минимизация функции Ро-зенброка-
• ODE1IVP — численное решение задачи Коши для ОДУ первого порядка.
2. РЕАЛИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ МЕТАЭВРИСТИЧЕСКИХ
АЛГОРИТМОВ И ИХ ГИБРИДИЗАЦИЯ
С ИСПОЛЬЗОВАНИЕМ ТЕХНОЛОГИИ ШАБЛОННОГО ПРОЕКТИРОВАНИЯ
В настоящий момент в библиотеке HeO реализованы два метаэвристических метода оптимизации: генетический алгоритм (GA — Genetic Algorithm) и метод имитационной нормализации или имитации отжига (SA — Simulated Annealing), а также их гибрид (GA+SA). Описания последовательных версий методов GA и SA можно найти, например, в [4]. Ниже будет рассмотрен использованный в библиотеке подход к параллельной реализации этих методов, основанный на технологии шаблонного проектирования. Подробное изложение методов шаблонного проектирования приведено в [5].
2.1. Реализация параллельных алгоритмов оптимизации
Как уже было отмечено выше, каждый из методов оптимизации реализован в библиотеке с помощью двух технологий параллельного программирования (MPI и OpenMP). В текущей версии библиотеки основной моделью параллельных вычислений является мультистартовая модель2. В этой модели алгоритм работает в несколько потоков, независимо решающих задачу с периодической кооперацией.
На рис. 1 представлен псевдокод потоков параллельного генетического алгоритма.
сгенерировать начальную популяцию хромосом
вычислить функцию стоимости для каждой хромосомы
while not (выполнено условие остановки) do
отобрать родительские хромосомы
выполнить кроссовер (получить
потомков)
применить мутацию к потомкам
вычислить функцию стоимости для потомков
сформировать новую популяцию
if (условие кооперации) then выполнить кооперацию end do
Выход: лучшие хромосомы (решение задачи)
Рис. 1. Псевдокод потоков параллельного генетического алгоритма
Кооперация в параллельном GA заключается в периодическом обмене выбранными с помощью некоторой процедуры решениями и фактически является аналогом миграции в островной модели GA.
Псевдокод потоков параллельного метода имитации отжига приведен на рис. 2.
Кооперация в параллельном SA представляет собой периодический обмен генерируемыми случайными решениями (ходами). В библиотеке
2 Для генетического алгоритма с использованием технологии ОрепМР реализована также модель глобальной популяции.
реализованы два режима кооперации: асинхронный и синхронный, схемы которых приведены на рис. 3 и 4.
сгенерировать начальное решение
вычислить функцию стоимости для начального решения
выбрать начальное значение температуры Т
установить счетчик начала итераций к равным 0
while not
(выполнено условие остановки) do
if (условие кооперации) then выполнить кооперацию выбрать случайное решение из окрестности текущего вычислить его стоимость сделать новое решение текущим с вероятностью P (T)
увеличить счетчик итераций к изменить температуру T end do
Выход: текущее решение
Рис. 2. Псевдокод потоков параллельного алгоритма имитации отжига
потоки
Рис. 3. Схема асинхронной кооперации потоков в мультистартовой модели
При синхронной кооперации осуществляется блокирование выполнения потоков и обмен данными между ними через фиксированное число итераций. Асинхронная кооперация инициируется первым потоком через фиксированные промежутки времени и выполняется без блокировки потоков по мере их готовности к
обмену данными. Использование синхронной кооперации может приводить к большой нагрузке на сеть в моменты кооперации. Асинхронный режим позволяет эффективно решать задачу на неоднородных кластерах и снизить нагрузку на сеть.
потоки
менении структуры класса придется вносить изменение и в функцию accept ().
кооперация
кооперация
Рис. 4. Схема синхронной кооперации потоков в мультистартовой модели
При использовании кооперации возникает проблема сериализации, т. е. перевода структур данных программы в последовательность битов и обратно. В большинстве существующих библиотек параллельной оптимизации загрузка, сохранение и передача по сети каждого поля класса производится индивидуально. Это приводит к тому, что при внесении изменений в структуру класса приходится вручную изменять программный код в каждом месте, где требуется сериализация.
С целью упрощения этих операций в библиотеке HeO используются приемы шаблонного метапрограммирования, позволяющие реализовать элементы технологии Reflection (Отражение) для строго типизированного доступа к полям классов. Реализованный алгоритм сериализации базируется на шаблоне проектирования Visitor (Посетитель), позволяющем определять новые операции над классами библиотеки, не изменяя исходный код классов. Для его использования достаточно определить метод accept () в требуемых классах и перечислить в нем необходимые поля класса (см. рис. 5).
В случае если поле само является структурой или классом, сериализация осуществляется рекурсивно. Для некоторых классов, в частности для std:: string, std:: vector и классов & quot-умных"- указателей, определены особые служебные классы, осуществляющие их сериализацию.
К сожалению, в языке C++ нет встроенного автоматического механизма Reflection. При из-
int memberl —
std: :vector<-float>- member2 —
ref ptr& lt-some interface& gt- member3_-
template& lt-class V& gt- void accept (V& amp-
v) {
v (member1, & quot-memberl"-) —
v (member2, & quot-member2"-) —
v (member3, & quot-member3"-) —
}
Рис. 5. Пример определения метода accept ()
Кооперация потоков в алгоритмах GA и SA реализована с использованием шаблона Strategy (Стратегия). Данный шаблон обеспечивает различные варианты кооперации без изменения исходного кода алгоритмов-клиентов. В настоящий момент реализована стратегия кооперации с обменом данными между потоками по кольцу, однако она может быть заменена любой другой.
2.2. Гибридизация параллельных алгоритмов
Для разных типов метаэвристических алгоритмов могут быть предложены разные способы гибридизации. В частности, для алгоритмов GA и SA наиболее популярными способами являются интеграционная (integrative) и кооперационная (cooperative) гибридизация. При интеграционной гибридизации один из алгоритмов является частью другого, например, SA может рассматриваться как один из генетических операторов, выполняемых в основном цикле GA. При кооперационной гибридизации алгоритмы обмениваются друг с другом решениями.
Наибольшие трудности возникают при практической реализации первой стратегии. Как правило, в существующих реализациях гибридного метода GA + SA жестко фиксируется структура алгоритма, а для ее модификации приходится вносить изменения в исходный код программы. Для решения этой проблемы в библиотеке HeO используется шаблон проектирования Factory (Фабрика), позволяющий сделать код создания объектов более универсальным, не привязываясь к конкретным классам, а оперируя лишь общим интерфейсом.
Все операторы гибридного алгоритма наследуются от абстрактного интерфейса abstract_operator. В исходном коде гиб-
рида и фабрики имена классов-операторов нигде не упоминаются, что упрощает добавление новых операторов. Каждый оператор регистрируется на фабрике с помощью вспомогательной функции. На рис. 6 показаны отношения между гибридом, фабрикой и операторами.
Рис. 6. Диаграмма отношений между гибридом, фабрикой и операторами
Одним из недостатков фабрики считается трудность восстановления класса создаваемого ею продукта по его абстрактному интерфейсу, с целью выполнения операции, зависящей от класса (к примеру, сериализации). Реализованный механизм Reflection позволяет эффективно обойти этот недостаток.
Параметры решателей в библиотеке HeO хранятся в конфигурационных файлах в формате xml. При выполнении кода, изображенного на рис. 7, в решателе solver будет создан вектор операторов, заданных в xml-файле конфигурации.
xml: :in in (env. property_tree_) —
in & gt->- solver-
Рис. 7. Пример инициализации класса
На рис. 8 и 9 приведены фрагменты xml-файлов, задающих различные векторы операторов для генетического алгоритма.
В первом случае будет создан вектор операторов [crossover, sa], а во втором [sa, crossover, mutation], которые будут последовательно применяться на каждой итерации алгоритма.
& lt-operator>-
& lt-crossover.. />-
& lt-sa.. />-
& lt-/operator>-
Рис. 8. Фрагмент конфигурационного файла
& lt-operator>-
& lt-sa.. />-
& lt-crossover.. />-
& lt-mutation … />-
& lt-/operator>-
Рис. 9. Фрагмент конфигурационного файла
Аналогично с помощью фабрики осуществляется выбор операторов отбора родительских и дочерних хромосом.
Поскольку для правильной работы программы требуется лишь один экземпляр конкретной фабрики, то для ее конструирования используется шаблонный класс Singleton (Одиночка).
При обмене данными между решателями, реализующими различные алгоритмы, может потребоваться необходимость преобразования проблемно-зависимых классов, поскольку представления данных в разных алгоритмах могут быть различными. Для решения этой проблемы в библиотеке HeO используется шаблон проектирования Adapter (Адаптер), позволяющий не принимать во внимание различия между проблемно-зависимыми классами разных алгоритмов.
Такой подход полностью избавляет пользователя от изменения исходного кода гибридного метода и позволяет получать гибридные алгоритмы, наиболее подходящие для решения конкретной задачи.
3. ПРИМЕРЫ
В качестве практических примеров использования параллельных эвристических алгоритмов оптимизации рассмотрим две задачи: задачу максимальной выполнимости и задачу поиска минимума функции Розенброка.
3.1. Задача максимальной выполнимости
Задача максимальной выполнимости (MAX-SAT) может кратко быть сформулирована следующим образом: дана конъюнктивная нормальная форма (КНФ) функции N переменных из M клауз. Требуется найти двоичный набор, при котором в этой функции будет выполнено наибольшее число клауз. Клаузы могут быть как фиксированной, так и переменной длины. Опи-
сание различных формулировок задач MAX-SAT можно найти, например, в [4].
В данном разделе будут приведены результаты тестирования для задачи ndhf_xits22_SAT из набора SAT 2009. Параметры задачи: число переменных — 4692, число клауз — 582 514. Данная задача является выполнимой, поэтому максимальное число выполнимых клауз совпадает с общим числом и равно 582 514.
Задача решалась на систе

Статистика по статье
  • 50
    читатели
  • 18
    скачивания
  • 0
    в избранном
  • 0
    соц. сети

Ключевые слова
  • МЕТАЭВРИСТИКИ,
  • ПАРАЛЛЕЛИЗМ,
  • ГИБРИДНЫЕ АЛГОРИТМЫ,
  • ШАБЛОНЫ ПРОЕКТИРОВАНИЯ,
  • METAHEURISTICS,
  • PARALLELISM,
  • HYBRID ALGORITHMS,
  • DESIGNING TEMPLATES

Аннотация
научной статьи
по автоматике и вычислительной технике, автор научной работы & mdash- Булычов Олег Иванович

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

ПоказатьСвернуть
Заполнить форму текущей работой