WikiDer > Итерированный локальный поиск - Википедия

Iterated local search - Wikipedia
Повторный локальный поиск пинки решение вне локального оптимума

Итерированный локальный поиск[1][2] (ILS) - это член в Прикладная математика и Информатикаопределение модификации местный поиск или же скалолазание методы решения задач дискретной оптимизации.

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

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

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

Итерированный локальный поиск основан на построении последовательности локально оптимальных решений путем:

  1. возмущение текущего локального минимума;
  2. применение локального поиска после запуска из модифицированного решения.

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

Алгоритм возмущения

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

  1. слишком слабый: вернуться к тому же локальному минимуму
  2. слишком сильный: случайный перезапуск

Эталонное возмущение

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

Адаптивное возмущение

Поскольку нет функции априори это говорит о том, какое значение является наиболее подходящим для нашего возмущения, лучший критерий - сделать его адаптивным. Например, Баттити и Протаси предложили алгоритм реактивного поиска для МАКС-СБ который идеально вписывается в ILS.framework. Они выполняют схему «направленного» возмущения, которая реализуется алгоритмом запретного поиска, и после каждого возмущения они применяют стандартный алгоритм локального спуска. Другой способ адаптации возмущения - детерминированное изменение его силы во время поиска.

Оптимизация возмущения

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

Выводы

Метод был применен к нескольким Комбинаторная оптимизация Проблемы, включая Планирование работы цеха Проблемы,[3][4] Проблемы Flow-Shop,[5] Проблемы с маршрутизацией транспортных средств [6] а также многие другие.

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

  1. ^ Lourenço, H.R .; Мартин О .; Штюцле Т. (2010). Итерированный локальный поиск: структура и приложения. Справочник по метаэвристике, 2-е. Версия. Kluwer Academic Publishers, Международная серия исследований операций и управления. 146. С. 363–397. CiteSeerX 10.1.1.187.2089. Дои:10.1007/978-1-4419-1665-5_12. ISBN 978-1-4419-1663-1.
  2. ^ Lourenço, H.R .; Мартин О .; Штюцле Т. (2003). "Повторный локальный поиск". Справочник по метаэвристике. Kluwer Academic Publishers, Международная серия исследований операций и управления. 57: 321–353.
  3. ^ Lourenço, H.R .; Цвейненбург М. (1996). Сочетание оптимизации с большим шагом и tabu-search: приложение к задаче планирования работы магазина. Мета-эвристика: теория и приложения. Kluwer Academic Publishers. Springer. С. 219–236. Дои:10.1007/978-1-4613-1361-8_14. ISBN 9780792397007.
  4. ^ Лоуренсу, Х.Р. (1995). «Планирование работы магазина: вычислительное исследование методов локального поиска и оптимизации с большим шагом». Европейский журнал операционных исследований. 83 (2): 347–364. Дои:10.1016 / 0377-2217 (95) 00012-Ф.
  5. ^ Juan, A.A .; Lourenço, H .; Mateo, M .; Luo, R .; Кастелла, К. (2013). «Использование итерированного локального поиска для решения проблемы Flow-Shop: вопросы параметризации, рандомизации и распараллеливания». Международные операции в операционных исследованиях.
  6. ^ Penna, Puca H.V .; Satori Ochi, L .; Субраманян, А. (2013). «Эвристика повторного локального поиска для задачи маршрутизации гетерогенного парка транспортных средств». Журнал эвристики. 19 (2): 201–232. Дои:10.1007 / s10732-011-9186-у.

[1]

  1. ^ «Роберто Кордоне - Корси - Algoritmi euristici (A.A. 2016/17)».