Модифицированные эволюционные алгоритмы и программные решения задачи ортогональной упаковки объектов (1095065), страница 2
Текст из файла (страница 2)
Москва),выполняющем высокотехнологичные разработки, в том числе, для решениязадач упаковки и логистики в интеллектуальных транспортных системах, атакже – для оптимизации работы аптечного склада многопрофильнойклинической больницы (г. Москва).Апробация работы. Основные научные и практические результатыработы докладывались на:6• научно-практическойконференции«Автоматизацияиинформационные технологии (АИТ)» (Москва, ГОУ ВПО МГТУ«Станкин», 2008, 2009, 2010);• XI научной конференции ГОУ ВПО МГТУ «Станкин» и «Учебнонаучного центра математического моделирования МГТУ «Станкин» ИММ РАН» по математическому моделированию и информатике,(Москва, 2008);• XI международной конференции «ПРОТЭК’08» (Москва, ГОУ ВПОМГТУ «Станкин», 2008);• школе-семинаре «Задачи системного анализа, управления и обработкиинформации» (Москва, ГОУ ВПО «Московский государственныйуниверситет печати», 2008, 2009);• II Всероссийской студенческой научно-технической конференции«Прикладная информатика и математическое моделирование»(Москва, ГОУ ВПО «Московский государственный университетпечати», 2008);• III Всероссийской студенческой научно-технической конференции«Прикладная информатика и математическое моделирование»(Москва, ГОУ ВПО «Московский государственный университетпечати», 2009);• IV Всероссийской студенческой научно-технической конференции«Прикладная информатика и математическое моделирование»(Москва, ГОУ ВПО «Московский государственный университетпечати», 2010);• межвузовской научной конференции молодых ученых и студентов«Инновации в экономике» (Москва, ГОУ ВПО МГТУ «Станкин»,2009);• III Всероссийской конференции студентов, аспирантов и молодыхученых «Искусственный интеллект: философия, методология,инновации» (Москва, ГОУ ВПО МИРЭА, 2009);• VII международной научно-практической конференции «Trans-MechArt-Chem» (Москва, ГОУ ВПО МИИТ, 2010);• III научно-образовательной конференции «Машиностроение –традиции и инновации» (Москва, ГОУ ВПО МГТУ «Станкин», 2010).В 2008 году проект «Повышение эффективности управления полезнымпространством складов на основе эволюционных алгоритмов», включающийнекоторые положения диссертационной работы, был удостоен дипломаВсероссийской выставки научно-технического творчества молодежи НТТМ2008.Публикации.
По теме диссертации опубликовано 20 научных работ, изних 14 основных, в том числе 3 статьи в изданиях, входящих в Переченьведущих периодических изданий ВАК Министерства образования и науки РФ и1 монография.7Структура и объем диссертации. Диссертационная работа состоит извведения, четырёх глав, списка литературы и трёх приложений. Основной текстсодержит 155 страниц.
Список литературы состоит из 137 наименований.Приложения выполнены на шести страницах.Основное содержание работыВо введении обосновывается актуальность темы диссертационнойработы; формулируются цели и задачи исследований; представляютсяосновные выносимые на защиту положения работы; определяются новизна,практическая значимость полученных результатов; приводится краткаяхарактеристика основных разделов диссертации.В первой главе представлен обзор существующих задач раскрояупаковки и методов их решения. Приведена классификация задач раскрояупаковки, проведенная H. Dyckhoff, а также современная классификация,предложенная H. Dyckhoff, J. Terno и G.
Scheithauer.В общем виде задача ортогональной упаковки размерности Dописывается следующим образом: имеются набор прямоугольных контейнеровс габаритами W 1j ,W j2 ,K,W jD , j = 1,K, N и набор прямоугольных предметов{}{w1i , wi2 ,K, wiD }, i = 1,K, n . Запишем положение объекта i в j -м контейнере вследующем виде: (xij1 ; xij2 ;K; xijD ). Необходимо разместить все объекты вминимальном числе контейнеров при выполнении следующих условий:1) ребра упакованных в контейнере прямоугольных объектовпараллельны ребрам контейнера;2) упакованные объекты не пересекаются друг с другом, т.е.
дляdd∀d = 1,K, D, ∀i, q = 1,K, n, i ≠ q xijd ≥ xqj+ wqd ∨ xqj≥ xijd + wid ;3) упакованные объекты не пересекаются со сторонами контейнера, т.е.для ∀d = 1,K, D; ∀i = 1,K, n xijd ≥ 0 ∧ xijd + wid ≤ W jd .Сформулированы задачи ортогональной упаковки объектов на листы и наполубесконечную полосу. Приведены основные методы решения задачиупаковки. Описаны методы комбинаторной оптимизации; эвристические,вероятностные и эволюционные методы, применяемые для решения задачраскроя и упаковки. Выделены основные факторы, влияющие на качествоконечной упаковки: модель представления объектов в контейнерах, схемыкодирования и декодирования строки решения, алгоритмы оптимизацииполучаемого решения.
Выделены области эффективного применения решениязадач раскроя-упаковки, а также классы наиболее распространенных напрактике задач, которые решаются в диссертационной работе.В конце главы формулируются задачи диссертационной работы.Вторая глава посвящена исследованию алгоритмов конструированияортогональной упаковки. Рассмотрены следующие модели представленияобъектов в контейнерах: модель на основе многомерного массива, узловаямодель, блочная модель.(() () ())8Решение любой задачи упаковки n объектов кодируется строкой sнатуральных чисел длиной 2n :s = {A1, B1, A2 , B2 ,K, An , Bn },(1)где число Ai содержит номер типа i -го размещаемого объекта из спискаразмещаемых объектов; число Bi – информацию об ориентации этого объекта впространстве контейнера.
Целевой функцией является отношение суммарногообъема размещенных в контейнере объектов к объему V * описанного вокругполученной D -мерной упаковки контейнера:nt DS=∑ ∏ widi =1d =1*,(2)Vгде nt – число размещенных в контейнере объектов.В узловой модели контейнер хранит информацию о размещенныхобъектах в виде набора точек, называемых узлами.
Каждый узел k содержитструктуру вида:U k = X k , a, b ,(3){}{}где X k = x1k1, xk2 ,K, xkD – вектор положения узла в контейнере при решенииD -мерной задачи ортогональной упаковки, a – ссылка на присоединенный кузлу объект, b – номер положения ориентации объекта в контейнере.Выделяется два типа узлов: свободные (с нулевой ссылкой на типприсоединенного объекта) и несвободные.Разработанная модель «виртуальные объекты» является производной отузловой модели.
В модели «виртуальные объекты» узлы дополнительносодержат информацию о наибольших габаритах ортогональных объектов,которые могут быть к ним присоединены. Каждый узел контейнера содержитструктуру вида:U k′ = X k , Pk , a , b ,(4)где Pk = p1k , pk2 ,K, pkD – вектор виртуального объекта, описывающий габаритынаибольшего прямоугольного объекта, который может быть присоединен кузлу k без пересечений с размещенными в контейнере объектами.На рис.
1 изображен двухмерный контейнер, содержащий объект сгабаритами l × w , присоединенный к узлу 1 контейнера с векторомвиртуального объекта P = {L;W }. После присоединения объекта в контейнереобразованы новые узлы: узел 2 с вектором P = {L − l ;W }, узел 3 с векторомP = {L − l ; W − w} и узел 4 с вектором P = {L;W − w}.9Рис. 1. Виртуальные объекты контейнераРабота модели «виртуальные объекты» представлена в виде блок-схемына рис. 2.Рис.
2. Блок-схема алгоритма размещения в модели «виртуальныеобъекты»10Значение целевойфункцииПри решении задач трёхмерной упаковки объектов с использованиеммодели «виртуальные объекты» возможно образование локальных пустот вконтейнере, поэтому качество полученной упаковки в этом случае хуже, чемпри использовании узловой модели, что подтверждается проведеннымиисследованиями (см. рис. 3).0.8950.8930.8880.890.8850.8820.88УзловаямодельБлочная Модельмодель "виртуальныеобъекты"Рис. 3. Качество размещения для различных моделей представленияПроведенные исследования показали, что при решении задач трёхмернойортогональной упаковки объектов целесообразно использовать узловуюмодель.
Узловая модель и модель «виртуальные объекты» обеспечиваютодинаковое качество размещения объектов при решении задач двухмернойупаковки. Поэтому при решении задачи двухмерной ортогональной упаковкинаиболееэффективнойявляетсямодель«виртуальныеобъекты»,обеспечивающая наивысшую скорость размещения объектов (см. рис. 4).4.33Время, с5431.981.51210УзловаямодельБлочная Модельмодель "виртуальныеобъекты"Рис. 4.
Скорость размещения для различных моделей представленияПри использовании модели «виртуальные объекты» определениевозможности присоединения размещаемого объекта к узлу вместо проверки на11пересечение со всеми размещенными в контейнере объектами сводится кединственной проверке нахождения объекта целиком внутри виртуальногообъекта узла k : wki ≤ pki ∀i = 1,K, d , к которому он присоединяется, за счетчего скорость размещения повышается.Проведен ряд вычислительных экспериментов, подтверждающихэффективность представления набора узлов в узловой модели в видединамического списка. Предложена модифицированная структура узлов вконтейнере, использование которой в среднем вдвое повышает скоростьразмещения объектов.Разработан унифицированный декодер Packer строки решения задачортогональной упаковки объектов различной размерности для моделейпредставления объектов, построенных на основе узловой модели.Декодер Packer работает следующим образом:1.
Проводятся выбор размещаемого объекта i из строки решения s ивыбор контейнера c , содержащего, как минимум, один свободныйузел. В случае если выбраны все объекты, работа декодеразавершается.2. Осуществляется последовательный поиск свободного узла j текущегоконтейнера c , к которому возможно присоединить текущий объектi : wid ≤ p dj ∀d = 1,K, D . В случае если искомый узел не может бытьнайден, осуществляется переход к следующему контейнеру c := c + 1 иповтор п.2. В случае если среди всех контейнеров не найден искомыйузел, выполняется переход к п.1.3. Объект i присоединяется к найденному узлу j контейнера c . Врезультате формируются новые узлы(){U *} = {(x1j ; x1j + wi1 )× (x 2j ; x 2j + wi2 )× K × (x Dj ; x Dj + wiD )}.(5)Узлы контейнера упорядочиваются в порядке, обеспечивающемневозрастание приоритета присоединения к ним объектов, т.е.D h D d D hxW≤x∑ j ∏ c ∑ j −1 ∏ Wcd ∀j ∈ {U ⊃ U *}.h =1d = h +1 h =1d = h +1 D(6)Осуществляется переход к п.1.Описанный алгоритм размещения объектов позволяет динамическизаполнять контейнеры объектами в порядке, определяемом положением узловконтейнеров.
Декодер Packer при размещении объектов учитывает всесвободные области контейнера и размещает новые объекты как можно ближе коснованию контейнера благодаря упорядочиванию узлов после добавления вконтейнер каждого нового объекта.12Исследованаресурснаяэффективностьалгоритмаразмещенияортогональных объектов. Его верхняя асимптотическая оценка равна O N 3 .Описаны оптимизационные методы повышения скорости размещения объектовв контейнерах.
Предложена модифицированная структура узлов в контейнере,использование которой в среднем вдвое сокращает время размещения объектов.Третья глава посвящена исследованию эффективности примененияэволюционных алгоритмов для решения задач раскроя-упаковки.Рассматривается общий подход к решению оптимизационных задач наоснове эвристических алгоритмов. Предложен алгоритм формированиядетерминированного начального множества решений, позволяющий повыситькачество конечного решения примерно на 10% по сравнению с решением,получаемым на основе случайного начального множества решений.Рассмотрены основные критерии останова поиска при решенииоптимизационных задач на основе эволюционных алгоритмов. Предложенновый критерий останова, использующий пороговое значение параметраостанова K , характеризующего относительное число постоянных решений впопуляции при её эволюции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
