страница 1
|
|||||||||||||||||||||||||||||||||||||||||||
Похожие работы
|
Задача нерегулярного размещения геометрических объектов - страница №1/1
Задача нерегулярного размещения геометрических объектов:современное состояние методов решения Верхотуров Михаил Александрович 450025, г. Уфа, ул. К. Маркса, 12, Уфимский государственный авиационный технический университет, Кафедра вычислительной математики и кибернетики, Тел.:(3472)237967, Факс:(3472)222918, verhotur@vmk.ugatu.ac.ru, Аннотация В статье рассматривается классификация методов, применяемых при решении задачи нерегулярного размещения геометрических объектов, приводятся ссылки на соответствующие литературные источники. 1. Введение Задачи размещения геометрических объектов (ГО) давно и широко встречаются как в теории, так и на практике и, поэтому, существует достаточное множество методов применяемых для их решения. Отличительной особенностью этого класса задач по сравнению с линейным и прямоугольным видами раскроя - упаковки (Р-У) является трудность определения условий взаимного непересечения в результирующих картах Р-У. Если в задачах прямолинейного раскроя - упаковки эта проблема решается тривиально и отдельно не выделяется, то при решении задач размещения ГО она является самостоятельной и вносит дополнительные сложности в разрешение основной задачи – оптимизации Р-У. Проектирование планов (карт) раскроя по сути является задачей оптимизационного геометрического моделирования, заключающейся в оптимизации размещения геометрических объектов в заданных областях. Во многих областях знаний одним из широко распространенных способов решения сложных задач является метод аппроксимации и декомпозиции, сводящий проблему к решению одной или последовательному решению нескольких простых задач. Этот метод используется и при решении задач проектирования упаковок ГО. Простейшим здесь является метод, заключающийся в аппроксимации каждого объекта (или нескольких объектов) из исходного их множества таким геометрическим объектом, для которого условия его взаимного непересечения с другими такими же объектами определяются достаточно тривиально []. Как пример такого типа объектов можно привести прямоугольники или окружности. Для случая прямоугольников решение будет состоять из следующих трех этапов: - нахождение для каждого ГО описывающего его прямоугольника минимальной площади (для изотропного, например, размещения ГО); - размещение полученных прямоугольников в заданную область Р-У; - доуплотнение исходных ГО после “отброса” прямоугольных оболочек. Метод аппроксимации и декомпозиции дает неплохие результаты для ГО, которые близки по своей форме к тем элементарным ГО, для которых известны точные и быстрые методы решения. Тем не менее, понятно, что большинство реальных задач размещения ГО имеет дело с такими объектами, которые сильно отличаются от простых ГО. Для такого же типа проблем этот метод не всегда применим, т.к. его использование ведет к значительному росту отходов раскраиваемого материала. В общем случае задачи решаются с учетом реального вида ГО. Основное деление методов, применяемых для решения этих задач, происходит по отношению к точности получаемых результатов. Рассматриваемый класс проблем, с позиции теории вычислительной сложности, относится к NP- трудным []. С учетом введения ограничений на возможность поворота ГО во время размещения (анизотропная упаковка), для нее существуют методы глобальной оптимизации. Эти методы представляют лишь теоретический интерес, т.к., переборная сложность NP- трудной задачи, даже с учетом этих ограничений, не позволяет находить их точное решение для достаточного количества объектов за приемлемое время. Для решения же реальных практических задач используются эвристические методы решения. Методы поиска локальных экстремумов основываются как на тех же идеях, используемых для точного решения задач [, ], так и методах нелинейного программирования (например, методом штрафных функций []). Эти методы используются для поиска локальных оптимумов и организации на этой базе некоторого перебора экстремальных значений функций цели и соответствующих им решений. Хорошо известно, что практически нет методов нахождения глобального оптимума для многих реальных задач нелинейного программирования. В этих случаях в основном используются и совершенствуются методы локальной оптимизации, как количественно - с улучшением их быстродействия, так и качественно - нахождение локальных оптимумов близких к глобальному. Одним из широко используемых в этой области математического программирования классом методов является класс поисковой оптимизации. Для него поиск решения осуществляется последовательными шагами, ведущими от исходной точки из области допустимых решений (ОДР) через некоторые промежуточные значения в заданную e - окрестность точки локального оптимума. Очень важным, в этом случае, является расположение исходной точки в ОДР. Выделим в этом классе два подхода: методы безусловной и условной оптимизации. В первом случае для устранения постоянной проверки ограничений на непересекаемость объектов между собой и с границей области производится переход от задачи условной к задаче безусловной оптимизации. Это достигается одним из широко известных методов - методом штрафных функций. В качестве функции штрафа в исходную целевую функцию добавляется слагаемое, характеризующее пересечение объектов между собой и с границей области []. Во втором случае используются классические методы условной оптимизации. В частности те же методы, которые использовались для нахождения точных решений: методы активного набора []. Вторым набором методов в приближенных способах решения являются методы нахождения рациональных (допустимых) укладок близких к оптимальным. Они, в отличие от вышерассмотренных методов, являются эвристическими. Но, как известно [, ], такие методы являются широко распространенными и оправданными при решении NP- трудных задач. Они отличаются тем, что, как правило, на каждом элементарном шаге решения оперируют отдельными геометрическими объектами (принцип пообъектного размещения), т.е. производят некоторые геометрические преобразования каждого из них. В методах моделирования геометрических преобразований (МГП) можно выделить три класса:
Отличие этих методов заключается в: - траектории, по которой производятся движения исходных ГО; - степени сложности для реализации вращения ГО; - возможности пересечений объектов друг с другом и с областью размещения в процессе моделирования геометрических преобразований. Безусловно, существует большое количество разнообразных эвристических методов, применяемых для решения задач нерегулярного размещения ГО. В основном же используются два, наиболее развитых и дающих неплохие результаты, класса методов. Первый - это метаэвристики типа “simulated annealing(SA)”, “genetic algorithm(GA), “tabu search(TS)”, "ant colonie(AC)" и их модификации. И, второй, эвристические методы, разработанные специально для этого класса задач. Анализ применимости различными эвристиками методов моделирования геометрических преобразований показывает, что:
Сравнивая эти классы методов можно сделать следующие выводы:
3. Заключение Вышеизложенное позволяет сделать вывод, что на данный момент времени для решения задачи нерегулярного размещения геометрических объектов наиболее перспективным является адаптация метаэвристических методов локального поиска в комбинации с методами моделирования геометрических преобразований, основанных на выполнении условий взаимного непересечения. Литература
Работа поддержана РФФИ, проект 01-01-00510 |
|