Локальный поиск (удовлетворение ограничений)

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

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

Точка А не является решением, но никакое локальное движение оттуда не снижает затраты. Однако решение существует в точке Б.

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

Жадные алгоритмы

восхождение на холм

Самая основная форма локального поиска основана на выборе изменения, которое максимально снижает стоимость решения. Этот метод, называемый восхождением на холм , действует следующим образом: сначала выбирается случайное задание; затем значение изменяется так, чтобы максимально улучшить качество полученного задания. Если после заданного количества изменений решение не найдено, выбирается новое случайное задание. Алгоритмы восхождения на холм могут выйти из плато только путем внесения изменений, которые не меняют качество задания. В результате они могут застрять на плато, где качество назначения имеет локальные максимумы.

GSAT (жадный сат) был первым алгоритмом локального поиска выполнимости и представляет собой форму восхождения на холм.

Метод взвешивания ограничений или метода прорыва

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

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

Табу-поиск

Недостатком восхождения на холм с движениями, которые не уменьшают стоимость, является то, что оно может циклически повторять задания одной и той же стоимости. Табу-поиск ^[1]^[2]^[3] решает эту проблему, поддерживая список «запрещенных» назначений, называемый списком запретов . В частности, список запретов обычно содержит только самые последние изменения. Точнее, он содержит последнюю пару переменная-значение, значение которой недавно было присвоено переменной.

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

Случайное блуждание

Алгоритм случайного блуждания иногда действует как жадный алгоритм, но иногда движется случайным образом. Это зависит от параметра $p$ , которое является действительным числом от 0 до 1. На каждом ходу с вероятностью $p$ алгоритм действует как жадный алгоритм, пытаясь максимально снизить стоимость задания. С вероятностью $1-p$ , однако решение изменяется каким-то другим способом, который предполагает некоторую степень случайности.

WalkSAT

Случайное перемещение WalkSAT — это изменение значения случайной величины случайного нарушенного ограничения. Для пропозициональной выполнимости формул конъюнктивной нормальной формы , которая является исходной настройкой этого алгоритма, каждый такой ход меняет значение переменной с истинного на ложное или наоборот и обеспечивает выполнимость нарушенного ограничения. Как и во всех стратегиях случайного блуждания, случайный ход делается только с заданной вероятностью, в противном случае делается ход, максимально уменьшающий стоимость.

Имитация отжига

Методика имитации отжига основана на изменении вероятности выполнения случайного хода на ту, которая максимально снижает стоимость. В частности, название происходит от стратегии уменьшения вероятности выполнения случайных ходов во время выполнения алгоритма, что фактически «замораживает» пространство поиска.

В частности, если улучшение стоимости $d$ хода отрицательный (ход увеличивает стоимость), этот ход делается с вероятностью $e^{-d\cdot T}$ , где $T$ это действительное число. Поскольку вероятность выполнения этого хода увеличивается с $T$ , этот параметр называется температурой . Имитированный отжиг снижает эту температуру с течением времени, тем самым допуская больше случайных движений в начале и меньше после времени.

Локальный поиск на циклическом разрезе

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

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

Это минимальное число находится путем определения стоимости каждого присвоения переменной. Эта стоимость представляет собой минимальное количество ограничений, нарушаемых присвоением переменных в поддереве, корнем которого является переменная, когда переменная принимает заданное значение. Эту стоимость можно рассчитать следующим образом. Если $Cost(x=a)$ обозначает стоимость задания $x=a$ и $y_{1},\ldots ,y_{n}$ дети $x$ , имеет место следующая формула. В этой формуле $Violates(x=a,y_{i}=b)$ это 0 или 1 в зависимости от того, было ли присвоение $x=a,y_{i}=b$ нарушает ограничение между $x$ и $y$ .

Cost(x=a)=\sum _{i=1,\ldots ,n}\min _{y_{i}=b}(Cost(y_{i}=b)+Violates(x=a,y_{i}=b))

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

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

Внешние ссылки

Принудительно выполнимые тесты CSP и SAT модели RB

Ссылки

^ Гловер, Фред (январь 1986 г.). «Будущие пути целочисленного программирования и связи с искусственным интеллектом» . Компьютеры и исследования операций . 13 (5): 533–549. дои : 10.1016/0305-0548(86)90048-1 .
^ Гловер, Фред (август 1989 г.). «Поиск табу — Часть I» . Журнал ORSA по вычислительной технике . 1 (3): 190–206. дои : 10.1287/ijoc.1.3.190 . ISSN 0899-1499 .
^ Гловер, Фред (февраль 1990 г.). «Поиск табу — Часть II» . Журнал ORSA по вычислительной технике . 2 (1): 4–32. дои : 10.1287/ijoc.2.1.4 . ISSN 0899-1499 .

Дектер, Рина (2003). Обработка ограничений . Морган Кауфманн. ISBN 978-1-55860-890-0 .

[1] Гловер, Фред (январь 1986 г.). «Будущие пути целочисленного программирования и связи с искусственным интеллектом» . Компьютеры и исследования операций . 13 (5): 533–549. дои : 10.1016/0305-0548(86)90048-1 .

[2] Гловер, Фред (август 1989 г.). «Поиск табу — Часть I» . Журнал ORSA по вычислительной технике . 1 (3): 190–206. дои : 10.1287/ijoc.1.3.190 . ISSN 0899-1499 .

[3] Гловер, Фред (февраль 1990 г.). «Поиск табу — Часть II» . Журнал ORSA по вычислительной технике . 2 (1): 4–32. дои : 10.1287/ijoc.2.1.4 . ISSN 0899-1499 .

[1]

[2]

[3]