Повторный локальный поиск - Iterated local search
Итерированный локальный поиск ( ILS ) - это термин в прикладной математике и информатике, определяющий модификацию локального поиска или методов восхождения на холм для решения дискретных задач оптимизации.
Методы локального поиска могут застрять в локальном минимуме , где нет доступных улучшающих соседей.
Простая модификация состоит из повторных вызовов процедуры локального поиска, каждый раз начиная с другой начальной конфигурации. Это называется повторным локальным поиском и подразумевает, что знания, полученные на предыдущих этапах локального поиска, не используются. Обучение подразумевает, что предыдущая история, например, память о ранее найденных локальных минимумах, добывается, чтобы создавать все более и более лучшие отправные точки для локального поиска.
Неявное предположение состоит в кластеризованном распределении локальных минимумов : при минимизации функции определение хороших локальных минимумов легче при запуске с локального минимума с низким значением, чем при запуске из случайной точки. Единственное предостережение - избегать заключения в заданный бассейн притяжения, так что толчок для преобразования локального минимизатора в начальную точку для следующего запуска должен быть достаточно сильным, но не слишком сильным, чтобы избежать возврата к случайным перезапускам без памяти.
Итерированный локальный поиск основан на построении последовательности локально оптимальных решений путем:
- возмущение текущего локального минимума;
- применение локального поиска после запуска из модифицированного решения.
Сила возмущения должна быть достаточной, чтобы привести траекторию к другому бассейну притяжения, ведущему к другому локальному оптимуму .
Алгоритм возмущения
Алгоритм возмущения для ILS - непростая задача. Основная цель - не застревать в одном и том же локальном минимуме, и для того, чтобы это свойство было истинным, операция отмены запрещена. Несмотря на это, хорошая перестановка должна учитывать множество значений, поскольку существует два вида плохих перестановок:
- слишком слабый: вернуться к тому же локальному минимуму
- слишком сильный: случайный перезапуск
Тестовое возмущение
Процедура состоит в том, чтобы зафиксировать ряд значений возмущения так, чтобы эти значения были значимыми для конкретного экземпляра: со средней вероятностью, а не с редкостью. После этого во время выполнения можно будет проверить график теста, чтобы получить среднее представление о переданных экземплярах.
Адаптивное возмущение
Поскольку не существует априорной функции, которая бы сообщала , какое значение является наиболее подходящим для нашего возмущения, лучший критерий - сделать его адаптивным. Например, Баттити и Протаси предложили алгоритм реактивного поиска для MAX-SAT, который идеально подходит для ILS. фреймворк. Они выполняют схему «направленного» возмущения, которая реализуется алгоритмом запретного поиска, и после каждого возмущения они применяют стандартный алгоритм локального спуска. Другой способ адаптации возмущения - детерминированное изменение его силы во время поиска.
Оптимизация возмущения
Другая процедура - оптимизировать подчасть проблемы, сохраняя активным свойство не отменять. Если эта процедура возможна, все решения, полученные после возмущений, будут очень хорошими. Кроме того , оптимизированы и новые детали.
Выводы
Этот метод был применен к нескольким задачам комбинаторной оптимизации, включая задачи планирования работы цеха, проблемы потока-цеха, проблемы маршрутизации транспортных средств, а также многие другие.
Рекомендации