Очень крупномасштабный поиск окрестностей - Very large-scale neighborhood search

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

Полученные в результате алгоритмы могут превзойти алгоритмы, использующие небольшие окрестности, потому что локальные улучшения больше. Если поиск соседства ограничен одним или очень небольшим количеством изменений из текущего решения, то может быть трудно выйти из локальных минимумов, даже с помощью дополнительных метаэвристических методов, таких как Имитация отжига или Табу поиск. В методах поиска больших окрестностей возможные изменения от одного решения к его соседнему могут позволить изменяться десяткам или сотням значений, и это означает, что размер окрестности может быть сам по себе достаточным, чтобы позволить процессу поиска избежать или избежать локальных минимумов, хотя дополнительные метаэвристические методы все же могут улучшить производительность.

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

• Ахуджа, Равиндра К.; Орлин, Джеймс Б.; Шарма, Душянт (2000), «Очень масштабный поиск окрестностей» (PDF), Международные операции в операционных исследованиях, 7 (4–5): 301–317, Дои:10.1111 / j.1475-3995.2000.tb00201.x