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

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

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

Примеры

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

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

Описание

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

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

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

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

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

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

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

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

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

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

Рекомендации

  1. ^ "12LocalSearch.key" (PDF).

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