Задача нерегулярного размещения геометрических объектов: годограф ориентированная адаптация метода \"моделирование отжига\" icon

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



НазваниеЗадача нерегулярного размещения геометрических объектов: годограф ориентированная адаптация метода "моделирование отжига"
Дата17.10.2016
Размер
ТипЗадача

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

годограф - ориентированная адаптация метода "моделирование отжига"


Верхотуров Михаил Александрович

Верхотурова Олеся Михайловна

Лохматов Олег Витальевич


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

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

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

Тел.:(3472)237967, Факс:(3472)222918, verhotur@vmk.ugatu.ac.ru,


Аннотация

В статье рассматривается задача нерегулярного размещения геометрических объектов (ГО). Для ее решения применяется метод "моделирование отжига" (Simulated Annealing - SA) и его модификации, адаптированные на базе применения годографа функции плотного размещения. Приводятся алгоритмы.


1. Введение

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


^ 2. Метод "Моделирование Отжига"

Метод SA был предложен независимо друг от друга двумя авторами Киркпатриком (1983г.)[1] и Церни (1985г.)[2], как метод минимизации функции многих переменных.

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

Если , то приращение "принимается". Это означает, что сделанное изменение улучшает состояние системы, в противном случае оно "принимается" с вероятностью ,

где - константа Больцмана.

Когда приращение принимается, процесс продолжается с нового состояния , заменившем старое; в противном случае предпринимается новое приращение .

Рассмотрим алгоритм Метрополиса:

Выбрать некоторое случайное начальное решение

while Критерий окончания do

{

некоторое случайное соседнее решение





if then

}

Таким образом, Киркпатриком и Церни была произведена аналогия между процессом охлаждения и решением задачи комбинаторной оптимизации. Аналогия между основными понятиями физической системы и комбинаторной оптимизации приведена в следующей таблице (см. Таблица 1).

Таблица 1 Соответствие понятий

Физические системы

Задачи оптимизации

Состояние

Решение

Энергия

Функция цели

Охлажденное состояние

Оптимальное решение

Постепенное охлаждение

Пошаговое улучшение

Отжиг

Моделирование отжига

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

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

Общий алгоритм SA выглядит следующим образом:

начальное решение ; начальное решение

while Критерий окончания do {

while НЕ Состояние равновесия do {

некоторое случайное соседнее решение





if then

}

Изменить

}

Вывести лучшее решение

Определение начальной температуры , приращение на каждом шаге и определение "Состояния равновесия" называется "режимом охлаждения". Для определения параметров режима охлаждения применяются различные эвристики. Сходимость с разными режимами охлаждения описана, например, в [4]. Для сходимости алгоритма может потребоваться экспоненциальное время.

Для адаптации метода SA к задаче нерегулярного размещения ГО необходимо выяснить следующие вопросы:

  • определить целевую функцию;

  • определить перечень возможных движений ГО.

Отличительной особенностью предложенных способов применения метода SA к рассматриваемой в работе задаче является использование таких произвольных перемещений и поворотов ГО, которые допускают взаимопересечение ГО между собой [5, 6]. А это влечет за собой следующий недостаток, присущий этим алгоритмам: достаточно часто бывает такая ситуация, при которой не находится допустимое решение, т.е. не выполняются условия взаимного непересечения ГО между собой.


^ 3. Годограф - ориентированная адаптация метода "Моделирование отжига "(HO-SA)

Рассмотрим один из возможных вариантов адаптации алгоритма SA для ICSP, использующий аппарат моделирования годографа и метод последовательно-одиночного размещения.

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

Для реализации метода SA необходимо определить:

  • целевую функцию;

  • механизм получения новых допустимых решений для каждого из агентов (способ перехода).

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

Способ перехода. Для изменения расположения объектов используются три типа перемещений ГО в ПС:

  • перемещение объекта на новое место;

  • взаимозамена мест двух объектов;

  • изменение ориентации объекта.

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

Для устранения этого недостатка Дюком и Шеуером [7, 8] был предложен целый ряд алгоритмов, которые являются модификациями метода SA. Это такие алгоритмы, как: "Пороговой Допустимости" (Threshold Accepting - TA), "Всемирного Потопа" (Great Deluge - GD).

Рассмотрим каждый из них:


Алгоритм "Пороговой Допустимости"

начальное решение ; начальный "порог"

while Критерий окончания do {

while НЕ Состояние равновесия do {

некоторое случайное соседнее решение



if then

}

Изменить

}

Вывести лучшее решение


Алгоритм TA переходит к новому решению, которое не намного хуже, чем предыдущее старое, в отличие от SA, который переходит к худшему решению только с довольно небольшой вероятностью.


Алгоритм "Всемирного Потопа" (максимизация)

начальная точка местности

начальная "интенсивность дождя"

начальный "уровень воды"

while Критерий окончания do {

случайная соседняя точка местности

if then {



Уровень_воды:=Уровень_воды+

}

}

Вывести лучшее решение


Если представить определенный участок горной местности, то алгоритм GD находит максимально высокую точку этого участка. Когда "идет дождь", то он постепенно "заливает" невысокие точки местности, которые становятся "недоступны" для "перехода к ним". И чем дольше он идет, тем меньше точек этой гористой местности остается над поверхностью воды.

Рассмотренные оптимизационные эвристики имеют то преимущество перед методом ^ SA, что они зависят только от одного параметра.

