Важное место в современной комбинаторной оптимизации занимают задачи раскроя-упаковки (ЗРУ), привлекая внимание многих ученых как в России, так и за рубежом [1, 2]. Интерес к ЗРУ объясняется, в частности, их большой практической значимостью. Как правило, приложения этих задач относятся к материалоемким производствам, где одним из основных факторов снижения себестоимости выпускаемой продукции является рациональное использование ресурсов.

Существует множество разновидностей этой задачи: двумерная упаковка, двумерная упаковка в полуограниченную полосу,линейная упаковка,упаковка по весу, упаковка по стоимости и другие. Задачи упаковки могут применяться в области оптимального заполнения контейнеров, загрузки грузовиков с ограничением по весу, созданием резервных копий на съемных носителях и т.д. На сегодняшний день для решения ЗРУ используются различные оптимизационные алгоритмы [3–6].

В работе рассматривается задача упаковки полуограниченной полосы (1.5 Dimensional Bin Packing, 1.5DBP). Термин 1.5D ввел в 1980 г. A. Hinxman. Задан набор прямоугольников. Дан один большой объект (называемый полосой), чья ширина W задана, а длина L – искомое значение переменной. Цель состоит в том, чтобы минимизировать длину L полосы, содержащей прямоугольники, помещенные в полосу без их взаимного перекрытия.

Известно, что ЗРУ относятся к классу NP-трудных задач комбинаторной оптимизации. Для их решения российскими и зарубежными учеными разработано большое количество методов и алгоритмов, различающихся как областью применения, так и эксплуатационными свойствами. Методы решения ЗРУ принято разделять на две большие группы: точные и приближенные. Поскольку точные методы не позволяют решать задачи упаковки большой размерности за полиномиальное время, во многих работах большое внимание уделяется разработке приближенных и эвристических методов [3–11]. Приближенные методы не гарантируют нахождения глобального оптимума ЗРУ и ориентированы на получение некоторого приемлемого или допустимого решения [8–11]. Для практических задач значимая потеря точности не всегда является приемлемой. В связи с этим большое значение приобретают разработка и исследование методов решения ЗРУ, в том числе и методов локального поиска, обеспечивающих высокое качество решения. Результатом непрекращающегося поиска наиболее эффективных методов упаковки стало использование бионических методов и алгоритмов. Одним из новых направлений таких методов являются мультиагентные методы интеллектуальной оптимизации, базирующиеся на моделировании коллективного интеллекта биологических систем [12]. К таким методам можно отнести генетические и роевые алгоритмы [12–14]. В работе излагается метод решения задачи упаковки полуограниченной полосы, основанный на моделях роевого интеллекта.

Постановка задачи

Задача прямоугольной упаковки в полосу (1.5 Dimensional Bin Packing, 1.5DBP) состоит в следующем. Исходная информация задается набором данных:H – ширина полубесконечной полосы; R = { r_i|i=1, 2, …, m} – набор прямоугольников, где m – количество прямоугольников; W = {w_i|i=1, 2, …, m} – вектор ширины прямоугольников; L = {l_i|i=1, 2, …, m} – вектор длин прямоугольников. Вводится прямоугольная система координат XOY, у которой оси OX и OY совпадают, соответственно, с нижней неограниченной и боковой сторонами полосы. Решение задачи представляется в виде набора элементов <X, Y>, где X = {x_i|i=1, 2, …, m), Y={y_i|i=1, 2, …, m) – векторы координат прямоугольников. (х_i, у_i) – координаты нижнего левого угла прямоугольника, соответственно, по оси OX и OY. Набор элементов <X, Y> называется допустимой прямоугольной упаковкой, если выполнены следующие условия:

– стороны прямоугольников параллельны граням полосы;

– прямоугольники не перекрывают друг друга;

– прямоугольники не выходят за границы полосы.

Анализ существующих методов и алгоритмов упаковки в блоки [1–11] показал, что в их основе лежит процедура упорядочения исходного списка элементов, последовательно распределяемых по блокам. Другими словами, в качестве структуры данных, несущих информацию об упаковке, чаще всего используется последовательность номеров прямоугольников, представляющая порядок их укладки, которая называется приоритетным списком. Приоритетный список – это кодированное решение, в терминах
генетического алгоритма – хромосома. Приоритетный список является косвенной схемой кодирования решения. Фактически приоритетный список является интерпретацией решения. Существенную роль в общем процессе нахождения решения играет декодер. Переход от приоритетного списка к решению производится с помощью декодера. Декодер – оператор, осуществляющий укладку прямоугольников по заложенным в нем правилам, позволяющий перейти от косвенной (числовой) схемы кодирования решения задачи к фенотипу.

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

