Управляемый локальный поиск - это метаэвристический метод поиска. Метаэвристический метод - это метод, расположенный поверх алгоритма локального поиска, чтобы изменить его поведение.
Управляемый локальный поиск накапливает штрафы во время поиска. Он использует штрафы, чтобы помочь алгоритмам локального поиска выйти из локального минимума и плато. Когда данный алгоритм локального поиска достигает локального оптимума, GLS изменяет целевую функцию, используя определенную схему (поясняется ниже). Затем локальный поиск будет работать с использованием расширенной целевой функции, которая предназначена для вывода результатов поиска за пределы локального оптимума. Ключ в том, как изменяется целевая функция.
Обзор
Особенности решения
Чтобы применить GLS, необходимо определить особенности решения для данной проблемы. Функции решения определены для различения решений с разными характеристиками, чтобы можно было распознать области сходства вокруг локальных оптимумов и избежать их. Выбор характеристик решения зависит от типа проблемы, а также в определенной степени от алгоритма локального поиска. Для каждой функции функция стоимости определено.
Каждая функция также связана со штрафом. (изначально установлен на 0), чтобы записать количество вхождений объекта в локальные минимумы.
Характеристики и затраты часто исходят непосредственно из целевой функции. Например, в задаче коммивояжера «идет ли тур напрямую из города X в город Y» можно определить как функцию. Расстояние между X и Y можно определить как стоимость. В задачах SAT и взвешенных MAX-SAT признаками могут быть «удовлетворяет ли пункт C текущими назначениями».
На уровне реализации мы определяем для каждой функции Индикаторная функция указывает, присутствует ли функция в текущем решении или нет. равно 1, когда решение выставляет собственность , 0 в противном случае.
Выборочные модификации штрафа
GLS вычисляет полезность штрафов за каждую функцию. Когда алгоритм локального поиска возвращает локальный минимум x, GLS штрафует все те функции (за счет увеличения штрафа функций), присутствующие в этом решении, которые имеют максимальную полезность,, как определено ниже.
Идея состоит в том, чтобы наказывать функции, которые имеют высокую стоимость, хотя полезность этого уменьшается, поскольку функция наказывается все чаще и чаще.
Поиск с помощью функции расширенной стоимости
GLS использует расширенную функцию стоимости (определенную ниже), чтобы позволить ему вывести алгоритм локального поиска за пределы локального минимума путем наложения штрафов на функции, присутствующие в этом локальном минимуме. Идея состоит в том, чтобы сделать локальный минимум более дорогостоящим, чем окружающее пространство поиска, где эти функции отсутствуют.
Параметр λ можно использовать для изменения интенсивности поиска решений. Более высокое значение λ приведет к более разнообразному поиску, при котором поиск плато и бассейнов будет более грубым; низкое значение приведет к более интенсивному поиску решения, при котором плато и бассейны в поисковом ландшафте просматриваются более детально. Коэффициентиспользуется для уравновешивания штрафной части целевой функции относительно изменений целевой функции и зависит от конкретной задачи. Простая эвристика для настройки просто записать среднее изменение целевой функции до первого локального минимума, а затем установить к этому значению, разделенному на количество функций GLS в экземпляре проблемы.
Расширения управляемого местного поиска
Миллс (2002) описал расширенный управляемый локальный поиск (EGLS), который использует случайные ходы и критерий стремления, разработанный специально для схем, основанных на штрафах. Полученный алгоритм улучшил устойчивость GLS по ряду настроек параметров, особенно в случае квадратичной задачи присваивания . Общая версия алгоритма GLS, использующая восхождение на холм, основанное на минимальных конфликтах (Минтон и др., 1992) и частично основанная на GENET для удовлетворения ограничений и оптимизации, также была реализована в проекте Computer Aided Constraint Programming .
Alsheddy (2011) расширил управляемый локальный поиск до многоцелевой оптимизации и продемонстрировал его использование для расширения возможностей персонала при составлении расписания [ необходима цитата ] .
Связанных с работой
GLS был построен на GENET, который был разработан Чанг Ван, Эдвард Цанг и Эндрю Дэвенпорт.
Метод прорыва очень похож на GENET. Он был разработан для удовлетворения ограничений .
Табу-поиск - это класс методов поиска, которые могут быть привязаны к определенным методам. GLS можно рассматривать как частный случай поиска Табу .
Поставив GLS на вершину генетического алгоритма , Тунг-ленг Лау представил алгоритм управляемого генетического программирования (GGA). Он был успешно применен к общей проблеме назначения (в планировании), проблеме конфигурации процессоров (в электронном дизайне) и к набору задач назначения частот радиосвязи (абстрактное военное приложение).
Choi et al. используйте GENET как поиск по Лагранжу.
Библиография
- Алшедди А. Планирование расширения прав и возможностей: многоцелевой подход к оптимизации с использованием управляемого локального поиска, докторская диссертация, Школа компьютерных наук и электронной инженерии, Университет Эссекса, 2011 [1]
- Чой, KMF, Ли, JHM и Стаки, П.Дж., Лагранжева реконструкция GENET, Искусственный интеллект, 2000, 123 (1-2), 1-39
- Давенпорт А., Цанг ЕПК, Кангмин Чжу и Си Джей Ван, GENET: Коннекционистская архитектура для решения проблем удовлетворения ограничений путем итеративного улучшения, Proc., AAAI, 1994, p.325-330 [2]
- Лау, Т.Л. и Цанг, EPK, Решение проблемы конфигурации процессора с помощью генетического алгоритма на основе мутаций , Международный журнал по инструментам искусственного интеллекта (IJAIT), World Scientific, Том 6, №4, декабрь 1997 г., 567-585
- Лау, Т.Л. и Цанг, EPK, Управляемый генетический алгоритм и его применение к проблемам присвоения частот радиолинии, Ограничения, Том 6, № 4, 2001, 373-398 [3]
- Лау, Т.Л. и Цанг, EPK, Управляемый генетический алгоритм и его применение к общим задачам присваивания , IEEE 10-я Международная конференция по инструментам с искусственным интеллектом (ICTAI'98), Тайвань, ноябрь 1998 г.
- Миллс, П. и Цанг, EPK, Управляемый локальный поиск для решения задач SAT и взвешенных задач MAX-SAT, Журнал автоматизированного мышления, специальный выпуск по проблемам выполнимости, Kluwer, Vol.24, 2000, 205-223 [4]
- Миллс, П. и Цанг, ЕПК и Форд, Дж., Применение расширенного управляемого локального поиска к квадратичной задаче назначения, Annals of Operations Research, Kluwer Academic Publishers, Vol.118, 2003, 121-135 [5]
- Минтон, С., Джонстон, М., Филипс, А.Б. и Лэрд, П., Минимизация конфликтов: эвристический метод исправления для удовлетворения ограничений и задач планирования, Искусственный интеллект (специальный том по рассуждению на основе ограничений), том 58, №№. 1-3 1992, 161-205
- Цанг, EPK & Voudouris, C., Быстрый локальный поиск и управляемый локальный поиск и их применение к проблеме планирования рабочей силы British Telecom, Письма об исследованиях операций, издательство Elsevier Science Publishers, Амстердам, том 20, № 3, март 1997 г., стр. 119–127 [6]
- Воудурис, К. Управляемый локальный поиск для задач комбинаторной оптимизации, докторская диссертация, факультет компьютерных наук, Эссекский университет, Колчестер, Великобритания, июль 1997 г. [7]
- Вудурис, К., Управляемый локальный поиск - наглядный пример оптимизации функций, BT Technology Journal, Том 16, № 3, июль 1998 г., стр. 46–50 [8]
- Вудурис, К. и Цанг, EPK, Управляемый местный поиск и его применение к проблеме коммивояжера, Европейский журнал оперативных исследований, Anbar Publishing, Vol.113, Issue 2, March 1999, 469-499 [9]
- Вудурис, К. и Цанг, EPK, Управляемый локальный поиск присоединяется к элите дискретной оптимизации, Серия DIMACS по дискретной математике и теоретической информатике, том 57, 2001, 29-39 [10]
- Вудурис, К. и Цанг, ЕПК, Управляемый локальный поиск, в Ф. Гловере (ред.), Справочник по метаэвристике, Kluwer, 2003, 185–218 [11]
- Вудурис, К., Цанг, ЕПК и Алшедди, А., Управляемый местный поиск, Глава 11, в М. Жендро и Дж. Я. Потвин (ред.), Справочник по метаэвристике, Springer, 2010, 321-361