автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Конструктивные и нейросетевые методы решения задач двух и трехмерного ортогонального раскроя-упаковки

На правах рукописи

КОРЧЕВСКАЯ ОКСАНА ВАЛЕРИЕВНА

КОНСТРУКТИВНЫЕ И НЕЙРОСЕТЕВЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ДВУХ И ТРЕХМЕРНОГО ОРТОГОНАЛЬНОГО РАСКРОЯ-УПАКОВКИ

05.13.17- теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Красноярск - 2008

003458441

Работа выполнена на кафедре информационных технологий ГОУ ВПО «Сибирский государственный технологический университет»

Научный руководитель кандидат технических наук, доцент

Жуков Леонид Александрович

Официальные оппоненты: доктор технических наук, профессор

Миркес Евгений Моисеевич,

доктор технических наук, профессор Ковалев Игорь Владимирович

Ведущая организация: Уфимский государственный авиационный

технический университет

Защита диссертации состоится 15 января 2009 года в 14.00 часов на заседании диссертационного совета Д 212.099.11 при Сибирском федеральном университете по адресу: 660074, г. Красноярск, ул. Киренского, 26, корпус Ж, ауд. 1-15.

С диссертацией можно ознакомиться в научной библиотеке Сибирского федерального университета по адресу: ул. Киренского, 26, ауд. Г274.

Автореферат разослан «И» декабря 2008 г.

Ученый секретарь диссертационного совета к.т.н., доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Для современного периода производства характерно использование технологических процессов и методов, минимизирующих потери, что особенно актуально на данном этапе развития рыночных отношений в России.

В один из классов задач комбинаторной оптимизации, достаточно часто встречающийся в реальных производственных условиях, выделены задачи раскроя и упаковки. Их объединяет необходимость установления определенного соответствия между двумя группами, как правило, больших и малых объектов.

Задачи раскроя-упаковки имеют различное прикладное толкование. Наиболее часто встречающимися задачами являются ортогональная упаковка и раскрой, где в качестве малых объектов выступают заготовки прямоугольной формы - прямоугольники или ящики различных размеров, а в качестве крупных - материал, поступающий в виде полос, рулонов, прямоугольных листов, стержней или контейнеров различной вместимости.

Эти задачи представляют собой проблему как теоретического, так и практического плана, которая в течение последних десятилетий привлекает внимание многих исследователей и производственников. Причина растущего интереса к задачам раскроя-упаковки состоит в широкой применимости результатов, их разнообразии и сложности.

Задачи раскроя-упаковки относят к классу NP-трудных задач комбинаторной оптимизации. Это означает, что не существует алгоритмов полиномиальной сложности для поиска оптимального решения, точный результат в общем случае может быть получен только за экспоненциальное время.

Точные и псевдоточные методы решения, так или иначе, связаны с методом ветвей и границ. Для их применения необходимо знать нижние границы решения или иметь алгоритм их вычисления. Однако точную нижнюю границу пока найти не удалось. Это ограничивает применение как точных, так и приближенных методов, основанных на методе ветвей и границ.

На практике большинство задач раскроя-упаковки имеют большую размерность. Из-за значительных затрат вычислительного времени и необходимости учета технологических ограничений для решения подобного класса задач, как правило, используют приближенные методы и эвристики.

Фундаментальные научные разработки в области решения задач раскроя-упаковки принадлежат Л.В. Канторовичу и В.А. Залгаплеру (1950). Результаты дальнейших исследований в этой области отражены в работах Э.А. Мухачевой (1979), Е.Г1. Бороновского (1967), А.Ф. Валеевой (2000), И.П. Норенкова (1999), Ю.А. Кочетова (2000), И.В. Романовского (1977), A.C. Филипповой (1999), В.М. Картак (2004); за рубежом - Р. Gilmore & R. Gomory (1965), G. Scheithauer & J. Terno (1970), H. Dyckhoff (1990), A. Bortfeldt (1998) и др.

В работах А.Ф. Валеевой выделена тенденция развития методов решения задач упаковки, которые развиваются в двух направлениях. Для первого характерно то, что поиск локально-оптимальных решений ведется в некоторой окрестности исходного решения с применением декодеров -алгоритмов, которые по закодированному решению восстанавливают эскиз упаковки. Другим направлением является разработка конструктивных методов, имеющих дело с покомпонентным построением упаковки: к частично построенной упаковке добавляется новый компонент до тех пор, пока она не будет построена полностью.

В большинстве работ в области раскроя-упаковки рассматриваются вопросы решения задач только прямоугольного раскроя. Для сравнения эффективности различных методов на однотипном классе задач определяют коэффициент раскроя. Для задачи двухмерной упаковки - это процентное отношение суммарной площади всех размещенных предметов к площади затраченного материала. Однако важным вопросом при выборе того или иного метода остается время решения, которое в виду МР-полноты и большой размерности задач, может быть значительным.

Для решения задач трехмерной упаковки используют, в основном, эвристические подходы. Большинство из них базируется на декомпозиции исходной задачи и сведению ее к задачам меньшей размерности путем разбиения на слои и заполнением каждого слоя какой-либо эвристикой. Некоторые алгоритмы используют двухфазные процедуры. На первой фазе происходит упаковка коробок в слои, на второй - процесс обмена коробок внутри слоя для улучшения локального решения. Разбиение параллелепипеда на блоки (слои), с одной стороны, облегчает решение, однако это не гарантирует плотную упаковку.

Важным вопросом для получения более плотной упаковки и грузовой стабильности является вопрос объединения пустот, которые образуются как внутри слоя, так и между ними. Кроме того, время решения задач трехмерной упаковки, за счет улучшения локального решения внутри каждого выделенного слоя последовательными методами приводит к большим временным затратам.

Основы общей методики решения математических задач в нейросетевом логическом базисе изложены А.И. Галушкиным (2000).

Для решения оптимизационных задач используют различные нейросетевые парадигмы, одной из которых является нейронная сеть Хопфилда. Этот подход основан на построении энергетической функции для прикладной задачи, которую удалось перевести на нейросетевое описание. Особенность подхода Хопфилда состоит в том, что нейронная сеть для конкретной задачи может быть создана без обучающих итераций. Суть общего подхода к решению задач комбинаторной оптимизации, основанного на использовании нейронных сетей Хопфилда, состоит в конструировании некоторой функции, вид которой соответствовал бы функции энергии общего вида. В результате сравнения «сконструированг.ой» функции энергии сети и функции энергии общего вида определяются искомая матрица

весовых коэффициентов сети п все остальные неизвестные константы. Определение функции энергии сети и ее коэффициентов не является тривиальным и требуется дальнейшая настройка параметров сети.

Цель работы состоит в разработке модели и высокопроизводительных методов решения задач двух (прямоугольного) и трехмерного (параллелегшпедного) ортогонального раскроя-упаковки с применением конструктивных и нейросетевых подходов.

В рамках цели решаются следующие задачи:

1. Проанализировать известные методы решения задач раскроя-упаковки и наметить пути их совершенствования.

2. Разработать алгоритмы для решения задач двух и трехмерного ортогонального раскроя и упаковки.

3. Применить общий метод синтеза нейронных сетей для решения задач комбинаторной оптимизации к задаче раскроя-упаковки.

4. Применить аппарат нейронных сетей для нахождения нижних границ решения задач раскроя-упаковки.

5. Провести серии экспериментов и проанализировать полученные результаты.

6. Реализовать теоретические результаты в виде алгоритмов и прикладного программного обеспечения, пригодных для их практического использования.

Методы исследования.

Результаты исследований, выполненных в работе, базируются на методах исследования операций, теории нейронных сетей, принципах модульного и структурного программирования. Для анализа эффективности предложенных методов проведены численные эксперименты.

На защиту выносятся:

1. Математические модели трех, двух и одномерного ортогонального раскроя-упаковки, включающие в себя учет ряда ограничений, а также минимизацию времени решения задачи.

2. Конструктивный метод плоскостей, предусматривающий непосредственное решение задач двух и трехмерного ортогонального раскроя-упаковки.

3. Алгоритмы формирования безотходных двух и трехмерных упаковок, обеспечивающие получение приоритетных списков для заданного количества объектов.

4. Нейросетевое представление задачи раскроя-упаковки в терминах энергетической функции Хопфилда.

5. Подход к определению нижних границ решения задачи раскроя-упаковки с помощью сигмоидных нейронных сетей.

Научная новизна работы:

1. Разработаны математические модели и методы решения задач двух и трехмерного ортогонального раскроя-упаковки.

2. Разработаны алгоритмы формирования двух и трехмерных

безотходных упаковок.

3. Задача раскроя-упаковки представлена в нейросетевом описании в терминах энергетической функции Хопфилда.

4. Разработан подход к определению нижних границ решения задач раскроя-упаковки с использованием сигмоидных нейронных сетей.

Практическая ценность работы:

¡.Разработаны модели п-мерной {п = 1, 2, 3) ортогональной упаковки-раскроя.

2. Разработаны высокоэффективные алгоритмы решения задач двух и трехмерного раскроя-упаковки, позволяющие быстро строить карты раскроя с коэффициентом раскроя, в среднем, от 85%.

Достоверность полученных результатов диссертации подтверждается обоснованием построенных моделей «-мерной упаковки (п = 1, 2, 3); сравнительным анализом существующих и предложенных подходов к решению поставленной задачи; результатами экспериментальных данных.

Реализация результатов работы. В настоящее время результаты исследования и разработок используются ГОУ ВПО «Сибирский государственный технологический университет», логистической компанией «Транс-Бизнес», что подтверждается соответствующими актами о внедрении.

Апробация работы и публикации.

Результаты работы, а также отдельные ее разделы были представлены на конференциях и семинарах, основными из которых являются: Всероссийская научно-практическая конференция «Лесной и химический комплексы -проблемы и решения (экологические аспекты)», Красноярск, 2004, 2007; Семинар «Новые информационные технологии», Москва, МГИЭМ, 2005; Всероссийская научно-техническая конференция «Нейроинформатика -2005», Москва, МИФИ, 2005; IV, V Всесибирский конгресс женщин -математиков, Красноярск, 2006, 2008; IX Всероссийский семинар «Моделирование неравновесных систем», Красноярск, ИВМ СО РАН, 2006; IV Международная научно-техническая конференция «Искусственный интеллект в XXI веке. Решения в условиях неопределенности», Пенза, 2006; III Всероссийская научно-практическая конференция «Компьютерная интеграция производства и ИПИ технологии», Оренбург, 2007; X Всероссийская конференция «Проблемы информатизации региона», Красноярск, 2007; Всероссийская научная конференция «Модели и методы обработки изображений», Красноярск, 2007; VI Международная научно-техническая конференция «Материалы и технологии XXI века», Пенза, 2008.

Публикации. Основные результаты работы опубликованы в 12 печатных работах, (из них 2 статьи в изданиях по списку ВАК), 1 свидетельство об официальной регистрации программ для ЭВМ.

Структура и объем диссертации.

Диссертация состоит из введения, 4 глав, заключения и списка использованных источников. Основное содержание работы изложено на 133 страницах текста, содержит 29 рисунков, 20 таблиц. Список используемых источников включает 183 наименования.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы исследования в области задач упаковки и раскроя. Сформулированы цель работы и решаемые в ней задачи, представлена научная новизна и практическая значимость вынесенных на защиту результатов.

В первой главе приведен обзор многообразия задач раскроя-упаковки и выделен класс задач, решаемых в рамках диссертационной работы. Приведены постановки наиболее известных задач «-мерного ортогонального раскроя-упаковки (и = 1, 2, 3). Описаны математические модели, приведен обзор работ и методов решения задач раскроя-упаковки.

Описано применение нейронных сетей для решения прикладных задач. Приведены достоинства и недостатки использования нейросетевой технологии. Определен класс нейронных сетей для решения задач комбинаторной оптимизации. Выявлен круг нерешенных задач.

Во второй главе приведены модели задач ортогонального раскроя-упаковки, описан метод плоскостей, а также алгоритмы формирования безотходных двух и трехмерных упаковок.

В диссертационной работе, в качестве основной, представлена модель трехмерной (параллелепипедцой) упаковки. Ее основное отличие от других моделей раскроя-упаковки - учет ряда ограничений, а также минимизация времени решения задачи.

Входная информация для задач параллелепипедной упаковки в общем виде может быть задана следующим образом:

<IV, и //, к, и, М, IV, /, /;, т, Ъ, £, у, g, У>, где (IV;, \У2,..„ Щ - ширина, 1= (¿,, 12.....Ц) - длина, Н = (Н,, Н2,..., //^

- высота параллелепипедов; к- количество параллелепипедов; и = (;//, и2,..., г<*) - количество параллелепипедов определенного вида; М - (Л//, М2.....ЛД)

- предельно допустимая масса параллелепипедов; № = (к/, IV;,..., м>„(/) -

ширина, / = /?,..., /,„) - длина, Л = (И/, ..... Ит) - высота коробок; ;;; -

количество типов коробок; Ь = Ъ2, ...,Ьт) - количество коробок определенного типа; е - признак направления: £ = 1, если объекты можно поворачивать, £ = 0 в противном случае; у - признак гильотинности: у = 1, если задачу решают с учетом признака гильотинности, и полагают равным О

в противном случае; g - (£/. g2..... д,„) - масса объектов; V - набор

технологических ограничений; с.£ии - общее количество

параллелепипедов и коробок, соответственно.

Выходной информацией является карта раскроя, представленная в виде следующего набора:

<П, X. У, г, Р, £>,

где П - преобразованный список коробок; Х= (Х], х2.....хп), У'= (у/, V;.....у„), 2

=(2/. г;..... 2„) - векторы минимальных координат коробок; Р ~ номера