Исходя из вышеизложенного, представляет интерес разработка новых поисковых алгоритмов для решения ЗРУ на базе эффективных метаэвристик формирования приоритетных списков и принципов их декодирования.

Оператор декодирования

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

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

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

Шельфовые рассматривают сразу несколько шельфов (полок) и распределяют по ним прямоугольники.

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

Next fit level – открывается следующий уровень, предыдущий закрывается, и его больше не рассматриваем;

First fit level – на каждом шаге алгоритма просматривается каждый уровень, начиная с самого нижнего, и прямоугольник упаковывается на первый подходящий, на котором достаточно места;

Best fit level – на каждом шаге алгоритма просматриваются все уровни и выбирается наиболее подходящий – тот, на котором после упаковки останется минимум места.

Модификацией алгоритма Best fit level является алгоритм Floor ceiling no rotation (FCNR). Упаковка осуществляется блоками. Каждый блок ограничен двумя уровнями. Нижний уровень блока – «пол», верхний уровень блока – «потолок». Пока есть возможность, прямоугольники пакуются на «пол» слева направо. Когда место заканчивается, предпринимается попытка упаковать на «потолок» справа налево; если нет места на потолке, то только тогда начинается формирование нового блока. В соответствии с эвристикой BFDH на каждом шаге просматриваются все уровни – сначала «пол», затем «потолок» – на наличие наиболее подходящего места. Метод удачно упаковывает по «потолкам» самые мелкие прямоугольники.

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

На первом этапе формируется код решения – приоритетный список прямоугольников.

На втором этапе оператором декодирования производится в соответствии с эвристикой «пол–потолок» последовательное заполнение блоков начиная с первого. При заполнении блока сначала заполняется нижний уровень, а затем верхний. Заполнение уровней производится в порядке с приоритетной последовательностью, полученной на первом этапе.

На третьем этапе в каждом блоке прямоугольники сортируются по невозрастанию высоты: на уровне «пол» слева направо; на уровне «потолок» справа налево.

На четвертом этапе заполненные уровни в каждом блоке сближаются на минимально допустимое расстояние, исключающее наложение прямоугольников.

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

Гибридный алгоритм решения задачи упаковки в полуограниченную полосу

Для решения ЗРУ предлагается композитная архитектура многоагентной системы бионического поиска на основе интеграции роевого интеллекта и генетической эволюции [15, 16].

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

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

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

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

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

Метод роя частиц (particle swarm optimization, PSO) является методом стохастической оптимизации, в чем-то схожим с эволюционными алгоритмами. Этот метод моделирует не эволюцию, а ройное и стайное поведение животных [6]. В отличие от популяционных методов PSO работает с одной статической популяцией, члены которой постепенно улучшаются с появлением информации о пространстве поиска. Данный метод представляет собой вид направленной мутации (directed mutation). Решения в PSO мутируют в направлении наилучших найденных решений. Частицы никогда не умирают (так как нет селекции).

Рассмотрим каноническую парадигму метода PSO, разработанную Д. Кеннеди и Р. Эберхартом [13]. Метод PSO работает в многомерных, вещественных, метрических пространствах. Многомерное пространство поиска населяется роем частиц [14]. Каждой частице соответствует некоторое решение, определяемое позицией в пространстве решений. Основу поведения роя P = { p_i|i=1, 2, …, n} частиц составляет самоорганизация, обеспечивающая достижение общих целей роя на основе низкоуровневого взаимодействия. Каждая частица p_i размещается в позиции x_i многомерного пространства поиска, связана и может взаимодействовать со всеми частицами роя, она тяготеет к лучшему решению роя. Процесс поиска решений итерационный и заключается в перемещении частиц на каждой итерации в новые позиции.

По аналогии с эволюционными стратегиями рой частиц можно трактовать как популяцию, а частицу как индивида. Это дает возможность построения гибридной структуры поиска решения, основанного на сочетании генетического поиска с методами роя частиц [16, 18]. Связующим звеном такого подхода является структура данных, описывающая решение задачи. В генетических алгоритмах генотип решения представляется в виде хромосомы. При решении комбинаторных задач гены в хромосомах имеют, как правило, дискретные, целочисленные значения. Положение частицы в пространстве поиска является эквивалентом генотипа в эволюционных алгоритмах. Если в качестве описания состояния частицы используется хромосома, то число параметров, определяющих положение частицы в пространстве решений, должно быть равным числу генов в хромосоме. Значение каждого гена откладывается на соответствующей оси пространства решений. В этом случае возникают некоторые требования к структуре хромосомы, значениям генов и пространству поиска.

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

