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

14 сентября 2018
299
Предметная область
Выходные данные
Ключевые слова
Вид публикации Статья
Контактные данные автора публикации ВАНИДОВСКИЙ ВЛАДИСЛАВ АНДРЕЕВИЧ, ЛЕБЕДЕВ ОЛЕГ БОРИСОВИЧ
Ссылка на публикацию в интернете elibrary.ru/item.asp?id=21782579

Аннотация

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