Содержание к диссертации
Введение
Глава 1 Постановка, последовательные и параллелные методы решения зада ч ортогональной упаковки и раскроя . 13
1.1 Постановка и методы решения задач ортогональной упаковки и раскроя... 13
1.1.1 Задачи упаковки и раскроя 13
1.1.2 Обзор методов решения задач линейного, прямоугольного и параллелепипедного раскроя-упаковки 21
1.1.3 Формирование приоритетного списка 33
1.2 Использование искусственных нейронных сетей для решения задач комбинаторной оптимизации 35
1.2.1 Нейронные сети как универсальные аппроксимирующие устройства 35
1.2.2 Формализация нейросетевой технологии 39
1.2.3 Общие сведения о нейронных сетях Хопфнлда 41
1.2.4 Применение нейронной сети Хопфнлда для решения задач комбинаторной оптимизации 43
Глава 2 Информационные модели задач раскроя-упаковки 47
2.1 Обобщенная схема решения задач ортогонального раскроя-упаковки 47
2.2 Модели задач одно, двух и трехмерного раскроя-упаковки 51
2.3 Модель обработки данных с помощью нейронных сетей 56
2.4 Формальное описание нейронной сети Хопфнлда 61
Глава 3 Конструктивные методы решения трех и двухмерных задач раскроя-упаковки . 65
3.1 Безотходные алгоритмы для задач раскроя-упаковки 65
3.1.1 Алгоритм формирования безотходных двухмерных упаковок 66
3.1.2 Алгоритм формирования безотходных трехмерных упаковок 68
3.2 Метод плоскостей 71
3.2.1 Метод плоскостей для решения трехмерных задач раскроя- упаковки 71
3.2.2 Метод плоскостей для решения двухмерных задач раскроя-упаковки84
3.3 Численный эксперимент 91
3.3.1 Численный эксперимент для задач трехмерного ортогонального раскроя-упаковки 91
3.3.2 Численный эксперимент для задач двухмерного ортогонального раскроя-упаковки 98
Глава 4 Применение аппарата искусственных нейронных сетей к решению задач раскроя-упаковки. 108
4.1 Подход к определению совокупности прямоугольников, приводящей к минимизации занятой части полосы, для задачи двухмерного раскроя-упаковки с помощью нейронных сетей Хопфилда 108
4.2 Использование сигмоидных нейронных сетей для определения нижних границ решения задач раскроя-упаковки 115
Заключение 122
Литература 127
- Использование искусственных нейронных сетей для решения задач комбинаторной оптимизации
- Модели задач одно, двух и трехмерного раскроя-упаковки
- Метод плоскостей для решения трехмерных задач раскроя- упаковки
- Использование сигмоидных нейронных сетей для определения нижних границ решения задач раскроя-упаковки
Введение к работе
Для современного периода производства характерно использование технологических процессов и методов, минимизирующих потери, что особенно актуально на данном этапе развития рыночных отношений в России.
Перед большинством хозяйствующих субъектов стоит задача получить преимущество в конкурентной борьбе за счет снижения уровня материальных затрат и использования новых перспективных технологий. Это достигается путем внедрения в производственную практику эффективных экономико-математических методов. Применение таких методов позволяет оптимизировать материальные потоки на стадии производства и обращения продукции, ускорить оборачиваемость оборотного капитала организации, улучшить финансовые результаты и повысить показатели рентабельности.
В один из классов задач комбинаторной оптимизации, достаточно часто встречающийся в реальных производственных условиях, выделены задачи раскроя и упаковки. Их объединяет необходимость установления определенного соответствия между двумя группами, как правило, больших и малых объектов.
Задачи раскроя-упаковки имеют различное прикладное толкование. Наиболее часто встречающимися задачами являются ортогональная упаковка и раскрой, где в качестве малых объектов выступают заготовки прямоугольной формы - прямоугольники или ящики различных размеров, а крупных - материал, поступающий в виде полос, рулонов, прямоугольных листов, стержней или контейнеров различной вместимости.
Эти задачи представляют собой проблему как теоретического, так и практического плана, которая в течение последних десятилетий
4 привлекает внимание многих исследователей и производственников. Причина растущего интереса к задачам раскроя-упаковки состоит в их разнообразии, сложности и широкой применимости результатов.
Задачи раскроя-упаковки относят к классу NP-трудных задач комбинаторной оптимизации. Это означает, что не существует алгоритмов полиномиальной сложности для поиска оптимального решения, точный результат в общем случае может быть получен только за экспоненциальное время.
Классические методы линейного программирования для решения задач упаковки и раскроя в условиях единичного производства трудно применимы. Кроме того, задачи раскроя в условиях единичного производства возникают при индивидуальном производстве и, как правило, из дорогостоящих материалов.
Точные и псевдоточные методы решения, так или иначе, связаны с методом ветвей и границ. Для их применения необходимо знать нижние границы решения или иметь алгоритм их вычисления. Однако точную нижнюю границу решения пока найти не удалось. Это ограничивает применение как точных, так и приближенных методов, основанных на методе ветвей и границ.
Из-за значительных затрат вычислительного времени и необходимости учета технологических ограничений для решения подобного класса задач, как правило, используют приближенные методы и эвристики.
Фундаментальные научные разработки в области решения задач раскроя-упаковки принадлежат Л.В. Канторовичу и В.А. Залгаллеру (1950). Результаты дальнейших исследований в этой области отражены в работах Э.А. Мухачевой (1979), Е.П. Бороновского (1967), А.Ф. Валеевой (2000), И.П. Норенкова (1999), Ю.А. Кочетова (2000), И.В. Романовского (1977), А.С. Филипповой (1999), В.М. Картак (2004); за рубежом - Р. Gilmore & R. Gomory (1965), G. Scheithauer & J. Terno (1970), H. Dyckhoff
5 (1990), A. Bortfeldt (1998) и др.
Существуют различные методы решения задач ортогонального раскроя-упаковки. В большинстве работ в этой области рассмотрены вопросы решения задач прямоугольного раскроя.
Особый интерес представляют унифицированные методы, позволяющие на общей теоретической основе создать математическое обеспечение для решения линейных (одномерных), прямоугольных (двухмерных) и параллелепипедных (трехмерных) задач раскроя-упаковки. Такой подход приведен в работах А.Ф. Валеевой: на базе модифицированного метода решения задачи 0-1 рюкзак создано инвариантное математическое обеспечение для решения задач и-мерной (п = 1, 2, 3) упаковки.
Для решения задач трехмерной упаковки используют, в основном, эвристические подходы. Большинство из них базируется на декомпозиции исходной задачи и сведении ее к задачам меньшей размерности путем разбиения на слои и заполнением каждого слоя какой-либо эвристикой.
В работах Э.А. Мухачевой и А.Ф. Валеевой выделена тенденция развития методов решения задач упаковки, которые развиваются в двух направлениях. Для первого характерно то, что поиск локально-оптимальных решений ведется в некоторой окрестности исходного решения с применением декодеров — алгоритмов, которые по закодированному решению восстанавливают эскиз упаковки. Другим направлением является разработка конструктивных методов, имеющих дело с покомпонентным построением упаковки: к частично построенной упаковке добавляется новый компонент до тех пор, пока она не будет построена полностью.
На данный момент существует много методов решения задач линейного, прямоугольного и параллелепипедного раскроя и упаковки, что затрудняет их классификацию и выбор при решении реальных задач.
В последнее время при решении прикладных задач комбинаторной
оптимизации ряд исследователей, столкнувшихся на практике с ограниченными возможностями последовательных машин, используют нейросетевые технологии.
Основы общей методики решения математических задач в нейросетевом логическом базисе изложены А.И. Галушкиным (2000).
Для решения оптимизационных задач используют различные нейросетевые парадигмы, одной из которых является нейронная сеть Хопфилда. Этот подход основан на построении энергетической функции для прикладной задачи, которую удалось перевести на неиросетевое описание.
Особенность подхода Хопфилда состоит в том, что нейронная сеть для конкретной задачи может быть создана без обучающих итераций. Суть общего подхода к решению задач комбинаторной оптимизации, основанного на использовании нейронных сетей Хопфилда, состоит в конструировании в соответствии с условиями задачи некоторой функции, вид которой соответствовал бы функции энергии общего вида. В результате сравнения «сконструированной» функции энергии сети и функции энергии общего вида определяются искомая матрица весовых коэффициентов сети и все остальные неизвестные константы.
Важным вопросом при разработке модели нейросети Хопфилда и дальнейшем моделировании работы системы является вопрос выбора коэффициентов Лагранжа. В настоящее время не существует формальной методики их определения. В связи с этим при построении энергетической функции в ряде работ используют один, два или более множителей Лагранжа, регулирующих строгость соблюдения дополнительных условий в конечном решении. Определение функции энергии сети и коэффициентов Лагранжа не является тривиальным и требуется настройка параметров сети.
Таким образом, проблема разработки рационального расчета, направленная на унификацию методов в области задач упаковки и раскроя,
7 является актуальной и своевременной.
Цель работы состоит в разработке информационных моделей и
высокопроизводительных методов решения задач двух (прямоугольного) и
трехмерного (параллелепипедного) ортогонального раскроя-упаковки с
применением конструктивных и нейросетевых подходов.
В рамках цели решаются следующие задачи:
1. Проанализировать известные постановки и методы решения
задач раскроя-упаковки и наметить пути их совершенствования.
Разработать алгоритмы для решения задач двух и трехмерного ортогонального раскроя и упаковки.
Применить аппарат нейронных сетей для решения задач раскроя-упаковки.
Провести серии экспериментов и проанализировать полученные результаты.
Реализовать теоретические результаты в виде алгоритмов и прикладного программного обеспечения.
Методы исследования.
Результаты исследований, выполненных в работе, базируются на методах исследования операций, теории нейронных сетей, принципах модульного и структурного программирования. Для анализа эффективности предложенных методов проведены численные эксперименты.
На защиту выносятся:
Информационные модели задач раскроя-упаковки.
Конструктивный метод плоскостей, предполагающий непосредственное решение задач двух и трехмерного ортогонального раскроя-упаковки.
Алгоритмы формирования безотходных двух и трехмерных упаковок, обеспечивающие получение приоритетных списков для заданного количества объектов.
8 4. Подход к определению нижних границ решения задачи раскроя-упаковки с помощью сигмоидных нейронных сетей.
Научная новизна работы:
Разработаны методы решения задач двух и трехмерного ортогонального раскроя-упаковки.
Разработаны алгоритмы формирования двух и трехмерных безотходных упаковок.
Разработан подход к определению нижних границ решения задач раскроя-упаковки с использованием сигмоидных нейронных сетей.
Практическая ценность работы:
Приведены информационные модели задач «-мерной {п = 1, 2, 3) ортогональной упаковки-раскроя.
Разработаны высокоэффективные алгоритмы решения задач двух и трехмерного раскроя-упаковки, позволяющие быстро строить карты раскроя с коэффициентом раскроя, в среднем, от 85%.
Достоверность полученных результатов диссертации
подтверждается сравнительным анализом существующих подходов к решению поставленной задачи и результатами экспериментальных данных.
Реализация результатов работы. В настоящее время результаты исследования и разработок используются несколькими организациями, что подтверждается соответствующими актами о внедрении: ГОУ ВПО «Сибирский государственный технологический университет», логистической компанией «Транс-Бизнес».
9 Апробация работы и публикации.
Результаты работы, а также отдельные ее разделы были
представлены на конференциях и семинарах, основными из которых
являются:
Всероссийская научно-практическая конференция «Лесной и химический комплексы - проблемы и решения (экологические аспекты)», Красноярск, 2004, 2007;
Семинар «Новые информационные технологии», Москва, МГИЭМ, 2005;
Всероссийская научно-техническая конференция «Нейроинформатика - 2005», Москва, МИФИ, 2005;
IV, V Всесибирский конгресс женщин-математиков, Красноярск, 2006, 2008;
IX Всероссийский семинар «Моделирование неравновесных систем», Красноярск, ИВМ СО РАН, 2006;
IV Международная научно-техническая конференция «Искусственный интеллект в XXI веке. Решения в условиях неопределенности», Пенза, 2006;
III Всероссийская научно-практическая конференция «Компьютерная интеграция производства и ИЛИ технологии», Оренбург, 2007;
X Всероссийская конференция «Проблемы информатизации региона», Красноярск, 2007;
Всероссийская научная конференция «Модели и методы обработки изображений», Красноярск, 2007;
VI Международная научно-техническая конференция «Материалы и технологии XXI века», Пенза, 2008.
10 Публикации.
Основные результаты работы опубликованы в 12 печатных работах (из них 2 статьи в изданиях по списку ВАК), 1 свидетельство об официальной регистрации программы для ЭВМ.
Структура и объем диссертации.
Диссертация состоит из введения, 4 глав, заключения и списка использованных источников. Основное содержание работы изложено на 126 страницах текста, содержит 29 рисунков, 20 таблиц. Список используемых источников включает 183 наименования.
Основное содержание работы.
Во введении обоснована актуальность темы исследования в области задач упаковки и раскроя. Сформулированы цель работы и решаемые в ней задачи, представлена научная новизна и практическая значимость вынесенных на защиту результатов.
В первой главе приведен обзор многообразия задач раскроя-упаковки и выделен класс задач, решаемых в рамках диссертационной работы. Приведены постановки наиболее известных задач «-мерного ортогонального раскроя-упаковки (п = 1, 2, 3), приведен обзор работ и методов решения задач раскроя-упаковки.
Описано применение нейронных сетей для решения прикладных задач. Приведены достоинства и недостатки использования нейросетевой технологии. Определен класс нейронных сетей для решения задач комбинаторной оптимизации. Выявлен круг нерешенных задач.
Во второй главе приведены информационные модели задач раскроя-упаковки.
В настоящее время существуют различные представления п-
мерных задач (п = 1, 2, 3) раскроя-упаковки. В диссертационной работе, в
качестве основных, представлены модели трехмерной
(параллелепипедной) упаковки для случаев с неограниченной длиной
параллелепипеда и упаковки в несколько параллелепипедов. Их основные отличия - учет ряда ограничений, а также минимизация времени решения задачи.
В работе приведена обобщенная модель обработки данных с помощью нейронных сетей в нотации IDEF0. Это позволяет наглядно представить и определить процессы обработки данных с помощью нейронных сетей при решении оптимизационных задач.
Представлено формальное описание 0 и 1-й групп операций при нейросетевом исследовании с помощью нейронных сетей Хопфилда. Такой подход в общем случае позволяет формализовать технологию работы пользователя при нейросетевом исследовании.
В третьей главе описан метод плоскостей, а также алгоритмы формирования безотходных двух и трехмерных упаковок.
В работе представлен новый метод решения задач прямоугольного и параллелепипедного раскроя-упаковки - метод плоскостей.
Особенностями метода плоскостей являются:
непосредственное решение задач двух и трехмерного раскроя-упаковки;
использование как слойной, так и бесслойной стратегий;
заполнение по, так называемым, приоритетным осям;
анализ пустот, по мере их появления, и рассмотрение способов их объединения;
допускается использование не одного, а нескольких параллелепипедов (листов).
Представленные алгоритмы формирования безотходных двух и трехмерных упаковок базируются на условии получения определенного количества и размеров прямоугольников (коробок) для заданных размеров листа (параллелепипеда).
Представлены экспериментальные исследования эффективности разработанных конструктивных методов и результаты их внедрения в виде
12 программного обеспечения.
Для оценки эффективности решения задач двух и трехмерного ортогонального раскроя-упаковки методом плоскостей проведена серия расчетов на основе методики Г. Вешера. За основу разбиения на различные классы предметов для задачи трехмерной упаковки взято: нижнее ограничение длины предметов - V/, верхнее ограничение длины предметов v2 (v, W < I, < v2 W, і ~1,..., n); нижнее ограничение ширины предметов Wj,
верхнее ограничение ширины предметов W2 (w, -W
Для сравнения результатов, полученных на основе одних и тех же тестовых данных, с другими методами решения задач раскроя-упаковки, кроме методики Г. Вешера, были использованы безотходные примеры Е. Hopper.
В четвертой главе рассмотрено применение аппарата искусственных нейронных сетей к решению задач раскроя-упаковки.
Задача раскроя-упаковки представлена в нейросетевом описании в терминах энергетической функции Хопфилда. Приведен вариант совместного использования программы-декодера и нейроимитатора для решения задачи раскроя-упаковки.
На основе алгоритмов формирования безотходных примеров проведено обучение сигмоидных нейронных сетей. Приведены тестовые данные, которые позволяют сделать вывод о целесообразности использования нейронных сетей для определения нижних границ решения задач двух и трехмерного ортогонального раскроя-упаковки.
Использование искусственных нейронных сетей для решения задач комбинаторной оптимизации
Биологические нейроны и нейронные сети стали прототипами при создании искусственных нейронных сетей. За два года до появления известной статьи фон Неймана была сделана попытка использования процессов, происходящих в нервных системах, для выработки новых технологических решений. Значительная часть аппарата нейронных сетей заимствована из разделов математики, среди которых: методы оптимизации, численные методы, математическая статистика и др. Для разработки новых методов и алгоритмов используют специальные способы описания архитектур и методов обучения. Самые распространенные элементы архитектур нейронных сетей - синапс, сумматор, нелинейный элемент, точка ветвления. Формальный нейрон, согласно [79], чаще всего состоит из входного сумматора, нелинейного преобразователя и точки ветвления на выходе (рисунок 7). Перечисленные выше простые элементы нейронных сетей могут быть объединены в более сложные элементы: блок, слой, колонка. Чаще всего используется слой.
Слой - набор нейронов или сумматоров, (псеводо) одновременно воспринимающих входную информацию и (псеводо) одновременно генерирующих выходные сигналы. Выделяют несколько видов слоев - входной, выходной, а также внутренний рабочий слой, который не получает входных сигналов и не генерирует выходных. Чаще всего используют от 1 до 3 скрытых слоев. Функция активации нейронов (характеристическая функция) (р, преобразующая выходной сигнал сумматора, может быть одной и той же для всех нейронов сети. В этом случае сеть называют однородной (гомогенной). Если же р зависит еще от одного или нескольких параметров, значения которых меняются от нейрона к нейрону, то сеть называют неоднородной (гетерогенной). Если функция активации имеет сигмоидный вид, то сеть называют сигмоидной. Искусственные нейронные сети после предъявления входных сигналов (возможно, вместе с требуемыми выходами) самонастраиваются, чтобы обеспечивать требуемую реакцию, т.е. могут менять свое поведение в зависимости от внешней среды. Некоторые из искусственных нейронных сетей обладают способностью извлекать сущность из входных сигналов, т.е. порождать то, чему сеть не обучали. Успех применения нейронных сетей в различных областях науки и техники связан с их универсальностью. В работе [111] приведены некоторые причины, по которым явное преимущество нейрокомпьютеров неоспоримо: нейрокомпьютерные технологии предлагают способы решения многих задач, неважно, что специализированные алгоритмы лучше решат один класс задач. Нейрокомпьютер способен решить многие и почти не хуже; вместо программирования - обучение.
Необходимо только сформировать обучающую выборку, которая в полной мере будет содержать скрытые закономерности исследуемой задачи; нейрокомпьютеры особенно эффективны там, где нужно подобие человеческой интуиции, когда трудно составить явный алгоритм решения. Одно из основных преимуществ нейрокомпьютеров - это возможность организовать параллельные вычисления, что особенно актуально для решения NP-полных задач. Задачи, решаемые с использованием нейроинформатики, следуя [128], можно условно классифицировать: задачи, имеющие известный и определенный набор условий, на основании которого необходимо получить четкий, точный, недвусмысленный ответ по известному определенному алгоритму; задачи, в которых не представляется возможным учесть все реально имеющиеся условия, от которых зависит ответ, а можно лишь выделить приблизительный набор наиболее важных условий. Для решения задач первой группы, как правило, с большим успехом применяют традиционные алгоритмы. Существует мнение [111], что в этом случае нейросетевые методы будут априорно хуже решать их. Наиболее важным исключением является случай, когда алгоритм вычисления ответа слишком большой и громоздкий, следовательно, время на решение конкретной задачи не удовлетворяет практическим требованиям.
При решении задач второй группы применение нейротехнологий оправдано при выполнении двух основных условий [111]: во-первых, при наличии универсального типа архитектуры и единого универсального алгоритма обучения (отсутствует необходимость в доработке метода для каждого типа задач); во-вторых, при наличии обучающей выборки, на основании которой проводится обучение нейронных сетей. Разработка методов решения оптимизационных задач с помощью нейронных сетей осуществляется уже несколько десятилетий. Учеными предложено огромное количество алгоритмов, способов проверки гипотез (при разработке экспертных систем). Как правило, метод хорошо работает только на той группе объектов, на которой проводились исследования; создать универсальный алгоритм невозможно. При использовании метода для другой подобной группы объектов его почти всегда приходится полностью переконструировать [115].
Модели задач одно, двух и трехмерного раскроя-упаковки
Для построения системы, решающей в целом задачу обработки данных с помощью нейронных сетей, необходимо определить ее границы, исходные данные и требуемый результат. С учетом выбора различных парадигм для решения прикладных задач предлагается обобщенная модель обработки данных с помощью нейронных сетей в нотации IDEF0, приведенная на рисунке 11. На рисунке 12 представлена декомпозиция контекстной диаграммы. Используя методологию системного анализа, необходимо выделить составные части проблемы и формализовать их, наметить пути решения (в том числе с использованием математических методов). Постановка задачи - это первичное описание поставленной задачи обработки данных. Практически все известные подходы к решению задач с помощью нейронных сетей связаны с выбором и анализом некоторых частных видов структур с хорошо изученными и определенными видами сетей с доказанными свойствами устойчивости и сходимости, так называемых, нейросетевых парадигм. Это упрощает работу и стандартизирует применяемые процедуры, однако не позволяет учитывать особенности конкретных задач. Поэтому при построении нейронной сети, возможно, Любую задачу можно сформулировать различными способами и в различных терминах. Выбор нейросетевой парадигмы предполагает, что исходная постановка задачи должна быть преобразована в нейросетевое описание. На этом шаге использование нейросетей сводится к применению известных или модифицированию существующих структур, предназначенных для описания определенного класса задач, адекватных поставленной проблеме.
В ходе нейросетевого решения задачи, необходимо задать алгоритмы настройки нейросетевых параметров. Например, весовые коэффициенты определяются в зависимости от задачи: аналитически из нейросетевой интерпретации задачи, или с помощью специальных методов, применив процедуру настройки весовых коэффициентов. На следующем этапе необходимо осуществить передачу всех параметров в сеть и ее запуск. Если в процессе решения задачи сеть не обучается, то следует переопределить параметры сети, т.е. вернуться на более ранние этапы, как правило, на этап формирования алгоритмов настройки параметров сети. Процесс «Выбор нейросетевой парадигмы» можно разбить на подпроцессы, представленные на рисунке 13. В зависимости от специфики задачи осуществляют выбор типа сети - сети Хопфилда, Кохонена, Гроссберга и т.д. Задание структуры сети предполагает определение числа слоев, количества нейронов в каждом слое, функции активации, функции ошибки. Эти параметры задают, как правило, исходя из личного опыта исследователя и могут корректироваться в дальнейшем при нейросетевом исследовании. Предложено много алгоритмов обучения нейронных сетей. Подпроцесс «Выбор алгоритма обучения» предполагает как использование «классических» методов, так и разработку собственных. Перед проведением нейросетевого исследования также необходимо определить — задать или сгенерировать начальные приближения параметров (весовые коэффициенты, шаг обучения, список параметров и т.п.).
Метод плоскостей для решения трехмерных задач раскроя- упаковки
Большинство методов решения задач трехмерной упаковки, описанных в 1.1.2, базируются на декомпозиции исходной задачи и сведению ее к задачам меньшей размерности путем разбиения на слои и заполнением каждого слоя какой-либо эвристикой. Наиболее простой способ - использование слойной стратегии, предложенной Г. Шайтхауэром. Как правило, параллелепипед разбивается на вертикальные слои и заполнение идет от задней стенки. Процесс построения параллелепипедной упаковки по стопкам был предложен P. Gilmore & R. Gomory. Сначала решается одномерная задача 0-1 рюкзак для определения высоты стопок, равных высоте параллелепипеда. На следующем этапе происходит решение задачи упаковки стопок на дно параллелепипеда. Некоторые алгоритмы используют двухфазные процедуры. На первой фазе происходит упаковка коробок в слои, на второй - процесс обмена коробок внутри слоя для улучшения локального решения. Например, в алгоритме И.Е. Тоцкова и др. предлагается использовать разбиение исходного параллелепипеда на параллелепипедные блоки, а затем для более плотного заполнения слоя используется алгоритм динамического перебора для каждого из полученных блоков. Таким образом, решение трехмерной задачи также сводится к решению задачи меньшей размерности. Разбиение параллелпипеда на блоки (слои), с одной стороны, облегчает решение задачи, однако это не гарантирует плотную упаковку. Важным вопросом для получения более плотной упаковки и грузовой стабильности является вопрос объединения пустот, которые образуются как внутри слоя, так и между ними. Некоторые авторы пытаются учитывать появляющиеся пустоты и их объединение.
В частности, в алгоритме A. Moura & J.F. Oliveira, как отмечают сами авторы, процесс обмена коробками между слоями приводит к важным заменам между соседними решениями. Поэтому авторы хотя и используют объединение, но используют подход: выбирать процесс обмена на коробках внутри слоя, а не обмен коробок между слоями. Однако если не принимать во внимание пустоты, которые образуются в смежных блоках, это может привести к проблемам при транспортировке груза. Кроме того, улучшение локального решения последовательными методами внутри каждого выделенного слоя приводит к большим временным затратам. После проведенного анализа методов решения задач трехмерной упаковки был реализован метод, получивший название метод плоскостей, особенностями которого являются: - непосредственное решение задач трехмерной упаковки; - использование как слойной, так и бесслойной стратегий; - заполнение по, так называемым, приоритетным осям; - анализ пустот и рассмотрение способов их объединения; - допускается использование не одного, а нескольких контейнеров. Ниже более подробно приведено описание метода плоскостей. Рассмотрим процесс построения слоя. Пусть имеется произвольный набор коробок и параллелепипед длины L, ширины W и высоты Н.
Для описания коробок используем их линейные размеры /,-, wi3 ht (і - 1, ..., п). При описании метода опустим учет накладываемых на задачу ограничений. Введем систему координат XYZ, началом которой является левый дальний угол основания параллелепипеда, а оси направлены вдоль его сторон таким образом, что длина предметов откладывается вдоль оси X, ширина - вдоль оси У, высота - вдоль оси Z. Метод плоскостей, как и большинство методов, основывай на понятии пустого места - области параллелепипеда без коробок, упакованных внутри. Метод имеет дело с двумя различными видами пустот.
Первый — когда высота и ширина пустого места равна высоте и ширине параллелепипеда - это рассматривается как новый слой. Второй вид пустот - когда высота и ширина пустого места отличается от размеров коробки. Алгоритм пробует упаковать коробки в образовавшиеся пустоты. Когда ни одна из коробок не может быть помещена в пустое место, это место отмечается как «временно отключено» или «отключено» (в последнем случае, чтобы сократить время решения задачи). Первая коробка определяет слой. Поэтому алгоритм оценивает все виды коробок и их ориентации, чтобы открыть новый слой. Допусти, что выбрано приоритетное заполнение по оси Z. Как только первая коробка помещена в параллелепипед, она автоматически формирует слой, который будет заполняться по высоте.
Использование сигмоидных нейронных сетей для определения нижних границ решения задач раскроя-упаковки
Поиск эффективных методов решения NP-полных задач является предметом исследования многих специалистов различных областей науки и практики. Одним из перспективных и интенсивно развивающихся направлений в этой области является использование нейротехнологий.
В связи с тем, что точные методы, основанные на полном переборе вариантов решений, нереализуемы при большой размерности данных, используют более эффективные методы сокращенного перебора, основанные, как правило, на методе ветвей и границ и его модификациях. Однако для их применения необходимо определить нижнюю границу решения. Задача определения нижних границ решения для задач раскроя-упаковки, с точки зрения нейронных сетей, может иметь следующую интерпретацию: имеется ряд примеров обучающей выборки с полем ответа - длиной занятой части полосы, отвечающей оптимальной упаковке. В принципе, обученная нейронная сеть может определить длину полосы для упаковки, нижняя граница решения которой неизвестна. Для оценки эффективности разработанных методов и программного обеспечения многие авторы используют данные из электронной библиотеки OR-library, размещенной на сайте http://mscmga.mc.ic.ac.uk.info.html. Эта библиотека содержит, так называемые, безотходные примеры упаковки, разработанные Е. Hopper, для которых заранее известно оптимальное значение длины занятой части полосы и оптимальный приоритетный список, отвечающий безотходной упаковке. Эти примеры серий JV и С содержат по 7 групп заданий для задач двухмерной упаковки, каждое задание серии С состоит из 3 примеров, серии N— из 5. В таблице 17 приведены количества прямоугольников п для каждой из серии. Примеры Е. Hopper, содержащие размеры листа (Z,, W), длину и ширину прямоугольников (/,, w,) для каждой серии, были сведены в файл данных формата DBASE. При обработке использовался нейроимитатор NeuroPro версии 0.25. Структура всех нейросетей - три слоя по десять нейронов каждый. В качестве поля ответа использовалось поле L — длина листа. В процессе обучения ни одна нейронная сеть не обучилась, даже когда изменяли структуру сети. Как видно из таблицы 17, количество прямоугольников изменяется в пределах от 16 до 197, что значительно превосходит количество примеров обучающей выборки (3 - для серии С и 5 для серии N). Для обучения нейронных сетей существует негласное правило — количество примеров обучающей выборки должно превосходить количество полей. Кроме того, обучающая выборка должна содержать практически такое же количество прямоугольников, как и тестируемая, иначе могут возникнуть проблемы с предобработкой данных, связанные с удалением пустот или же, наоборот, с добавлением новых полей. В данном случае применение безотходных примеров Е.
Hopper недопустимо, поэтому для обучения нейронных сетей требуется разработка алгоритмов формирования безотходных упаковок. В пункте 3.1 приведены алгоритмы формирования безотходных двух и трехмерных упаковок. На основе тестовых данных, полученных с помощью этих алгоритмов, для задач раскроя-упаковки были проведены численные эксперименты по обучению нейронных сетей в нейроимитаторе NeuroPro 0.25. Структура нейросети: три слоя, каждый из которых содержал по десять нейронов. С помощью разработанного программного средства было сгенерировано для нескольких классов задач обучающие и тестовые выборки. Количество прямоугольников/коробок изменялось в диапазоне от 20 до 100, количество примеров для каждой обучающей выборки было сгенерировано в два и более раза больше, чем количество объектов. Было проведено обучение нейронных сетей, при этом количество правильно решенных примеров составило 100%. В таблице 18 приведены результаты тестирования для задачи двухмерной упаковки. На примере 20 прямоугольников была исследована зависимость разброса длины и ширины в обучающих примерах (№ 1-4), и, соответственно, в тестовых, на значение ошибки. Было выявлено, что при подборе обучающей выборки следует установить фиксированное значение одной из граней полосы на основе известной, например, W, другое следует выбрать в диапазоне: Из таблицы 18 также следует, что при увеличении количества прямоугольников и их размеров, увеличивается ошибка определения значения длины полосы. Таким образом, обученная на безотходных примерах, сигмоидная нейронная сеть способна прогнозировать значение длины занятой части полосы для упаковки с произвольным, не обязательно оптимальным, списком прямоугольников, среднее значение модуля ошибки составило 4.4%. В таблице 20 приведены экспериментальные данные, полученные для безотходных трехмерных упаковок. В качестве поля ответы выбрано поле Н - высота параллелепипеда. Для каждого класса задач было сгенерировано по 5 обучающих и тестовых выборок. В процессе нейросетевого исследования было определено значение высоты параллелепипеда. В целом, для задач трехмерных упаковок наблюдаются практически такие же тенденции и зависимости, как и для двухмерных.
Выводы по четвертой главе: получение приоритетного списка прямоугольников, позволяющего достичь экстремума, является достаточно актуальной проблемой. Использование «простых» способов упорядочивания по невозрастанию какой-либо из величин не позволять достичь желаемого результата; приведен подход к определению приоритетного списка прямоугольников. Задача раскроя-упаковки представлена в нейросетевом описании в терминах энергетической функции Хопфилда, рассчитаны значения весов и порогов. Настройка коэффициентов Лагранжа позволит получить оптимальное или близкое к нему решение; обученные на безотходных примерах сигмоидные нейронные сети пригодны для определения нижних границ решения задач раскроя-упаковки. Использование такого подхода позволяет получить нижнюю границу решения с приемлемым уровнем ошибки; совместное использование нейросетевых и традиционных подходов позволяет глубже проанализировать проблему решения NP-полных задач и приблизиться к получению приемлемых решений задач раскроя-упаковки.
