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

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

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

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

Примеры

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

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

Описание

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

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

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

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

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

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

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

См. также

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

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

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

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

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

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

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

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

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