Войти
В информатике локальный поиск является эвристикой метод решения вычислительно сложных задач оптимизации. Локальный поиск можно использовать для решения проблем, которые можно сформулировать как поиск решения, максимизирующего критерий среди множества возможных решений. Алгоритмы локального поиска переходят от решения к решению в пространстве возможных решений (пространстве поиска), применяя локальные изменения, до тех пор, пока не будет найдено решение, которое считается оптимальным, или не истечет срок.
Алгоритмы локального поиска широко применяются для решения множества сложных вычислительных задач, включая задачи из информатики (в частности, искусственного интеллекта ), математики, исследования операций, инженерия и биоинформатика. Примерами алгоритмов локального поиска являются WalkSAT, 2-опционный алгоритм для задачи коммивояжера и алгоритм Метрополиса – Гастингса.
Некоторые проблемы, связанные с применением локального поиска:
Большинство проблем можно сформулировать в терминах пространства поиска и цели несколькими разными способами. Например, для задачи коммивояжера решением может быть цикл, а критерий максимизации - сочетание количества узлов и длины цикла. Но решение также может быть путем, а быть циклом - это часть цели.
Алгоритм локального поиска начинается с решения-кандидата, а затем итеративно переходит к соседнему решению. Это возможно только в том случае, если в области поиска определено a. Например, окрестность вершинного покрытия - это другое вершинное покрытие, отличающееся только одним узлом. Для логической выполнимости соседями присвоения истинности обычно являются присвоения истинности, отличающиеся от него только оценкой переменной. Одна и та же проблема может иметь несколько разных окрестностей; локальная оптимизация с соседями, включающая изменение до k компонентов решения, часто называется k-opt .
Как правило, каждое решение-кандидат имеет более одного соседнего решения; выбор, к которому перейти, осуществляется с использованием только информации о решениях в окрестности текущего, отсюда и название локальный поиск. Когда выбор соседнего решения осуществляется путем взятия решения, локально максимизирующего критерий, метаэвристика принимает название восхождение на холм. Если поблизости нет улучшающих конфигураций, локальный поиск застревает в локально оптимальной точке. Эта проблема локальной оптимизации может быть решена с помощью перезапусков (повторный локальный поиск с разными начальными условиями) или более сложных схем, основанных на итерациях, таких как итерационный локальный поиск, в памяти, как оптимизация реактивного поиска, в памяти -без стохастических модификаций, таких как имитация отжига.
Прекращение локального поиска может быть основано на ограничении по времени. Другой распространенный выбор - завершить работу, когда лучшее решение, найденное алгоритмом, не было улучшено за заданное количество шагов. Локальный поиск - это алгоритм в любое время : он может вернуть действительное решение, даже если он прерван в любой момент до его завершения. Алгоритмы локального поиска обычно представляют собой приближение или, поскольку поиск может остановиться, даже если лучшее решение, найденное алгоритмом, не является оптимальным. Это может произойти, даже если остановка связана с невозможностью улучшения решения, поскольку оптимальное решение может находиться далеко от окрестности решений, пересекаемых алгоритмами.
Для конкретных задач можно разработать окрестности очень большого размера, возможно, экспоненциального размера. Если лучшее решение в окрестности может быть эффективно найдено, такие алгоритмы называются алгоритмами очень крупномасштабного поиска по соседству.
Локальный поиск - это подполе:
Поля в локальном поиске включают:
Существуют несколько методов для выполнения локального поиска вещественных пространств поиска:
