Задача нерегулярного размещения геометрических объектов - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Задача для объекта. 6 Глоссарий Поисковая задача 1 30.11kb.
Региональный норматив градостроительного проектирования: Планировка... 12 1463.77kb.
Приложение n 1 к Схеме размещения нестационарных торговых объектов... 19 3623.81kb.
Принципы построения локальных систем оповещения на базе комплекса... 1 101.65kb.
Дискретное программирование 1 48.87kb.
11 февраля 1998 г. N 148-рп 1 40.13kb.
3. Таблицу 7 изложить в следующей редакции 1 287.51kb.
Схема размещения нестационарных торговых объектов (нто) в границах... 4 567.28kb.
Кемеровская область калтанский городской округ администрация калтанского... 1 189.05kb.
Задача: Привлечь иностранных туристов в Москву, рассказывая о городе... 1 13.86kb.
Задача по улучшению информационного обеспечения процесса лицензирования... 1 21.18kb.
Оценка живучести противоборствующих информационно-управляющих систем 1 133.17kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Задача нерегулярного размещения геометрических объектов - страница №1/1

Задача нерегулярного размещения геометрических объектов:

современное состояние методов решения



Верхотуров Михаил Александрович
450025, г. Уфа, ул. К. Маркса, 12,

Уфимский государственный авиационный технический университет,

Кафедра вычислительной математики и кибернетики,

Тел.:(3472)237967, Факс:(3472)222918, verhotur@vmk.ugatu.ac.ru,
Аннотация

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



1. Введение
Задачи размещения геометрических объектов (ГО) давно и широко встречаются как в теории, так и на практике и, поэтому, существует достаточное множество методов применяемых для их решения.

Отличительной особенностью этого класса задач по сравнению с линейным и прямоугольным видами раскроя - упаковки (Р-У) является трудность определения условий взаимного непересечения в результирующих картах Р-У. Если в задачах прямолинейного раскроя - упаковки эта проблема решается тривиально и отдельно не выделяется, то при решении задач размещения ГО она является самостоятельной и вносит дополнительные сложности в разрешение основной задачи – оптимизации Р-У.

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

2. Классификация методов решения
Классификация методов решения задач нерегулярного размещения геометрических объектов выглядит следующим образом (Рис. 1).

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

Простейшим здесь является метод, заключающийся в аппроксимации каждого объекта (или нескольких объектов) из исходного их множества таким геометрическим объектом, для которого условия его взаимного непересечения с другими такими же объектами определяются достаточно тривиально []. Как пример такого типа объектов можно привести прямоугольники или окружности. Для случая прямоугольников решение будет состоять из следующих трех этапов:

- нахождение для каждого ГО описывающего его прямоугольника минимальной площади (для изотропного, например, размещения ГО);

- размещение полученных прямоугольников в заданную область Р-У;

- доуплотнение исходных ГО после “отброса” прямоугольных оболочек.

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

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

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

Рассматриваемый класс проблем, с позиции теории вычислительной сложности, относится к NP- трудным []. С учетом введения ограничений на возможность поворота ГО во время размещения (анизотропная упаковка), для нее существуют методы глобальной оптимизации. Эти методы представляют лишь теоретический интерес, т.к., переборная сложность NP- трудной задачи, даже с учетом этих ограничений, не позволяет находить их точное решение для достаточного количества объектов за приемлемое время.

Для решения же реальных практических задач используются эвристические методы решения.

Методы поиска локальных экстремумов основываются как на тех же идеях, используемых для точного решения задач [, ], так и методах нелинейного программирования (например, методом штрафных функций []). Эти методы используются для поиска локальных оптимумов и организации на этой базе некоторого перебора экстремальных значений функций цели и соответствующих им решений.

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

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

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

Вторым набором методов в приближенных способах решения являются методы нахождения рациональных (допустимых) укладок близких к оптимальным. Они, в отличие от вышерассмотренных методов, являются эвристическими. Но, как известно [, ], такие методы являются широко распространенными и оправданными при решении NP- трудных задач. Они отличаются тем, что, как правило, на каждом элементарном шаге решения оперируют отдельными геометрическими объектами (принцип пообъектного размещения), т.е. производят некоторые геометрические преобразования каждого из них.

В методах моделирования геометрических преобразований (МГП) можно выделить три класса:


    1. методы, основанные на моделировании движений ГО с учетом взаимного непересечения (в области допустимых размещений) [, , , и др.];

    2. методы на основе произвольных движений (параллельных переносов и вращений)[, ], в процессе которых ГО могут пересекаться друг с другом и с областью размещения;

    3. методы, основанные на процедуре занесения объекта в произвольную область [].

Отличие этих методов заключается в:

- траектории, по которой производятся движения исходных ГО;

- степени сложности для реализации вращения ГО;

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

