Software & Systems

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

Одной из тенденций последних лет является появление универсальных программных средств, предназначенных для решения широкого класса задач. Как правило, в таких программных продуктах реализуются различные метаэвристические подходы к решению ЗДО. В качестве примера можно привести следующие библиотеки (в англоязычной литературе для них часто применяется термин frameworks): EasyLocal++ [1], MaLLBa [2], ParadisEO [3] и др. Основной особенностью данных библиотек является разделение программного кода на две части: проблемно-независимую, общую для всех решаемых задач, и проблемно-зависимую, отражающую специфику конкретной задачи. Эффективная реализация проблемно-независимой части выполняется разработчиками библиотеки, а реализация (точнее, модификация) проблемно-зависимой части ложится на плечи пользователя библиотеки.

Целью данной работы является исследование эффективности библиотеки MaLLBa, предназначенной для решения трудных ЗДО. Несмотря на то, что данная библиотека появилась довольно давно, информация о ней в отечественной литературе и Рунете практически отсутствует.

Архитектура и методы библиотеки MaLLBa

Библиотека MaLLBa (сокращение от названий трех городов: Malaga, La Laguna, Barcelona) является результатом сотрудничества исследователей из нескольких испанских университетов в 1999–2002 гг. Данная библиотека предоставляет в распоряжение пользователя так называемые алгоритмические каркасы (или скелеты, от англ. skele­tons), реализующие различные методы комбинаторной оптимизации. В каждом из каркасов реализованы как последовательная версия алгоритма, так и параллельные версии для локальных (LAN) и глобальных (WAN) сетей с использованием технологии MPI.

Все каркасы в MaLLBa реализованы в рамках единой идеологии. Каждый из каркасов представляет собой набор классов на языке C++, которые делятся на две группы:

1) provided classes – классы, описывающие проблемно-независимую часть каркаса;

2) required classes – классы, описывающие проблемно-зависимую часть каркаса.

Основными классами первой группы являются классы-решатели: абстрактный класс Solver и его наследники Solver_Seq, Solver_Lan и Solver_Wan.

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

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

Основные файлы любого алгоритмического каркаса:

1) .hh – определения всех классов каркаса;

2) .pro.cc – реализация проблемно-независимых классов;

3) .req.cc – реализация проблемно-зависимых классов;

4) .cfg – параметры метода,

где – название каркаса, например, newga или chc.

Библиотека MaLLBa доступна в двух версиях: полной, для которой необходимо оформление соответствующей лицензии, и краткой, доступной для скачивания в исходных кодах по адресу: http://neo.lcc.uma.es/mallba/easy-mallba. Последней версией библиотеки является версия 2.0. По указанному адресу доступна on-line документация с кратким описанием архитектуры библиотеки и методов оптимизации.

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

1) ACO (Ant Colony Optimization) – метод муравьиной колонии;

2) CHC (Cross-generational elitist selection, Heterogeneous recombination, and Cataclysmic mutation) – разновидность генетического алгоритма с разрушительной рекомбинацией генов;

3) CLS (Cooperative Local Search) – совместный локальный поиск;

4) ES (Evolutionary Strategies) – эволюционный алгоритм;

5) newGA (Genetic Algorithm) – генетический алгоритм;

6) PSO (Particle Swarm Optimization) – метод роящихся частиц;

7) SA (Simulated Annealing) – метод имитации отжига (имитационной нормализации);

8) SS (Scatter Search) – рассеянный поиск.

Одним из принципов использования алгоритмических каркасов в программировании является возможность их комбинирования. Применительно к ЗДО это означает возможность получения на основе имеющихся методов новых гибридных методов. В рассматриваемой версии библиотеки гибриды представлены всего одним методом – newGA+SA. К сожалению, несмотря на заявления авторов библиотеки, процедура гибридизации методов не является достаточно прозрачной, так как требует внесения изменений в проблемно-незави­симые классы.

В краткой версии отсутствуют точные методы оптимизации, однако в полной они имеются. В частности, в нее входят метод ветвей и границ (BnB), динамическое программирование (DP) и др., а также гибридные методы на их основе, например BnB+SA.

Для каждого из перечисленных методов авторами библиотеки реализованы проблемно-зависи­мые классы для нескольких известных ЗДО, например, задачи коммивояжера, задачи максимальной выполнимости и др. Однако не все методы могут применяться для решения этих задач, например, задача коммивояжера решается только методом ACO.

Библиотека написана под Linux и не является кросс-платформенной, но опыт использования показывает, что перенос ее на другие платформы не является сложной задачей.

Тестовая конфигурация и методика тестирования

Исследование эффективности реализованных в библиотеке MaLLBa методов проводилось на примере задачи максимальной выполнимости: дана конъюнктивная нормальная форма (КНФ) функции N переменных из M клауз по K литералов в каждой. Необходимо определить, какое максимальное количество ее клауз может быть выполнено.

Расчеты производились на кластере Тольяттинского государственного университета. Аппаратно-программная конфигурация кластера следующая: количество машин в кластере – 24; процессоры – Intel Core 2 Duo E7200@ 2.53 ГГц; ОЗУ – 2 ГБ; сеть – 100 Мбит Ethernet; операционная система – Linux 2.6.25-gentoo-r7; MPI – LAM 7.1.2.

