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

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

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

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

Обзор

Особенности решения

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

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

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

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

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

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

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

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

Поиск с использованием функции расширенной стоимости

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

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

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

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

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

Альшедди (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, том 24, 2000 г., стр. 205-223
• Миллс, П. и Цанг, Э. П. К. и Форд, Дж., Применение расширенного управляемого локального поиска к квадратичной задаче о назначениях, Annals of Operations Research, Kluwer Academic Publishers, том 118, 2003 г., стр. 121–135
• Минтон, С., Джонстон, М., Филипс, А. Б. и Лэрд, П., Минимизация конфликтов: эвристический метод исправления для удовлетворения ограничений и проблем планирования, Искусственный интеллект (Специальный том по рассуждениям на основе ограничений), том 58, №№ 1-3 1992, 161-205
• Цанг, Э. П. К. и Вудурис, К., Быстрый локальный поиск и управляемый локальный поиск и их применение к проблеме планирования рабочей силы British Telecom, Operations Research Letters, Elsevier Science Publishers, Амстердам, том 20, № 3, март 1997 г., стр. 119–127
• Voudouris, C., Tsang, EPK, Частичные проблемы удовлетворения ограничений и управляемый локальный поиск, Труды Второй международной конференции по практическому применению технологии ограничений (PACT'96), стр. 337-356, Лондон, Великобритания, 1996
• Voudouris, C, Управляемый локальный поиск для задач комбинаторной оптимизации, докторская диссертация, кафедра компьютерных наук, Эссекский университет, Колчестер, Великобритания, июль 1997 г.
• Voudouris, C., Управляемый локальный поиск — наглядный пример оптимизации функций, BT Technology Journal, том 16, № 3, июль 1998 г., стр. 46-50
• Voudouris, C., Tsang, E., Решение проблем распределения частот радиолиний с использованием управляемого локального поиска, в трудах симпозиума НАТО по распределению, совместному использованию и сохранению частот в системах (AEROSPACE), AGARD, доклад № 14, Ольборг, Дания, 5-7 октября 1998 г.
• Voudouris, C. & Tsang, EPK, Управляемый локальный поиск и его применение к задаче коммивояжера, Европейский журнал операционных исследований, Anbar Publishing, том 113, выпуск 2, март 1999 г., стр. 469-499
• Voudouris, C. & Tsang, EPK, Управляемый локальный поиск присоединяется к элите дискретной оптимизации, Серия DIMACS в Дискретной математике и теоретической информатике, том 57, 2001 г., стр. 29-39
• Voudouris, C. & Tsang, EPK, Управляемый локальный поиск, в F. Glover (ред.), Справочник по метаэвристике, Kluwer, 2003, 185-218
• Voudouris, C., Tsang, EPK и Alsheddy, A., Управляемый локальный поиск, Глава 11, в M. Gendreau & JY Potvin (ред.), Справочник по метаэвристике, Springer, 2010, 321-361
• Voudouris, C., Tsang, E., Alsheddy, A., Управляемый локальный поиск, Wiley Encyclopedia of Operations Research and Management Science, Wiley, 2010
• Voudouris, C., Tsang, E., Alsheddy, A., Эффективное применение управляемого локального поиска, Wiley Encyclopedia of Operations Research and Management Science, Wiley, 2010

Ссылки

1. Voudouris, C, Управляемый локальный поиск для задач комбинаторной оптимизации, докторская диссертация, кафедра компьютерных наук, Университет Эссекса, Колчестер, Великобритания, июль 1997 г.

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

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