В методе PS формируется множество К, элементами которого являются кортежи из номеров заданных прямоугольников. Если число прямоугольников п > 40, то число кортежей значительно увеличивается и при построении дерева вариантов упаковок не хватает машинных ресурсов для хранения и поиска кортежей по всем ветвям дерева. Вследствие этого многие "хорошие" решения могут остаться нерассмотренными.
Алгоритм частичного перебора с элементами стохастики (PSR). Модифицированный алгоритм динамического перебора (PSR) состоит из нескольких процедур, представленных на рис. 4 в виде структограммы.
Опишем основные процедуры PSR.
Процедура 1. Строятся множества Мi, i = 1, 2, …, и, на базе алгоритма решения SSP для ширины полосы W.
Процедура 5. Случайным образом формируются упаковки RP из кортежей, полученных в процедуре 2. Дерево вариантов упаковок не строится.
Численный эксперимент
При выполнении численного эксперимента критерием оценки алгоритма решения задачи двумерной упаковки помимо времени его выполнения выступает коэффициент раскроя (КРА). Для эксперимента использовали персональный компьютер Pentium 200 с оперативной памятью 128 Мбайт. Для генерации задач в данном эксперименте был применен генератор BPPGEN [19].
Целью эксперимента являлось выяснение качества работы стохастического метода динамического перебора PSR для двумерной упаковки в зависимости от параметра р — вероятности включения кортежа в множество кортежей Kw. Параметрами задачи двумерной упаковки являются:
Для каждого класса было просчитано 50 примеров. Число запусков k = 10. В табл. 3 показаны значения параметра р для различных классов задач, при которых метод PSR получает наилучшие значения.
В табл. 4 и рис. 5 (см. третью сторону обложки) показаны отклонения КРА от нижней границы при решении 2DBPP методом PSR с использованием наилучших значений параметра р для различных классов задач.
Эксперимент N 2. На рис. 6-8 (см. третью сторону обложки) рассмотрена работа метода PSR на наборах "малые предметы", "средние предметы", "малые и большие предметы". Среднее время работы метода PSR от 1 до 4 мин. Метод PSR сравнивался с методами GCA&BD — генетическим классическим алгоритмом с блочным декодером (D. Liu, Н. Teng, А. В. Чиглинцев) и GCA&IBL — генетическим классическим алгоритмом с улучшенным декодером "нижний левый" (D. Liu, H. Teng).
Результаты экспериментов показали, что на наборах "средние предметы" коэффициент раскроя, полученный методом PSR для двумерной упаковки, составляет KRA = 98-99 % и превышает коэффициент раскроя для сравниваемых методов на 6- 16 %; на наборах "малые предметы" результаты (KRA = 92-96 %) также превышают KRA сравниваемых методов на 4-14 %; на наборах "малые и большие предметы" метод PSR (KRA = 92-94 %) уступает KRA для алгоритма GCA&BD примерно на 1 %.
С помощью метода PSR может быть получено множество различных упаковок с одной и той же длиной занятой части полосы. На рис. 9 показаны четыре различные упаковки с одним и тем же значением целевой функции / = 1628, полученные с помощью PSR для п = 40 прямоугольников с.
Таким образом, проведение вычислительного эксперимента позволяет сделать вывод, что внесение в алгоритм частичного перебора элемента случайности резко повышает эффективность его работы. Предложен детерминированный алгоритм частичного перебора и с элементами стохастики. Проведен вычислительный эксперимент с PS и PSR. При этом время работы алгоритмов — от нескольких секунд до нескольких минут. PSR и PS дают лучшие результаты для трудного класса задач при v2 = 0.4. PSR и PS позволяют получить множество квазиоптимальных решений, что существенно при решении практических задач. Окончательный выбор остается за пользователем. PSR и PS могут служить оптимизационным ядром для других комбинаторных задач.