Для тестирования были выбраны следующие алгоритмические каркасы: CHC, newGA, SA и SS. Тестирование проводилось на четырех задачах из набора SAT-02 Challenge Set, доступного на сайте SATLIB [4] по адресу: http://www.satlib.org. Параметры использованных задач приведены в табли- це 1: N – число переменных, M – число клауз, K – число литералов.

Таблица 1

Заметим, что одно из ограничений, примененных авторами при реализации проблемно-зависи­мых классов, – фиксированное число литералов в клаузе. Поэтому для тестирования были отобраны задачи, удовлетворяющие данному требованию. В общей постановке задачи максимальной выполнимости такое ограничение отсутствует.

Для решения задач выполнимости (SAT) и максимальной выполнимости (MAX-SAT) разработано большое количество специализированных алгоритмов и программ. Одной из лучших программ в своем классе является UBCSAT, доступная для скачивания на сайте SATLIB. В этой программе реализовано более 30 алгоритмов стохастического локального поиска для решения задач SAT и MAX-SAT с возможностью гибкой настройки алгоритмов и получения разнообразной статистики. В таблице 2 приведены лучшие решения рассматриваемых задач, найденные программой UBCSAT с использованием алгоритма GWSAT по результатам 10 попыток с ограничением на время одной попытки 120 секунд.

Таблица 2

Методика тестирования состояла в следующем. Каждая из задач поочередно решалась все- ми методами. Для каждого из методов сначала использовался последовательный решатель Solver_Seq, а затем параллельный Solver_Lan с числом потоков 2, 4, 8, 16 и 32. Каждый запуск состоял из 10 попыток, при этом фиксировались полученное решение и время выполнения. За- тем проводилась статистическая обработка результатов.

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

Таблица 3

Результаты тестирования

Результаты, полученные для всех четырех задач, оказались схожими, поэтому приведем результаты решения только для одной из них, а именно unif-c4550-v700-s97754000.

Лучшие решения, найденные каждым из методов библиотеки MaLLBa, и их относительные погрешности по сравнению с лучшим решением, найденным UBCSAT (4483), приведены в табли- це 4.

Таблица 4

Из таблицы 4 видно, что лучший результат со значительным отрывом показал метод CHC, а худший – метод SS.

В таблице 5 приведено время выполнения одной итерации по результатам всех запусков. Значения в таблице округлены до целого числа секунд.

Таблица 5

Как правило, при увеличении числа потоков время выполнения одной итерации для всех методов увеличивается, причем наиболее существенное увеличение наблюдается для метода SA.

В заключение приведем график зависимости средней относительной погрешности решения (по результатам 10 запусков) от числа пото- ков (см. рис.).

В целом полученные результаты можно считать хорошими для универсального пакета. Заметим, что некоторые методы в специализированном пакете UBCSAT (например URWALK) показывают результаты хуже метода SS библиотеки MaLLBa даже при времени выполнения одной попытки порядка нескольких минут. Следует отметить, что все методы UBCSAT являются однопоточными.

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

Проведенное в работе исследование позволяет сделать следующие выводы. Достоинствами библиотеки MaLLBa являются:

1) простота и наглядность организации библиотеки;

2) наличие общедоступной (хотя и значительно урезанной) версии с документацией и демонстрационными примерами;

3) большое количество точных и приближенных методов оптимизации (особенно в полной версии);

4) достаточно высокая эффективность реализованных методов;

5) наличие последовательных и параллельных версий для каждого метода оптимизации;

6) прозрачность параллелизма для пользователя библиотеки.

Среди недостатков библиотеки можно отметить следующие: отсутствие точных методов оптимизации в краткой версии; наличие ошибок в демонстрационных примерах и документации; сравнительно невысокая масштабируемость параллельных методов; непрозрачность гибридизации методов; отсутствие кросс-платформен­ности.

Несмотря на указанные недостатки, библиотека MaLLBa может с успехом использоваться как в прикладных, так и в академических целях.

Литература

1.   Gaspero L.Di, Schaerf A. EasyLocal++: an object-oriented framework for the flexible design of local search algorithms and metaheuristics. In 4th Metaheuristics International Conference (MIC’2001), 2001, pp. 287–292.

2.   E. Alba, et al. MaLLBa: A Library of Skeletons for Combinatorial Optimization. Proceedings of the Euro-Par’02, vol. 2004 of LNCS. – Springer-Verlag, 2002, pp. 927–932.

3.   S. Cahon, N. Melab and E-G. Talbi. ParadisEO: A Framework for the Reusable Design of Parallel and Distributed Metaheuristics, Journal of Heuristics, vol. 10(3), pp. 357–380, May 2004.

4.   Holger H. Hoos, Thomas Stützle. SATLIB: An Online Resource for Research on SAT. In: I.P.Gent, H.v.Maaren, T.Walsh, editors, SAT 2000, pp. 283–292, IOS Press, 2000.