Переменный поиск окрестностей - Variable neighborhood search

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

Вступление

VNS систематически меняет окрестности в две фазы: сначала спуск, чтобы найти локальный оптимум, и, наконец, фазу возмущения, чтобы выбраться из соответствующей долины.

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

Есть несколько книг, важных для понимания VNS, таких как: Справочник по метаэвристике , 2010 г., Справочник по метаэвристике, 2003 г. и Методологии поиска, 2005 г. Более ранние работы, которые мотивировали этот подход, можно найти в

1. Давидон, WC
2. Флетчер, Р., Пауэлл, Мэриленд
3. Младенович, Н. и
4. Бримберг, Дж., Младенович, Н.

Последние обзоры методологии VNS, а также многочисленные приложения можно найти в 4OR, 2008 и Annals of OR, 2010.

Определение проблемы

Определите одну детерминированную задачу оптимизации с помощью

${\ Displaystyle \ мин {\ {е (х) | х \ в X, X \ substeq S \}}}$, (1)

где S , X , x и f - пространство решений, допустимое множество, допустимое решение и действительная целевая функция соответственно. Если S - конечное, но большое множество, задается задача комбинаторной оптимизации. Если есть модель непрерывной оптимизации. ${\ displaystyle {S = R ^ {n}}}$

Решение оптимально, если ${\ displaystyle {x ^ {*} \ in X}}$

${\ Displaystyle {е (х ^ {*}) \ Leq е (х), \ qquad \ forall {x} \, \ in X}}$.

Точный алгоритм для задачи (1) должен найти оптимальное решение x * , с проверкой его оптимальной структуры, или, если оно нереализуемо, в процедуре должно быть показано, что не существует достижимого решения, т. Е. , Или решение неограничен. Процессорное время должно быть ограниченным и коротким. Для непрерывной оптимизации разумно допустить некоторую степень допуска, т. Е. Остановиться, когда будет найдено возможное решение , такое, что ${\ displaystyle X = \ varnothing}$${\ displaystyle x ^ {*}}$

${\ Displaystyle {е (х ^ {*}) \ Leq е (х) + \ epsilon, \ qquad \ forall {x} \, \ in X}}$ или же ${\ Displaystyle {(е (х ^ {*}) - е (х)) / е (х ^ {*}) <\ epsilon, \ qquad \ forall {x} \, \ in X}}$

Некоторые эвристики быстро принимают приближенное решение или оптимальное решение, но без подтверждения его оптимальности. Некоторые из них имеют неверный сертификат, т. Е. Полученное решение удовлетворяет ${\ displaystyle x_ {h}}$

${\ displaystyle {(е (x_ {h}) - f (x)) / f (x_ {h}) \ leq \ epsilon, \ qquad \ forall {x} \, \ in X}}$ для некоторых , хотя это редко бывает маленьким. ${\ displaystyle \ epsilon}$

Эвристика сталкивается с проблемой локальных оптимумов, поскольку позволяет избежать безграничного времени вычислений. Локальный оптимум проблемы таков, что ${\ displaystyle x_ {L}}$

${\ Displaystyle {е (x_ {L}) \ leq f (x), \ qquad \ forall {x} \, \ in N (x_ {L}) \ cap X}}$

где обозначает окрестность${\ Displaystyle N (x_ {L})}$${\ displaystyle x_ {L}}$

Описание

Согласно (Mladenović, 1995), VNS - это метаэвристика, которая систематически выполняет процедуру изменения соседства, как при спуске к локальным минимумам, так и при бегстве из долин, которые их содержат.

VNS строится на следующих представлениях:

1. Локальный минимум по отношению к одной структуре соседства не обязательно является локальным минимумом для другой структуры соседства.
2. Глобальный минимум - это локальный минимум по отношению ко всем возможным структурам соседства.
3. Для многих задач локальные минимумы по отношению к одной или нескольким окрестностям относительно близки друг к другу.

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

Среди недавно упомянутых работ есть несколько работ, в которых его можно было бы изучить, например (Hansen and Mladenović 1999, 2001a, 2003, 2005; Moreno-Pérez et al .;)

Локальный поиск

