Жадная рандомизированная процедура адаптивного поиска

Жадная рандомизированная процедура адаптивного поиска (также известная как GRASP ) — это метаэвристический алгоритм, обычно применяемый для решения комбинаторной оптимизации задач . GRASP обычно состоит из итераций, состоящих из последовательных построений жадного рандомизированного решения и последующих итеративных его улучшений посредством локального поиска . ^[1] Жадные рандомизированные решения генерируются путем добавления элементов в набор решений проблемы из списка элементов, ранжированных жадной функцией в соответствии с качеством решения, которого они достигнут. Чтобы добиться вариативности в наборе кандидатов жадных решений, элементы-кандидаты с хорошим рейтингом часто помещаются в ограниченный список кандидатов (RCL) и выбираются случайным образом при построении решения. Этот вид жадного метода рандомизированного построения также известен как полужадная эвристика , впервые описанная Хартом и Шоганом (1987). ^[2]

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

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

См. также

Ссылки

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

Эта комбинаторике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее .

[Feo1995-1] Перейти обратно: ^а ^б Фео, Томас А.; Резенде, Маурисио Г.К. (1995). «Жадные рандомизированные процедуры адаптивного поиска». Журнал глобальной оптимизации . 6 (2): 109–133. дои : 10.1007/BF01096763 . S2CID 2110014 .

[2] Харт, JP; Шоган, AW (июль 1987 г.). «Полужадная эвристика: эмпирическое исследование». Письма об исследованиях операций . 6 (3): 107–114. дои : 10.1016/0167-6377(87)90021-6 .

[3] Фео, Томас А.; Ресенде, Маурисио Г.К. (апрель 1989 г.). «Вероятностная эвристика для вычислительно сложной задачи покрытия множества». Письма об исследованиях операций . 8 (2): 67–71. дои : 10.1016/0167-6377(89)90002-3 .

[Resende2003-4] Перейти обратно: ^а ^б Ресенде, Маурисио Г.К.; Рибейро, Селсо К. (2003). «Жадные рандомизированные процедуры адаптивного поиска». Справочник по метаэвристике . Спрингер. стр. 219–249. ISBN 978-0-306-48056-0 .

[5] Слава Марсело; Рибейро, Селсо К. (2000). «Реактивный GRASP: приложение к задаче разложения матрицы при назначении трафика TDMA». ИНФОРМС Журнал по вычислительной технике . 12 (3): 164–176. дои : 10.1287/ijoc.12.3.164.12639 .

[1]

[2]

[3]

[4]

[5]