заполненных параллелепипедов (р1(„, - номер параллелепипеда с, в который

упакован н-й объект); Е = (е/, е2..... е„) - признаки поворота коробок,

значение которых изменяется от 1 доб.

Зададим к - коэффициент раскроя (процентное отношение суммарного объема всех упакованных объектов к занятому объему), а т - время решения задачи.

Если задан параллелепипед неограниченной длины (L = оо), необходимо найти такое отображение

< П, X, У, Z, Р, Е> = Q. (<W, L. Н, к, и, М, w, 1, h, т, b, s, у, g, К>), (1)

L—> min k~> 100 t —» III in

которое преобразует входные данные в выходные, причем соблюдаются условия ортогональности и неперекрытия объектов.

Таким образом, требуется на множестве допустимых упаковок за минимальное время и с максимальным коэффициентом раскроя, учитывая ограничения по массе и технологические ограничения, минимизировать длину занятой части параллелепипеда.

Для задачи с фиксированным сторонами параллелепипедов, необходимо найти их минимальное количество S, т.е. к (1) добавляется еще одно условие:

S min Sj.

На данную систему оказывают влияние следующие факторы:

•способ (метод) решения задачи;

• приоритетный список (последовательность объектов);

• параметры оптимизации.

Метод плоскостей для решения трехмерных задач раскроя-упаковки.

Особенностями метода являются:

- непосредственное решение задач, а не сведение их к задачам меньшей размерности;

- использование как слойной, так и бесслойной стратегий;

- заполнение по, так называемым, приоритетным осям;

- анализ пустот и рассмотрение способов их объединения;

- допускается использование не одного, а нескольких параллелепипедов.

Слойная стратегия. Метод плоскостей, как и большинство методов,

основан на понятии пустого места - области параллелепипеда без коробок, упакованных внутри. Первая коробка определяет слой. Поэтому, алгоритм оценивает все виды коробок и их ориентации, чтобы открыть новый слой. Допусти, что выбрано приоритетное заполнение по оси Z. Как только первая коробка помещена в параллелепипед, она автоматически формирует слой, который будет заполняться по высоте. В зависимости от размеров коробки и параллелепипеда все пространство разбивается на параллелепипедные области.

Для описания размеров пустых областей используются координаты: х/.у/, у2. г/. 2: . а также флаг: 0 - область не заполнена: 1 - область полностью заполнена; -1 - игнорировать при заполнении данного слоя; -2 -игнорировать полностью. Запоминать значение координаты л.-, не

целесообразно, т.к. для случая слойной стратегии она определяется длиной слоя, для бесслойной - это длина самого параллелепипеда.

Рисунок 1 - Разбиения на области, определяемые первой коробкой

Существует восемь случаев размещения коробки в пустую область. В каждом случае вновь образованные области пустот будут разбиваться на одну, две, три, ни одной.

Кроме сохранения файла с координатами пустых областей, динамически создается файл коробок, в котором содержится следующая информация:

- координаты коробок х/, х2, уи у2, ¿1, г? относительно параллелепипеда;

- номер коробки из первоначального приоритетного списка;

- номер слоя, в котором размещена коробка.

Когда алгоритм отмечает новое место, как «временно отключено», подключается процедура, которая пробует увеличить размер этого места, соединяя его со смежными, которые также были «временно отключены», либо заполнены не полностью. Предусмотрено четырнадцать вариантов, когда пустота может быть объединена с одной или двумя соседними.

С целью сокращения полного перебора вариантов решений в режим оптимизации включены следующие параметры:

• метод сортировки: без сортировки; по невозрастанию объема; по невозрастанию ширины; по невозрастанию массы; по невозрастанию удельного веса;

• шесть способов поворота коробок;

• шесть вариантов заполнения по приоритетным направлениям;

• использование как слойной, так и бесслойной стратегий.

После завершения цикла оптимизации будет выведена карта раскроя с максимальным значением коэффициента раскроя.

Бесслойная стратегия. Процедура с использованием метода без формирования слоев отличается от рассмотренной выше тем, что толщина слоя принимается равной длине параллелепипеда, т.е. отсутствует блок, отвечающий за формирование слоев.

Приведенный выше метод плоскостей с некоторыми доработками реализован и для решения задач двухмерной упаковки.

Для оценки эффективности разработанных методов и программного обеспечения многие авторы используют данные из электронной библиотеки (Ж-НЬгагу. Эта библиотека содержит, так называемые, безотходные примеры

только для задач двухмерной упаковки. Они разработаны Е. Hopper и содержат оптимальное значение длины занятой части полосы и оптимальный приоритетный список, отвечающий безотходной упаковке.

Алгоритм формирования безотходной двухмерной упаковки базируется на условии получения определенного количества п прямоугольников для заданных размеров листа.

Шаги алгоритма:

1) задать количество полос q на которые следует разбить лист;

2) для получившихся полос вычислить целое количество прямоугольников в каждой полосе, и разделить на два: р =[ n/(2q) ]\

