ДВУМЕРНАЯ УПАКОВКА В ПОЛУОГРАНИЧЕННУЮ ПОЛОСУ НА ОСНОВЕ МОДЕЛИРОВАНИЯ АДАПТИВНОГО ПОВЕДЕНИЯ МУРАВЬИНОЙ КОЛОНИИ

Рассматривается задача двумерной упаковки в полуограниченную полосу (1.5 DBP). В качестве структуры данных, несущих информацию об упаковке, используется последовательность номеров прямоугольников, представляющую порядок их укладки. Существенную роль в получении решения играет декодер, осуществляющий укладку прямоугольников по заложенным в нем правилам. Предложены новые способы решения задачи упаковки, использующие математические методы, в которых заложены принципы природных механизмов принятия решений. В качестве базовой структуры декодера выбрана эвристика Floor Сeiling No Rotation (FCNR). Для построения декодера и кодовой последовательности использованы модификации эвристики (FCNR) и метаэвристики, базирующиеся на моделировании адаптивного поведения муравьиной колонии. В отличие от канонической парадигмы муравьиного алгоритма муравьем на графе поиска решений G=(X,U) строится маршрут с разбиением на части и формированием на вершинах, входящих в каждую часть, подграфов, на ребрах которых откладывается феромон. Описывается структура графа поиска решений, процедура поиска решений на графе, способы отложения и испарения феромона. В работе используется циклический (ant-cycle) метод муравьиных систем. Экспериментальные исследования проводились на IBM PC. Временная сложность алгоритма (ВСА), полученная экспериментальным путем, практически совпадает с теоретическими исследованиями и для рассмотренных тестовых задач составляет (ВСА ≈ О(n 2)). По сравнению с существующими алгоритмами достигнуто улучшение результатов на 2-3 %.