Переменный поиск соседей

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

Введение

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

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

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

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

Недавние обзоры методологии VNS, а также многочисленных приложений можно найти в 4OR, 2008 г. и Анналы ОР, 2010.

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

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

$\min {\{f(x)|x\in X,X\subseteq S\}}$, (1)

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

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

${f(x^{*})\leq f(x),\qquad \forall {x}\,\in X}$.

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

${f(x^{*})\leq f(x)+\epsilon ,\qquad \forall {x}\,\in X}$ или ${(f(x^{*})-f(x))/f(x^{*})<\epsilon ,\qquad \forall {x}\,\in X}$

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

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

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

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

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

Описание

Согласно (Младенович, 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(x) определена для всех x ∈ X. На каждом шаге окрестность N(x) точки x исследуется полностью. Поскольку это может занять много времени, альтернативой является использование эвристики первого спуска. Векторы $x^{i}\in N(x)$ затем систематически пересчитываются, и движение производится, как только будет найдено направление спуска. Это суммировано в алгоритме 2.

Алгоритм 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'

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

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

Чтобы решить проблему с использованием нескольких окрестностей, факты 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 и экспериментирование с настройками параметров.

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

Алгоритм 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 — это лучший метод спуска улучшений с рандомизацией. Без особых дополнительных усилий его можно преобразовать в метод спуска-восхождения: в функции NeighbourhoodChange() замените также x на x" с некоторой вероятностью, даже если решение хуже действующего. Его также можно превратить в первое метод улучшения. Другим вариантом базовой VNS может быть поиск решения x' на шаге «Встряхивание» как лучшего среди b (параметр) случайно сгенерированных решений из k -й окрестности. Возможны два варианта такого расширения: (1) выполнять только один локальный поиск из лучшей среди b точек; (2) выполнить все b локальных поисков и затем выбрать лучший. В статье (Флессар и хинди ) можно найти алгоритм.

Расширения

• донг

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

• РВНС

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

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

• Искаженный VNS

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

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

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

• Параллельная VNS

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

• Первично-двойной ВНС

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

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

• Ветвление переменного окружения

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

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

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

Приложения

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

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

Заключение

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

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

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

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

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