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

Управляемый локальный поиск — это метод метаэвристического поиска. Метаэвристический метод — это метод, который находится поверх алгоритма локального поиска и изменяет его поведение.

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

Метод в его нынешней форме был разработан доктором Кристосом Вудурисом и подробно описан в его докторской диссертации. GLS был вдохновлен и расширен GENET, архитектурой нейронной сети для решения проблем удовлетворения ограничений, которая была разработана Чанг Вангом, Эдвардом Цангом и Эндрю Дэвенпортом. Механизм выхода из локальных минимумов как в GLS, так и в GENET напоминает обучение с подкреплением .

Обзор

Возможности решения

Для применения GLS необходимо определить особенности решения для данной задачи. Характеристики решения определяются для того, чтобы различать решения с разными характеристиками, чтобы можно было распознать области сходства вокруг локальных оптимумов и избежать их. Выбор признаков решения зависит от типа задачи, а также в определенной степени от алгоритма локального поиска. Для каждой функции $f_{i}$ функция стоимости $c_{i}$ определяется.

Каждая функция также связана со штрафом. $p_{i}$ (изначально установлено значение 0) для записи количества вхождений признака в локальные минимумы.

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

На уровне реализации мы определяем для каждой функции $i$ индикаторная функция $I_{i}$ указывая, присутствует ли эта функция в текущем решении или нет. $I_{i}$ равно 1, когда решение $x$ экспонаты собственности $i$, 0 в противном случае.

Выборочные модификации штрафов

GLS вычисляет полезность штрафа за каждую функцию. Когда алгоритм локального поиска возвращает локальный минимум x, GLS штрафует все те функции (путем увеличения штрафа за функции), присутствующие в этом решении, которые имеют максимальную полезность. $\operatorname {util} (x,i)$, как определено ниже.

$\operatorname {util} (x,i)=I_{i}(x){\frac {c_{i}(x)}{1+p_{i}}}.$

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

Поиск через расширенную функцию стоимости

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

$g(x)=f(x)+\lambda a\sum _{1\leq i\leq m}I_{i}(x)p_{i}$

Параметр λ может использоваться для изменения интенсификации поиска решений. Более высокое значение λ приведет к более разнообразному поиску, при котором плато и котловины будут искаться более грубо; низкое значение приведет к более интенсивному поиску решения, при этом плато и впадины в поисковом ландшафте будут просматриваться более детально. Коэффициент $a$ используется для того, чтобы сделать штрафную часть целевой функции сбалансированной относительно изменений целевой функции и зависит от конкретной задачи. Простая эвристика для настройки $a$ состоит в том, чтобы просто записать среднее изменение целевой функции до достижения первого локального минимума, а затем установить $a$ на это значение, разделенное на количество функций GLS в проблемном экземпляре.

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

Миллс (2002) описал расширенный управляемый локальный поиск (EGLS), который использует случайные ходы и критерий стремления, разработанный специально для схем, основанных на штрафах. Полученный алгоритм улучшил надежность GLS в диапазоне настроек параметров, особенно в случае квадратичной задачи назначения . Общая версия алгоритма GLS, использующая алгоритм восхождения на холм на основе минимальных конфликтов (Minton et al. 1992) и частично основанная на GENET для удовлетворения ограничений и оптимизации, также была реализована в проекте «Компьютерное программирование ограничений».

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

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

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

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

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

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

Чой и др. использовать GENET как лагранжев поиск.

Библиография

• Алшедди, А., Планирование расширения возможностей: многокритериальный подход к оптимизации с использованием управляемого локального поиска, докторская диссертация, Школа компьютерных наук и электронной инженерии, Университет Эссекса, 2011 г.
• Чой, К.М.Ф., Ли, Дж.Х.М. и Стаки, П.Дж., Лагранжева реконструкция GENET, Искусственный интеллект, 2000, 123(1-2), 1-39.
• Давенпорт А., Цанг ЭПК, Канмин Чжу и Си Джей Ван, GENET: Коннекционистская архитектура для решения проблем удовлетворения ограничений путем итеративного улучшения, Proc., AAAI, 1994, стр. 325-330
• Лау, Т.Л. и Цанг, Е.П.К., Решение проблемы конфигурации процессора с помощью генетического алгоритма, основанного на мутациях, Международный журнал по инструментам искусственного интеллекта (IJAIT), World Scientific, Том 6, № 4, декабрь 1997 г., 567-585.
• Лау, Т.Л. и Цанг, Е.П.К., Управляемый генетический алгоритм и его применение к задачам назначения частот радиосвязи, Ограничения, Том 6, № 4, 2001, 373-398.
• Лау, Т.Л. и Цанг, Е.П.К., Управляемый генетический алгоритм и его применение к общим задачам назначения, 10-я Международная конференция IEEE по инструментам с искусственным интеллектом (ICTAI'98), Тайвань, ноябрь 1998 г.
• Миллс П. и Цанг ЭПК, Управляемый локальный поиск для решения задач SAT и взвешенных задач MAX-SAT, Журнал автоматизированного рассуждения, Специальный выпуск по проблемам выполнимости, Kluwer, Vol.24, 2000, 205-223
• Миллс П., Цанг ЭПК и Форд Дж. Применение расширенного управляемого локального поиска к квадратичной задаче назначения, Анналы исследования операций, Kluwer Academic Publishers, Vol.118, 2003, 121–135.
• Минтон С., Джонстон М., Филипс А.Б. и Лэрд П., Минимизация конфликтов: эвристический метод устранения ограничений и проблем планирования, Искусственный интеллект (Специальный том по рассуждениям, основанным на ограничениях), Том 58, №№. 1–3 1992, 161–205
• Цанг, Е.П.К. и Вудурис, К., Быстрый локальный поиск и управляемый локальный поиск и их применение к проблеме планирования рабочей силы British Telecom, Письма об исследованиях операций, Elsevier Science Publishers, Амстердам, Том 20, № 3, март 1997 г., 119–127.
• Вудурис, К., Цанг, Е.П.К., Проблемы удовлетворения частичных ограничений и управляемый локальный поиск, Труды Второй международной конференции по практическому применению технологии ограничений (PACT'96), стр. 337-356, Лондон, Великобритания, 1996 г.
• Вудурис, К., Управляемый локальный поиск задач комбинаторной оптимизации, докторская диссертация, факультет компьютерных наук, Университет Эссекса, Колчестер, Великобритания, июль 1997 г.
• Вудурис, К., Управляемый локальный поиск — наглядный пример оптимизации функций, BT Technology Journal, Том 16, № 3, июль 1998 г., 46–50.
• Вудурис, К., Цанг, Э., Решение проблем присвоения частот радиоканала с использованием управляемого локального поиска, В материалах симпозиума НАТО по присвоению, совместному использованию и сохранению частот в системах (AEROSPACE), AGARD, документ № 14, Ольборг, Дания , 5-7 октября 1998 г.
• Вудурис, К. и Цанг, ЕПК, Управляемый локальный поиск и его применение к задаче коммивояжера, Европейский журнал операционных исследований, Anbar Publishing, том 113, выпуск 2, март 1999 г., 469-499.
• Вудурис, К. и Цанг, ЕПК, Управляемый локальный поиск присоединяется к элите в области дискретной оптимизации, Серия DIMACS по дискретной математике и теоретической информатике, том 57, 2001, 29–39.
• Вудурис, К. и Цанг, ЕПК, Управляемый локальный поиск, в Ф. Гловере (ред.), Справочник по метаэвристике, Kluwer, 2003, 185–218.
• Вудурис, К., Цанг, Е.ПК. и Альшедди, А., Управляемый локальный поиск, глава 11, в М. Жандро и Дж. Я. Потвине (ред.), Справочник по метаэвристике, Springer, 2010, 321–361.
• Вудурис, К., Цанг, Э., Альшедди, А., Управляемый локальный поиск, Энциклопедия исследований операций и науки управления Wiley, Wiley, 2010 г.
• Вудурис, К., Цанг, Э., Альшедди, А., Эффективное применение управляемого локального поиска, Энциклопедия исследований операций и науки управления Wiley, Wiley, 2010 г.

Внешние ссылки

• Домашняя страница управляемого локального поиска
• Ресурсы для управляемого локального поиска
• Google OR-Tools – управляемый локальный поиск