Управляемый локальный поиск (Rhjgflxybdw lktgl,udw hknvt)

Перейти к навигации Перейти к поиску

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

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

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

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

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

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

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

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

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

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

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

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

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

Поиск увеличенной функции цены

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

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

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

Примечания

[править | править код]
  1. Скобцов и Фёдоров (Скобцов, Фёдоров 2013, 28) ссылаются на статью (Voudouris, Tsang 2001, 29-39), хотя сам Цанг пишет: «Управляемый локальный поиск является результатом исследований с главной целью развить нейронную сеть GENET на задачу удовлетворения ограничений с частичным удовлетворением и комбинаторные оптимизационные задачи. Начав с GENET мы разработали много промежуточных алгоритмов, таких как Tunneling Algorithm и завершили разработкой алгоритма управляемого локального поиска, представленного в этой статье». Речь идёт о статье 1995 года (Voudouris, Tsang 1995)
  2. Minton, Johnston, Philips, Laird, 1992, с. 161-205.
  3. Yokoo, Hirayama, 1996, с. 401-408.
  4. Zhang, Wittenburg, 2002.
  5. 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.