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


Из Википедии, свободной энциклопедии

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

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

Примеры

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

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

Описание

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

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

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

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

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

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

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

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

Вещественнозначный поиск -пространства

Существует несколько способов выполнения локального поиска вещественнозначную поиска пространств:

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

Список используемой литературы