Локальный поиск (оптимизация)
-
Основы локального поиска
- Локальный поиск — это эвристический метод оптимизации, который применяется для решения сложных задач.
- Алгоритмы локального поиска исследуют пространство решений, используя локальные изменения, пока не будет найдено оптимальное решение или не истечет время.
-
Применение и примеры
- Локальный поиск используется в различных областях, включая компьютерные науки, математику, инженерию и биоинформатику.
- Примеры алгоритмов включают WalkSAT, двухпозиционный алгоритм для задачи коммивояжера и алгоритм Метрополиса-Гастингса.
-
Проблемы и решения
- Задачи, решаемые локальным поиском, включают покрытие вершин, задачу коммивояжера, логическую выполнимость и планирование работы медсестер.
- Локальный поиск предлагает наилучшие известные коэффициенты аппроксимации для задач кластеризации k-medoid и нейронных сетей Хопфилда.
-
Описание и оптимизация
- Задачи могут быть сформулированы различными способами, включая поиск кратчайшего маршрута или цикла.
- Локальный поиск начинается с решения-кандидата и итеративно переходит к соседним решениям, определяя окрестность решений.
- Выбор следующего решения осуществляется на основе информации о ближайших решениях, что приводит к названию «локальный поиск».
-
Завершение и эффективность
- Локальный поиск может остановиться в локально оптимальной точке или после достижения заданного времени или улучшения текущего решения.
- Алгоритм может вернуть верное решение даже после прерывания, и он обычно является неполным, так как может не найти оптимальное решение.
-
Показатели эффективности
- Шуурман и Саути предложили три показателя эффективности: глубину, мобильность и охват.
- Алгоритмы должны быстро перемещаться по пространству поиска и исследовать его на малых глубинах.
-
Методы локального поиска
- Существуют различные методы локального поиска для вещественнозначных пространств, включая равномерное распределение и экспоненциальное уменьшение диапазона поиска.
-
Рекомендации и библиография
- В статье приведены ссылки на литературу по стохастическому локальному поиску и эвристике локального поиска для различных задач.
Полный текст статьи: