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

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

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

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

ОбзорПравить

Свойства решенияПравить

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

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

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

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

Выборочные изменения штрафовПравить

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

\text{[math]}

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

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

Поиск увеличенной функции ценыПравить

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

\text{[math]}

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

Может быть использован параметр $\text{[math]}$ $\text{[math]}$ $\lambda$ , чтобы изменить интенсивность поиска решений. Более высокие значения $\text{[math]}$ $\text{[math]}$ $\lambda$ приведёт к более широкому поиску, когда горизонтальные участки и впадины просматриваются более грубо. Низкое значение приведёт к более детальному поиску на горизонтальных участках и впадинах. Коэффициент $\text{[math]}$ $\text{[math]}$ $a$ используется для того, чтобы сделать штрафную часть целевой функции более сбалансированной относительно изменений целевой функции, и зависит от задачи. Простой эвристический подход для назначения $\text{[math]}$ $\text{[math]}$ $a$ — просто записывать среднее изменение в целевой функции до первого локального минимума, а потом установить $\text{[math]}$ $\text{[math]}$ $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]