Управляемый локальный поиск

Для применения GLS свойства решения должны быть определены для заданной задачи. Свойства решения определены для разграничения решений с различными характеристиками, так что области сходства вокруг оптимума могут быть распознаны и исключены. Выбор свойств решения зависит от типа задачи и также от алгоритмов поиска. Для каждого свойства ${\displaystyle f_{i}}$ определяется ценовая функция ${\displaystyle c_{i}}$.

Каждое свойство ассоциируется со штрафом ${\displaystyle p_{i}}$ (первоначально равным 0), отражающим число попаданий свойства в локальный минимум.

Свойства и цены зачастую приходят прямо вместе с целевой функцией. Например, в задаче коммивояжёра «маршрут из города X идёт непосредственно в город Y» можно рассматривать как свойство. Расстояние между X и Y можно определить как цену. В задачах SAT и взвешенной MAX-SAT свойствами могут быть «утверждение C удовлетворяет текущим назначениям переменных».

На уровне реализации мы определяем для каждого свойства ${\displaystyle i}$ характеристическую функцию ${\displaystyle I_{i}}$, указывающую, представлено ли свойство в текущем решении или нет. ${\displaystyle I_{i}}$ равно 1, если решение ${\displaystyle x}$ содержит свойство ${\displaystyle i}$, 0 в противном случае.

GLS вычисляет полезность штрафов для каждого свойства. Когда алгоритм локального поиска возвращает локальный минимум x, GLS штрафует все те свойства (путём увеличения штрафа на свойство), представленные в решении, в которых имеется максимальная полезность ${\displaystyle \operatorname {util} (x,i)}$, как определено ниже.

${\displaystyle \operatorname {util} (x,i)=I_{i}(x){\frac {c_{i}(x)}{1+p_{i}}}.}$

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

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

${\displaystyle g(x)=f(x)+\lambda a\sum _{1\leq i\leq m}I_{i}(x)p_{i}}$

Может быть использован параметр ${\displaystyle \lambda }$, чтобы изменить интенсивность поиска решений. Более высокие значения ${\displaystyle \lambda }$ приведёт к более широкому поиску, когда горизонтальные участки и впадины просматриваются более грубо. Низкое значение приведёт к более детальному поиску на горизонтальных участках и впадинах. Коэффициент ${\displaystyle a}$ используется для того, чтобы сделать штрафную часть целевой функции более сбалансированной относительно изменений целевой функции, и зависит от задачи. Простой эвристический подход для назначения ${\displaystyle a}$ — просто записывать среднее изменение в целевой функции до первого локального минимума, а потом установить ${\displaystyle a}$ в это значение, делённое на число свойств GLS в задаче.

Миллс (2002) описал расширенный управляемый локальный поиск (EGLS), который использует случайные движения и критерий использования, специально разработанный для основанных на штрафных схемах. Получающийся алгоритм улучшает устойчивость GLS относительно разброса параметров, особенно в случае квадратичной задачи о назначениях. Основная версия алгоритма GLS, использующая восхождение на основе минимального конфликта[2] и частично основанная на GENET для удовлетворения ограничений и оптимизации, была реализована в проекте Computer Aided Constraint Programming (Компьютеризованное Программирование в Ограничениях).

Алшедди (2011) расширил управляемый локальный поиск для многокритериальной оптимизации и продемонстрировал его использование в планировании.