Управляемый локальный поиск

Управляемый локальный поиск

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

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

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

Алгоритм был разработан для задач дискретной оптимизации, где решение состоит из независимо оцениваемых «функций», таких как комбинаторная оптимизация, хотя он применялся для оптимизации непрерывной функции, моделируемой как двоичные строки.

Параметр λ представляет собой масштабный коэффициент для штрафа за функцию, который должен быть в той же пропорции, что и затраты на решение-кандидат конкретного экземпляра проблемы, к которому применяется алгоритм. Таким образом, значение λ должно быть значимым при использовании в расширенной функции стоимости (например, при добавлении к стоимости возможного решения в минимизация и вычитается из стоимости в случае задачи максимизации).

управляемый локальный поиск

 

Делиться
ru_RURU