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

Управляемый локальный поиск (англ. Guided Local Search, GLS) — это метаэвристический метод поиска, то есть метод поверх алгоритма локального поиска с целью изменить его поведение.

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

Управляемый локальный поиск (англ. guided local search) был предложен Вудурисом (Voudouris) и Цангом (Tsang)^[1].

Для применения 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) расширил управляемый локальный поиск для многокритериальной оптимизации и продемонстрировал его использование в планировании.

GLS была построена на системе GENET, которую разработали Чанг Ван, Эдвард Цанг и Эндрю Дэвенпорт.

Метод прорыва^[англ.] очень похож на GENET. Он был разработан для удовлетворения ограничений^[3][4].

Поиск с запретами — это класс методов поиска, который может быть реализован для специфичных методов. GLS можно рассматривать как специальный случай поиска с запретами.

Используя GLS поверх генетического алгоритма, Тунг-ленг Лау ввёл управляемый генетический алгоритм (англ. Guided Genetic Programming, GGA). Он был успешно применён для общей задачи назначения (для расписаний), задачи конфигурации процессоров и назначения радиочастот (военного назначения).

Чой, Ли и Стаки^[5] представили GENET как лагранжианов поиск.

• Guided Local Search Home Page