Эвристика локального поиска выполняется путем выбора начального решения x, обнаружения направления спуска от x в окрестности N (x) и перехода к минимуму f (x) в пределах N (x) в том же направлении. Если нет направления спуска, эвристика останавливается; в противном случае он повторяется. Обычно используется самое высокое направление спуска, которое также считается лучшим улучшением. Этот набор правил обобщен в алгоритме 1, где мы предполагаем, что задано начальное решение x . Выход состоит из локального минимума, обозначенного x ' , и его значения. Заметим , что структура окрестности N (х) определена для всех х ∈ Х . На каждом шаге, окрестность N (х) из й исследуются полностью. Поскольку это может занять много времени, альтернативой является использование эвристики первого спуска. Затем векторы систематически нумеруются, и движение совершается, как только обнаруживается направление спуска. Это обобщено в алгоритме 2. ${\ Displaystyle х ^ {я} \ в N (х)}$

Алгоритм 1: эвристика наилучшего улучшения (наивысший спуск)

Function BestImprovement(x)
  1: repeat
  2:     x' ← x
  3:     x ← argmin_{ f(y) }, y ∈ N(x)
  4: until ( f(x) ≥ f(x') )
  5: return x'

Алгоритм 2: эвристика первого улучшения (первого спуска)

Function FirstImprovement(x)
  1: repeat
  2:    x' ← x; i ← 0
  3:    repeat
  4:       i ← i + 1
  5:       x ← argmin{ f(x), f(x^i)}, x^i ∈ N(x)
  6:    until ( f(x) < f(x^i) or i = |N(x)| )
  7: until ( f(x) ≥ f(x') )
  8: return x'

Обозначим один конечный набор предварительно выбранных структур соседства с множеством решений в k-й окрестности точки x . ${\ displaystyle {\ mathcal {N}} _ {k} (k = 1, ..., k_ {max})}$${\ Displaystyle {\ mathcal {N}} _ {к} (х)}$

Обозначения также будут использоваться при описании местного происхождения. Окрестности или могут быть вызваны из одного или нескольких метрических (или квази-метрика) функций , введенных в раствор пространства S . Оптимальное решение (или глобальный минимум ) - это возможное решение, при котором достигается минимум проблемы. Назовем x '∈ X локальным минимумом проблемы относительно , если не существует такого решения , что . ${\ displaystyle {\ mathcal {N '}} _ {k} (x), k = 1, ..., k' _ {max}}$${\ Displaystyle {\ mathcal {N}} _ {к} (х)}$${\ Displaystyle {\ mathcal {N '}} _ {к} (х)}$${\ displaystyle x_ {opt}}$${\ Displaystyle {\ mathcal {N}} _ {к} (х)}$${\ displaystyle x \ in {\ mathcal {N '}} _ {k} (x) \ substeq X}$${\ Displaystyle е (х) <е (х ')}$

Чтобы решить проблему с использованием нескольких окрестностей, факты 1–3 могут использоваться тремя различными способами: (i) детерминированными; (ii) стохастический ; (iii) как детерминированный, так и стохастический. Сначала мы дадим в алгоритме 3 шаги функции изменения окрестности, которые будут использоваться позже. Функция NeighborhoodChange () сравнивает новое значение f (x ') с действующим значением f (x), полученным в окрестности k (строка 1). Если достигается улучшение, k возвращается к исходному значению и обновляется новый действующий оператор (строка 2). В противном случае рассматривается следующая окрестность (строка 3).

Алгоритм 3: - Смена района

Function NeighborhoodChange (x, x', k)
 1: if f (x') < f(x) then
 2:    x ← x'     // Make a move
 3:    k ← 1      // Initial neighborhood
 4: else
 5:    k ← k+1    // Next neighborhood

Когда VNS не предоставляет хорошее решение, есть несколько шагов, которые могут быть полезны в процессе, например, сравнение первых и лучших стратегий улучшения в локальном поиске, уменьшение соседства, усиление тряски, принятие VND, принятие FSS и экспериментирование с настройками параметров.

Базовый метод VNS (BVNS) ( Справочник по метаэвристике , 2010) объединяет детерминированные и стохастические изменения соседства. Его шаги приведены в алгоритме 4. Часто следующие друг за другом окрестности будут вложенными. Обратите внимание, что точка x ' генерируется случайным образом на шаге 4, чтобы избежать цикличности, которая могла бы произойти, если бы применялось детерминированное правило. На шаге 5 обычно применяется лучший улучшенный локальный поиск (алгоритм 1). Однако его можно заменить первым улучшением (алгоритм 2). ${\ displaystyle {\ mathcal {N}} _ {k}}$

Алгоритм 4: Базовая VNS

Function VNS (x, kmax, tmax)
 1: repeat
 2:    k ← 1
 3:    repeat
 4:       x' ← Shake(x, k)                   // Shaking
 5:       x'' ← BestImprovement(x' )         // Local search
 6:       x ← NeighbourhoodChange(x, x'', k) // Change neighbourhood
 7:    until k = kmax
 8:    t ← CpuTime()
 9: until t > tmax

Варианты VNS

Базовый VNS - лучший метод улучшения с рандомизацией. Без особых дополнительных усилий его можно преобразовать в метод спуска-восхождения: в функции NeighbourhoodChange () замените также x на x " с некоторой вероятностью, даже если решение хуже, чем у действующего оператора. Его также можно превратить в первое Метод улучшения. Другой вариант базовой VNS может заключаться в том, чтобы найти решение x ' на этапе «Встряхивание» как лучшее среди b (параметр a) случайно сгенерированных решений из k- й окрестности. Возможны два варианта этого расширения: (1) выполнить только один локальный поиск из лучших среди b точек; (2) выполнить все b локальных поисков с последующим выбором лучшего.В документе (Fleszar and Hindi) можно найти алгоритм.

Расширения

• VND

Метод спуска по переменной окрестности (VND) получается, если изменение окрестностей выполняется детерминированным способом. В описании его алгоритмов мы предполагаем, что задано начальное решение x . Большинство эвристик локального поиска на стадии спуска используют очень мало окрестностей. Окончательное решение должно быть локальным минимумом по отношению ко всем окрестностям; следовательно, шансы достичь глобального больше при использовании VND, чем при использовании структуры с одним соседством.${\ displaystyle k_ {max}}$

• РВНС

Метод сокращенного VNS (RVNS) получается, если выбраны случайные точки и не выполняется спуск. Скорее, значения этих новых точек сравниваются со значениями действующего оператора, и в случае улучшения происходит обновление. Предполагается, что было выбрано условие остановки, такое как максимальное разрешенное время ЦП или максимальное количество итераций между двумя улучшениями.${\ Displaystyle {\ mathcal {N}} _ {к} (х)}$${\ displaystyle t_ {max}}$

Для упрощения описания алгоритмов он используется ниже. Следовательно, RVNS использует два параметра: и . RVNS полезен в очень крупных случаях, когда локальный поиск обходится дорого. Было замечено, что наилучшее значение для параметра часто равно 2. Кроме того, максимальное количество итераций между двумя улучшениями обычно используется в качестве условия остановки. RVNS сродни методу Монте-Карло , но более систематичен.${\ displaystyle t_ {max}}$${\ displaystyle t_ {max}}$${\ displaystyle k_ {max}}$${\ displaystyle k_ {max}}$

• Перекошенный VNS

Метод перекоса VNS (SVNS) (Hansen et al.) Решает проблему исследования долин, далеких от действующего решения. В самом деле, как только лучшее решение в большом регионе было найдено, необходимо пойти каким-то образом, чтобы получить улучшенное. Решения, выбранные случайным образом в отдаленных районах, могут существенно отличаться от существующих, и VNS может затем выродиться в некоторой степени в эвристику Multistart (в которой спуски выполняются итеративно из решений, сгенерированных случайным образом, эвристика, которая, как известно, не очень эффективна. ). Следовательно, необходимо сделать некоторую компенсацию за удаленность от действующего оператора.

• Поиск разложения переменных окрестностей

Метод поиска с разложением переменных окрестностей (VNDS) (Hansen et al.) Расширяет базовую VNS до двухуровневой схемы VNS, основанной на декомпозиции проблемы. Для простоты изложения, но без ограничения общности предполагается, что решение x представляет собой набор некоторых элементов.

• Параллельный VNS

Недавно было предложено несколько способов распараллеливания VNS для решения проблемы p-медианы. В Гарсиа-Лопес и др. протестированы три из них: (i) распараллелить локальный поиск; (ii) увеличить количество решений, взятых из текущей окрестности, и выполнить локальный поиск параллельно из каждого из них и (iii) сделать то же самое, что и (ii), но обновить информацию о найденном наилучшем решении. Три параллельных стратегии VNS также предлагаются для решения проблемы путешествующего покупателя в Ochi et al.

• Primal-dual VNS

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

Однако, когда размер проблемы велик, даже упрощенную задачу может быть невозможно решить в точности стандартными коммерческими решателями. Таким образом, неплохо было бы также решить двойные расслабленные задачи эвристическим путем. Получены гарантированные оценки производительности первичной эвристики. В Primal-dual VNS (PD-VNS) (Hansen et al.) Предлагается один возможный общий способ достижения как гарантированных границ, так и точного решения.

• Ветвление с переменным окружением

Задача смешанного целочисленного линейного программирования (MILP) состоит из максимизации или минимизации линейной функции с учетом ограничений равенства или неравенства и ограничений целочисленности для некоторых переменных.

• Поиск пространства формулировки переменного окружения

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

Приложения

Применения VNS или разновидностей VNS очень многочисленны и многочисленны. Некоторые области, где можно найти сборники научных трудов:

• Промышленное применение
• Проблемы дизайна в общении
• Проблемы с расположением
• Сбор данных
• Проблемы с графиком
• Проблемы с рюкзаком и упаковкой
• Смешанные целочисленные задачи
• Таблицы времени
• Планирование
• Проблемы с маршрутизацией автомобиля
• Разводка дуги и сбор мусора
• Проблемы с автопарком
• Расширенные проблемы с маршрутизацией транспортных средств
• Проблемы бионаук и химии
• Непрерывная оптимизация
• Другие проблемы оптимизации
• Наука открытия

Заключение

VNS подразумевает несколько функций, которые представлены Хансеном и Младеновичем, а некоторые из них представлены здесь:

1. Простота: VNS прост, понятен и универсален
2. Точность: VNS сформулирована в точных математических определениях.
3. Согласованность: все действия эвристики для решения проблем следуют принципам VNS.
4. Эффективность: VNS предоставляет оптимальные или почти оптимальные решения для всех или, по крайней мере, наиболее реалистичных случаев.
5. Эффективность: VNS требует умеренного времени вычислений для создания оптимальных или почти оптимальных решений.
6. Надежность: функционирование VNS согласовано в различных случаях.
7. Удобство для пользователя: VNS не имеет параметров, поэтому его легко понять, выразить и использовать.
8. Инновация: VNS создает новые типы приложений
9. Универсальность: VNS дает хорошие результаты для широкого круга проблем.
10. Интерактивность: VNS позволяет пользователю использовать свои знания для улучшения процесса разрешения проблем.
11. Множественность: VNS может предлагать определенные решения, близкие к оптимальным, из которых пользователь может выбирать;

Интерес к VNS быстро растет, о чем свидетельствует увеличение количества статей, публикуемых каждый год по этой теме (10 лет назад - всего несколько; 5 лет назад - около десятка; и около 50 в 2007 году). Более того, 18-я мини-конференция EURO, состоявшаяся на Тенерифе в ноябре 2005 года, была полностью посвящена VNS. Это привело к выпуску специальных выпусков IMA Journal of Management Mathematics в 2007 году, European Journal of Operational Research ( http://www.journals.elsevier.com/european-journal-of-operational-research/ ) и Journal of Heuristics ( https : //www.springer.com/mat Mathematics/applications/journal/10732/ ) в 2008 году.

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

Внешние ссылки

• Европейская мини-конференция XXVIII по поиску переменных соседей
• 5-я Международная конференция по поиску переменного соседства
• 8-я Международная конференция по поиску переменного соседства