АНАЛІЗ ПАРАМЕТРІВ ГЕНЕТИЧНОГО АЛГОРИТМУ РОЗВ’ЯЗАННЯ ДВОВИМІРНОЇ ЗАДАЧІ УПАКОВКИ

Анотація

Задача упаковки є актуальною і зустрічається у багатьох промислових виробництвах. Вона належить до класу NP-складних задач, тому використання точного перебірного алгоритму можливе лише для задач невеликої розмірності. Метаевристичні методи є популярним інструментом для наближеного вирішення складних комбінаторних оптимізаційних задач. У статті розглядається розв’язання задачі упаковки прямокутників у напівнескінченну смугу фіксованої ширини за допомогою генетичного алгоритму. Метою статті є дослідження впливу генетичних операторів схрещування та відбору на ефективність роботи алгоритму. У роботі наводиться постановка задачі, представлено генетичні оператори кросинговеру та відбору, які використовуються в алгоритмі. Розв’язання задачі упаковки ділиться на два етапи: визначення за допомогою генетичного алгоритму перестановки для послідовності пакування прямокутних елементів та застосування алгоритму декодування для їх розміщення у смузі. В якості декодеру використовувся алгоритм BLF. Проведено обчислювальний експеримент на тестових прикладах, відомих з літературних джерел, а також на двох згенерованих наборах прямокутників. Всі тестові задачі, що використовуються в цьому дослідженні, мають оптимальне рішення з мінімально допустимою довжиною зайнятої частини смуги. Програму реалізовано за допомогою мови програмування Python та пакету Deap. Аналіз результатів експериментів показав, що найкращі рішення задачі упаковки прямокутників у напівнескінченну смугу було отримано при використанні в генетичному алгоритмі оператора схрещування PMX та оператора турнірного відбору. Генетичний алгоритм показав найгірший результат при застосуванні оператора кросинговеру UPMX та відбору за правилом рулетки.