ПОНЯТЬ

Процедура жадного рандомизированного адаптивного поиска (GRASP)

Алгоритм жадной рандомизированной адаптивной процедуры поиска (GRASP) представляет собой метаэвристический введен Фео и Резенде в 1989 году.

Его действие основано на повторении двух фаз: прожорливая конструкция, за которой следует локальный поиск.

Характерной чертой метода GRASP является этап построения решения. Для этого алгоритм поддерживает список возможных фрагментов решения (RCL, ограниченный список кандидатов). Решение строится шаг за шагом путем выбора элементов (в нашем случае это выигрыши от объединения мешей в зоны) в списке RCL. Этот список отсортирован, это жадная часть алгоритма.

Элемент выбирается случайным образом среди лучших возможностей списка RCL, это случайная часть алгоритма. Таким образом, благодаря случайной части фаза построения позволяет варьировать форму генерируемых решений, но они хорошего качества, поскольку случайный выбор делается из набора хороших кандидатов. Локальные исследования применяются к возможному решению, полученному на этапе строительства, чтобы увидеть, возможно ли улучшить это решение.

Следует отметить два момента:
  • RCL обновляется элементами, выбранными в соответствии с определенной эвристикой, адаптированной к рассматриваемой проблеме.
  • выбор элемента в RCL для построения решения является случайным.
Процедура жадного рандомизированного адаптивного поиска GRASP

 

Делиться
ru_RURU
%d такие блоггеры, как: