Повторный локальный поиск
Повторный локальный поиск [1] [2] ( ILS ) — термин в прикладной математике и информатике. определение модификации методов локального поиска или восхождения на холм для решения задач дискретной оптимизации.
Методы локального поиска могут застрять в локальном минимуме , где нет улучшающихся соседей.
Простая модификация состоит из повторных вызовов процедуры локального поиска, каждый раз начиная с другой начальной конфигурации. Это называется повторным локальным поиском и подразумевает, что знания, полученные на предыдущих этапах локального поиска, не используются. Обучение подразумевает, что предыдущая история, например, память о ранее найденных локальных минимумах, извлекается для создания все более и более лучших отправных точек для локального поиска.
Неявным предположением является кластерное распределение локальных минимумов : при минимизации функции определить хорошие локальные минимумы легче, начиная с локального минимума с низким значением, чем начиная со случайной точки. Единственное предостережение — избегать удержания в заданном бассейне притяжения, чтобы толчок для преобразования локального минимизатора в отправную точку следующего запуска должен быть достаточно сильным, но не слишком сильным, чтобы избежать возврата к случайным перезапускам без памяти.
Итерированный локальный поиск основан на построении последовательности локально оптимальных решений путем:
- возмущение текущего локального минимума;
- применение локального поиска после запуска с измененного решения.
Сила возмущения должна быть достаточной, чтобы привести траекторию к другому бассейну притяжения, ведущему к другому локальному оптимуму .
Алгоритм возмущения
[ редактировать ]Найти алгоритм возмущений для ILS — непростая задача. Основная цель состоит в том, чтобы не застрять на одном и том же локальном минимуме, и для обеспечения этого свойства операция отмены запрещена. Несмотря на это, хорошая перестановка должна учитывать множество значений, поскольку существует два типа плохих перестановок:
- слишком слабый: вернуться к тому же локальному минимуму
- слишком сильно: случайный перезапуск
Эталонное возмущение
[ редактировать ]Процедура заключается в фиксации ряда значений возмущения таким образом, чтобы эти значения были значимыми для данного экземпляра: в среднем вероятностном и нередком. После этого во время выполнения можно будет проверить график теста, чтобы получить среднее представление о пройденных экземплярах.
Адаптивное возмущение
[ редактировать ]не существует функции, Поскольку априори которая бы определяла, какое из значений является наиболее подходящим для данного возмущения, лучший критерий — сделать его адаптивным. Например, Баттити и Протаси предложили [3] алгоритм реактивного поиска для MAX-SAT , который идеально вписывается в структуру ILS. Они выполняют «направленную» схему возмущений, которая реализуется алгоритмом поиска с запретами , и после каждого возмущения они применяют стандартный алгоритм локального спуска. Другой способ адаптации возмущения — детерминированное изменение его силы во время поиска.
Оптимизация возмущения
[ редактировать ]Другая процедура заключается в оптимизации части проблемы, сохраняя при этом свойство запрета отмены активным. Если эта процедура возможна, все решения, полученные после возмущений, будут иметь тенденцию быть очень хорошими. Кроме того, новые детали также оптимизированы.
Приложения
[ редактировать ]Этот метод был применен к нескольким задачам комбинаторной оптимизации, включая задачи планирования цеха , [4] [5] Проблемы поточного цеха, [6] Проблемы с маршрутом транспортного средства [7] как и многие другие.
Ссылки
[ редактировать ]- ^ Лоренсо, HR; Мартин О.; Штютцле Т. (2010). «Итерированный локальный поиск: структура и приложения». Справочник по метаэвристике . 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 .
{{cite book}}:|journal=игнорируется ( помогите ) - ^ Лоренсо, HR; Мартин О.; Штютцле Т. (2003). «Итерационный локальный поиск» . Справочник по метаэвристике . Kluwer Academic Publishers, Международная серия по исследованию операций и науке управления. 57 : 321–353.
- ^ Баттити, Роберто; Протаси, Марко (1 января 1997 г.). «Реактивный поиск, эвристика с учетом истории для MAX-SAT» . Журнал экспериментальной алгоритмики ACM . 2 : 2–с. дои : 10.1145/264216.264220 . ISSN 1084-6654 .
- ^ Лоренсо, HR; Звиненбург М. (1996). «Сочетание крупношаговой оптимизации с табу-поиском: применение к задаче планирования цеха». Мета-эвристика . Академическое издательство Клювер. Спрингер. стр. 219–236. дои : 10.1007/978-1-4613-1361-8_14 . ISBN 9780792397007 .
{{cite book}}:|journal=игнорируется ( помогите ) - ^ Лоренсо, HR (1995). «Планирование работы цеха: вычислительное исследование методов локального поиска и крупношаговой оптимизации». Европейский журнал операционных исследований . 83 (2): 347–364. дои : 10.1016/0377-2217(95)00012-F .
- ^ Хуан, А.А.; Лоренсо, Х.; Матео, М.; Луо, Р.; Кастелла, К. (2013). «Использование итерированного локального поиска для решения задачи Flow-Shop: проблемы параметризации, рандомизации и распараллеливания» . Международные сделки в области операционных исследований .
- ^ Пенна, Пука Х.В.; Сатори Очи, Л.; Субраманиан, А. (2013). «Эвристика повторного локального поиска для решения проблемы маршрутизации неоднородного парка транспортных средств». Журнал эвристики . 19 (2): 201–232. дои : 10.1007/s10732-011-9186-y .