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

Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Май 2015 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

Примеры

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

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

Описание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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