Задача нерегулярного размещения геометрических объектов:
применение методов дискретной оптимизации*
2,
Уфимский государственный авиационный технический университет,
Кафедра вычислительной математики и кибернетики,
Тел.:(3472) Факс:(3472) *****@***ugatu. *****,
Аннотация
В статье рассматриваются вопросы, связанные с применением методов дискретной оптимизации для решения задачи нерегулярного размещения геометрических объектов (ГО). Особое внимание уделено использованию метаэвристических методов локального поиска: "поиск с запретами" TS, "моделирование отжига" SA, "генетические алгоритмы" GA, "муравьиной колонии" AC, "пороговой допустимости" TA, "всемирного потопа" GD, "перехода от рекорда к рекорду" RTR и т. д.
1. Введение
Многие задачи, относящиеся к задачам непрерывного математического программирования (в том числе и задача нерегулярного размещения геометрических объектов), решаются методами дискретной (или комбинаторной) оптимизации. Самый известный, наверное, здесь пример - это задача линейного программирования. Она является непрерывной, но наиболее широко применяемый для ее решения симплекс-метод является методом комбинаторной оптимизации, т. к. его суть - это направленный перебор вершин симплекса.
К комбинаторному решению задачи приводит и чисто физическое ее понимание. До сих пор на многих предприятиях она решается человеком путем поочередного размещения укладываемых объектов и нахождения лучшего среди полученных вариантов укладки.
2. Классификация методов дискретной оптимизации
Две вышеуказанные логические предпосылки привели к возникновению целого класса методов, применяемых для решения нерегулярного размещения геометрических объектов и базирующихся на принципе пообъектного размещения (методы моделирования геометрических преобразований). Принцип пообъектного размещения предполагает разбиение процесса на две части:
- моделирование геометрических преобразований - внутренняя часть;
- формирование последовательности размещаемых объектов - внешняя (комбинаторная) часть.
С точки зрения возможности нахождения точного решения за полиномиальное время эта комбинаторная задача относится к классу NP- трудных.
Основными подходами к решению таких задач являются [1, 2]: методы перебора, приближенные методы и методы локального поиска.
|
Рис. 1 Методы решения задач дискретной оптимизации и задачи нерегулярного размещения ГО
Рассмотрим классификацию методов применяемых для решения таких задач и проанализируем возможность их практического применения для нашей задачи.
На верхнем уровне их можно разбить на две группы: точные и локального поиска (Рис. 1). Точные методы имеют экспоненциальную сложность.
Расположим точные методы слева направо по убыванию сложности. Метод полного перебора приведен для сравнения, так как с практической точки зрения он интереса не вызывает. Количество шагов в случае полного перебора равно n! n. Но функция от n подобного вида растет быстрее, чем произвольная экспоненциальная функция вида an, a>1, так как
Сравнительная характеристика метода динамического программирования и метода ветвей и границ на примере задачи коммивояжера для n городов дает следующие величины: n2n для динамического программирования и 1.26n для метода ветвей и границ.
«Поиск с ограничениями» является границей, разделяющей точные методы и методы локального поиска. Рассмотрим методы локального поиска. Наиболее известен в этом классе - детерминированный "жадный" или градиентный метод. В литературе его обычно называют "жадным" алгоритмом, но, на данный момент времени, его можно причислить к методам, т. к. он применим для решения многих задач и имеет множество модернизаций. В нашей классификации "жадный" метод относится к методам локального поиска хотя для задач на матроидах он дает точный результат [3].
Характеристикой "жадного" алгоритма, часто приводимой в литературе, является то, что объект включенный в множество элементов решения, остается в этом множестве до конца. Здесь не бывает “откатов назад” как в методе с возвратом, а именно они ведут к экспоненциальному росту числа шагов. Классический "жадный" алгоритм имеет всегда полиномиальную сложность.
Еще одним классом методов, получившим свое развитие в работах [4, 5] являются вероятностные методы локального поиска. Одним из первых для решения рассматриваемой задачи был разработан метод асимптотического перебора локальных экстремумов [6].
Для реализации методов такого типа применяется способ последовательно-одиночного размещения. Его отличительной особенностью является начальная фиксация последовательности укладываемых объектов.
Основными недостатками подходов, которые работают на основе способов с зафиксированным приоритетным списком, являются:
1). Отсутствие учета зависимости размещаемого объекта от уже уложенных ГО.
2). Отсутствие учета зависимости процесса размещения очередного объекта от еще не размещенных ГО.
3). Неподвижность ранее размещенных объектов.
В большинстве вышеописанных методов (точные методы и жадный метод) существует жестко зафиксированный приоритетный список. Поэтому предлагается выделить способ выборочного размещения и удаления (ВРУ), в котором такой список отсутствует.
При использовании ВРУ на каждом шаге размещения из всего множества (или подмножества) неуложенных объектов выбирается объект, наилучшим образом удовлетворяющий критериям оптимальности. Он укладывается в область упаковки. При необходимости, возможно удаление одного или нескольких размещенных на последних i шагах объектов из области и занесении их обратно в множество объектов, подлежащих укладке.
Основная проблема при решении задач дискретной оптимизации заключается в том, что одни из используемых методов приводят к большому перебору, другие - останавливаются в точках локального оптимума, а таких точек может оказаться слишком много, причем они могут сильно отличаться от глобального оптимума.
Для решения задач дискретной оптимизации одного типа на начальном историческом этапе применялись специальные (чаще всего пригодные только для решения этого конкретного типа задач) эвристические методы. Реализованные на их основе приближенные алгоритмы хотя и являлись полиномиальными, но требовали значительных затрат времени для решения и иногда получали решения плохого качества.
В последнее же время широкое распространение получили эвристики, которые подходят для нахождения приближенных решений задач дискретной оптимизации любого типа, т. е. являются инвариантными по отношению к виду задачи, это - так называемые метаэвристики. В литературе их также часто называют методами локального поиска. Суть этих методов часто следует или из разумных умозаключений (метод "поиск с запретами" (tabu search - TS)), или из механизмов функционирования, "подсмотренных" у живой (генетический алгоритм (genetic algorithm - GA), алгоритм муравьиной колонии (ant colonies - AC)) или неживой природы (моделирование отжига (simulated annealing - SA), алгоритм всемирного потопа (great deluge algorithm - GDA)) и др. [4].
Анализ вышеуказанных методов локального поиска позволяет заметить, что такие алгоритмы, как TS, SA, "алгоритм пороговой допустимости" TA, GDA и "алгоритм перехода от рекорда к рекорду" RTR, в каждый момент времени оперируют только с одним решением, в то время как GA и AC одновременно работают с набором решений. Другими словами, генетический алгоритм и алгоритм муравьиной колонии несут в себе коллективное начало, и это позволяет им исследовать разные части допустимой области и использовать информацию, накопленную в рамках многих решений, для получения хорошего итогового результата (Рис. 2).
Рис. 2 Разбиение метаэвристик по группам методов, несущих индивидуальное и коллективное начала
Кроме того, в последнее время все более широкое распространение получают гибридные схемы, реализующие разнообразные сочетания различных методов локального поиска.
Можно предложить следующую схему гибридизации различных алгоритмов: на начальном этапе используется один из алгоритмов, несущих коллективное начало, а на втором шаге применяется алгоритм, несущий индивидуальное начало. Таким образом, на начальном этапе охватывается большая часть допустимой области, что, безусловно, влечет за собой положительный момент. Затем к каждому из "хороших" решений, полученных на предыдущем шаге, применяется один из алгоритмов SA, TA, GD, RTR или TS.
На заключительном шаге к наилучшему из полученных решений возможно применение одного из точных методов, описанных в [7], что позволит найти локальный экстремум целевой функции.
Также возможно сочетание метаэвристических методов поиска с другими специальными эвристиками, хорошо зарекомендовавшими себя при решении задач размещения ГО. Например, различные схемы взаимодействия метаэвристик с методом последовательного улучшения оценок[8].
3. Заключение
Анализ приведенных выше алгоритмов с учетом трудоемкости процесса моделирования УВН позволяет сделать вывод, что на данный момент времени из детермированных алгоритмов реальным является практическое применение модификаций "жадного" метода и метода с возвратом с жесткими ограничениями. Также перспективным является применение метаэвристических методов локального поиска как по отдельности, так и в комбинации друг с другом.
Литература
1. Комбинаторная оптимизация. – М.:Мир,1985.-432с.
2. Комбинаторные алгоритмы: Теория и практика. М.: Мир, 1980.-213с.
3. Комбинаторика для программистов. - М: Мир, 1988.-213с.
4. Aarts E., Lenstra J. K. (eds.) Local search in combinatorial optimization, John Wiley & Sons Ltd, 1997.-315p.
5. , Соколовский некоторых задач методом сужающихся окрестностей. - Киев: Наук. думка, 1980.-206с.
6. , Гиль и алгоритмы размещения плоских геометрических объектов. - Киев: Наук. думка, 19с.
7. Верхотуров нерегулярного размещения геометрических объектов: современное состояние методов решения (Статья публикуется в этом же сборнике).
8. Верхотуров нерегулярного раскроя плоских геометрических объектов: моделирование и расчет рационального раскроя// Информационные технологии, 2000, №5. С.37-42.
* Работа поддержана РФФИ, проект
