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

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

Метод. Существует два основных метода решения задач оптимизации – точные и приближенные. В исследование рассматривается одно из направлений приближенных алгоритмов – эвристические, которые основаны на предположении о свойствах оптимального решения. В статье рассматривается генетический алгоритма как метод, который позволяет находить такое размещение деталей, которое близко к оптимальному. Для решения задачи задаются малые объекты, которые необходимо разместить без взаимного перекрытия внутри больших объектов так, чтобы целевая функция достигала минимума. Актуальность исследования данной задачи обусловлена ее принадлежностью к классу NP-трудных задач.

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

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

1. Гладков, Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы // ООО Издательская фирма "Физико-математическая литература", 2009, – 320 с.

2. Майрамты М.В. Сравнительный анализ работы некоторых метаэвристических методов при решении задачи упаковки в полубесконечную полосу // Естественные и технические науки: актуальные вопросы : Сборник статей V Международной научно-практической конференции, 2018, С.13-19.

3. A Novel Genetic Algorithm for the Three-Dimensional Bin Packing Problem with Rotations – L.-Y. Chen, C.-H. Wu. https://ieeexplore.ieee.org/document/8029218

4. Валиахметова, Ю.И., Филиппова А.С. Теория оптимального использования ресурсов Л.В. Канторовича в задачах раскроя-упаковки: обзор и история развития методов решения // Вестник Уфимского государственного авиационного технического университета. 2014, Т. 18, № 1(62). – С. 186-197.

5. Sergievskiy M., Syroezhkin S. Use of genetic algorithms for solving problems of optimal cutting // 6th Seminar on Industrial Control Systems: Analysis, Modeling and Computation. ITM Web of Conferences, 2016. https://www.semanticscholar.org/author/M.-Sergievskiy/70370738

6. Майрматы М.В. Анализ некоторых метаэвристических методов при решении задачи упаковки в полубесконечную полосу // XCII Международной научно-практической конференции «Научное сообщество студентов XXI столетия. Технические науки», 2020, С. 23-29.

7. Тимофеева О.П., Чернышева Т.Ю., Корелин О.Н., Волков А.В. Генетический алгоритм в оптимизации трехмерной упаковки блоков в контейнер // Информатика и управление в технических и социальных системах, 2017, [Интернет-ресурс]. https://cyberleninka.ru/article/n/geneticheskiy-algoritm-voptimizatsiitrehmernoy-upakovki-blokov-v-konteyner/viewer (дата обращения 21.06.2025 г.).

8. Файзрахманов Р.И. Конструктивный вероятностный алгоритм для задачи размещения кругов и прямоугольников / Уфа: Изд-во «Вестник УГАТУ». – 2010. – № 4 (39) –С. 132–138.

9. Yuliia P., Kaidan M., Tchaikovskyi I., Pleskanka M. Research of Genetic Algorithms for Increasing the Efficiency of Data Routing// 3rd International Conference on Advanced Information and Communications Technologies (AICT), 2019.

10. Дивеев А.И., Шмалько Е.Ю. Решение задачи двумерной упаковки методом вариационного генетического алгоритма // Cloud of Science, 2016, Т. 3, № 3.С. 380-395.