В отличие от канонической парадигмы роя частиц гибридные алгоритмы в качестве моделей для представления решений используют широкий диапазон графовых структур (маршрут, дерево, двудольный граф, паросочетание, внутренне устойчивое множество и т.д.) [8–11]. Это не позволяет напрямую использовать каноническую парадигму роя частиц (например, задача направленной мутации одного дерева в направлении другого, с формальной точки зрения, является весьма нетривиальной).

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

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

Аффинное пространство поиска

Пусть имеется линейное векторное пространство (ЛВП), элементами которого являются n-мерные точки. Каждым любым двум точкам p и q этого пространства однозначным образом сопоставим единственную упорядоченную пару этих точек, которую в дальнейшем будем называть геометрическим вектором (вектором):

p, q ∈ V(p, q) – геометрический вектор (упорядоченная пара).

Совокупность всех точек ЛВП, пополненная геометрическими векторами, называют точечно-векторным, или аффинным пространством. Аффинное пространство является n-мерным, если соответствующее ЛВП также является n-мерным.

Аффинно-релаксационная модель (АРМ) роя частиц – это граф, вершины которого соответствуют позициям роя частиц, а дуги аффинным связям между позициями (точками) в аффинном пространстве. Аффинность – мера близости двух агентов (частиц). На каждой итерации каждый агент p_i переходит в аффинном пространстве в новое состояние (позицию), при котором вес аффинной связи между агентом p_i и базовым (лучшим) агентом p_* уменьшается. Переход агентаp_i в новую позицию x_i( t+1) из x_i(t) осуществляется с помощью релаксационной процедуры.

Специальная релаксационная процедура перехода зависит от вида структуры данных (хромосомы): вектор, матрица, дерево и их совокупности, являющейся интерпретацией решений.

Лучшие частицы (и их позиции) с точки зрения целевой функции объявляются центром притяжения. Векторы перемещения всех частиц в аффинном пространстве устремляются к этим центрам.

Переход возможен с учетом степени близости к одному базовому элементу либо к группе соседних элементов и с учетом вероятности перехода в новое состояние.

Каждую хромосому, описывающую i-е решение популяции, обозначим какH_i(t)={g_il|l=1, 2, …, n}. Позиция x_i(t) соответствует решению, задаваемому хромосомой H_i(t), то есть x_i (t)=H_i(t)={ g_il|l=1, 2, …, n}. Число осей в пространстве решений равно числу n генов в хромосомеН_i(t). Точками отсчета на каждой оси l являются дискретные целочисленные значения генов.

Принципы кодирования хромосом и механизмы перемещения частиц
в аффинном пространстве

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

Пространство поиска включает число осей, равное числу элементов списка (число генов в хромосоме). Каждая ось (номер оси) соответствует номеру позиции элемента в списке. Точками отсчета на оси являются значения элементов списка. Расположены точки счета на оси в одном заранее выбранном порядке, принятом в качестве базового.

Хромосома, описывающая решение, имеет следующую структуру: Н_i(t)={g_il(t)|l=1, 2, …, n}. Значение гена g_il(t) равно значению соответствующего элемента списка M_i.

Пусть в качестве базового списка используется список B=<1, 7, 21, 4, 8, 18>. |B|=6. Пространство поиска X включает 6 осей: X₁–X₆, в соответствии с числом элементов списка. Каждая ось соответствует позиции списка. Точками отсчета x_ij на оси X_i=<x_ij|j=1, 2, …, 6> являются упорядоченные значения элементов списка В, X_i=<x_i1=1,x_i2 =7, x_i3=21, x_i4=4, x_i5=8, x_i6 =18>=<1, 7, 21, 4, 8, 18>.

Например , список M_i=<21, 8, 7, 1, 8, 4, 18> представляется в виде позиции Н_i={x_13, x_25, x_32, x_41, x_54, x₆₆}.

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

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

В процессе поиска методом роя частиц каждая частица перемещается в новую позицию [14]. Новая позиция в канонической парадигме роя частиц определяется как

x_i (t+1)=x_i(t)+ v_i(t+1),                    (1)

