ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2008, № 3, с. 99-105
^ КОМПЬЮТЕРНЫЕ ^^^^^^^^^^^^^^
МЕТОДЫ
УДК 519.854.7
ЭКСПЕРЕМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ КОМБИНИРОВАННЫХ АЛГОРИТМОВ ВЕТВЕЙ И ГРАНИЦ И ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ ДЛЯ ЗАДАЧИ О РАНЦЕ*
© 2008 г. Н. Н. Галимьянова
Москва, МГУ ПС (МИИТ) Поступила в редакцию 26.11.07 г.
Предложен комбинированный алгоритм ветвей и границ и динамического программирования для задачи о ранце с одним ограничением. Проведен обширный вычислительный эксперимент для размерности задач до 3000, на основе которого сделано сравнение предложенного алгоритма с алгоритмами ветвей и границ и динамического программирования. Для комбинированного алгоритма рассмотрен коэффициент потенциального количества процессоров.
Введение. Задачи дискретной оптимизации и, в частности, задачи ранцевого типа служат математическими моделями многих проблем, встречающихся в приложениях. Методы, наиболее часто применяемые при решении задач дискретной оптимизации - динамическое программирование и метод ветвей и границ. Целью работы является исследование последовательной реализации комбинированных алгоритмов для решения задачи о ранце, основные элементы которых - алгоритмы локальной оптимизации, ветвей и границ и динамического программирования. Рассматриваются последовательные реализации алгоритмов [1-3] для упомянутой задачи. Разработанная реализация алгоритма может быть применена для решения задачи в параллельном режиме [4-9, 10]. Для исследования и проведения вычислительного эксперимента была выбрана задача о ранце с одним ограничением. Эта задача является ^Р-полной и хорошо изучена.
1. Постановка задачи и общие сведения об алгоритмах. Пусть имеется п предметов, у каждого из которых ценность Ср > 0 и вес ар > 0,р = 1, 2, ..., п. Существует ранец (рюкзак), грузоподъемность которого равна Я. Необходимо положить в ранец набор предметов с максимальной суммарной ценностью. При
этом предполагается, что =: а ^ > Я , 0 < ар < Я, все
значения ар Ср и Я целые, р = 1, 2, ..., п. Для описания задачи на языке целочисленного линейного программирования введем булевы переменные Хр (0, если предмет с номером р не кладется в ранец и 1 в противном случае), х = (х1, х2, ... , хп). Сформирована следующая задача целочисленного (буле-вого) линейного программирования:
* Работа выполнена при финансовой поддержке РФФИ (грант < 05-01-00495).
n
fx) = £ CjXj —► max, (1.1)
j = i n
£ ajXj < Я, (и)
j = 1
Xj e{ 0, 1}, j = 1, 2 ..., n. (1.3)
Подробное описание задачи и алгоритмов ее решения содержится в [1-3].
Метод динамического программирования основан на утверждении, имеющем название принцип оптимальности Беллмана. Смысл этого принципа состоит в том, что оптимальная стратегия при любых первоначальных состоянии и решении предполагает, что последующие решения должны быть оптимальны относительно состояния, полученного в результате предыдущего решения (подробное описание дано в [1-3]). Под методом ветвей и границ понимается метод с древовидной структурой поиска оптимального решения и использующий результаты решения оценочных задач. Древовидная структура называется обычно деревом ветвления. Подробное описание метода ветвей и границ содержится в [1-3]. Методы локальной оптимизации рассмотрены в [1].
2. Комбинированный алгоритм. Среди точных методов решения задачи (1. 1)—(1.3) можно выделить два: динамическое программирование и ветвей и границ. Оба основываются на последовательном анализе вариантов и применяют различные способы отсева подмножеств из множества допустимых решений, не содержащих оптимального решения. В методе ветвей и границ производится отсев по верхней оценке для подмножества. В методе динамического программирования исключаются все доминируемые подмножества. По-
99
7*
этому представляется естественным совместное применение обеих процедур (правил) отсева. Комбинированный алгоритм - это алгоритм динамического программирования с дополнительным правилом отсева. Предлагается следующий способ совместного применения вышеупомянутых процедур. За основу берется метод динамического программирования, но отсев осуществляется по обоим правилам. Обозначим
(к к ^
х х ал=
) =1 ) =1 > Решение задачи (1.1)—(1.3) методом динамического программирования сводится к расчетам по рекуррентным соотношениям
gk (у) = тах ^к - х(у - акхк) + СкХк}, (2.1)
хк е {0,1} к
0 < у = X а1х} < Я к = 2, ..., п.
1 = 1
Совместное применение правил отсева, реализованных в методах динамического программирования и ветвей и границ достигается путем исключения из последовательности (2.1) тех членов gk(y), для которых выполняется условие
gk (У) + [g* (У)] < g0,
(2.2)
здесь g0 — значение целевой функции для наилучшего из полученных целочисленных решений (рекорд),
g* (у) — верхняя оценка суммы Хп = к + 1 с]х] при ограничениях
к
X а]х] < Я - у, (2.3)
} = к +1
вычисляемая по правилу Данцига [1]. Величина
gk(y) + g* (у) — верхняя оценка, соответствующая данному члену последовательности (2.1). Поэтому стандартная процедура динамического программирования может рассматриваться как своеобразное правило ветвления подмножеств решений, обеспечивающее исключение бесперспективных вариантов.
Опишем алгоритм решения задачи в виде последовательности шагов:
Шаг 1. Находим g0 — значение целевой функции для начального решения (например, по двум правилам последовательного назначение единиц: по не-
возрастанию значений с и X
_ 1
с ■ > с ■ > с ■ '
Х^ > Х^ ... > Xj с применением локальной оптимизации.
Шаг 2. Определяем верхнюю оценку gl* (0), к = 0.
Шаг 3. Если [go (0)] < g0, то задача решена, иначе переход к шагу 4.
Шаг 4. Увеличиваем значение к на единицу.
Шаг 5. Исходя из величин ук - 1 находим два значения ук = ук -1 и ук = ук — 1 + ак, которые соответствуют значениям хк = 0 и 1.
Шаг 6. Для всех ук рассчитываются значения gk(y) по формуле (2.1), g* (у) — из формулы (2.3) и соответственно g0.
Шаг 7. Выполняем отсев по правилу (2.2).
Шаг 8. Если в столбце, отвечающем значению gk(y), все элементы отсеяны, то задача решена и вектор, для которого достигнуто рекордное значение g0, является решением; если к = п, то задача решена и решение выбирается по максимальному значению gn(y); если к < п, то переходим к шагу 4.
3. Формирование параметров задач для вычислительного эксперимента. Эксперимент проводился для трех серий из N = 10 задач размерности п = 1000; 2000 и 3000. Для всех серий Я задавалось как
тХп = 1 а1, где у = 0.1, 0.2, ..., 0.9. Способ формирования параметров и названия серий задач заимствованы из [2., 3].
Серия 1. Слабосвязанные параметры: в качестве с1 использовались целые случайные, равномерно распределенные на отрезке [1, 1000] числа, а^ представляли собой целые случайные, равномерно распределенные на отрезке [с^ с + 100] числа.
Серия 2. Независимые параметры: с1 и а^ формировались как целые случайные, равномерно распределенные на отрезке [1, 1000] числа.
Серия 3. Сильносвязанные параметры: с1 — целые случайные числа, равномерно распределенные на отрезке [1, 1000], а] задавались как с1 + 100.
Цели эксперимента состоят в исследованиях:
зависимости времени решения задачи от параметра у для указанных размерностей;
отклонения начального решения от оптимального;
величины потенциального количества процессоров для комбинированного алгоритма; для определений этой величины найдем для каждой реализации количество независимо вычисляемых значений gk(y), а по ним — среднее количество. Далее усредним полученные значения по всем N реализациям.
3.1. Результаты эксперимента. В
табл. 1 приведены зависимости относительного отклонения приближенного решения от оптимального для различных серий, значений параметра у и размерности задачи. В табл. 2 отражен средний процент улучшения приближенного решения с применением алгоритма локальной оптимизации для
Таблица 1
п У Среднее по у
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
Серия 1
1000 0.0116 0.0106 0.0052 0.0039 0.0033 0.0035 0.0017 0.0019 0.0012 0.0048
2000 0.0048 0.0018 0.0016 0.0016 0.0012 0.0009 0.0005 0.0004 0.0006 0.0015
3000 0.0034 0.0017 0.0010 0.0008 0.0006 0.0005 0.0004 0.0005 0.0003 0.0010
Серия 2
1000 0.0121 0.0040 0.0052 0.0038 0.0028 0.0023 0.0010 0.0008 0.0007 0.0036
2000 0.0024 0.0018 0.0022 0.0051 0.0013 0.0008 0.0005 0.0003 0.0001 0.0016
3000 0.0028 0.0015 0.0014 0.0005 0.0004 0.0011 0.0006 0.0005 0.0001 0.0010
Серия 3
1000 0.0002 0.0009 0.0002 0.0000 0.0002 0.0002 0.0003 0.0001 0.0000 0.0002
2000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
3000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
Таблица 2
п У Среднее по у
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
Серия 1
1000 0.6570 0.3621 0.2222 0.1977 0.1078 0.1297 0.0914 0.0438 0.0297 0.2046
2000 0.2471 0.1720 0.1410 0.0771 0.0825 0.0605 0.0541 0.0321 0.0175 0.0982
3000 0.2387 0.1204 0.0660 0.0556 0.0548 0.0443 0.0229 0.0200 0.0125 0.0706
Серия 2
1000 0.1489 0.1440 0.1764 0.0873 0.0442 0.0388 0.0349 0.0131 0.0134 0.0779
2000 0.0811 0.0698 0.0963 0.0511 0.0295 0.0335 0.0137 0.0109 0.0061 0.0435
3000 0.0617 0.0393 0.0441 0.0376 0.0211 0.0198 0.0115 0.0080 0.0034 0.0274
Серия 3
1000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
2000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
3000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
различных серий, значений параметра у и размерности задачи. Из табл. 1 и 2 видно, что для всех серий, значений параметра у и размерностей начальное, улучшенное и оптимальное решения задачи практически совпадают. Отклонения начального решения от улучшенного и улучшенного оптимального составляют доли процента, максимальная величина равна 0.7%.
В табл. 3 представлены средние величины потенциального количества процессоров в комбинированном алгоритме для различных серий, значений параметра у и размерности задачи. Все времена, содержащиеся в таблицах и последующих графиках, выражены в секундах.
3.1.1. Ре
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.