Жадная рандомизированная процедура адаптивного поиска - Википедия - Greedy randomized adaptive search procedure

В жадная рандомизированная процедура адаптивного поиска (также известен как ПОНЯТЬ) это метаэвристический алгоритм обычно применяется к комбинаторная оптимизация проблемы. GRASP обычно состоит из итераций, состоящих из последовательных построений жадный рандомизированный решение и последующие итерационные улучшения его через местный поиск.[1] Жадные рандомизированные решения генерируются путем добавления элементов в набор решений проблемы из списка элементов, ранжированных по жадная функция в зависимости от качества решения, которого они добьются. Чтобы получить вариативность в наборе кандидатов жадных решений, хорошо ранжированные элементы-кандидаты часто помещаются в ограниченный список кандидатов (RCL) и выбирается случайным образом при построении решения. Этот вид жадного рандомизированного метода построения также известен как полужадный эвристический, впервые описанный в Hart and Shogan (1987).[2]

GRASP был впервые представлен Фео и Резенде (1989).[3]Обзорные статьи по GRASP включают Feo and Resende (1995),[1] и Ресенде и Рибейро (2003).[4]

Существуют вариации классического алгоритма, например, Reactive GRASP. В этом варианте основной параметр, определяющий ограниченность RCL на этапе строительства, саморегулируется в соответствии с качеством ранее найденных решений.[5]Существуют также методы для ускорения поиска, такие как изменение стоимости, функции смещения, запоминание и обучение, а также локальный поиск частично построенных решений.[4]

Рекомендации

  1. ^ а б Feo, Thomas A .; Ресенде, Маурисио Г. К. (1995). «Жадные рандомизированные процедуры адаптивного поиска». Журнал глобальной оптимизации. 6 (2): 109–133. Дои:10.1007 / BF01096763.
  2. ^ Hart, J. P .; Шоган, А. В. (июль 1987 г.). «Полужадная эвристика: эмпирическое исследование». Письма об исследованиях операций. 6 (3): 107–114. Дои:10.1016/0167-6377(87)90021-6.
  3. ^ Feo, Thomas A .; Ресенде, Маурисио Г. К. (апрель 1989 г.). «Вероятностная эвристика для вычислительно сложной задачи покрытия множества». Письма об исследованиях операций. 8 (2): 67–71. Дои:10.1016/0167-6377(89)90002-3.
  4. ^ а б Resende, Mauricio G.C .; Рибейро, Селсо К. (2003). «Жадные рандомизированные процедуры адаптивного поиска». Справочник по метаэвристике. Springer. С. 219–249. ISBN  978-0-306-48056-0.
  5. ^ Хвала, Марсело; Рибейро, Селсо К. (2000). «Реактивный GRASP: приложение к проблеме матричной декомпозиции в назначении трафика TDMA». ИНФОРМС Журнал по вычислительной технике. 12 (3): 164–176. Дои:10.1287 / ijoc.12.3.164.12639.

Смотрите также