Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу

Досліджено клас генетичних алгоритмів вирішення задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу фіксованої ширини. Наведено результати теоретичного аналізу складності реалізації декодерів MERA та BLF; запропоновані власні реалізації цих декодерів з низкою еври...

Full description

Saved in:

Bibliographic Details
Published in:	Проблеми програмування
Date:	2016
Main Authors:	Глибовець, М.М., Гулаєва, Н.М., Морозов, І.О.
Format:	Article
Language:	Ukrainian
Published:	Інститут програмних систем НАН України 2016
Subjects:	Прикладні засоби програмування та програмне забезпечення
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/126440
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу / М.М. Глибовець, Н.М. Гулаєва, І.О. Морозов // Проблеми програмування. — 2016. — № 4. — С. 104-116. — Бібліогр.: 17 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-126440
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
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу
spellingShingle	Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу Глибовець, М.М. Гулаєва, Н.М. Морозов, І.О. Прикладні засоби програмування та програмне забезпечення
title_short	Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу
title_full	Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу
title_fullStr	Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу
title_full_unstemmed	Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу
title_sort	аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу
author	Глибовець, М.М. Гулаєва, Н.М. Морозов, І.О.
author_facet	Глибовець, М.М. Гулаєва, Н.М. Морозов, І.О.
topic	Прикладні засоби програмування та програмне забезпечення
topic_facet	Прикладні засоби програмування та програмне забезпечення
publishDate	2016
language	Ukrainian
container_title	Проблеми програмування
publisher	Інститут програмних систем НАН України
format	Article
title_alt	Анализ генетических алгоритмов решения задачи двухмерной ортогональной упаковки прямоугольных объектов в полубесконечную полосу Analysis of Genetic Algorithms for solving the 2D Orthogonal Strip Packing Problem
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.
issn	1727-4907
url	https://nasplib.isofts.kiev.ua/handle/123456789/126440
citation_txt	Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу / М.М. Глибовець, Н.М. Гулаєва, І.О. Морозов // Проблеми програмування. — 2016. — № 4. — С. 104-116. — Бібліогр.: 17 назв. — укр.
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
first_indexed	2025-12-07T17:50:53Z
last_indexed	2025-12-07T17:50:53Z
_version_	1850872800857817088

Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу

Institution

Similar Items