Русская Википедия:Управляемый локальный поиск

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Управляемый локальный поиск (Шаблон:Lang-en, GLS) — это метаэвристический метод поиска, то есть метод поверх алгоритма локального поиска с целью изменить его поведение.

Управляемый локальный поиск строит штрафы во время поиска и использует их, чтобы помочь локальным алгоритмам поиска уйти из локального минимума и (почти) горизонтальных участков. Когда локальный алгоритм поиска попадает в локальный минимум, GLS модифицирует целевую функцию с помощью специальной схемы (объяснена ниже). Затем локальный поиск работает с этой увеличенной целевой функцией, которая строится так, чтобы вывести из локального оптимума. Ключевым вопросом является способ модификации целевой функции.

Управляемый локальный поиск (Шаблон:Lang-en) был предложен Вудурисом (Voudouris) и Цангом (Tsang)[1].

Обзор

Свойства решения

Для применения GLS свойства решения должны быть определены для заданной задачи. Свойства решения определены для разграничения решений с различными характеристиками, так что области сходства вокруг оптимума могут быть распознаны и исключены. Выбор свойств решения зависит от типа задачи и также от алгоритмов поиска. Для каждого свойства <math>f_i</math> определяется ценовая функция <math>c_i</math>.

Каждое свойство ассоциируется со штрафом <math>p_i</math> (первоначально равным 0), отражающим число попаданий свойства в локальный минимум.

Свойства и цены зачастую приходят прямо вместе с целевой функцией. Например, в задаче коммивояжёра «маршрут из города X идёт непосредственно в город Y» можно рассматривать как свойство. Расстояние между X и Y можно определить как цену. В задачах SAT и взвешенной Шаблон:Не переведено 5 свойствами могут быть «утверждение C удовлетворяет текущим назначениям переменных».

На уровне реализации мы определяем для каждого свойства <math>i</math> характеристическую функцию <math>I_i</math>, указывающую, представлено ли свойство в текущем решении или нет. <math>I_i</math> равно 1, если решение <math>x</math> содержит свойство <math>i</math>, 0 в противном случае.

Выборочные изменения штрафов

GLS вычисляет полезность штрафов для каждого свойства. Когда алгоритм локального поиска возвращает локальный минимум x, GLS штрафует все те свойства (путём увеличения штрафа на свойство), представленные в решении, в которых имеется максимальная полезность <math>\operatorname{util}(x,i)</math>, как определено ниже.

<math>\operatorname{util}(x,i) = I_i(x)\frac{c_i(x)}{1+p_i}.</math>

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

Поиск увеличенной функции цены

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

<math>g(x) = f(x) + \lambda a \sum_{1\leq i\leq m} I_i(x) p_i </math>

Может быть использован параметр <math>\lambda</math>, чтобы изменить интенсивность поиска решений. Более высокие значения <math>\lambda</math> приведёт к более широкому поиску, когда горизонтальные участки и впадины просматриваются более грубо. Низкое значение приведёт к более детальному поиску на горизонтальных участках и впадинах. Коэффициент <math>a</math> используется для того, чтобы сделать штрафную часть целевой функции более сбалансированной относительно изменений целевой функции, и зависит от задачи. Простой эвристический подход для назначения <math>a</math> — просто записывать среднее изменение в целевой функции до первого локального минимума, а потом установить <math>a</math> в это значение, делённое на число свойств GLS в задаче.

Расширения управляемого локального поиска

Миллс (2002) описал расширенный управляемый локальный поиск (EGLS), который использует случайные движения и критерий использования, специально разработанный для основанных на штрафных схемах. Получающийся алгоритм улучшает устойчивость GLS относительно разброса параметров, особенно в случае квадратичной задачи о назначениях. Основная версия алгоритма GLS, использующая восхождение на основе минимального конфликтаШаблон:Sfn и частично основанная на GENET для удовлетворения ограничений и оптимизации, была реализована в проекте Computer Aided Constraint Programming (Компьютеризованное Программирование в Ограничениях).

Алшедди (2011) расширил управляемый локальный поиск для многокритериальной оптимизации и продемонстрировал его использование в планировании.

Связанные работы

GLS была построена на системе GENET, которую разработали Чанг Ван, Эдвард Цанг и Эндрю Дэвенпорт.

Шаблон:Не переведено 5 очень похож на GENET. Он был разработан для удовлетворения ограниченийШаблон:SfnШаблон:Sfn.

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

Используя GLS поверх генетического алгоритма, Тунг-ленг Лау ввёл управляемый генетический алгоритм (Шаблон:Lang-en, GGA). Он был успешно применён для общей задачи назначения (для расписаний), задачи конфигурации процессоров и назначения радиочастот (военного назначения).

Чой, Ли и СтакиШаблон:Sfn представили GENET как лагранжианов поиск.

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Ссылки

Шаблон:Методы оптимизации Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Скобцов и Фёдоров Шаблон:Harv ссылаются на статью Шаблон:Harv, хотя сам Цанг пишет: «Управляемый локальный поиск является результатом исследований с главной целью развить нейронную сеть GENET на задачу удовлетворения ограничений с частичным удовлетворением и комбинаторные оптимизационные задачи. Начав с GENET мы разработали много промежуточных алгоритмов, таких как Tunneling Algorithm и завершили разработкой алгоритма управляемого локального поиска, представленного в этой статье». Речь идёт о статье 1995 года Шаблон:Harv
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Управляемый_локальный_поиск&oldid=11061509