Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу
Досліджено клас генетичних алгоритмів вирішення задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу фіксованої ширини. Наведено результати теоретичного аналізу складності реалізації декодерів MERA та BLF; запропоновані власні реалізації цих декодерів з низкою еври...
Збережено в:
| Опубліковано в: : | Проблеми програмування |
|---|---|
| Дата: | 2016 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут програмних систем НАН України
2016
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/126440 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу / М.М. Глибовець, Н.М. Гулаєва, І.О. Морозов // Проблеми програмування. — 2016. — № 4. — С. 104-116. — Бібліогр.: 17 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862714484736393216 |
|---|---|
| author | Глибовець, М.М. Гулаєва, Н.М. Морозов, І.О. |
| author_facet | Глибовець, М.М. Гулаєва, Н.М. Морозов, І.О. |
| citation_txt | Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу / М.М. Глибовець, Н.М. Гулаєва, І.О. Морозов // Проблеми програмування. — 2016. — № 4. — С. 104-116. — Бібліогр.: 17 назв. — укр. |
| collection | DSpace DC |
| container_title | Проблеми програмування |
| description | Досліджено клас генетичних алгоритмів вирішення задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу фіксованої ширини. Наведено результати теоретичного аналізу складності реалізації декодерів MERA та BLF; запропоновані власні реалізації цих декодерів з низкою евристичних оптимізацій. Запропоновано реалізацію генетичного алгоритму розв’язання задачі упаковки для окремих випадків (із забороною поворотів об’єктів та з поворотами на 90 °). Описано результати тестових випробувань розробленого алгоритму за різних конфігурацій основних параметрів з використанням загальновідомих тестових наборів. Наведено результати порівняння отриманого алгоритму з іншими відомими алгоритмами.
Исследован класс генетических алгоритмов решения задачи двухмерной ортогональной упаковки прямоугольных объектов в полубесконечную полосу фиксированной ширины. Приведены результаты теоретического анализа сложности реализации декодеров MERA и BLF; предложены собственные реализации этих декодеров с рядом эвристических оптимизаций. Предложена реализация генетического алгоритма решения задачи упаковки для отдельных случаев (с запретом поворотов объектов и с поворотами на 90°). Описаны результаты тестирования разработанного алгоритма при разных конфигурациях основных параметров с использованием общеизвестных тестовых наборов. Приведены результаты сравнения полученного алгоритма с другими известными алгоритмами.
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.
|
| first_indexed | 2025-12-07T17:50:53Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-126440 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Ukrainian |
| last_indexed | 2025-12-07T17:50:53Z |
| publishDate | 2016 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Глибовець, М.М. Гулаєва, Н.М. Морозов, І.О. 2017-11-23T16:34:46Z 2017-11-23T16:34:46Z 2016 Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу / М.М. Глибовець, Н.М. Гулаєва, І.О. Морозов // Проблеми програмування. — 2016. — № 4. — С. 104-116. — Бібліогр.: 17 назв. — укр. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/126440 004.023 Досліджено клас генетичних алгоритмів вирішення задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу фіксованої ширини. Наведено результати теоретичного аналізу складності реалізації декодерів MERA та BLF; запропоновані власні реалізації цих декодерів з низкою евристичних оптимізацій. Запропоновано реалізацію генетичного алгоритму розв’язання задачі упаковки для окремих випадків (із забороною поворотів об’єктів та з поворотами на 90 °). Описано результати тестових випробувань розробленого алгоритму за різних конфігурацій основних параметрів з використанням загальновідомих тестових наборів. Наведено результати порівняння отриманого алгоритму з іншими відомими алгоритмами. Исследован класс генетических алгоритмов решения задачи двухмерной ортогональной упаковки прямоугольных объектов в полубесконечную полосу фиксированной ширины. Приведены результаты теоретического анализа сложности реализации декодеров MERA и BLF; предложены собственные реализации этих декодеров с рядом эвристических оптимизаций. Предложена реализация генетического алгоритма решения задачи упаковки для отдельных случаев (с запретом поворотов объектов и с поворотами на 90°). Описаны результаты тестирования разработанного алгоритма при разных конфигурациях основных параметров с использованием общеизвестных тестовых наборов. Приведены результаты сравнения полученного алгоритма с другими известными алгоритмами. 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. uk Інститут програмних систем НАН України Проблеми програмування Прикладні засоби програмування та програмне забезпечення Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу Анализ генетических алгоритмов решения задачи двухмерной ортогональной упаковки прямоугольных объектов в полубесконечную полосу Analysis of Genetic Algorithms for solving the 2D Orthogonal Strip Packing Problem Article published earlier |
| spellingShingle | Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу Глибовець, М.М. Гулаєва, Н.М. Морозов, І.О. Прикладні засоби програмування та програмне забезпечення |
| title | Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу |
| title_alt | Анализ генетических алгоритмов решения задачи двухмерной ортогональной упаковки прямоугольных объектов в полубесконечную полосу Analysis of Genetic Algorithms for solving the 2D Orthogonal Strip Packing Problem |
| title_full | Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу |
| title_fullStr | Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу |
| title_full_unstemmed | Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу |
| title_short | Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу |
| title_sort | аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу |
| topic | Прикладні засоби програмування та програмне забезпечення |
| topic_facet | Прикладні засоби програмування та програмне забезпечення |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/126440 |
| work_keys_str_mv | AT glibovecʹmm analízgenetičnihalgoritmívrozvâzannâzadačídvovimírnoíortogonalʹnoíupakovkiprâmokutnihobêktívunapívneskínčennusmugu AT gulaêvanm analízgenetičnihalgoritmívrozvâzannâzadačídvovimírnoíortogonalʹnoíupakovkiprâmokutnihobêktívunapívneskínčennusmugu AT morozovío analízgenetičnihalgoritmívrozvâzannâzadačídvovimírnoíortogonalʹnoíupakovkiprâmokutnihobêktívunapívneskínčennusmugu AT glibovecʹmm analizgenetičeskihalgoritmovrešeniâzadačidvuhmernoiortogonalʹnoiupakovkiprâmougolʹnyhobʺektovvpolubeskonečnuûpolosu AT gulaêvanm analizgenetičeskihalgoritmovrešeniâzadačidvuhmernoiortogonalʹnoiupakovkiprâmougolʹnyhobʺektovvpolubeskonečnuûpolosu AT morozovío analizgenetičeskihalgoritmovrešeniâzadačidvuhmernoiortogonalʹnoiupakovkiprâmougolʹnyhobʺektovvpolubeskonečnuûpolosu AT glibovecʹmm analysisofgeneticalgorithmsforsolvingthe2dorthogonalstrippackingproblem AT gulaêvanm analysisofgeneticalgorithmsforsolvingthe2dorthogonalstrippackingproblem AT morozovío analysisofgeneticalgorithmsforsolvingthe2dorthogonalstrippackingproblem |