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

Метод решения задач оптимизации

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

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

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

Примеры

Вот некоторые проблемы, при которых применялся локальный поиск:

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

Описание

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

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

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

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

Шурман и Саути предлагают три показателя эффективности локального поиска (глубина, мобильность и охват): ^[2]

• глубина: стоимость текущего (лучшего) решения;
• мобильность: возможность быстрого перемещения в различные области поискового пространства (при сохранении низких затрат);
• охват: насколько систематично поиск охватывает поисковое пространство, максимальное расстояние между любым неисследованным заданием и всеми посещенными заданиями.

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

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

Локальный поиск является подобластью:

• Метаэвристика
• Стохастическая оптимизация
• Оптимизация

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

• Подъем в гору
• Имитация отжига (подходит как для локального, так и для глобального поиска)
• Поиск табу
• Позднее принятие восхождения на холм
• Реактивная оптимизация поиска (объединение машинного обучения и локальной эвристики поиска)

Реально-значные поисковые пространства

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

• Луус–Яакола выполняет локальный поиск, используя равномерное распределение и экспоненциально убывающий диапазон поиска.
• Случайная оптимизация выполняет локальный поиск с использованием нормального распределения .
• Случайный поиск выполняет локальный поиск путем выборки гиперсферы , окружающей текущую позицию.
• Поиск по шаблону осуществляется по осям пространства поиска с использованием экспоненциально уменьшающихся размеров шагов.

Ссылки

1. "12LocalSearch.key" (PDF) .
2. Д. Шурманс и Ф. Саути. Локальные поисковые характеристики неполных процедур SAT. AI J., 132(2):121–150, 2001.

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

• Баттити, Роберто; Мауро Брунато; Франко Массия (2008). Реактивный поиск и интеллектуальная оптимизация. Спрингер Верлаг . ISBN 978-0-387-09623-0. Архивировано из оригинала 2012-03-16.
• Хус, Х. Х. и Статцл, Т. (2005) Стохастический локальный поиск: основы и приложения, Морган Кауфманн.
• Виджай Арья, Навин Гарг, Рохит Кхандекар, Адам Мейерсон, Камеш Мунагала и Винаяка Пандит (2004): Эвристика локального поиска для задач k-медианы и определения местоположения предприятий, SIAM Journal of Computing 33(3).
• Юрай Громкович : Алгоритмика для сложных проблем: Введение в комбинаторную оптимизацию, рандомизацию, аппроксимацию и эвристику (Springer)
• Уил Михилс, Эмиль Аартс, Ян Корст: Теоретические аспекты локального поиска (Спрингер)