Войти
жадная рандомизированная процедура адаптивного поиска (также известная как GRASP ) - это метаэвристический алгоритм, обычно применяемый к задачам комбинаторной оптимизации. GRASP обычно состоит из итераций, состоящих из последовательных построений greedy рандомизированного решения и последующих итерационных улучшений его посредством локального поиска. Жадные рандомизированные решения генерируются путем добавления элементов к набору решений проблемы из списка элементов, ранжированных жадной функцией в соответствии с качеством решения, которого они достигают. Чтобы получить вариативность в наборе кандидатов жадных решений, хорошо ранжированные элементы-кандидаты часто помещаются в ограниченный список кандидатов (RCL) и выбираются случайным образом при построении решения. Этот вид жадного рандомизированного метода построения также известен как полужадная эвристика, впервые описанный в Hart and Shogan (1987).
GRASP был впервые представлен в Feo and Resende (1989).. Обзорные статьи по GRASP включают Feo and Resende (1995) и Resende and Ribeiro (2003).
Существуют разновидности классического алгоритма, такие как Reactive GRASP. В этом варианте основной параметр, определяющий ограниченность RCL на этапе строительства, саморегулируется в соответствии с качеством ранее найденных решений. Существуют также методы ускорения поиска, такие как изменение стоимости, функции смещения, запоминание и обучение, а также локальный поиск частично сконструированных решений.
.
.