3) задать случайным образом координаты правого верхнего угла р - 1 прямоугольников: по оси X случайным образом генерируется координата в диапазоне от 1 до Llq - Д, по оси У - от 1 до W - Д, где Д - случайная величина, введенная для устранения попадания на края полосы;

4) координаты последнего прямоугольника определяются остатком от незанятой части полосы по ширине и случайным числом по оси Х\

5)в связи с тем, что для первой полосы построена только половина прямоугольников, достроить прямоугольники до вертикальной линии, разделяющей полосы. Для устранения признака гильотинности при построении нового прямоугольника необходимо осуществлять сдвиг полосы на неопределенный шаг.

6) повторить шаги 3-5 для оставшихся полос.

На рисунке 2а приведено построение первых сгенерированных прямоугольников для q = 2, п = 20. Достроенные прямоугольники для первой полосы приведены на рисунке 26.

а) б)

Рисунок 2 - Формирование безотходной гильотинной двухмерной упаковки

В результате такого разбиения формируется последовательность заданного количества прямоугольников, отвечающего безотходной упаковке, с указанием их размеров I, при фиксированных значениях ширины \У и длины Ь листа.

Приведенный выше алгоритм может быть использован и для формирования безотходной трехмерной упаковки. Для этого следует также осуществить разбиение исходного параллелепипеда с заданными размерами (см. рисунок 3).

Рисунок 3 - Формирование безотходной трехмерной гильотинной упаковки

В третьей главе рассмотрено применение аппарата искусственных нейронных сетей к решению задач раскроя-упаковки.

Приведена обобщенная модель обработки данных с помощью нейронных сетей в нотации ШЕРО. Представлено формальное описание нулевой и первой групп операций при нейросетевом исследовании с помощью нейронных сетей Хопфилда. Задача раскроя-упаковки представлена в нейросетевом описании в терминах энергетической функции Хопфилда. Приведен вариант совместного использования программы-декодера и нейроимитатора для решения задачи раскроя-упаковки. На основе алгоритмов формирования безотходных упаковок обучены сигмоидные нейронные сети. Приведены тестовые данные определения нижних границ решения для задач двух и трехмерных упаковок.

Подход к определению совокупности прямоугольников, приводящей к минимизации занятой части полосы, для задачи двухмерного раскроя-упаковки с помощью нейронных сетей. На получение оптимального решения задачи раскроя-упаковки большое влияние оказывает начальный приоритетный список прямоугольников. Использование одного и того же метода на одной и той же группе предметов, но упорядоченных различными способами, как правило, приводит к получению различных решений. Поэтому важным вопросом является получение совокупности прямоугольников, позволяющих получить оптимальное или близкое к нему решение.

Приоритетный список прямоугольников может быть представлен в виде таблицы, в которой единица в строке, отвечающая данному прямоугольнику, определяет его номер в формируемом списке. Сопоставим клетке таблицы на пересечении строки Л'и столбца / нейрон 5Л„ принимающий значения {0,1}. Возбужденное состояние данного нейрона свидетельствует о том, что прямоугольник Xв список следует размещать в ;'-ю очередь.

Целевая функция Е задачи поиска оптимального размещения будет включать следующие слагаемые:

- Е] - в каждой строке имеется не больше одной единицы (каждый прямоугольник должен быть в списке только один раз);

- Е2 - в каждом столбце не больше одной единицы (под каждым номером должен быть только один уникальный прямоугольник);

- Е} - минимизация длины занятой части полосы.

Для построения третьего члена энергетической функции введем следующие допущения. Пусть используется уровневая упаковка и стратегия нижний-левый. Минимизация занятой части полосы будет только в том случае, если будет минимальна или равна нулю оставшаяся ширина между упакованными прямоугольниками и полосой. Таким образом, требуется минимизировать суммарные остатки от незанятой части ширины каждой из корзин. Будем полагать, что прямоугольники можно поворачивать. Тогда энергетическую функцию для задачи двухмерной упаковки можно записать в следующем виде:

* = у! I X * А + у I I X/.*.-. + 1.(1 I </,-, * )" ^ )•

Множители а, Д ;/ имеют смысл относительных весов слагаемых.

Используем следующий вид функции Ляпунова для сети Хопфилда:

1 -V 1 / у \ 1

Таким образом, значения весов и порогов для рассмотренной выше задачи можно представить в следующем виде:

= -а -<УХУ (1-5,. )-/?■<?,,•(!-£„ )-';■((/„ + ™г,)-№)г(\-б„).

=-уЫ.

Использование сигмондных нейронных сетей для определения нижних границ решения задач раскроя-упаковки. На основе тестовых данных, полученных с помощью безотходных двух и трехмерных алгоритмов, были проведены численные эксперименты по обучению сигмондных нейронных сетей в нейроимитаторе ЫеигоРго 0.25. Структура нейросети: три слоя, каждый из которых содержал по десять нейронов.

