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