Очень масштабный поиск соседей

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

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

Ссылки

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