где v_i(t+1) – скорость перемещения частицы из позиции x_i(t) в позицию x_i(t+1). Начальное состояние определяется как x_i(0), v_i (0) [1].

Приведенная формула представлена в векторной форме. Для отдельного измерения j пространства поиска формула примет вид

x_ij (t+1)=x_ij(t)+ v_ij(t+1),                (2)

где x_ij(t) – позиция частицыp_i в измерении j; v_ij(t+1) – скорость частицы p_i в измерении j.

Введем обозначения:

x_i (t) – текущая позиция частицы, f_i(t) – значение целевой функции частицы p_i в позиции x_i(t) ;

x^* _i (t) – лучшая позиция частицы p_i, которую она посещала с начала первой итерации, а f^*_i(t) – значение целевой функции частицы p_i в этой позиции (лучшее значение с момента старта жизненного цикла частицы p_i);

x^* (t) – позиция частицы роя с лучшим значением целевой функции f^*(t) среди частиц роя в момент времени t.

Тогда скорость частицы p_i на шаге (t+1) в измерении j вычисляется как

v_ij (t+1) = w∙v_ij(t)+k₁∙rnd(0,1)∙(x^*_ij(t)–x_ij(t))+k₂∙rnd(0,1)∙(x_j(t)–x_ij(t)),              (3)

где rnd(0,1) – случайное число на интервале (0,1); ( w, k₁, k₂) – некоторые коэффициенты.

Скорость v_i(t+1) рассматривается как средство изменения решения.

В отличие от канонического метода роя частиц в рассматриваемом случае скорость v_i(t+1) не может быть представлена в виде аналитического выражения с целочисленными дискретными значениями переменных. Если в качестве позиции используется хромосома, то число параметров, определяющих положение частицы в пространстве решений (позицию), должно быть равно числу генов в хромосоме. Значение каждого гена откладывается на соответствующей оси пространства решений. В этом случае возникают некоторые требования к структуре хромосомы и значениям генов. Значения генов должны быть дискретными и не зависеть друг от друга. В качестве аналога скорости v_i(t+1) выступает оператор направленной мутации (ОНМ), суть которого в изменении целочисленных значений генов в хромосоме Н_i(t). Перемещение частицы p_i в новую позицию означает переход от хромосомы Н_i(t) к новой – Н_i(t+1) c новыми целочисленными значениями генов g_il. В работе предлагается подход к построению структур и принципов кодирования гомологичных хромосом (имеющих одинаковый набор генов), обеспечивающих их гомологичность и возможность одновременного использования в генетическом алгоритме и в алгоритме на основе роя частиц, полученными после применения ОНМ.

По аналогии с каноническим методом роя частиц позицию x^*_i(t) будем называть когнитивным центром притяжения, а позицию x^*(t ) – социальным центром притяжения. Когнитивный центр выступает в роли индивидуальной памяти о наиболее оптимальных позициях данной частицы. Благодаря социальному центру частица имеет возможность передвигаться в оптимальные позиции, найденные соседними частицами.

Как уже указывалось выше, позиции задаются хромосомами. Позициям x (t), x_i(t), x^*_i(t) , x^с_i(t) соответствуют хромосомы Н^*(t)={g^*_l(t)||l=1, 2, …, n_l}, Н_i(t)={g_il(t)|l=1, 2, …, n_l}, Н^*_i(t)={g^*_il(t)|l=1, 2, …, n_l} Н^с_i(t={g^с_il(t)|l=1, 2, …, n_i}.

В качестве оценки степени близости между двумя позициями x_i(t) и x_z( t) будем использовать величину S_iz расстояния (аффинной связи) между хромосомами Н_i(t) и Н_z( t).

Целью перемещения хромосомы Н_i(t) в направлении хромосомы Н_z(t) является сокращение расстояния между ними.

Для учета одновременного тяготения частицы p_i к лучшей к позиции x^*(t) среди частиц роя в момент времени t и к лучшей позиции x^* _i(t) частицы p_i, которую она посещала с начала первой итерации, формируется виртуальный центр (позиция) притяжения x^c _i(t) частицы p_i. Формирование виртуальной позиции x^c_i(t) осуществляется путем применения процедурывиртуального перемещения из позицииx^*_i(t) в виртуальную позицию x^c_i(t) по направлению к позиции x^*(t). После определения центра притяжения x^c _i(t) частица p_i перемещается в направлении виртуальной позиции x^c_i(t) из позицииx_i(t) в позицию x_i(t+1). После перемещения частицы p_i в новую позицию x_i(t+1) виртуальная позиция x^c _i(t) исключается.

Локальная цель перемещения частицы p_i – достижение ею позиции с наилучшим значением целевой функции. Глобальная цель роя частиц – формирование оптимального решения задачи.

Суть процедуры перемещения, реализуемой ОНМ в алгоритме роя частиц, заключается в изменении взаимного расположения элементов в списке (генов в хромосоме). Частица p_i перемещается из позиции Н_i(t) в направлении позиции в новую позицию Н_i(t+1) c новым взаимным расположением элементов в списке.

Введем характеристику, отражающую степень различия между позициямиН_i(t) и H_z( t). Для этого произведем сравнение взаимного расположения элементов у всех возможных пар генов в сравниваемых позициях Н _i(t) и H_z(t). Пусть S_iz(t) – число пар, у которых взаимное расположение элементов в сравниваемых позицияхН_i(t) и H_z( t) не совпадает.

Чем больше S_iz(t), тем больше различие междуН_i(t) и H_z(t), и наоборот, чем меньше S_iz( t), тем различие меньше. Тяготение частицы p_i в позиции Н_i(t) к лучшей позиции H_z(t) выражается в стремлении уменьшения различия между Н_i( t) и H_z(t), то есть уменьшения показателя S_iz(t). Будем считать, чем меньше различие между Н_i(t) и H_z(t), тем ближе позицияН_i(t) к лучшей позиции H_z(t).

Модификация позиции Н_i(t), то есть переход к позиции Н_i(t+1), производится путем выборочных групповых парных перестановок соседних элементов в позиции Н_i(t). Модификация позиции Н_i(t) выполняется за два такта.

На первом такте формируется множество D₁ непересекающихся пар элементов в позиции Н_i(t), таких, у которых индекс l – нечетное число:P₁={(g_il(t), g_{il + 1}(t))|l=1, 3, 5, …}. Подсчитывается число пар S_iz(t) в множестве D₁, у которых взаимное расположение элементов пары в позиции Н_i(t) не совпадает с взаимным расположением этих элементов в позиции H_z( t). Принимается решение о перестановке элементов каждой такой пары в позиции Н_i(t), вычисляются показатели S_ik(t) и осуществляется модификация Н_i(t).

На втором такте формируется множество D₂ непересекающихся пар элементов в позиции Н _i(t), у которых индекс l – четное число: D₂={(g_il(t ), g_il+1(t))|l=2, 4, 6, …}. Подсчитывается число пар S_iz(t) множества D ₂, у которых взаимное расположение элементов пары в позиции Н_i(t) не совпадает с взаимным расположением этих элементов в позиции H_z(t). Принимается решение о перестановке элементов каждой такой пары в позицииН_i(t), вычисляются показателиS_ik(t+1) и формируется позиция Н _i(t+1).

Перестановка выполняется с вероятностью Р=α S_iz(t)/n, где n – число пар множества D.

Отметим, что изменение взаимного расположения пары соседних элементов в позиции не приводит к изменению относительного расположения каждого элемента пары с остальными элементами позиции, а также к изменению взаимного расположения остальных элементов друг относительно друга.

Пример работы процедуры перемещения.

Пусть позиции Н_i(t) иH_z(t) имеют вид:H_i(t)={1, 3, 2, 10, 8}, H_z(t)={1, 10, 2, 3, 8}. S_iz(t)=2.

На первом такте шага t формируется множество пар D ₁=(1, 3), (2, 10). Взаимное расположение элементов пары (1, 3) в Н_i(t ) и H_z(t) совпадают, пары (2, 10) – нет. Отсюда S_iz(t₁)=1. Переставляются в H_i(t) местами элементы пары (2, 10). H_i(t₁)={1, 3, 10, 2, 8}.

На втором такте формируется множество пар D₂=(3, 10), (2, 8). Взаимное расположение элементов пары (2, 8) в Н_i(t₁) иH_z(t) совпадают, пары (3, 10) – нет. Отсюда S_iz(t₂)=1. Переставляются в H_i(t₁) местами элементы пары (3,10). H_i(t+1)={1, 10, 3, 2, 8_,} . S_iz(t+1)=1.

Механизмы улучшения упаковки блоков

Сформируем для прямоугольников R_k={ r_ki|i=1, 2, …, m} одного блока b_k полный неориентированный граф с взвешенными ребрами G_k(X_k, U_k), где X_k – множество вершин, соответствующих множеству прямоугольников R_k, u_kijÎU_k – ребро, связывающее вершины x_ki и x_kj. Вес ребра φ(u_kij) равен сумме высот связываемых им вершин: φ(u_kij)=(l_ki+ l_kj)_. Определяются множества прямоугольников X_1k и X_2k, расположенных соответственно на верхнем и нижнем уровнях блока b_k, X_1k È X _2k =X_k.

Пусть l^*_k1 и l⁰_k1 – соответственно максимальная и минимальная высота прямоугольников, входящих в подмножество R_k1. Соответственно,l^*_k2 и l⁰_k2 – максимальная и минимальная высота прямоугольников, входящих в подмножество R_k2. Минимально возможная высота F^k блока b_k, образованного двумя уровнями R_k1 и R_k2, определится как большее из двух величин (l^*_k1+l⁰_k1) и (l^*_k2 +l ⁰_k2):

F^k = max((l^*_k1+h⁰_k1), (l^*_k2+l⁰ _k2)).                (4)

Зададим ограничения на взаимное расположение прямоугольников по вертикали в одном блоке с помощью двудольного графа ограничений D_k(X_1kÈX_2k,E_k), где X_1k и X_{2 k} – множества вершин, соответствующих множествам прямоугольников, расположенных на нижнем и верхнем уровнях блока соответственно; E_k – множество ориентированных ребер, связывающих вершины множества X_1k с вершинами множества X_{2 k}. Наличие ребра e_kij означает, что прямоугольник x_kj Î X_k2 должен располагаться выше x_kiÎX_k1, x_kjÎX_k2.

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

На рисунке 1 показано исходное расположение прямоугольников в блоке, полученное после работы гибридного алгоритма и выполнения процедуры сближения. На этом же рисунке представлен двудольный граф для данного расположения прямоугольников. Минимально возможная высота блока в соответствии с формулой (4) определяется как

F^k =φ(u₅₄)=(l₅ + l ₄).                          (5)

Состояние, при котором два прямоугольника соприкасаются друг с другом по вертикали, будем называть конфликтом. На рисунке 1 в состоянии конфликта находятся прямоугольники 5 и 3. Высота блока определяется размерами этих прямоугольников: φ(u ₅₃)=(l ₅ +l ₃). Поскольку F^k<φ(u ₅₃), существует потенциальная возможность улучшить решения. Для этого необходимо ликвидировать конфликт между прямоугольниками 5 и 3. Ликвидация конфликта осуществляется путем парных перестановок. Перестановка называется реализуемой, если после ее выполнения суммарная ширина прямоугольников, располагающихся как на верхнем, так и на нижнем уровнях, не превосходит ширины полосы, не появляются новые конфликты и наложения прямоугольников. Затем путем последовательного просмотра реализуемых перестановок отыскивается та, при которой ликвидируется конфликт. Отметим, что в общем случае такой перестановки может и не быть. Для нашего примера: перестановки (3:6), (3:7) нереализуемы, а перестановка (1:8) реализуема. На рисунке 2 показано расположение прямоугольников после обмена расположением прямоугольников 1 и 8.

После смены расположения прямоугольников 1 и 8 появляется возможность дополнительного сближения, что приводит к уменьшению высоты блока (рис. 3).

Временная сложность этого алгоритма определяется как O(n ²).

Улучшающий алгоритм решения, полученного алгоритмом упаковки на основе гибридного алгоритма [14], формулируется следующим образом.

1. В качестве исходных данных служит множество блоков B={ b_k|k=1, 2, …, n_b }, сформированных гибридным алгоритмом и процедурой сужения. Для каждого блока b_k задано начальное расположение Ω _k уложенных в нем прямоугольников.

2. k=1 (k – номер блока).

3. Выбирается блок b_k. Определяется множество прямоугольников X_1k и X_2k, расположенных соответственно на верхнем и нижнем уровнях блока b_k.

4. Строится полный граф G_k(X_k, U_k).

5. Строится двудольный граф ограничений D_k(X_1kÈX_2k, E_k) для расположения Ω _k в блоке b_k.

6. Рассчитывается минимально возможная высота F^k блока b_k в соответствии с формулой (3).

7. Отыскивается пара прямоугольников α=(r_ki,r_kj), r_kiÎX_1k1 и r_kjÎ X_k2, находящихся в конфликте друг с другом, такая, что F^k <φ(u_kij)=(l_ki+ l_kj) Если такой нет, то переход к пункту 9, иначе переход к пункту 8.