8.2.  Упаковка блоков

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

Задача упаковки в классической постановке определяется следующим образом. Дано конечное множество чисел (размеров элементов) Е и константа МАХ (размер блока), цель: найти разбиение множества Е на минимальное количество подмножеств, таких, что сумма элементов в каждом подмножестве не будет превышать МАХ (размера блока).

Отметим, что задача упаковки блоков тесно связана с задачей разбиения графов на части с минимизацией суммарного числа связей К, когда заданное число объектов надо разместить в N блоках с выполнением заданных ограничений и с минимизацией числа блоков. Приведем набор основных эвристик для решения этой задачи [186]:

•    FF (First Fit) — это простейшая эвристика, когда, начиная с одного пустого блока, берется объект за объектом и для каждого из них ищется подходящий блок. Если такой блок найден, то в него помещается объект, если не найден, то выбирается другой блок и процесс продолжается до распределения всех объектов.

•    FFD (First Fit Decreasing) — в этой эвристике предполагается по заданным предварительно критериям отсортировать объекты, а далее применить эвристику FF.

•    BF (Best Fit) — здесь происходит поиск самого заполненного блока, а далее применяется эвристика FF.

•    BFD (Best Fit Decreasing) — здесь реализуется эвристика «лучший подходящий в порядке убывания».

Запишем модифицированный FF для задачи упаковки блоков. Пусть подмножества стандартных блоков пронумерованы Хі,Х2,... и каждый из них не содержит вершин (блоков, которые должны быть размещены). Вершины х\, х2, • • • будут располагаться в блоках Х\, Х2,... в указанном порядке. Чтобы разместить Хі, необходимо найти наименьший из Xj такой, что Xj заполнен до уровня а ^ S(Xj) — S(xi) и разместить Хі в Xj, где S(Xj) — размер (мощность) блока Xj. Теперь Xj заполнен до уровня а + + S(xi). Другими словами, вершина Хі помещается в первый из блоков, куда она может войти без нарушений ограничений по размеру и значению ЦФ Q. Критерий Q комплексный, так как учитывает число заполненных блоков и площадь. Его необходимо минимизировать.

Алгоритмы FFD и BF для построения популяции альтернативных решений задачи упаковки блоков реализуются аналогично. Отметим алгоритм BF; в худшем случае он имеет те же характеристики, что и FF. Для FFD известно, что даже в худшем случае он выдает решения, когда Q отличается от оптимального не более, чем на 22%, причем существуют задачи

упаковки блоков, для которыхОценка BFD в худшем слу

чае совпадает с оценкой работы алгоритма BF. Для построения популяции альтернативных решений задачи упаковки блоков применяют также модификацию FF, называемую RFF (refined first fit) — первый подходящий с удалением. Здесь множество X всех блоков разбивается на 4 подмножества и после упорядочивания всех вершин выполняются пробные помещения

вершин в указанные блоки. Оценка RFF:Например, начиная

с одного пустого блока, брать последовательно элементы и для каждого из них искать уже используемый блок с достаточным свободным местом. Если такой блок найден, то поместить в него элемент, иначе взять пустой блок. Это эвристика FF. Если элементы перед распределением отсортировать, то получим эвристику FFD, которая решает задачу лучше, но работает медленнее. А если искать самый заполненный блок, имеющий достаточно места, то это — эвристика BF [186].

Задача упаковки является членом семейства задач группировки, цель которых состоит в разбиении множества элементов Е в непересекающи- еся подмножества Еі, такие что IJ = U, U{ f\ Uj = 0, i ф j. Цель этой задачи — сгруппировать члены множества U в одну или больше (максимум |t/|)rpynny элементов, причем каждый элемент должен находиться только в одной группе. В большинстве задач не все возможные группировки допустимы. Обычно элемент не может быть сгруппирован со всеми возможными подмножествами оставшихся элементов. Цель задачи—оптимизировать целевую функцию, определенную на множестве всех реальных решений.

Опишем группирующий ГА для решения задач одномерной упаковки. Сначала определим целевую функцию, а затем опишем кодировку хромосом и генеттеские операторы. Целевую функцию определим так:

где N — число используемых блоков. Si; — сумма размеров элементов в (заполненном) блоке і, max — размер блока, к константа, ifc > 0. Требуется максимизировать /ьрр. Константа к выражает концентрацию на «хорошо» заполненные блоки в сравнении с менее заполненными. Если увеличиваем к, значит, предпочитаем хорошо заполненные «элитные» блоки в сравнении с набором примерно одинаково заполненных блоков. Увеличение к ведет к предварительной сходимости алгоритма в локальном оптимуме.

Очевидно, что в задаче упаковки блоков следует применять групповой подход со знаниями о решаемой задачи, так как целевая функция зависит

от порядка размещения групп элементов. При этом хромосома (альтернативное решение) будет состоять из двух частей:

•    элементной части (фиксированной длины, равной числу элементов);

•    групповой части (переменной длины).

Например, в хромосоме ACBADC|CBDA часть ACBADC — элементная, а C.BDA — групповая. Элементная часть будет кодировать следующее частичное решение (рис. 8.3):

В элементной части ACBADC хромосомы будет кодироваться решение, в котором первый элемент лежит в блоке А, второй — в блоке С, третий в — В, четвертый в — А, пятый в — D, шестой — в блоке С. Групповая часть хромосомы представляет только группы (блоки в задаче упаковки блоков) и порядок их следования. В рассматриваемой выше хромосоме А = {1,4}, В = {3}, С = {2,6}, D = {5}. И хромосома может быть записана так: {2,6} {3} {5} {1,4}. Далее генетические операторы будут работать с групповой частью хромосом, а элементная часть будет служить только для определения, какие элементы формируют группу. Для задачи упаковки блоков опишем оператор скрещивания с заменой [187]. Его работу покажем на примере. Даны две хромосомы родителя рі : BFECFADCCEDA|ABCDEF (рис. 8.4) МР2'. bcdbcaaddacd | abed (рис. 8.5).

Возьмем групповые части двух хромосом и выберем случайным образом две точки разрыва в каждой:

Процесс формирования первого потомка рз следующий: блоки между точками разрыва в р2 вставляются в рі после первой точки разрыва. Формирование второго потомка происходит аналогично. Если некоторые элементы в Рз встречаются дважды, то они устраняются (рис. 8.6). Получим, что Рз: А Ь с Е (рис. 8.7).

Как видно после устранения элементы 7, 8, 9 не присутствуют в блоках. Для вставки в решение пропущенных элементов (рис. 8.8) используем

FFD-эвристику. Здесь сначала выполняется локальная оптимизация по следующему принципу. Берутся один за другим блоки, уже присутствующие в решении, выполняется проверка, возможно ли заменить элемент в блоке на упущенный элемент таким образом, чтобы общий размер элементов в блоке увеличился без переполнения блока. Если такое возможно, то выполняется замена. Замена имеет две особенности. Во-первых, блок заполняется лучше, чем он был до этого. Во-вторых, уменьшается размер пропущенных элементов, и, следовательно, для них будет легче найти место в блоках, которые уже присутствуют в решении.

Этот процесс продолжается до тех пор, пока такие замены возможны.

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

В заключение отметим, что рассмотренные эвристики совместно с ГА для решения задачи упаковки блоков позволяют находить оптимальные и квазиоптимальные решения.