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