Количество прямоугольников/коробок изменялось в диапазоне от 20 до 100, количество примеров для каждой обучающей выборки было сгенерировано в два раза больше количества объектов. Было произведено обучение нейронных сетей, при этом количество правильно решенных примеров составило 100%. В таблице 1 приведены результаты тестирования для задач двухмерной упаковки.

Была исследована зависимость разброса длины и ширины в обучающих примерах на значение ошибки. Выявлено, что при подборе обучающей выборки следует установить фиксированным значение одной из граней полосы на основе известной, например, IV, а другое выбрать в диапазоне: /,„,,,, = 15, / IV; ¿тах = ¿„„„ + Срзнач(//), где Е5, - суммарная площадь всех прямоугольников, Срзнач(/,) - среднее значение длин прямоугольников.

Как обучающие, так и тестовые примеры были сгенерированы на основе безотходных упаковок. Однако известно, что изменение порядка следования прямоугольников приводит, как правило, к получению другой карты раскроя и, соответственно, длины занятой части полосы. В связи с этим для тестовой выборки случайным образом был изменен порядок следования прямоугольников. Было сгенерировано по 10 тестовых примеров для случая п = 20. Среднее значение ошибки составило 4.4 %.

Таблица 1 - Тестовые данные для задач двухмерной упаковки и полученные значения ошибок _______

№ Кол-во прямоугольников Диапазон изменения L Диапазон изменения IV Средняя j ошибка, % Средняя максимальная ошибка, %

1. 20 100-200 100-200 : 46.3 127.3

2. 20 100-300 100-300 ! 50.5 127.9

3. 20 278-288 278-288 ! 12.1 ji.j

4. 10 100-120 100 i 6.3 16.1

5. 10 400-440 400 ! 14.9 29.9

6. 40 400-440 400 1 14.0 32.8

7. 100 400-440 400 ¡ 13.4 30.5

При обучении сигмоидных нейронных сетей на основе трехмерных безотходных примеров наблюдались такие же тенденции, что и для задач двухмерных упаковок.

В четвертой главе представлены экспериментальные исследования эффективности разработанных конструктивных методов.

Для оценки эффективности решения задач двух и трехмерной упаковок методом плоскостей проведена серия расчетов на основе методики Г. Вешера. За основу разбиения взято следующее: нижнее ограничение длины предметов - v,, верхнее ограничение длины предметов v2 (v, -II' </, < \>, -W,

i =1.....п); нижнее ограничение ширины предметов vv'y, верхнее ограничение

ширины предметов us (н. И'< и-, < и , •((', /=/,..., и); нижнее ограничение высоты предметов //,, верхнее ограничение высоты предметов ij2 {nrW<n, <n2-W, i=h—, »)•

Серия Л«1. Целью данного эксперимента была проверка необходимости включения в оптимизацию разбиение на слои для разных групп предметов. Выполнены численные эксперименты, параметрами которых являлись: высота параллелепипеда Н = 150, его ширина W= 100; количество предметов п = 50, 100, 200, 250, 500, 1000. Предметы были отсортированы по классам: «мелкие» (V/, = 0.1, v2= 0.2; \vt = 0.1, w2 - 0.2; tji = 0.2, ц2 = 0.25), «средние» (v,= 0.2, vi= 0.4; wj = 0.2, w2 = 0.4: tj, = 0.2, tj2= 0.25) и «разнородные» (v, = 0.1, v?= 0.3; iv/= 0.1, iv? = 0.2; = 0.2, t]2= 0.25). Для каждого класса задач было сгенерированно по 10 тестовых примеров, усредненные значения коэффициентов раскроя приведены на рисунке 4.

Таким образом, при тестировании метода плоскостей для задач трехмерных упаковок на разной группе предметов было выявлена необходимость совместного использования как процедуры формирования слоя, так и бесслойной процедуры. Это позволяет формировать более плотную упаковку и, следовательно, повышает грузовую стабильность при решении реальных задач. Метод плоскостей показывает лучшие результаты при большом количестве и. в основном, «разнородных» предметов. Время

решения задачи на ПК (Celeron (R) CPU 3.2 GHz, 1Гб ОЗУ) от нескольких секунд до двух минут (для л — 1000).

Серия .\°2. Выполнены численные эксперименты для анализа различных методов решения задач трехмерной упаковки, параметрами которой являлись: длина параллелепипеда L = 150, его ширина W = 100; количество предметов п = 50, 100, 200, 250. Предметы были отсортированы по классам: «мелкие» (y¡, = 0.1, v¡= 0.2; \v¡ = 0.1. w2 — 0.2; tj¡ = 0.1, r¡2 = 0.25), «средние» (v/= 0.2, Vr= 0.1; W/ = 0.2, w2 = 0.25; ц, = 0.2, r¡2 = 0.25) и «разнородные» (v/, = 0.1, v2= 0.25; w, = 0.1. w2 = 0.2; r\¡ = 0.2, rj¡ = 0.25). Значения коэффициентов раскроя приведены в таблице 2.

