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

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. Ge...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2018
Автори:	Glybovets, M.M., Gulayeva, N.M., Morozov, I.O.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут програмних систем НАН України 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
Завантажити файл:

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-217
record_format	ojs
resource_txt_mv	ppisoftskievua/dc/c640751b84bddc9d741ef3d58ecc27dc.pdf
spelling	pp_isofts_kiev_ua-article-2172024-04-28T11:59:07Z Analysis of Genetic Algorithms for solving the 2D Orthogonal Strip Packing Problem Анализ генетических алгоритмов решения задачи двухмерной ортогональной упаковки прямоугольных объектов в полубесконечную полосу Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу Glybovets, M.M. Gulayeva, N.M. Morozov, I.O. genetic algorithm; packing problem; decoder; MERA; BLF UDC 004.023 генетический алгоритм; задача упаковки-кроя; декодер; MERA; BLF УДК 004.023 генетичний алгоритм; задача упаковки-розкрою; декодер; Packing problem; MERA; BLF УДК 004.023 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 Исследован класс генетических алгоритмов решения задачи двухмерной ортогональной упаковки прямоугольных объектов в полубесконечную полосу фиксированной ширины. Приведены результаты теоретического анализа сложности реализации декодеров MERA и BLF; предложены собственные реализации этих декодеров с рядом эвристических оптимизаций. Предложена реализация генетического алгоритма решения задачи упаковки для отдельных случаев (с запретом поворотов объектов и с поворотами на 90°). Описаны результаты тестирования разработанного алгоритма при разных конфигурациях основных параметров с использованием общеизвестных тестовых наборов. Приведены результаты сравнения полученного алгоритма с другими известными алгоритмами.Problems in programming 2016; 4: 104-116 Досліджено клас генетичних алгоритмів вирішення задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу фіксованої ширини. Наведено результати теоретичного аналізу складності реалізації декодерів MERA та BLF; запропоновані власні реалізації цих декодерівз низкою евристичних оптимізацій. Запропоновано реалізацію генетичного алгоритму розв’язання задачі упаковки для окремих випадків (із забороною поворотів об’єктів та з поворотами на 90 °). Описано результати тестових випробувань розробленого алгоритму за різних конфігурацій основнихпараметрів з використанням загальновідомих тестових наборів. Наведено результати порівняння отриманого алгоритму з іншими відомими алгоритмами.Problems in programming 2016; 4: 104-116 Інститут програмних систем НАН України 2018-07-03 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/217 10.15407/pp2016.04.104 PROBLEMS IN PROGRAMMING; No 4 (2016); 104-116 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2016); 104-116 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2016); 104-116 1727-4907 10.15407/pp2016.04 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/217/209 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2024-04-28T11:59:07Z
collection	OJS
language	Ukrainian
topic	genetic algorithm packing problem decoder MERA BLF UDC 004.023
spellingShingle	genetic algorithm packing problem decoder MERA BLF UDC 004.023 Glybovets, M.M. Gulayeva, N.M. Morozov, I.O. Analysis of Genetic Algorithms for solving the 2D Orthogonal Strip Packing Problem
topic_facet	genetic algorithm packing problem decoder MERA BLF UDC 004.023 генетический алгоритм задача упаковки-кроя декодер MERA BLF УДК 004.023 генетичний алгоритм задача упаковки-розкрою декодер Packing problem MERA BLF УДК 004.023
format	Article
author	Glybovets, M.M. Gulayeva, N.M. Morozov, I.O.
author_facet	Glybovets, M.M. Gulayeva, N.M. Morozov, I.O.
author_sort	Glybovets, M.M.
title	Analysis of Genetic Algorithms for solving the 2D Orthogonal Strip Packing Problem
title_short	Analysis of Genetic Algorithms for solving the 2D Orthogonal Strip Packing Problem
title_full	Analysis of Genetic Algorithms for solving the 2D Orthogonal Strip Packing Problem
title_fullStr	Analysis of Genetic Algorithms for solving the 2D Orthogonal Strip Packing Problem
title_full_unstemmed	Analysis of Genetic Algorithms for solving the 2D Orthogonal Strip Packing Problem
title_sort	analysis of genetic algorithms for solving the 2d orthogonal strip packing problem
title_alt	Анализ генетических алгоритмов решения задачи двухмерной ортогональной упаковки прямоугольных объектов в полубесконечную полосу Аналіз генетичних алгоритмів розв’язання задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу
description	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
publisher	Інститут програмних систем НАН України
publishDate	2018
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/217
work_keys_str_mv	AT glybovetsmm analysisofgeneticalgorithmsforsolvingthe2dorthogonalstrippackingproblem AT gulayevanm analysisofgeneticalgorithmsforsolvingthe2dorthogonalstrippackingproblem AT morozovio analysisofgeneticalgorithmsforsolvingthe2dorthogonalstrippackingproblem AT glybovetsmm analizgenetičeskihalgoritmovrešeniâzadačidvuhmernojortogonalʹnojupakovkiprâmougolʹnyhobʺektovvpolubeskonečnuûpolosu AT gulayevanm analizgenetičeskihalgoritmovrešeniâzadačidvuhmernojortogonalʹnojupakovkiprâmougolʹnyhobʺektovvpolubeskonečnuûpolosu AT morozovio analizgenetičeskihalgoritmovrešeniâzadačidvuhmernojortogonalʹnojupakovkiprâmougolʹnyhobʺektovvpolubeskonečnuûpolosu AT glybovetsmm analízgenetičnihalgoritmívrozvâzannâzadačídvovimírnoíortogonalʹnoíupakovkiprâmokutnihobêktívunapívneskínčennusmugu AT gulayevanm analízgenetičnihalgoritmívrozvâzannâzadačídvovimírnoíortogonalʹnoíupakovkiprâmokutnihobêktívunapívneskínčennusmugu AT morozovio analízgenetičnihalgoritmívrozvâzannâzadačídvovimírnoíortogonalʹnoíupakovkiprâmokutnihobêktívunapívneskínčennusmugu
first_indexed	2024-09-16T04:08:18Z
last_indexed	2024-09-16T04:08:18Z
_version_	1818568404527742976
fulltext	Прикладні засоби програмування та програмне забезпечення © М.М. Глибовець, Н.М. Гулаєва, І.О. Морозов, 2016 104 ISSN 1727-4907. Проблеми програмування. 2016. № 4 УДК 004.023 М.М. Глибовець, Н.М. Гулаєва, І.О. Морозов АНАЛІЗ ГЕНЕТИЧНИХ АЛГОРИТМІВ РОЗВ’ЯЗАННЯ ЗАДАЧІ ДВОВИМІРНОЇ ОРТОГОНАЛЬНОЇ УПАКОВКИ ПРЯМОКУТНИХ ОБ’ЄКТІВ У НАПІВНЕСКІНЧЕННУ СМУГУ Досліджено клас генетичних алгоритмів вирішення задачі двовимірної ортогональної упаковки пря- мокутних об’єктів у напівнескінченну смугу фіксованої ширини. Наведено результати теоретичного аналізу складності реалізації декодерів MERA та BLF; запропоновані власні реалізації цих декодерів з низкою евристичних оптимізацій. Запропоновано реалізацію генетичного алгоритму розв’язання задачі упаковки для окремих випадків (із забороною поворотів об’єктів та з поворотами на 90°). Описано результати тестових випробувань розробленого алгоритму за різних конфігурацій основних параметрів з використанням загальновідомих тестових наборів. Наведено результати порівняння отриманого алгоритму з іншими відомими алгоритмами. Ключові слова: генетичний алгоритм, задача упаковки-розкрою, декодер, Packing problem, MERA, BLF. Вступ Розв’язання задачі упаковки- розкрою (Packing problem) полягає у зна- ходженні оптимального розташування множини предметів меншого розміру (де- талей) на об’єктах більшого розміру (заго- товках). Цільовою функцією задачі зазви- чай є мінімізація втрат заготовок: необхід- но розмістити предмети або як можна щільніше, або в як можна меншу кількість контейнерів. Загальновідоме широке прак- тичне застосування задачі. В цій роботі розглянуто задачу дво- вимірної ортогональної упаковки прямо- кутних об’єктів у напівнескінченну смугу (ДОУПОНС) з окремими випадками (забо- роною поворотів об’єктів та з поворотами на 90°). Тобто, на смузі фіксованої ширини потрібно так розмістити прямокутники, щоб вони не перетинались, не виходили за межі смуги, а довжина використаної час- тини смуги була мінімальною. Досліджен- ня розв’язків цієї задачі має давню історію [1–3] і привели до її занесення до класу NP-складних задач комбінаторної оптимі- зації [4]. Тому широке розповсюдження для її розв’язання дістали евристичні та мета- евристичні методи. Серед метаевристич- них методів виділяють генетичні алгорит- ми [5–7], дослідженню яких присвячено цю роботу. Метою роботи є розробка та аналіз генетичного алгоритму (ГА) розв’язання задачі ДОУПОНС для випадків з заборо- ною повороту прямокутників та з дозво- леним поворотом на 90°. Особлива увага приділялася теоретичному аналізу скла- дності реалізації декодерів MERA та BLF. Для аналізу роботи ГА використовувався експериментальний підхід (проведення численних прогонів ГА на загальновідо- мих тестових даних). У статті ми опише- мо аналіз розробленого ГА з використан- ням різних наборів параметрів (методи відбору, оператор кросинговеру, ймовір- ність мутації, використаний декодер) та виділимо набори параметрів, які дають найкращі результати для різних класів задач, і сформулюємо рекомендації щодо використання певних конфігурацій пара- метрів ГА. Формальна постановка задачі Задача ДОУПОНС фіксованої ши- рини (two dimensional orthogonal rectangular strip packing problem) форму- люється так. Вхідну інформацію задають набором даних ),,,( lwmW , де NW – ширина напівнескінченої смуги; Nm – кількість прямокутних об’єктів; ,,( 21 ww ),,, mi ww  , Nwi  – ширина і-го прямокутника; ),,,,( 21 mi llll  , Прикладні засоби програмування та програмне забезпечення 105 Nli  – довжина і-го прямокутника. Вве- дено прямокутну систему координат XOY, таку що осі OX та OY збігаються відпо- відно з нижньою необмеженою та боко- вою сторонами смуги. Позиція і-го пря- мокутника називається горизонтальною, якщо його сторона довжини il є парале- льною до необмеженої сторони смуги, а друга сторона є перпендикулярною до неї. Задамо горизонтальну позицію і-го пря- мокутника парою координат його ниж- нього лівого кута ( , )i ix y . Набір векторів ( , ),i ix y i=1,2,3,…,m, називається допус- тимою прямокутною упаковкою, якщо виконуються такі умови:  сторони прямокутників є паралельними до сторін смуги (умова ортогональнос- ті);  прямокутники не перетинаються між собою: mji ,...,1,  , ji  :  ))()(( iijjji lxxlxx ));()(( iijjji wyywyy   прямокутники не виходять за межі сму- ги: mi ,...,1 : ))(()0()0( Wwyyx iiii  ;  дозволені або заборонені повороти пря- мокутників на кути, кратні 90°. Прямокутник розташований щільно, якщо він дотикається хоча б нижньою та лівою сторонами до інших прямокутників упаковки або до країв смуги. Упаковку називають щільною, якщо всі її прямокут- ники розташовані щільно. Допустима прямокутна упаковка називається оптимальною, якщо довжина зайнятої упакованими прямокутниками частини смуги сягає мінімуму (при цьому втрати невикористаних частин смуги є мінімальними). Нескладно бачити, що оп- тимальна упаковка є щільною. Діркою в упаковці називається не- заповнена ділянка смуги, з усіх боків ото- чена прямокутниками або краями смуги. Упаковка називається ідеальною, якщо використана ділянка смуги є прямо- кутником без дірок з шириною, що дорів- нює ширині смуги. Розв’язком задачі двовимірної ор- тогональної упаковки прямокутних об’єктів у напівнескінчену смугу є опти- мальна упаковка. Найпоширеніші методи розв’язку Методи розв’язку задачі двовимір- ної ортогональної упаковки діляться на точні, евристичні та метаевристичні [2]. Точні методи розв’язку засновані на методі гілок та границь. Запропонова- ний у [8] алгоритм є ні чим іншим, як пе- ребором порядку «приклеювання» прямо- кутників один до одного, що відсікає гіл- ку тоді, коли не можна приставити новий прямокутник до старих без утворення «ді- рок». При цьому алгоритм спирається на припущення про існування ідеальної упа- ковки. Цей метод довів свою ефективність на задачах розміром до 30 об’єктів. Інші точні методи цей результат не покращу- ють, доводячи необхідність евристичних методів. Перша вдала евристика «Нижній лівий» (Bottom Left) датується 1980 роком [9]. Метод полягав у впорядкуванні пря- мокутників за спаданням площі. Потім об’єкти розташовувались у верхньому правому куті та зсувались вниз та вліво, наскільки це дозволяли вже встановлені об’єкти. Цей метод був покращений у 1983 р. [10] та названий «Нижній лівий із заповненням» (Bottom Left Fill): кожен об’єкт розташовується в найлівішому та найнижчому можливому місці. Тривалий час ці методи були кращими і давали при- йнятні результати. Але в XXI сторіччі інтерес до задачі виріс, а з ним – і вимоги до розв’язків. Тому популярність набрали ймовірнісно-жадібні методи. Вони теж спочатку сортують об’єкти за певним критерієм, але розміщують новий прямо- кутник тільки з певною ймовірністю. Піс- ля одного прогону невстановлені об’єкти знову проходять цю процедуру, і так поки Прикладні засоби програмування та програмне забезпечення 106 жодного не залишиться. Прикладом тако- го алгоритму є GRASP [11]. Описані методи є так званими «ев- ристиками нижнього рівня»; згодом над ними були побудовані метаевристичні алгоритми. Наприклад, BLF-метод був комбінований з генетичним алгоритмом та з методом імітації відпалу; відповідні методи отримали назву GA+BLF та SA+BLF, відповідно. Кодування розв’язків Генетичні алгоритми оперують хромосомами – закодованими розв’язками поставленої задачі. Спосіб кодування розв’язків – фундаментальна підзадача алгоритму; огляд способів ко- дування наведено в [2]. Для даної задачі найочевидніший спосіб кодування упа- ковки – прямий код, або кодування на основі об’єктів: у хромосомі закодовано позиції прямокутників (наприклад, коор- динати лівих нижніх кутів на смузі). Та- кий спосіб має свої переваги: простота реалізації та декодування. Але критичний недолік полягає у тому, що дуже багато отриманих упаковок є недопустимими або нещільними, причому складність ви- правлення «поганих» упаковок є квадра- тичною від кількості прямокутників. То- му цей спосіб кодування для задачі дво- вимірної ортогональної упаковки рідко використовується на практиці, а найпо- ширенішим є кодування перестановками прямокутників. В цьому випадку хромо- сома містить послідовність номерів пря- мокутників, яка представляє порядок їх укладки на смугу. Правила укладки ви- значаються спеціальним алгоритмом – декодером, причому декодери розробля- ються в такий спосіб, щоб побудовані ними упаковки були допустимими та щільними. Оскільки одну перестановку можна розшифрувати багатьма способа- ми у допустимі щільні упаковки (резуль- туючі упаковки матимуть різну довжину або вимагатимуть різної кількості опера- цій для побудови), декодери можна порі- внювати між собою. Як правило, в генетичних алгорит- мах використовуються однопрохідні он- лайн декодери [2]. Найпоширеніші з цих декодерів – «Нижній лівий» (Bottom Left – BL), «Удосконалений нижній лівий» (Improved Bottom Left – IBL), «Нижній лівий із заповненням» (Bottom Left Fill – BLF), «Мінімізація площі оточуючого прямокутника» (Minimization of Enclosing Rectangle Area – MERA) – генерують BL- компактні упаковки. Такі упаковки задо- вольняють BL-умові: жоден розташований на смузі прямокутник не може бути зсуну- тий далі вниз або вліво. Далі проводиться порівняльний аналіз роботи двох декодерів – MERA та BLF – в контексті генетичного алгоритму. Складність реалізації обох декодерів є кубічною; якість отриманих розв’язків аналізується експериментально. Декодер «Мінімізація площі оточуючого прямокутника» Декодер «Мінімізація площі ото- чуючого прямокутника» (MERA) генерує BL-компактні упаковки та орієнтований на заповнення «дірок», що утворилися в процесі упаковки прямокутників. Алго- ритм намагається розташувати кожен на- ступний прямокутник, зіставляючи кожен його кут з кожним із кутів уже упакова- них прямокутників. Серед допустимих розташувань алгоритм обирає таке, за якого координати нижнього лівого кута нового прямокутника є мінімальними (площа оточуючого прямокутника є міні- мальною; оточуючим прямокутником називають найменший прямокутник, опи- саний навколо упакованої частини смуги). У роботі [13] стверджується, що склад- ність MERA-алгоритму є O( 2m ). Втім, строго кажучи, немає чіткого доведення цього факту: наводяться міркування про проведення аналогії із доведенням склад- ності BL-декодера, хоча таку аналогію проводити не можна. Аналіз наведеного в [13] псевдокоду також викликає серйозні сумніви щодо правильності оцінки склад- ності MERA-декодера. Зокрема, перебір пари прямокутників – нового для вставки та старого, з кутом якого проводиться зіставлення – вже є квадратичним. Додат- кова перевірка на наявність перетинів з іншими, вже упакованими прямокутника- Прикладні засоби програмування та програмне забезпечення 107 ми, має в такому разі бути виконана за константний час. Задача зробити цю пе- ревірку за константний час – як мінімум, нетривіальна, якщо взагалі розв’язна. Нам не вдалось знайти алгоритм, який би ро- бив таку перевірку зі складністю O(1). Для проведення експерименталь- ного аналізу MERA-декодера нами була розроблена його реалізація складності O( 3m ) з такими евристичними оптиміза- ціями. Перша оптимізація – запам’ято- вування вже декодованих перестановок. Експериментальний аналіз виявив, що у наборі особин за весь прогін алгоритму в середньому міститься лише близько 30 % унікальних хромосом, інші хромосоми – їх копії, що були отримані в результаті невдалого кросинговеру/мутації. Така оптимізація дозволяє більш ніж втричі зменшити об’єм обчислень, запам’ято- вуючи значення функції здоров’я для вже обрахованих особин в окремому асоціати- вному масиві. Друга оптимізація – відкидання безперспективних та малоперспективних комбінацій кутів. У псевдокоді, запропо- нованому в [13], розглядаються усі 16 комбінацій зіставлення кутів нового та старого прямокутників. Але 4 з цих ком- бінацій є апріорі неможливими (напри- клад, верхній правий до верхнього право- го), ще 4 з високою ймовірністю супере- чать BL-умові (наприклад, розташування нового прямокутника повністю зліва або знизу старого). Було пораховано (експе- риментально), що за описаних комбінацій кутів більш ніж 99.9 % отриманих упако- вок не проходили перевірку на допусти- мість. Тому було прийнято рішення про відкидання таких комбінацій заради прис- корення роботи алгоритму. Третя оптимізація – при пошуку мі- сця розташування нового прямокутника спочатку перевіряти перетин з тими пря- мокутниками, що були укладені пізніше. Так недопустимість упаковки виявляється раніше. Ця ідея прискорила роботу про- грами ще приблизно на 20 %. Щодо константи під асимптотикою – вона повністю визначається кількістю комбінацій кутів зіставлення і дорівнює 8. Декодер «Нижній лівий із заповненням» Декодер «Нижній лівий із запов- ненням» (BLF) був запропонований у [10]. Цей декодер також генерує BL-компактні упаковки та здатен запов- нювати дірки, що утворилися під час упаковки. Але алгоритм заповнення ді- рок є зовсім іншим. BLF-декодер постій- но тримає в пам’яті упорядкований зліва направо та знизу догори список точок, які можуть бути координатами лівого нижнього кута чергового прямокутника; послідовно переглядаючи цей список, алгоритм намагається розташувати чер- говий прямокутник у вільному місці та, у разі успіху, оновлює список точок. Цей список фактично є декартовим добутком списку Х-координат лівих та правих кін- ців вже упакованих прямокутників та аналогічного списку Y-координат. Саме пріоритет в бік зменшення X-координати і дає тенденцію заповнення дірок BLF- декодером. Наївна складність BLF-алгоритму – )( 4mO , покращена – )( 3mO . Найкраща існуюча реалізація має складність )( 2mO [10]; втім, ця реалізація використовує специфічний спосіб кодування, є об’єм- ною та важкою для розуміння. Тому нами був реалізований алгоритм складності )( 3mO ; псевдокод цього алгоритму пока- зано на рис. 1. Реалізація алгоритму поєднує дві ідеї для отримання кубічної складності: метод скануючої прямої та метод двох указників. Перший метод у цій реалізації слугує для перетворення нескінченної кількості варіантів розміщення нового прямокутника на скінченну: по осі OY обираються лише координати нижніх та верхніх кінців вже упакованих прямокут- ників. Ці координати грають роль «подій» для алгоритму – в них або новий прямо- кутник починається (нижній край), або закінчується (верхній край). У результаті задача перевірки допустимості нового Прикладні засоби програмування та програмне забезпечення 108 Алгоритм BLF(permutation, rectangles) if permutation in permutation_buffer: return permutation_buffer[permutation] #Список Y-координат початків та кінців прямокутників #Перший прямокутник встановлюємо в точку (0,0) events = list((0, open), (rectangles[0].width, close)) for new_rectangle in rectangles: for left_border in all_possible_left_borders: opened_rectangles = 0, closed_rectangles = 0 bot_index = 0, top_index = 0 while events[bot_index].Y + new_rectangle.width<= W: while events[top_index].Y <= events[bot_index].Y + new_rectangle.width: if events[top_index].type == open and coincide_by_X: opened_rectangles = opened_rectangles + 1 top_index = top_index+1 if events[bot_index].Y == close and coincide_by_X: closed_rectangles = closed_rectangles + 1 if opened_rectangles == closed_rectangles: new_rectangle.X = left_border new_rectangle.Y = events[bot_index].Y break bot_index = bot_index + 1 events.append(new_rectangle.Y, open) events.append(new_rectangle.Y + new_rectangle.width, close) sort(events) permutation_buffer[permutation] = placing return placing Рис. 1. Псевдокод алгоритму BLF-декодера розташування прямокутника зводиться до перевірки, скільки прямокутників було «відкрито» до верхньої границі нового прямокутника і скільки «завершено» до його нижньої границі. Якщо ці кількості збігаються, розміщувати прямокутник можна, інакше є старі прямокутники, що перетинають новий в його поточному по- ложенні. Метод двох указників, у свою чер- гу, робить два прогони по масиву «подій» одночасно замість того, щоб один прогін був вкладений в інший. Ці два указники вказують на нижню границю для укладки нового прямокутника та на останню «по- дію» перед верхньою границею. Несклад- но побачити, що при зсуві вгору нижнього указника верхній також може просуну- тись тільки вгору. Це й зменшує склад- ність двох циклів while з )( 2mO до )(mO , а загальну складність роботи алгоритму – до )( 3mO . Щодо константи під асимптотикою: зовнішній цикл виконується m разів, лівих кінців може бути до 2m, нижніх і верхніх – так само. В результаті отримуємо 38)22(2 mmmmm  – верхню грани- цю кількості операцій. Прикладні засоби програмування та програмне забезпечення 109 Функція пристосованості Найочевиднішим вибором функції пристосованості для даної задачі є або мі- німізація довжини упакованої частини смуги, або – що майже еквівалентно – мак- симізація відношення загальної площі упа- кованих прямокутників до площі зайнятої ними частини смуги. Така функція пристосованості оці- нює лише найважливіший атрибут розв’язку – безпосередню відповідь на за- дачу. Проте оцінювати пристосованість хромосоми можна не так «сухо», напри- клад, ввести доданок «суб’єктивної есте- тичності» – функцію від площі дірок, утворених при упаковці [6]. Звісно, цей доданок потрібно взяти з меншим ваговим коефіцієнтом, ніж перший, але він буде враховувати «привабливість» розкрою. Для визначення цього доданку наведемо декілька понять, введених в [6]. Розрідженістю гена хромосоми на- зивають величину )(_ )(_ )(_ iwidthblock ispacefree igenesparseness  , де )(_ ispacefree – частина лівої сторони i -го прямокутника, що не дотична до жод- ного іншого прямокутника або до краю смуги, )(_ iwidthblock – ширина i -го прямокутника. Відносною розріджденістю хромо- соми називають величину    m i igenesparsenessXsparseness 1 )(_)( , де m – кількість генів у хромосомі, )(_ igenesparseness – розрідженість і-го гену. Функцію пристосованості визначи- мо таким чином: )(XFitness max,)( _ 10  Xsparseness S shapesS де shapesS _ – загальна площа прямокут- ників, S – площа використаної частини смуги. Коефіцієнт 10 був підібраний емпі- рично. Огляд широко вживаних функцій пристосованості для задачі, що розгляда- ється, наведено в [2]. Відбір Для аналізу були обрані такі опера- тори відбору. Відбір за методом рулетки (Roulette-Wheel Selection, RWS). Згідно з цим методом, ймовірність особини бути обраною в батьківський пул прямо пропо- рційна значенню її пристосованості:    N j j i i Xf Xf XP 1 )( )( )( , де )( iXf – коефіцієнт пристосованості хромосоми iX , N – кількість хромосом в популяції. Стохастичний універсальний відбір (Stochastic Universal Selection, SUS). Цей оператор відбору має більш детерміновану природу, ніж рулетка, а саме обирає рів- номірно розподілені значення з ймовірніс- ного відрізка. Це дає реальний шанс слаб- шим особинам вижити та загалом пом’якшує шум відбору [2]. Ці два методи відбору є антиподами і ведуть себе по-різному на різних задачах. З метою дослідження впливу відбору на якість роботи алгоритму реалізовані обид- ва оператори. Оператор кросинговеру Кросинговер є основним операто- ром ГА. У роботі реалізовано два операто- ри кросинговеру, що широко використо- вуються в комбінаторних задачах. PMX-кросинговер (Partially Mapped Crossover). Робота оператора складається з двох кроків. На першому кроці випадково обираються дві точки схрещування та відбувається обмін гене- тичним матеріалом між обраними точка- ми. У більшості випадків такий обмін частинами породжує недопустимі хромо- соми: різні гени хромосоми можуть набу- ти однакових значень. Тому другий крок Прикладні засоби програмування та програмне забезпечення 110 полягає в усуненні дублів. Якщо k зна- чень у кожному протонащадку продуб- льовані (а кількість дублів буде однако- ва), то на позиціях поза зонами обміну дублі замінюються на продубльовані значення іншого протонащадка зі збере- женням порядку цих значень. OX-кросинговер (Order Crossover) з одною точкою схрещування. Цей оператор кросинговеру розрахований на збереження не стільки абсолютних позицій елементів, скільки їх відносного порядку в переста- новці. Для цього випадково обирається точка схрещування. Значення генів зліва від цієї точки переносяться нащадкам без змін. Значення генів справа від неї перено- сяться до нащадків у порядку, в якому во- ни зустрічаються у другій батьківській хромосомі. Оператор мутації Оператор мутації у генетичному алгоритмі використовується для урізно- манітнення генетичного матеріалу попу- ляції. Для аналізу було обрано мутацію вставкою (Insertion Mutation). В ній ви- падково обирається позиція в хромосомі, значення гену вилучається з цієї позиції та вставляється у випадково обрану нову позицію. Для задачі двовимірної упаков- ки з поворотами прямокутників на кут, кратний 90°, використовується мутація, яка змінює знак гена при повороті. Результати Для порівняння роботи декодерів MERA та BLF, для аналізу роботи гене- тичного алгоритму та виявлення оптима- льних значень його параметрів було про- ведено серію обчислювальних експери- ментів. Тестові дані Як тестові дані використані відомі тести Єви Гоппер [14]. Ці тести мають властивість гільйотинності: оптимальний розв’язок може бути отриманий в резуль- таті серії розрізів, паралельних осям ко- ординат, кожен з яких перетинає усю ши- рину або довжину прямокутника, що за- лишився. Більш того, тестові дані мають ідеальну упаковку. Інакше кажучи, щоб отримати n прямокутників, береться один великий прямокутник і n-1 разів розріза- ється паралельно осям координат. Опти- мальна довжина смуги тому відома зазда- легідь (як довжина початкового прямоку- тника). Тестові приклади розбиті на 7 ка- тегорій, в кожній різна кількість прямоку- тників. З метою прискорення обчислень запуски відбувались на тестах перших чотирьох категорій. Характеристики ви- користаних тестових наборів наведено у табл. 1. Критерієм оцінювання розв’язку, знайденого генетичним алгоритмом, слу- гує значення відхилення (у відсотках) знайденої алгоритмом довжини упаковки від оптимальної довжини смуги: %100   opt opt L LL gap , де L – найкращий знайдений розв’язок алгоритму, optL – оптимальна довжина смуги. Таблиця 1. Характеристика тестів Є. Гоппер Категорія/приклади Кількість об’єктів Ширина смуги Оптимальна довжина С1/Р1,Р2 16,17 20 20 С2/Р1 25 40 15 С3/Р1 28 60 30 С4/Р1 49 60 60 Прикладні засоби програмування та програмне забезпечення 111 Результати експериментів У табл. 2 наведено результати екс- периментів для описаних тестових набо- рів у випадку задачі із забороною поворо- тів прямокутників з використанням різних генетичних операторів, описаних вище. Інші параметри генетичного алгоритму задавались так: максимальна кількість ітерацій – 100; кількість особин у популя- ції – 100; ймовірність застосування опера- тора кросинговеру – 1; ймовірність засто- сування оператора мутації – 0.07. Для аналізу не тільки якості знайдених розв’язків, а й стабільності роботи алго- ритму виконувалось по 10 прогонів гене- тичного алгоритму з однаковими параме- трами для кожної задачі, найкращий та середній результати по всіх прогонах збе- рігались. Таблиця 2. Результати для задачі без поворотів (gap, %) Параметри Тестові набори d ec o d er se le ct io n cr o ss o v er m u ta ti o n C1/P1 C1/P2 C2/P1 C3/P1 C4/P1 M E R A B L F R W S S U S O X P M X In se rt io n N o n e B es t A v g B es t A v g B es t A v g B es t A v g B es t A v g * * * * 5.00 8.50 10.00 12.50 20.00 22.00 10.00 16.67 11.67 12.83 * * * * 5.00 11.00 10.00 15.50 20.00 26.00 16.67 20.00 11.67 14.17 * * * * 0.00 8.00 5.00 11.00 20.00 22.00 13.33 18.33 10.00 11.33 * * * * 0.00 8.00 10.00 13.30 20.00 22.00 10.00 16.67 10.00 13.33 * * * * 0.00 6.50 5.00 10.00 20.00 20.00 10.00 16.00 10.00 11.33 * * * * 0.00 7.00 5.00 11.50 13.33 21.33 16.67 18.67 11.67 12.33 * * * * 0.00 4.00 10.00 10.00 20.00 20.00 10.00 15.33 10.00 12.00 * * * * 0.00 6.50 10.00 10.50 20.00 20.00 16.67 17.00 11.67 12.33 * * * * 0.00 5.50 10.00 10.00 13.33 21.33 23.33 28.00 11.67 12.00 * * * * 0.00 6.50 5.00 9.50 20.00 22.67 26.67 28.33 11.67 13.00 * * * * 0.00 1.50 5.00 9.00 20.00 20.00 20.00 26.00 10.00 11.00 * * * * 0.00 6.00 10.00 10.00 20.00 20.00 23.33 26.67 10.00 11.67 * * * * 0.00 1.50 5.00 8.00 20.00 20.00 20.00 25.67 11.67 12.00 * * * * 0.00 2.00 5.00 9.00 20.00 20.00 16.67 26.67 11.67 12.33 * * * * 0.00 1.50 5.00 8.00 20.00 20.00 16.67 24.67 10.00 11.33 * * * * 0.00 1.50 5.00 9.00 20.00 20.00 23.33 23.67 11.67 12.33 Прикладні засоби програмування та програмне забезпечення 112 У табл. 3 наведені середні по про- гонах та по задачах результати для кож- ного набору параметрів. Як видно з цієї таблиці, найкращі результати дає декодер MERA в комбінації зі стохастичним від- бором та мутацією вставкою. Водночас, декодер BLF працює стабільніше, з мен- шою дисперсією. Враховуючи однакову часову складність реалізації алгоритмів, рекомендуємо використовувати декодер MERA із вдало підібраними значеннями інших параметрів. Аналізуючи табл. 3, також можна констатувати, що застосування мутації є необхідним для успішної роботи алгори- тму: за кожного набору параметрів алго- ритм без мутації давав гірший результат, ніж з нею. Стохастичний універсальний відбір показав очевидні переваги перед відбором за методом рулетки, що не су- перечить теорії: цей метод має менший шум відбору та стабільніший тиск відбо- ру при переході від покоління до поко- ління [2]. Зазначимо, що тип оператора кросинговеру особливого впливу на ре- зультати не має. Таблиця 3. Середні результати для задачі без поворотів (gap, %) Параметри Середні значення д ек о д ер в ід б ір к р о си н го в ер м у та ц ія По всіх наборах На наборах C1 На наборах C2, C3, C4 M E R A B L F R W S S U S O X P M X In se rt io n N o n e A v g (B es t) A v g (A v er ag e) A v g (B es t) A v g (A v er ag e) A v g (B es t) A v g (A v er ag e) * * * * 11,33% 14,50% 7,50% 10,50% 13,89% 17,17% * * * * 12,67% 17,33% 7,50% 13,25% 16,11% 20,06% * * * * 9,67% 14,13% 2,50% 9,50% 14,44% 17,22% * * * * 10,00% 14,66% 5,00% 10,65% 13,33% 17,33% * * * * 9,00% 12,77% 2,50% 8,25% 13,33% 15,78% * * * * 9,33% 14,17% 2,50% 9,25% 13,89% 17,44% * * * * 10,00% 12,27% 5,00% 7,00% 13,33% 15,78% * * * * 11,67% 13,27% 5,00% 8,50% 16,11% 16,44% * * * * 11,67% 15,37% 5,00% 7,75% 16,11% 20,44% * * * * 12,67% 16,00% 2,50% 8,00% 19,45% 21,33% * * * * 11,00% 13,50% 2,50% 5,25% 16,67% 19,00% * * * * 12,67% 14,87% 5,00% 8,00% 17,78% 19,45% * * * * 11,33% 13,43% 2,50% 4,75% 17,22% 19,22% * * * * 10,67% 14,00% 2,50% 5,50% 16,11% 19,67% * * * * 10,33% 13,10% 2,50% 4,75% 15,56% 18,67% * * * * 12,00% 13,30% 2,50% 5,25% 18,33% 18,67% Прикладні засоби програмування та програмне забезпечення 113 Таким чином, для розв’язку задачі двовимірної ортогональної упаковки із забороною поворотів прямокутників у загальному випадку можна порекоменду- вати наступний набір параметрів: декодер MERA, стохастичний універсальний від- бір, PMX-кросинговер, мутація вставкою. Більш глибокий аналіз отриманих результатів дозволяє диференціювати випадки незначної (до 20) та великої (бі- льше 20) кількості прямокутників, що підлягають упаковці. У першому випадку рекомендований набір параметрів: деко- дер BLF, стохастичний універсальний відбір, PMX-кросинговер або OX- кросинговер, мутація вставкою; в друго- му випадку – декодер MERA, стохастич- ний універсальний відбір, PMX- кросинговер або OX-кросинговер, мута- ція вставкою. Назвемо ГА з такими па- раметрами GA+MERA та порівняємо йо- го з роботою відомих алгоритмів на цих же тестах. В порівнянні окрім GA+MERA братимуть участь алгоритми GA+IBL ([6]), H-SP та R-GRASP ([16]), а також розроблений в [17] GA+BLF. Алгоритм R-GRASP на сьогодні вважається най- кращим для задачі без поворотів прямо- кутників. Результати порівняння наведені у табл. 4. Як видно з таблиці, розробле- ний нами генетичний алгоритм GA+MERA поступається навіть GA+IBL, який має меншу часову складність. Вод- ночас GA+MERA поступається розроб- леному в [17] GA+BLF, але є кращим за розроблений нами GA+BLF. Аналіз табл. 3 показує чітку тенденцію до однакової динаміки поведінки генетичного алгори- тму для кожного з розглянутих декодерів (MERA, BLF) при відповідних змінах інших параметрів. Це дозволяє припус- тити, що параметри алгоритму в цілому були підібрані не дуже вдало, а за більш вдалого набору параметрів (наприклад, набір параметрів у сполученні з евристи- чними оптимізаціями, що були викорис- тані в роботі [17]), алгоритм GA+MERA міг би дати значно кращі результати як у порівнянні з GA+IBL, так і у порівнянні з GA+BLF. Це мета наших подальших дос- ліджень. Результати для задачі з поворотами Для задачі з можливістю поворотів були застосовані ті ж значення параметрів, що й для задачі без поворотів. Результати для різних наборів параметрів подані у табл. 5. Висновок, який можна зробити з цієї таблиці, полягає у тому, що самі пово- роти нічим не покращили якість знайдених розв’язків. Причиною є те, що разом зі збільшенням кількості якісних розв’язків збільшилась і кількість неякісних, а харак- тер пошуку не сильно змінився. Отже, не- обхідне проведення подальших досліджень з використанням комбінації поворотів та мутації вставкою. Таблиця 4. Порівняння роботи алгоритму GA+MERA з іншими відомими алгоритмами для задачі із забороною поворотів (gap, %) Клас GA+BLF GA+MERA GA+IBL R-GRASP H-SP Best Best Avg Best Avg Best Avg Best Avg C1 4 2.5 4.75 5 5 0 0 0 1.33 C3 5 10 15 7 8 1.08 1.08 2.22 2.22 C4 3 10 12 8 10 1.64 1.64 1.67 2.11 Avg 4 7.5 10.58 6.66 7.66 0.91 0.91 1.30 1.89 Прикладні засоби програмування та програмне забезпечення 114 Таблиця 5. Результати для задачі з поворотами (gap, %) se le ct io n cr o ss o v er C1/P1 C1/P2 C2/P1 C3/P1 C4/P1 T o ta l a v er a g e RWS SUS OX PMX Best Avg Best Avg Best Avg Best Avg Best Avg * * 5.00 8.00 5.00 7.00 13.33 14.67 10.00 12.67 10.00 11.33 10.73 * * 5.00 7.50 5.00 7.00 13.33 13.33 10.00 12.00 10.00 11.33 10.23 * * 5.00 7.00 5.00 8.00 13.33 13.33 10.00 13.33 10.00 11.67 10.67 * * 5.00 8.00 5.00 9.00 13.33 13.33 10.00 11.33 10.00 12.00 10.73 Висновки та рекомендації У цьому дослідженні проаналізова- но вплив параметрів на роботу генетично- го алгоритму розв’язку задачі двовимірної ортогональної упаковки прямокутних об’єктів у напівнескінченну смугу фіксо- ваної ширини з можливістю поворотів на 90° та без неї. Особливу увагу приділено аналізу декодерів MERA та BLF. Виділено найкращі набори параметрів. Проведено порівняльний аналіз запропонованого ал- горитму з найкращими відомими. Розроблений алгоритм GA+MERA поступається найкращим відомим сьогод- ні алгоритмам розв’язку поставленої за- дачі: найкращі по всіх прогонах результа- ти є гіршими на 5 % – 13 % у випадках з дозволеними поворотами та без них. Цей алгоритм показав навіть гірші ре- зультати у порівнянні з GA+IBL, що має меншу часову складність. Втім, беручі до уваги результати роботи [17] та дані з табл. 3, є підстави сподіватись на сут- тєве покращення роботи алгоритму за умови більш вдалого підбору інших пара- метрів. Окреслимо можливі шляхи удо- сконалення.  Впровадження оператора упа- ковки, що об’єднує прямокутники, які ма- ють однакову довжину/ширину та упако- вані поруч, в один метапрямокутник [6].  Застосування параметрів та евристик, запропонованих в роботі [17].  Модифікація функції пристосо- ваності.  Застосування кількох декодерів та автоматичний вибір декодера для роз- ташування чергового об’єкта. 1. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геоме- трического проектирования. – Киев: Нау- кова думка, 1986. – 268 с. 2. Глибовець М.М., Гулаєва Н.М. Еволюційні алгоритми: підручник. – НаУКМА, 2013. – С. 334–357. 3. Мухачева Э.А., Мухачева А.С. Л.В. Кан- торович и задачи раскроя- упаковки: новые подходы для решения комбинато- рных задач линейного раскроя и прямоу- гольной упаковки // Записки научных семинаров ПОМИ. – 2004. – Т. 312. – С. 239–255. 4. Fowler R.J., Paterson M.S., Tatimoto S.L. Optimal packing and covering in the plane are NP-complete // Information Processing Letters. – 1981 – N 12. – P. 133–137. 5. Гребенник И.В., Панкратов А.В., Чугай А.М. и др. Упаковка n-мерных параллепи- педов с возможностью изменения их орто- гональной ориентации в n-мерном пара- ллелепипеде // Кибернетика и системный анализ. – 2010. – № 5. – С.122–131. Прикладні засоби програмування та програмне забезпечення 115 6. Гулаєва Н.М., Щур О.П. Аналіз параметрів генетичного алгоритму розв’язку задачі ортогональної упаковки // Наукові записки НаУКМА. – 2012. – Т. 138: Комп’ютерні науки. – С. 6–14. 7. Чеканин В.А. Модифицированные эволю- ционные алгоритмы и программные реше- ния задачи ортогональной упаковки объек- тов // Автореф. дис. ... канд. техн. наук. М.: УГАТУ, 2011. – 14 с. 8. Lesh.N., Marks J., Mc. Mahon A. Exhaustive approaches to 2D rectangular perfect packings. Information Processing Letters – 2004. – P. 7–14. 9. Baker B.S., Coffman E.G., Rivest R.L. Orthogonal packings in two dimensions // SIAM Journal on computing 10. Chazelle B. The bottom left bin packing heuristic: an efficient implementation // IEEE Transaction on computers. – 1983 – N 32. – P. 697–707. 11. Lesh N., Mitzenmacher M. Bubble search: a simple heuristic for improving priority-based greedy algorithms // Information processing letters. – 2006. – P. 161–169. 12. Bortfeldt A. A genetic algorithm for the two-dimensional strip-packing problem with rectangular pieces. European Journal of Operational Research. – 2006. – P. 814–837. 13. Ahmad, Abdul-Rahim, An Intelligent Expert System for Decision Analysis and Support in Multi-Attribute Layout Optimization, PhD thesis, University of Waterloo, Ontario, Canada, 2005. – 207 p. 14. Hopper E., Turton B.C.H. Problem generators for rectangular packing problems // Computers in Engineering. – 2000. – P. 123–135. 15. Riff M.C., Bonnaire X., Neveu B. A revision of recent approaches for two-dimensional strip-packing problems // Engineering application of Artificial Intelligence. – 2009. 16. Araya I., Neveu B., Riff M.C. An Efficient Hyperheuristic for Strip Packing problem // Book Adaptive and Multilevel Heuristics, Series Studies in Computational Intelligence. – Springer. – 2008. – P. 61–76. 17. Hopper E., B. C. H. Turton. An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem. Eur. J. Oper. Res. – 2000. – Vol. 128. – P. 34–57. References 1. Stoyan Y.G., Yakovlev S.V. Mathematical models and optimization methods of the geometric projection. – Kiev: Scientific thought. – 1986. – 268 p. 2. Glibovets M.M., Gulayeva N.M. Evolutionary algorithms: a textbook. – NaUKMA, 2013. – P. 334–357. 3. Mukhacheva E.A., Mukhacheva A.S. L.V. Kantorovich and problems of cutting- package, new approaches to combinatorial problems of linear cutting and rectangular package // Notes of POMI scientific seminars. – 2004. – Vol. 312. – P. 239–255. 4. Fowler R.J., Paterson M.S., Tatimoto S.L. Optimal packing and covering in the plane are NP-complete // Information Processing Letters. – 1981 – N 12. – P. 133–137. 5. Grebennik I.V., Pankratov A.V., Chugai A.M., Baranov A.V. Packaging n- dimensional parallelepipeds with the ability to change their orthogonal orientation in n-dimensional parallelepiped // Cybernetics and Systems Analysis. – 2010. – N 5. – P. 122–131. 6. Gulayeva N.M. Analysis of the parameters of the genetic algorithm solving the prob- lem of orthogonal package / Gulayeva N.M., Shchur O.P. // Scientific notes NaUKMA. – 2012. – Vol 138: Computer science. – P. 6–14. 7. Chekanin V.A. Modified evolutionary algorithms and programmatic solving of the problem of orthogonal packing of objects // Abstract. Dis. on the scientific degree of Ph.D. : 05.13.17. – Moscow: USATU, 2011. – 14 p. 8. Lesh.N., Marks J., Mc. Mahon A. Exhaustive approaches to 2D rectangular perfect packings. Information Processing Letters – 2004. – P. 7–14. 9. Baker B.S., Coffman E.G., Rivest R.L. Orthogonal packings in two dimensions // SIAM Journal on computing 10. Chazelle B. The bottom left bin packing heuristic: an efficient implementation // IEEE Transaction on computers. – 1983 – N 32. – P. 697–707. 11. Lesh N., Mitzenmacher M. Bubble search: a simple heuristic for improving priority-based greedy algorithms // Information processing letters. – 2006. – P. 161–169. Прикладні засоби програмування та програмне забезпечення 116 12. Bortfeldt A. A genetic algorithm for the two-dimensional strip-packing problem with rectangular pieces. European Journal of Operational Research. – 2006. – P. 814–837. 13. Ahmad, Abdul-Rahim, An Intelligent Expert System for Decision Analysis and Support in Multi-Attribute Layout Optimization, PhD thesis, University of Waterloo, Ontario, Canada, 2005. – 207 p. 14. Hopper E., Turton B.C.H. Problem generators for rectangular packing problems // Computers in Engineering. – 2000. – P. 123–135. 15. Riff M.C., Bonnaire X., Neveu B. A revision of recent approaches for two- dimensional strip-packing problems // Engineering application of Artificial Intelligence. – 2009. 16. Araya I., Neveu B., Riff M.C. An Efficient Hyperheuristic for Strip Packing problem // Book Adaptive and Multilevel Heuristics, Series Studies in Computational Intelligence. – Springer. – 2008. – P. 61–76. 17. Hopper E., B. C. H. Turton. An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem. Eur. J. Oper. Res. – 2000. – Vol. 128. – P. 34–57. Одержано 01.07.2016 Про авторів: Глибовець Микола Миколайович, доктор фізико-математичних наук, професор, декан факультету інформатики НаУКМА. Кількість наукових публікацій в українських виданнях – понад 150. Кількість наукових публікацій в іноземних виданнях – 11. Індекс Хірша – 1. http://orcid.org/0000-0002-3853-2171, Гулаєва Наталія Михайлівна, кандидат фізико-математичних наук, доцент кафедри інформатики НаУКМА. Кількість наукових публікацій в українських виданнях – 20. Кількість наукових публікацій в іноземних виданнях – 1. Індекс Хірша – 1. http://orcid.org/0000-0003-4588-0702, Морозов Ігор Олегович, магістр факультету інформатики НаУКМА. Кількість наукових публікацій в українських виданнях – 0. Кількість наукових публікацій в іноземних виданнях – 0. Індекс Хірша – 0. http://orcid.org/0000-0003-4085-170X. Місце роботи авторів: Національний університет «Києво-Могилянська Академія», 04655, м. Київ, вул. Сковороди, 2. Тел.: (044) 463 6985, факс: (044) 416 4515. E-mail: glib@ukma.kiev.ua, ngulayeva@yahoo.com, hospital-at-home@yandex.ru mailto:hospital-at-home@yandex.ru

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

Репозитарії

Схожі ресурси