Управляемый местный поиск - Guided Local Search

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

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

Обзор

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

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

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

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

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

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

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 г (х) = е (х) + лямбда а сумма _ {1 leq i leq m} I_ {i} (x) p_ {i}}

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

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

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

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

Связанных с работой

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

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

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

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

Choi et al. использовать GENET как поиск по лагранжеву.

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

Алшедди А., Планирование расширения прав и возможностей: многоцелевой подход к оптимизации с использованием управляемого локального поиска, докторская диссертация, Школа компьютерных наук и электронной инженерии, Университет Эссекса, 2011 г. [1]
Чой, К.М.Ф., Ли, J.H.M. И Стаки П.Дж., Лагранжева реконструкция GENET, Искусственный интеллект, 2000, 123 (1-2), 1-39
Давенпорт А., Цанг Е. П. К., Кангмин Чжу и К. Дж. Ван, GENET: Коннекционистская архитектура для решения проблем удовлетворения ограничений путем итеративного улучшения, Proc., AAAI, 1994, p.325-330 [2]
Лау, Т. И Цанг, E.P.K., Решение проблемы конфигурации процессора с помощью генетического алгоритма на основе мутаций, Международный журнал по инструментам искусственного интеллекта (IJAIT), World Scientific, Том 6, № 4, декабрь 1997 г., 567-585
Лау, Т. И Цанг, E.P.K., Управляемый генетический алгоритм и его применение к проблемам присвоения частот радиолинии, Ограничения, Том 6, № 4, 2001, 373-398 [3]
Лау, Т. И Цанг, E.P.K., Управляемый генетический алгоритм и его применение к общим задачам о назначениях, 10-я Международная конференция IEEE по инструментам с искусственным интеллектом (ICTAI'98), Тайвань, ноябрь 1998 г.
Миллс П. и Цанг E.P.K., Управляемый локальный поиск для решения SAT и взвешенных задач MAX-SAT, Journal of Automated Reasoning, Special Issue on Satisfability Problems, Kluwer, Vol.24, 2000, 205-223 [4]
Миллс, П. и Цанг, E.P.K. И Форд, Дж., Применение расширенного управляемого локального поиска к задаче квадратичного распределения, Annals of Operations Research, Kluwer Academic Publishers, Vol.118, 2003, 121-135 [5]
Минтон, С., Джонстон, М., Филипс, А.Б. И Лэрд П., Минимизация конфликтов: эвристический метод исправления для удовлетворения ограничений и задач планирования, Искусственный интеллект (специальный том по основанным на ограничениях рассуждениям), Том 58, №№ 1-3 1992, 161-205
Цанг, E.P.K. И Вудурис, К., Быстрый локальный поиск и управляемый локальный поиск и их применение к проблеме планирования рабочей силы British Telecom, Письма об исследованиях операций, Издательство Elsevier Science, Амстердам, Том 20, № 3, март 1997 г., стр. 119–127 [6]
Вудурис, К., Управляемый локальный поиск задач комбинаторной оптимизации, докторская диссертация, факультет компьютерных наук, Эссекский университет, Колчестер, Великобритания, июль 1997 г. [7]
Вудурис, К., Управляемый локальный поиск - наглядный пример оптимизации функций, BT Technology Journal, Том 16, № 3, июль 1998 г., стр. 46-50 [8]
Вудурис, К. и Цанг, E.P.K., Управляемый местный поиск и его применение к проблеме коммивояжера, Европейский журнал оперативных исследований, Anbar Publishing, Vol.113, Issue 2, March 1999, 469-499 [9]
Вудурис, К. и Цанг, Е. П. К., Управляемый локальный поиск присоединяется к элите дискретной оптимизации, Серия DIMACS по дискретной математике и теоретической информатике, том 57, 2001, 29-39 [10]
Вудурис, К. и Цанг, E.P.K., Управляемый локальный поиск, в Ф. Гловере (ред.), Справочник по метаэвристике, Kluwer, 2003, 185-218. [11]
Вудурис, К., Цанг, Э.П.К. И Алшедди А., Управляемый местный поиск, Глава 11, в М. Жендро и Дж. И. Потвин (ред.), Справочник по метаэвристике, Springer, 2010, 321-361

внешняя ссылка

Домашняя страница управляемого местного поиска