: es Мелкие

Мелкие (со с ¡■Средние □ Средние (со О Разнородны« Разнородные (со

200 250 500

Рисунок 4 - Усредненные значения коэффициентов раскроя для задач трехмерной упаковки (на основе метода плоскостей)

Таким образом, метод плоскостей показывает лучшие результаты в классе «средних» и «разнородных» предметов.

Таблица 2

Значения коэффициентов раскроя для задач

Методы Мелкие предметы, % Средние предметы, % Разнородные предметы, %

МВА - Метод на основе бесслойного алгоритма 77 79 80

EABD - «Наивный» эволюционный алгоритм 74 78 76

GABD - Классический генетический алгоритм 76 77 75

SABD - Метод случайных перестановок- 73 74 76

Метод плоскостей 76 82 83

Серия Лё 3. Метод плоскостей для решения задач двухмерной упаковки

был протестированы с помощью безотходных примеров Е. Hopper на определение признака реставрации - способности метода восстанавливать карту раскроя по приоритетному списку. В тестовых примерах в качестве входной информации, кроме размеров прямоугольников и ширины полосы, подавался оптимальный (Опт.) и измененный (Изм.) список (см. таблицу 3). В измененном приоритетном списке случайным образом изменялся порядок следования предметов.

Выявлено, что метод плоскостей обладает свойством «реставрации», с его помощью по известному оптимальному приоритетному списку формируется оптимальная безотходная упаковка. В реальных условиях, в связи с отсутствием в методе схем полного перебора, при подаче измененного оптимального списка, он позволяет получить упаковку с коэффициентом раскроя более 90%.

Серия Л? 4. Целью данного эксперимента было сравнение метода плоскостей с алгоритмом рандомизированного динамического перебора (DSR) для решения задач прямоугольной упаковки. Были сгенерированы следующие классы задач для IV = 225: «малые» предметы (v;, = 0.05, v?= 0.1; W] = 0.1, и'2 = 0.15), «средние» предметы (vt, = 0.25, vv= 0.35; w, = 0.35, w2 = 0.45) и «малые и большие» предметы (v,. = 0.05, v3= 0.25; u>;= 0.05, ir> = 0.95). Для каждого класса задач сгенерировано по 10 тестовых примеров. Критерием оценок также выступал коэффициент раскроя к, значения которого приведены на рисунке 5.

Таблица 3 - Результаты решения безотходных задач Е. Hopper серии N и С

| Задачи \ п \ \ Среднее значение к, % ; Задач ! » и \ I Среднее значение к, %

Опт. Изм. Опт. Изм.

\ Nla-Nle ' 17 100 92.6 ci ; 16,17 100 96.0

! N2a - N2e I 25 100 92.7 С2 ! 25 100 95.4

! N3a- N3e : 29 100 94.1 СЗ : 28.29 100 93.8

I Via - N4e i 49 100 94.0 С4 ; 49 100 95.2

¡N5a-N5e i 73 100 94.9 С5 ! 73 100 97.1

] N6a - N6e , 97 100 96.7 С6 i 97 100 96.8

1 N7a - N7e ; 197 100 97.0 С7 196.197 100 96.6

-Малые • Средние Малые и большие

Рисунок 5 - Усредненные значения коэффициентов раскроя для задач двухмерной упаковки, полученные методом плоскостей

Согласно данным, приведенным А.Ф. Валеевой для такого же класса задач, значения коэффициентов раскроя, полученных методом БЭЯ, для класса «малых» предметов составляет 92 - 96%; «средних» - 98 - 100%; «малых и больших» - 93 - 95%. Таким образом, метод плоскостей показывает не худшие результаты для классов «малых» и «разнородных» («малых и больших») предметов.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ II ВЫВОДЫ

■ Разработаны математические модели и предложены методы решения задач раскроя-упаковки. Конструктивный метод плоскостей позволяет существенно повысить коэффициент раскроя и снизить время решения за счет использования эвристических подходов. Метод плоскостей обладает свойством реставрации и позволяет получить решение для задач большой размерности за приемлемое время. Алгоритмы формирования безотходных двух и трехмерных упаковок обеспечивают получение приоритетных списков для заданного количества объектов.

■ Задача упаковки представлена в нейросетевом описании в терминах энергетической функции Хопфилда. На основании сконструированной энергетической функции вычислены веса и пороги.

■ Для определения нижних границ решения задач раскроя-упаковки применен аппарат нейронных сетей. На основании разработанных безотходных алгоритмов обучены сигмоидные нейронные сети. Результаты тестовых выборок дают конечную оценку с приемлемой точностью.

■ Предложенные в работе эвристические подходы реализованы в виде прикладного программного обеспечения. Полученные в работе результаты используются в ГОУ ВПО «Сибирский государственный технологическом университете» и ГОУ СПО «Красноярский техникум информатики и вычислительной техники» в учебном процессе при выполнении практических, курсовых и дипломных работ, а также логистической компанией «Транс-Бизнес».

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Корчевская, О.В. О преимуществах комбинирования нейросетевого и традиционных подходов при решении дискретных и комбинаторных задач (на примере задачи раскроя) / О.В. Корчевская // Вестник КрасГАУ № 15, 2006.-С. 172-177.

2. Жуков, Л.А. Метод плоскостей: численный эксперимент для задач двух и трехмерной ортогональной упаковки / Л.А.Жуков, О.В. Корчевская // Информационные технологии, 2008. -№ 11. -С. 41-45.

3. Корчевская О.В., Получение нижних границ для задач двух и трехмерной ортогональной упаковки с помощью нейронных сетей, используя алгоритм безотходной упаковки / О.В Корчевская, Л.А. Жуков // Электронный журнал "Исследовано в России", 62, 2008. - С. 685-694, http: // zhurnal. аре, relarn.ru / articles'' 2008/062.pdf

4. Корчевская, О.В. Элементы формального описания технологии обработки данных с помощью нейронных сетей Хопфилда / О.В. Корчевская, J1.A. Жуков // Новые информационные технологии: сб. материалов восьмого семинара. - М.: МГИЭМ, 2005. - С.89-95.

5. Жуков, J1.А. О формализации непросетевой технологии решения прикладных задач на примере сетей с учителем и сетей Хопфилда / Л.А. Жуков, Н.В. Решетникова, О.В. Корчевская // Нейроинформатика - 2005: сб.

научн. тр. VII Всероссийской научно-технической конференции.- М.: МИФИ, 2005. - Ч. 1. - С. 68-75.

6. Жуков, Л. А. Особенности применения нейронных сетей Хопфилда для решения прикладных оптимизационных задач / Л. А. Жуков, О. В. Корчевская // Сибирский государственный технологиче'ский университет. -Красноярск, 2006.-44 с. - Деп. в ВИНИТИ 04.12.2006, № 1486 - В2006.

7. Корчевская, О.В. Однопроходный эвристический алгоритм для решения задачи двумерной ортогональной упаковки / О.В. Корчевская Н Искусственный интеллект в XXI веке. Решения в условиях неопределенности: Сб.ст. IV Международной научно - технической конференции. - Пенза, 2006. - С. 71 - 73.

8. Корчевская, О.В. Решение задачи двумерной упаковки в полубесконечную полосу с помощью метода профиля / О.В. Корчевская // Вестник КрасГАУ № 1. - Красноярский государственный аграрный университет, 2007. - С. 34-37.

9. Корчевская, О.В., Конструирование функции энергии сети для задачи ортогональной упаковки / О.В. Корчевская, Л.А.Жуков, А. В. Больсявичус // Компьютерная интеграция производства и ИПИ технологии: Сб. материалов III Всероссийской научно - практической конференции. - Оренбург: ИПК ГОУ ОГУ, 2007. - С. 352-357.

10. Корчевская, О.В. Решение задачи трехмерной упаковки методом профиля / О.В. Корчевская, Л.А. Жуков // V Всесибирский конгресс женщин - математиков: тез. докл. - Красноярск: Изд. РИО СибГТУ, 2007. - С. 58-60.

11. Корчевская, О.В. Обобщенная модель обработки данных с помощью нейронных сетей на примере задачи раскроя / упаковки / О.В. Корчевская, Л.А. Жуков // Альманах современной науки и образования. -Тамбов: Грамота, 2008. - № 1(8): Математика, физика, строительство, архитектура, технические науки и методика их преподавания. - С. 100-103.

12. Корчевская, О.В. Применение метода плоскостей для решения безотходных задач раскроя / упаковки Е. Hopper / О.В. Корчевская, Л.А. Жуков // Материалы и технологии XXI века: Сб.ст. VI Международной научно-технической конференции. - Пенза, 2008. - С. 147-149.

Корчевская Оксана Валериевна

КОНСТРУКТИВНЫЕ И НЕЙРОСЕТЕВЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ДВУХ И ТРЕХМЕРНОГО ОРТОГОНАЛЬНОГО РАСКРОЯ-

УПАКОВКИ

05.13.17 - Теоретические основы информатики Автореферат

Подписано в печать 6.12.2008г. Формат 60x84/16. Бумага писчая. Объем 1п.л. Тираж 100 экз. Заказ № 843 Отпечатано в Экспресс-Офсет 660062, г. Красноярск, ул. Крупской, 42.