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

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

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

Ссылки