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

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

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

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

Обзор[править | править код]

Свойства решения[править | править код]

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

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

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

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

Выборочные изменения штрафов[править | править код]

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

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

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

Поиск увеличенной функции цены[править | править код]

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

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

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

Расширения управляемого локального поиска[править | править код]

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

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

Связанные работы[править | править код]

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

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

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

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

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

Примечания[править | править код]

↑ Скобцов и Фёдоров (Скобцов, Фёдоров 2013, 28) ссылаются на статью (Voudouris, Tsang 2001, 29-39), хотя сам Цанг пишет: «Управляемый локальный поиск является результатом исследований с главной целью развить нейронную сеть GENET на задачу удовлетворения ограничений с частичным удовлетворением и комбинаторные оптимизационные задачи. Начав с GENET мы разработали много промежуточных алгоритмов, таких как Tunneling Algorithm и завершили разработкой алгоритма управляемого локального поиска, представленного в этой статье». Речь идёт о статье 1995 года (Voudouris, Tsang 1995)
↑ Minton, Johnston, Philips, Laird, 1992, с. 161-205.
↑ Yokoo, Hirayama, 1996, с. 401-408.
↑ Zhang, Wittenburg, 2002.
↑ Choi, Lee, Stuckey, 2000, с. 1-39.

Литература[править | править код]

Chris Voudouris and Edward Tsang. Guided Local Search // Technical Report CSM. — 1995. — Вып. CSM-247.
Alsheddy A. Empowerment scheduling: a multi-objective optimization approach using Guided Local Search. — University of Essex: School of Computer Science and Electronic Engineering, 2011. — (PhD Thesis).
Choi K.M.F., Lee J.H.M., Stuckey P.J. A Lagrangian Resconstruction of GENET // Artificial Intelligence. — 2000. — Т. 123, № 1-2. — С. 1—39.
Davenport A., Tsang E.P.K., Kangmin Zhu, Wang C. J. GENET: A connectionist architecture for solving constraint satisfaction problems by iterative improvement // Proc., AAAI. — 1994. — С. 325—330.
Lau T.L., Tsang E.P.K. Solving the processor configuration problem with a mutation-based genetic algorithm // International Journal on Artificial Intelligence Tools (IJAIT). — World Scientific, 1997. — Декабрь (т. 6, № .4). — С. 567—585.
Lau T.L., Tsang E.P.K. Guided genetic algorithm and its application to radio link frequency assignment problems // Constraints. — 2001. — Т. 6, № 4. — С. 373—398.
Lau T.L., Tsang E.P.K. The guided genetic algorithm and its application to the general assignment problems // IEEE 10th International Conference on Tools with Artificial Intelligence (ICTAI'98). — Taiwan, 1998.
Mills P., Tsang E.P.K. Guided local search for solving SAT and weighted MAX-SAT problems // Journal of Automated Reasoning, Special Issue on Satisfiability Problems. — Kluwer, 2000. — Т. 24. — С. 205—223.
Mills P., Tsang E.P.K., Ford J. Applying an Extended Guided Local Search on the Quadratic Assignment Problem // Annals of Operations Research. — Kluwer Academic Publishers, 2003. — Т. 118. — С. 121—135.
Minton S., Johnston M., Philips A.B., Laird P. Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems // Artificial Intelligence (Special Volume on Constraint Based Reasoning). — 1992. — Т. 58, № 1-3. — С. 161—205.
Tsang E.P.K., Voudouris C. Fast local search and guided local search and their application to British Telecom's workforce scheduling problem // Operations Research Letters. — Amsterdam: Elsevier Science Publishers, 1997. — Март (т. 20, № .3). — С. 119—127.
Voudouris C. Guided local search for combinatorial optimisation problems. — Colchester, UK: Department of Computer Science, University of Essex, 1997. — (PhD Thesis). Архивная копия от 14 февраля 2007 на Wayback Machine
Voudouris C. Guided Local Search—An illustrative example in function optimization // BT Technology Journal. — 1998. — Июль (т. 16, № 3). — С. 46—50.
Voudouris C., Tsang E.P.K. Guided Local Search and its application to the Travelling Salesman Problem // European Journal of Operational Research. — Anbar Publishing, 1999. — Март (т. 113, вып. 2). — С. 469—499.
Скобцов Ю.А., Фёдоров Е.Е. Метаэвристики. — Донецк: «Ноулидж» Донецкое отделение, 2013. — ISBN 978-617-579-613-9.
Voudouris C., Tsang E.P.K. Guided local search joins the elite in discrete optimization // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. — 2001. — Т. 57. — С. 29—39.
Voudouris C., Tsang E.P.K. Guided local search, in F. Glover (ed.) // Handbook of metaheuristics. — Kluwer, 2003. — С. 185—218.
Voudouris C., Tsang E.P.K., Alsheddy A. Guided local search, Chapter 11 // Handbook of Metaheuristics / M. Gendreau, J-Y Potvin (ed.). — Springer, 2010. — С. 321—361.
M. Yokoo, K. Hirayama. Distributed breakout algorithm for solving distributed constraint satisfaction problems // Proceedings of the Second International Conference on Multi-Agent Systems. — 1996. — С. 401—408.
W. Zhang, L. Wittenburg. Distributed breakout revisited // Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI-02). — Edmonton, AB, 2002.

Ссылки[править | править код]

Guided Local Search Home Page

[1] Скобцов и Фёдоров (Скобцов, Фёдоров 2013, 28) ссылаются на статью (Voudouris, Tsang 2001, 29-39), хотя сам Цанг пишет: «Управляемый локальный поиск является результатом исследований с главной целью развить нейронную сеть GENET на задачу удовлетворения ограничений с частичным удовлетворением и комбинаторные оптимизационные задачи. Начав с GENET мы разработали много промежуточных алгоритмов, таких как Tunneling Algorithm и завершили разработкой алгоритма управляемого локального поиска, представленного в этой статье». Речь идёт о статье 1995 года (Voudouris, Tsang 1995)

[_0d4c6a92aa6d4e87-2] Minton, Johnston, Philips, Laird, 1992, с. 161-205.

[_8d42e3d8641b580d-3] Yokoo, Hirayama, 1996, с. 401-408.

[_4b1ac6a8af99f280-4] Zhang, Wittenburg, 2002.

[_ddcee215f5b4b086-5] Choi, Lee, Stuckey, 2000, с. 1-39.

[1]

[2]

[3]

[4]

[5]

Методы оптимизации
Одномерные	Метод золотого сечения Дихотомия Метод парабол Перебор по сетке Метод равномерного блочного поиска Метод Фибоначчи Троичный поиск Метод Пиявского Метод Стронгина
Нулевого порядка	Метод Гаусса Метод Нелдера — Мида Метод Хука — Дживса Метод Розенброка Метод Пауэлла
Первого порядка	Градиентный спуск Метод Зойтендейка Покоординатный спуск Метод сопряжённых градиентов Квазиньютоновские методы Алгоритм Левенберга — Марквардта Риманова оптимизация
Второго порядка	Метод Ньютона Метод Ньютона — Рафсона Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно (BFGS)
Стохастические	Метод Монте-Карло Имитация отжига Эволюционные алгоритмы Дифференциальная эволюция Муравьиный алгоритм Метод роя частиц Алгоритм пчелиной колонии Метод случайных блужданий
Методы линейного программирования	Симплекс-метод Алгоритм Гомори Метод эллипсоидов Метод потенциалов
Методы нелинейного программирования	Последовательное квадратичное программирование