Analysis of Genetic Algorithms for solving the 2D Orthogonal Strip Packing Problem

• Опубліковано в: PROBLEMS IN PROGRAMMING
• Дата: 2018
• Випуск: 4
• Сторінки: 104-116
• ISSN: 1727-4907
• Автори та афіліації: M.M. Glybovets — National University "Kyiv-Mohyla Academy"; N.M. Gulayeva — National University "Kyiv-Mohyla Academy"; I.O. Morozov — National University "Kyiv-Mohyla Academy"
• Ключові слова: задача упаковки-розкрою, packing problem, декодер, упаковка, 0–1 задача пакування рюкзака, екологічна упаковка, генетичний алгоритм, декомпозиція задачі, проблема дедекінда, алгоритми декодування
• Автори: Glybovets, M.M., Gulayeva, N.M., Morozov, I.O.
• Формат: Стаття
• Мова: Українська
• Опубліковано: PROBLEMS IN PROGRAMMING 2018
• Теми: genetic algorithm; packing problem; decoder; MERA; BLF; UDC 004.023
• Онлайн доступ: https://pp.isofts.kiev.ua/index.php/ojs1/article/view/217
• Назва журналу: Problems in programming

A class of genetic algorithms for solving the 2D Strip Packing Problem is investigated. The theoretical analysis of the complexity of implementing decoders MERA and BLF is done. Original implementations of these MERA and BLF decoders enhanced with a number of heuristic optimizations are proposed. Genetic algorithm for solving the 2D Strip Packing Problem for special cases (allowed/forbidden objects rotation by 90°) with the use of MERA/BLF decoders is proposed. Extensive computational experiments with well-known instances are performed to analyze different configurations of basic parameters of proposed genetic algorithm. The comparison of the obtained algorithm with other known algorithms is given.Problems in programming 2016; 4: 104-116