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

годограф - ориентированная адаптация метода "поиск с запретами"

г. Уфа, ул. К. Маркса, 12,

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

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

Тел.:(3472) Факс:(3472) *****@***ugatu. *****,

Аннотация

В статье рассматривается задача нерегулярного размещения геометрических объектов (ГО). Для ее решения применяется метод "Поиск с Запретами" (Tabu search - TS). Приводятся алгоритмы.

1. Введение

Задача нерегулярного размещения геометрических объектов формулируется следующим образом: необходимо разместить n объектов Pi в области W пространства R2 (R3) так, чтобы минимизировать незанятую область. Геометрические объекты должны быть размещены в области W таким образом, чтобы они не пересекались друг с другом и не выходили за границу области размещения. Эта проблема, с точки зрения вычислительной сложности, относится к NP - трудным. Переборная сложность NP - трудных задач не позволяет находить их точное решение для большого числа объектов за приемлемое время даже при введении некоторых ограничений. Поэтому для решения практических задач применяются эвристические методы решения. Эти методы используются для поиска локальных оптимумов и организации некоторого перебора экстремальных значений функций цели для получения решений, близких к оптимальным, за приемлемое время. Существует много разнообразных эвристических методов. Одному из них, методу "Поиск с Запретами" (TS), посвящена данная статья.

НЕ нашли? Не то? Что вы ищете?

2. Метод "Поиск с Запретами" (TS)

Родоначальником алгоритма поиска с запретами (tabu search - TS) (1986 год) является Фред Гловер, ко­торый предложил следующую схему локального поиска [4, 5, 6]. Пусть для задачи дис­кретной оптимизации

удалось найти некоторое допустимое решение . Рассмотрим окрестность точки и найдем решение задачи

.

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

Идея алгоритма "Поиска с Запретами" состоит в том, чтобы не останавливаться в локаль­ном оптимуме, как это предписано в алгоритмах локального спуска, а продолжить поиск, руководствуясь теми же правилами, запрещая посещение уже пройденных то­чек.

На k-м шаге алгоритма точка находится из решения задачи

.

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

Обозначим через N'(x) часть окрестности N(x), взятую случайным образом. То­гда алгоритм поиска с запретами можно представить в следующем виде.

Алгоритм TS

1. Выбираем начальное решение , полагаем . Формируем пустой список запретов.

2. Находим новое решение z такое, что

а) ;

б) ;

в) переход не является запрещенным или .

3. Переходим в новую точку .

Изменяем список запретов.

Если , то меняем рекорд .

4. Если выполнен критерий остановки, то STOP, иначе идти на п.2.

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

В 1992 году Файгл и Керн [3] предложили вероятностную версию метода TS, который при количестве итераций стремящихся к бесконечности, сходится к глобальному оптимуму, что, впрочем, свойственно большинству вероятностных алгоритмов. Так рандомизация окрестности сокращает трудоемкость алгоритма на шаге 2 и вносит элемент случайности при выборе направления спуска. Если рандомизированная окрестность составляет от 1 до 10 процентов от исходной, то алгоритм не зацикливается даже без списка запретов. Алгоритм TS применялся к широкому кругу задач дискретной оптимизации [6], показал высокую работоспособность и на сегодняшний день является одной из наиболее популярных вероятностных эвристик.

Одно из возможных применений метода "Поиск с запретами" для решения задач нерегулярного раскроя - упаковки (Р-У) предложено в работе [2] польскими авторами Блазевичем, Хаврулюком и Валковяком. Другой подход предлагается авторами статьи.

3. Годограф - ориентированная адаптация метода "Поиск с Запретами" (HO-TS)

Рассмотрим один из возможных способов применения метода TS для решения задачи нерегулярного размещения геометрических объектов (ICSP), основанный на применении годографа - HO-TS. Для его реализации используется также метод последовательно одиночного размещения, который подразумевает использование "приоритетного списка" - ПС для определения последовательности размещения геометрических объектов (ГО) в область Р-У.

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

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

Основные моменты метода TS применительно к решению задачи размещения плоских ГО состоят в следующем.

Способ перехода

Первая и наиболее важная проблема при адаптации метода TS для решения любой комбинаторной задачи - это определение способа перехода от одного допустимого решения к другому. В алгоритме TS способу перехода соответствует понятие перемещение. Перемещение определяется в следующем виде: это изменение расположения ГО в ПС.

Список запретов

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

где

- индекс итерации, - перемещение обратное перемещению и - перемещение на итерации .

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

Целевая функция

В качестве целевой функции используется длина занятой части полосы.

Годограф ориентированная адаптация алгоритма TS может быть представлена в следующем виде:

Алгоритм HO-TS

Переместить в ПС ГО Pi согласно случайному перемещению

Произвести генерацию карты Р-У Knew согласно ПС

if then

{

}

В случае более сложной реализации HO-TS, в качестве дополнительного списка запретов используются допустимые размещения объекта рядом с объектом . Эти размещения определяются матрицей , каждый элемент которой характеризует качество размещения объекта с объектом . Величины могут вычисляться при помощи метода оценок [1]. Они вычисляются и для тех вновь генерируемых карт Р-У, которые имеют качество хуже, чем лучшее решение, полученное на данный момент времени. Таким образом, такой способ формирования списка запретов, позволяет не только не возвращаться к уже "пройденным" решениям (запоминание положительного опыта), но и накапливать информацию о взаимном размещении объектов (как положительный, так и отрицательный опыт).

Заключение

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

Литература

1.  , , Мартынов и методы расчета раскроя – упаковки геометрических объектов. - УГАТУ, Уфа: 1998, 217с.

2.  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.

3.  Faigle U., Kern W. Some convergence results for probabilistic tabu search. ORSA Journal on Computing 4(1),pp.32-37,1992.

4.  Glover F. Tabu search - part I, ORSA Journal on Computing 1(3),pp.190-206, 1989.

5.  Glover F. Tabu search - part II, ORSA Journal on Computing 2(1),pp.4-32, 1990.

6.  Glover F., Laguna M. Tabu search in modern heuristic techniques for combinatorial problems, Blackwell Publishing, 1992.