Локальный поиск (оптимизация) - Local search (optimization)

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

Алгоритмы локального поиска широко применяются для решения множества сложных вычислительных задач, включая задачи информатики (особенно искусственного интеллекта ), математики , исследования операций , инженерии и биоинформатики . Примерами алгоритмов локального поиска являются WalkSAT , двунаправленный алгоритм для задачи коммивояжера и алгоритм Метрополиса – Гастингса .

Примеры

Некоторые проблемы, связанные с применением локального поиска:

  1. Проблема вершины крышки , в котором раствор представляет собой вершину крышка из графика , и цель , чтобы найти решение с минимальным числом узлов
  2. Задача коммивояжера , в которой решение представляет собой цикл, содержащий все узлы графа, а цель состоит в том, чтобы минимизировать общую длину цикла.
  3. Проблема логической выполнимости , в которой возможным решением является присвоение истинности, а цель состоит в том, чтобы максимизировать количество предложений, удовлетворяемых этим назначением; в этом случае окончательное решение можно использовать только в том случае, если оно удовлетворяет всем пунктам
  4. Задача расписания медсестер, решение которой - распределение медсестер по сменам, удовлетворяющее всем установленным ограничениям.
  5. К-медоид проблема кластеризации и другие связанные местоположения объекта задачи , для которых локального поиска предлагает оптимальное соотношение между известным приближением из наихудшего перспективы
  6. Задача нейронных сетей Хопфилда, для которой необходимо найти стабильные конфигурации в сети Хопфилда .

Описание

Большинство проблем можно сформулировать с точки зрения пространства поиска и цели несколькими различными способами. Например, для задачи коммивояжера решением может быть цикл, а критерием максимизации является комбинация количества узлов и длины цикла. Но решение также может быть путем, а быть циклом - это часть цели.

Алгоритм локального поиска начинается с решения кандидата, а затем итеративно переходит к решению соседа . Это возможно только в том случае, если в пространстве поиска определено отношение соседства . Например, окрестность вершинного покрытия - это другое вершинное покрытие, отличающееся только одним узлом. Для логической выполнимости соседями присвоения истинности обычно являются присвоения истинности, отличающиеся от него только оценкой переменной. Одна и та же проблема может иметь несколько разных окрестностей; локальная оптимизация с окрестностями, включающая изменение до k компонентов решения, часто называется k-opt .

Как правило, каждое решение-кандидат имеет более одного соседнего решения; выбор того, к какому из них перейти, осуществляется с использованием только информации о решениях в окрестности текущего, отсюда и название локальный поиск. Когда выбор соседнего решения осуществляется путем взятия решения, локально максимизирующего критерий, метаэвристика получает название « восхождение на холм» . Когда поблизости нет улучшающих конфигураций, локальный поиск застревает в локально оптимальной точке . Эта проблема локальной оптимизации может быть решена с помощью перезапусков (повторный локальный поиск с разными начальными условиями) или более сложных схем, основанных на итерациях, таких как повторный локальный поиск , в памяти, например, оптимизация реактивного поиска, на стохастических модификациях без памяти, например имитация отжига .

Прекращение локального поиска может быть основано на ограничении времени. Другой распространенный выбор - завершить работу, когда лучшее решение, найденное алгоритмом, не было улучшено за заданное количество шагов. Локальный поиск - это алгоритм, работающий в любое время : он может вернуть действительное решение, даже если он был прерван в любое время до его завершения. Алгоритмы локального поиска обычно представляют собой приближенные или неполные алгоритмы , поскольку поиск может остановиться, даже если лучшее решение, найденное алгоритмом, не является оптимальным. Это может произойти, даже если остановка связана с невозможностью улучшения решения, поскольку оптимальное решение может находиться далеко от окрестностей решений, пересекаемых алгоритмами.

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

Смотрите также

Локальный поиск - это подполе:

Поля местного поиска включают:

Поисковые пространства с действительными значениями

Существует несколько методов для выполнения локального поиска вещественных пространств поиска:

использованная литература

Библиография