Так, например, для алгоритма GD необходимо выбрать только величину . Эта величина, которая влияет на время вычислений и качество получаемого результата. Если выбирается большой, то алгоритм работает быстро, но выдает результат среднего качества. Если же эта величина выбирается малой, то алгоритм выдает хороший результат, но после длительного времени счета.

Применение алгоритмов "Пороговой Допустимости" ^ TA, "Всемирного Потопа" GD для решения ICSP производится аналогично адаптации метода SA с использованием годографа HO-SA.


4. Заключение

В заключении можно сделать следующие выводы:

  • недостатком известных адаптаций метода SA для ICSP является использование метода произвольных движений, что влечет за собой не всегда успешное (нарушаются условия взаимного непересечения размещаемых ГО) завершение работы соответствующих алгоритмов;

  • разработана адаптация метода "моделирование отжига" SA для решения задач нерегулярного размещения ГО на базе аппарата построения годографа;

  • в связи с тем, что операция годографа является для данного метода базовой и часто повторяемой процедурой, то она должна работать максимально надежно и быстро;

  • применение таких модификаций метода "моделирование отжига" SA, как: "Пороговая Допустимость" TA, "Всемирный Потоп" GD для решения ICSP производится аналогично HO-SA.


Литература

  1. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by simulated annealing, Science 220, 1983, pp.671-680.

  2. Cerny V. Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm, J. Opt. Theory Appl., 45, 1985, pp.41-51.

  3. Metropolis, N., Rosenbluth A., Rosenbluth M., Teller, A. and Teller, E., "Equation of State Calculations by Fast Computing Machines" J. Of Chem. Physics, 21, 1953, pp.1087-1092.

  4. Aarts L., Van Laarhoven P. Statistical cooling: a general approach to combinatorial optimization problems, Philips J.Res 40, pp.193-226, 1985.

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

  6. Dowsland K.A. Some experiments with simulated annealing techniques for packing problems, EJOR, 68, 1993, pp.389-399.

  7. Dueck G. New optimization heuristics, J.Comp. Phys. 104, 1993, pp.86-92.

  8. Dueck G. Scheuer T. Threshold accepting : a general purpose optimization algorithm appearing superior to simulated annealing. - J.Comp.Phys., 1990,90p.

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




Похожие:

Задача нерегулярного размещения геометрических объектов: годограф ориентированная адаптация метода \"моделирование отжига\" iconЗадача нерегулярного размещения геометрических объектов: годограф ориентированная адаптация алгоритма "муравьиной колонии"
В статье рассматривается задача нерегулярного размещения геометрических объектов (ГО). Для ее решения применяется алгоритм "муравьиной...
Задача нерегулярного размещения геометрических объектов: годограф ориентированная адаптация метода \"моделирование отжига\" iconЗадача нерегулярного размещения геометрических объектов: применение методов дискретной оптимизации
ГО. Особое внимание уделено использованию метаэвристических методов локального поиска: "поиск с запретами" ts, "моделирование отжига"...
Задача нерегулярного размещения геометрических объектов: годограф ориентированная адаптация метода \"моделирование отжига\" iconРеферат статические модели задачи размещения
Производственно-транспортные задачи оптимального размещения предприятий и применимость метода последовательных расчетов
Задача нерегулярного размещения геометрических объектов: годограф ориентированная адаптация метода \"моделирование отжига\" iconУрок Моделирование объектов на основе примитивов Светлана Шляхтина
Комплексное использование различных вариантов выделения, выравнивания и клонирования объектов при создании сцен
Задача нерегулярного размещения геометрических объектов: годограф ориентированная адаптация метода \"моделирование отжига\" iconМорской симулятор Задание параметров судна
«Конструирование» судна из заданных геометрических объектов и задача параметров, таких как масса, коэффициенты сопротивления и т...
Задача нерегулярного размещения геометрических объектов: годограф ориентированная адаптация метода \"моделирование отжига\" iconУрок по теме «Моделирование» Цель: обобщить и систематизировать знания по теме «Моделирование», продолжить формирование умений строить модели объектов и процессов
Развивать представление об информационной картине мира, умение работать в программе Power Point
Задача нерегулярного размещения геометрических объектов: годограф ориентированная адаптация метода \"моделирование отжига\" iconВісник Харківського національного університету №987, 2011
Этим методом получена параллельная модификация компактной схемы метода Гаусса решения линейных систем, ориентированная на современную...
Задача нерегулярного размещения геометрических объектов: годограф ориентированная адаптация метода \"моделирование отжига\" iconЛекция По дисциплине «Социально-психологическая адаптация»
Айрапетян С. Г. Возникновение, развитие и основные сферы использования понятия «адаптация». Ереван, 1984
Задача нерегулярного размещения геометрических объектов: годограф ориентированная адаптация метода \"моделирование отжига\" iconУрок обобщения и систематизации знаний. Цель урока: систематизация сведений о четырехугольниках. Задачи
Активизация поисково-познавательной деятельности в процессе решения задач на моделирование геометрических фигур, установление их...
Задача нерегулярного размещения геометрических объектов: годограф ориентированная адаптация метода \"моделирование отжига\" iconПлан-конспект родительского собрания №1 по плану лектория Тема: «Адаптация первоклассников к обучению в школе»
Ознакомить родителей с трудностями вступления в школьную жизнь. Понятия «школьная зрелость», «психологическая адаптация»
Разместите ссылку на наш сайт:
Уроки, сочинения


База данных защищена авторским правом ©izlov.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
связаться с нами