Статья

Название статьи ДВУМЕРНАЯ УПАКОВКА В ПОЛУОГРАНИЧЕННУЮ ПОЛОСУ НА ОСНОВЕ МОДЕЛИРОВАНИЯ АДАПТИВНОГО ПОВЕДЕНИЯ МУРАВЬИНОЙ КОЛОНИИ
Автор В.А. Ванидовский, O.Б. Лебедев
Рубрика РАЗДЕЛ I. ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ, ГЕНЕТИЧЕСКИЕ И БИОНИЧЕСКИЕ АЛГОРИТМЫ
Месяц, год 07, 2014
Индекс УДК 681.325
DOI
Аннотация Рассматривается задача двумерной упаковки в полуограниченную полосу (1.5 DBP). В качестве структуры данных, несущих информацию об упаковке, используется последовательность номеров прямоугольников, представляющую порядок их укладки. Существенную роль в получении решения играет декодер, осуществляющий укладку прямоугольников по заложенным в нем правилам. Предложены новые способы решения задачи упаковки, использующие математические методы, в которых заложены принципы природных механизмов принятия решений. В качестве базовой структуры декодера выбрана эвристика Floor Сeiling No Rotation (FCNR). Для построения декодера и кодовой последовательности использованы модификации эвристики (FCNR) и метаэвристики, базирующиеся на моделировании адаптивного поведения муравьиной колонии. В отличие от канонической парадигмы муравьиного алгоритма муравьем на графе поиска решений G=(X,U) строится маршрут с разбиением на части и формированием на вершинах, входящих в каждую часть, подграфов, на ребрах которых откладывается феромон. Описывается структура графа поиска решений, процедура поиска решений на графе, способы отложения и испарения феромона. В работе используется циклический (ant-cycle) метод муравьиных систем. Экспериментальные исследования проводились на IBM PC. Временная сложность алгоритма (ВСА), полученная экспериментальным путем, практически совпадает с теоретическими исследованиями и для рассмотренных тестовых задач составляет (ВСА ≈ (n2)). По сравнению с существующими алгоритмами достигнуто улучшение результатов на 2–3 %.

Скачать в PDF

Ключевые слова Двумерная упаковка в полуограниченную полосу; роевой интеллект; муравьиная колония; адаптивное поведение; оптимизация.
Библиографический список 1. Bischoff E.E. and Wдscher G. Cutting and packing. European Journal of Operational Research. – 1995. – No 84. – P. 503-505.
2. Ross P., Marin-Blazquez J.G., Schulenburg, S. and Hart E. Learning a Procedure That Can Solve Hard Bin-Packing Problems: A New GA-Based Approach to Hyper-heurstics, Proceeding of the Genetic and Evolutionary Computation Conference, GECCO 2003, Chicargo, Illinois, USA, 2003. – P. 1295-1306.
3. Потарусов Р.В., Курейчик В.М. Проблема одномерной упаковки элементов // Известия ТРТУ. – 2006. – № 8 (66). – C. 88-93.
4. Курейчик В.М. лгоритмы одномерной упаковки элементов // Известия ЮФУ. Технические науки. – 2013. – № 7 (144). – С. 8-11.
5. Валеева А.Ф., Аглиуллин М.Н. Моделирование прямоугольной упаковки на базе метаэвристики муравьиной колонии // Межвуз. науч. сб. «Принятие решений в условиях неопределенности». – Уфа, 2005. – Вып. 2. – С. 55-63.
6. Levine J. and Ducatelle F. Ant Colony Optimization and Local Search for Bin Packing and Cutting Stock Problems. Centre for Intelligent Systems and their Applications, School of Informatics, University of Edinburgh, 2003.
7. Тимофеева О.П., Соколова Э.С., Милов К.В. Генетический алгоритм в оптимизации упаковки контейнеров // Труды НГТУ. Информатика и системы управления. – 2013. – № 4 (101). – С. 167-172.
8. Лебедев О.Б., Зорин В.Ю. Упаковка на основе метода муравьиной колонии // Известия ЮФУ. Технические науки. – 2010. – № 12 (113). – С. 25-30.
9. Лебедев В.Б., Лебедев О.Б. Роевой интеллект на основе интеграции моделей адаптивного поведения муравьиной и пчелиной колоний // Известия ЮФУ. Технические науки. – 2013. – № 7 (144). – С. 41-47.
10. Лебедев Б.К., Лебедев В.Б. Оптимизация методом кристаллизации россыпи альтернатив // Известия ЮФУ. Технические науки. – 2013. – № 7 (144). – С. 11-17.
11. Лебедев Б.К., С Моделирование адаптивного поведения муравьиной колонии при поиске решений, интерпретируемых деревьями // Известия ЮФУ. Технические науки. – 2012. – № 7 (132). – С. 27-35.
12. Dorigo M. and Stьtzle T. Ant Colony Optimization. MIT Press, Cambridge, MA, 2004.
13. Лебедев О.Б. Модели адаптивного поведения муравьиной колонии в задачах проектирования. – Таганрог: Изд-во ЮФУ, 2013.
14. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Разбиение на основе моделирования адаптивного поведения биологических систем // Нейрокомпьютеры: разработка, применение. – 2010. – № 2. – С. 28-34. Модели адаптивного поведения муравьиной колонии в задачах проектирования. – Таганрог: Изд-во ЮФУ, 2013.

Comments are closed.