ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2007, том 47, < 9, с. 1524-1537
УДК 519.6:519.852.6
ПРИМЕНЕНИЕ ПАРАЛЛЕЛЬНЫХ ЭВРИСТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ УСКОРЕНИЯ ПАРАЛЛЕЛЬНОГО МЕТОДА
ВЕТВЕЙ И ГРАНИЦ1
© 2007 г. М. А. Посыпкин*, И. X. Сигал**
(* 109004 Москва, пр-т 60-летия Октября, 9, ИСА РАН;
** 119991 Москва, ул. Вавилова, 40, ВЦ РАН) e-mail: mposypkin@mail.ru; sigal@ccas.ru Поступила в редакцию 08.02.2007 г.
Предложена схема параллельной реализации совместной работы метода ветвей и границ и эвристических алгоритмов. Приводятся результаты экспериментов для задачи об одномерном булевом ранце, которые демонстрируют эффективность предлагаемого подхода. Анализируются основные факторы, влияющие на сокращение времени решения задачи с применением методов локальной оптимизации. Библ. 22. Фиг. 4. Табл. 8.
Ключевые слова: задача о ранце, метод ветвей и границ, алгоритмы параллельных вычислений, дискретная оптимизация, локальная оптимизация.
ВВЕДЕНИЕ
В наиболее общем варианте задача дискретной оптимизации формулируется следующим образом: дано конечное множество G и функция f : G —► R, требуется найти х* е G такое, что f(x*) > f (х) для всех х е G в случае задачи максимизации или f (х*) < f (х) для всех х е G в случае задачи минимизации. Для целей данной работы задачи максимизации и минимизации эквивалентны, и для упрощения формулировок далее мы будем всегда рассматривать только задачу максимизации.
Многие задачи дискретной оптимизации относятся к классу NP, и их решение требует значительных вычислительных ресурсов. Поэтому представляется целесообразным применение методов параллельных (см. [1], [2]) и распределенных вычислений (см. [3]). Метод ветвей и границ (МВГ) является одним из наиболее распространенных алгоритмов решения задач дискретной оптимизации. В основе этого метода лежит идея декомпозиции, которая делает естественным применение методов параллельных вычислений. Этим фактом можно объяснить значительный интерес исследователей к вопросам параллельной реализации МВГ. Обзор различных подходов можно найти в работах [4]-[8].
Несмотря на то, что применение методов параллельных вычислений позволяет существенно ускорить решение задач, в ряде случаев время, затраченное на решение, не является приемлемым. Известно (см. [9]), что трудоемкость - число решаемых оценочных задач в методе ветвей и границ - существенно зависит от того, насколько быстро удается найти хорошее приближение к оптимуму. Для этого обычно применяют эвристические алгоритмы построения начальных решений и их последующего улучшения с применением процедур локальной оптимизации.
В отличие от точных методов, к которым, в частности, относятся МВГ и динамического программирования, эвристические алгоритмы не гарантируют оптимальность найденных решений. Они предназначены для поиска приближенных решений на основе правдоподобных, но не обоснованных строго предположений о структуре множества решений. В комбинации с МВГ эвристические алгоритмы позволяют получить близкие к оптимуму значения рекорда, поэтому трудоемкость МВГ при решении конкретной задачи может существенно уменьшиться. Полученное таким образом уменьшение трудоемкости не всегда приводит к сокращению времени работы в последовательном варианте, так как время, затраченное на работу эвристических алгоритмов, может превзойти уменьшение времени за счет сокращения числа ветвлений. Этого недостатка можно избежать, если локальная оптимизация будет производиться параллельно с оптимизацией по МВГ без увеличения таким способом общего времени работы.
1)Работа выполнена при финансовой поддержке РФФИ (код проекта 05-01-00495).
В данной статье предлагается подход, основанный на комбинировании параллельного МВГ и параллельного эвристического поиска в одном приложении. В такой схеме эвристические алгоритмы обрабатывают допустимые решения, получаемые по ходу работы МВГ, а МВГ использует для отсева рекордные значения, формируемые эвристиками. Предлагаемый подход был реализован и протестирован для задачи о ранце. Результаты экспериментов показывают, что даже применение достаточно простой эвристики позволяет существенно ускорить работу алгоритма.
1. МЕТОД ВЕТВЕЙ И ГРАНИЦ И ЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ
1.1. Постановка задачи об одномерном булевом ранце
Задача об одномерном булевом ранце формулируется следующим образом. Пусть существует п предметов, для каждого из них заданы стоимость с, > 0 и вес а, > 0. Требуется найти совокупность этих предметов максимальной суммарной стоимости, общий вес которой не превосходит
R: предполагается, что ХП вид:
ai > R. Формально постановка задачи о ранце имеет следующий
f( x) = X<
max,
i = 1
X
QiXl < R,
(1)
1 = 1
хг е {0, 1}, 1 = 1, 2, ..., п.
Определим некоторые термины, связанные с данной задачей. Вектор х = (х1, ..., хп), удовлетворяющий неравенству ^П = 1 а,Хг ^ называется допустимым решением задачи (1). Максимальное значение функции / при данных ограничениях называется оптимумом и обозначается через /*. Максимальное значение функции /, найденное на текущем шаге алгоритма, будем называть рекордом и обозначать через/0.
n
n
1.2. Метод ветвей и границ
Метод ветвей и границ является одним из основных методов, применяемых при численном решении задач дискретной оптимизации. Суть его заключается в последовательном разбиении множества допустимых решений на подмножества с последующим отсевом подмножеств, не содержащих оптимальных решений.
Рассмотрим задачу дискретного программирования f (x) —► max, x e G. Будем говорить, что функция ф : 2G —- Ш, является верхней оценкой для функцииf, если для любого подмножества G множества G справедливо следующее соотношение: Vx e G : ф^) > f (x). Правило отсева подмножеств, не содержащих оптимальные решения, состоит в том, что если для некоторого x0 e G и G с G известно, что ф^') < f (x0), то подмножество G может быть исключено из дальнейшего поиска, так как согласно определению верхней оценки, оно не содержит оптимальных решений.
Для получения оценки ф(5) для подмножества S с G решается оценочная задача. На основании результатов решения оценочной задачи подмножество S исключается из дальнейшего процесса поиска, если для него выполнено хотя бы одно из следующих свойств:
1) S не содержит допустимых решений;
2) при решении оценочной задачи на подмножестве S получено допустимое решение исходной задачи;
3) S может быть отсеяно по правилу отсева.
Каждое подмножество, получаемое в процессе решения, определяет подзадачу оптимизации. Поэтому в контексте статьи далее термины подмножество и подзадача будут употребляться как эквивалентные. Подзадачи, которые еще не подверглись операции ветвления, будем называть задачами-кандидатами.
В процессе решения поддерживается список задач-кандидатов, который в начальный момент содержит только один элемент, соответствующий всему множеству допустимых решений G,
Фиг. 1.
определяемому исходной задачей. На каждом шаге в методе ветвей и границ производится разбиение (ветвление) одного из элементов списка на несколько новых подзадач, для каждой из которых решается оценочная задача. В этом списке подзадача, подвергнутая ветвлению, заменяется подзадачами, полученными в результате этого ветвления, т.е. производится модификация списка подзадач.
Графически процесс решения задачи методом ветвей и границ можно представить в виде дерева, называемого деревом ветвлений. Вершинам дерева соответствуют подзадачи, получаемые в результате ветвления, а дуги соединяют данную подзадачу с подзадачами, полученными из нее в результате ветвления. Ветвлению подвергаются подзадачи, соответствующие концевым вершинам дерева. Будем обозначать черным кружком подзадачи, исключенные из дальнейшего процесса поиска по правилам 1)-3), серым кружком - подзадачи, подвергнутые ветвлению, а светлым кружком - задачи-кандидаты. Тогда текущий список задач-кандидатов соответствует всем белым концевым вершинам дерева ветвления (фиг. 1).
Выбирать очередную подзадачу для ветвления из списка задач-кандидатов можно различными способами. Наиболее известными являются следующие (см. [9]):
а) одностороннее ветвление: выбирается одна из подзадач, полученных на предыдущем шаге;
б) фронтальное ветвление: выбирается подзадача с наибольшей верхней оценкой;
в) комбинация первого и второго способов.
Метод ветвей и границ относится к числу основных при решении задачи о ранце. В случае задачи о булевом ранце с одним ограничением оценочная задача линейного программирования получается заменой дискретных ограничений на переменные линейными:
n n
f (х) = ^е,х, —► max, ^а,х, < R, 0 < xi < 1, i = 1, 2, ..., n.
i=1 i=1
Очевидно, оптимум данной задачи не меньше, чем оптимум задачи (1). Этот оптимум определяется по правилу Данцига [9] и содержит не более одной переменной с дробным значением. Разбиение задачи на подзадачи осуществляется приданием дробной переменной значений 0 и 1 соответственно.
1.3. Эвристические и локальные методы оптимизации
Скорость работы метода ветвей и границ во многом определяется интенсивностью отсева задач-кандидатов, так как отсев позволяет существенно сократить объем перебора. В свою очередь, интенсивность отсева зависит от близости найденного в некоторый момент рекорда к оптимуму: чем точнее найденный рекорд, тем интенсивнее отсев. Поэтому применение различных методов, направленных на улучшение найденного рекорда, может существенно ускорить работу алгоритма ветвей и границ.
Общепринятым методом для улучшения допустимых решений являются эвристические алгоритмы (см. [10]), основанные на правдоподобных, но строго не обоснованных свойствах оптимального решения задачи. Эвристические алгоритмы применяются, как правило, совместно с алгоритмами локальной оптимизации, которые также могут рассматриваться как частный случай эвристики.
Локальной оптимизацией называется задача поиска экстремума функции f(x) в заданной окрестности G(x0) некоторой точки x0 : f (x) —► max, x e G(x0). Для задачи дискретной оптимизации понятие окрестности вводится, как правило, с помощью различных искусственных построений и поэтому представляет определ
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.