Безусловно, существует большое количество разнообразных эвристических методов, применяемых для решения задач нерегулярного размещения ГО. В основном же используются два, наиболее развитых и дающих неплохие результаты, класса методов. Первый - это метаэвристики типа “simulated annealing(SA)”, “genetic algorithm(GA), “tabu search(TS)”, "ant colonie(AC)" и их модификации. И, второй, эвристические методы, разработанные специально для этого класса задач.

Анализ применимости различными эвристиками методов моделирования геометрических преобразований показывает, что:



  • первый класс, базирующийся на понятии “годограф”, охватывает большую часть из методов, применяемых для нахождения решений близких к локально-оптимальным;

  • второй класс методов, использующих набор произвольных движений, достаточно невелик, это, в основном, методы типа simulated annealing и такие его модификации, как threshold accepting, great deluge... и т.д.;

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

Сравнивая эти классы методов можно сделать следующие выводы:

  1. Методы, основанные на изначальном моделировании таких движений, которые не приводят к пересечению объектов между собой и с границей области размещения (моделирование "годографа") хороши тем, что они всегда дают в результате допустимое размещение (упаковку). В этом же и кроится их недостаток - необходимо моделировать условия взаимного непересечения (УВН), а это достаточно трудоемко, с одной стороны, и моделирование УВН производится для фиксированного угла поворота объекта - с другой. Прямой аналог этих методов - это методы условной оптимизации.

  2. Методы, основанные на произвольных движениях, обладают тем преимуществом, что в них не фиксируется угол поворота, и нет необходимости учета УВН. Однако, последнее приводит к следующему важному недостатку: в результате различных движений может сложиться такая ситуация (что часто и происходит на практике), когда поиск такого решения (если оно вообще существует) может происходить сколь угодно долго. Прямым содержательным аналогом этих методов являются методы безусловной оптимизации.

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


  1. Adamowicz M., Albano A. Nesting Two-dimensional shapes in rectangular modules. Comput. Aided Des., 1976, 8,N1,pp.27-33.

  2. Стоян Ю.Г., Новожилова М.В., Карташов А.В. Математическая модель и оптимизация линейных Ek(R2) - задач размещения. - Харьков, 1991.-44с.-(Препринт /АН УССР. Ин-т пробл. Машиностроения: №353).

  3. Daniels K., Milenkovic V.J. Multiple translational containment, part I: an approximation algorithm. - Algorithmica special issue on Computational geometry in manufacturing, 1994, 46p.

  4. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. – М.:Мир,1985. – 509с.

  5. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. - Киев. : Наук. думка, 1986. - 286с.

  6. Milenkovic V.J., Daniels K. Translational polygon containment and minimal enclosure using mathematical programming. -ITOR special issue with papers from IFORS'96, 1996, 30p.

  7. Milenkovic V.J. Multiple translational containment, part II: exact algorithms.- Algorithmica special issue on Computational geometry in manufacturing, 1994, 40p.

  8. Иванов Г.А. Проектирование размещения плоских геометрических объектов методами нелинейного программирования: Автореф.дисс... канд.техн.наук. – Йошкар-Ола: МарПИ,1993.-16с.

  9. Рейнгольд Э., Нивергольд Ю., Део Н. Комбинаторные алгоритмы: Теория и практика. М.: Мир, 1980.-213с.

  10. Компьютер и задачи выбора/Автор предисл. Ю.И. Журавлев. - М:Наука,1989.-208с.

  11. Гиль Н.И. Математическое моделирование нерегулярного размещения плоских геометрических объектов в системах автоматизации проектирования (теоретические основы, методы, приложения): Автореф.дис....докт.техн.наук.-Минск,1990.-32с.

  12. Стоян Ю.Г., Гиль Н.И. Методы и алгоритмы размещения плоских геометрических объектов. - Киев: Наук. думка, 1976. -247с.

  13. Верхотуров М.А. Об устойчивых алгоритмах построения годографа// Принятие решений в условиях неопределенности: Межвузовский сборник. - Уфа: УГАТУ, 1998.- С.270-284.

  14. Heckmann R., Lengauer T. Computing closely matching upper and lower bounds on textile nesting problems. - European Journal of Operational Research, 108, 1998, pp.473-489.

  15. Heckmann R., Lengauer T. A simulated annealing approach to the nesting problem in the textile manufacturing industry.- Annals of OR, 57, pp.103-133, 1995.

  16. Lutfiyya H., McMillin B., Poshyanonda P., Dagli C. Composite stock cutting through simulated annealing.- Tech. report numbers CSC 91-09 and ISC 91-04, University of Missouri at Rolla, Rolla,50p.,1991.

  17. Blazewicz J., Hawryluk P., Walkowiak R. Using a tabu search approach for solving the two-dimensional irregular cutting problem. - Annals of OR, 41(1-4), pp.313-325, 1993.

 Работа поддержана РФФИ, проект 01-01-00510