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

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

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

• 1 Обзор
  • 1.1 Возможности решения
  • 1.2 Выборочные модификации штрафов
  • 1.3 Поиск с помощью функции расширенной стоимости
  • 1.4 Расширения управляемого локального поиска
• 2 Связанные работы
• 3 Библиография
• 4 Внешние ссылки

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

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

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

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

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

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

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

$util\; \; (x,\; i)\; =\; I\; i\; (x)\; c\; i\; (x)\; 1\; +\; p\; i.\; \{\backslash \; displaystyle\; \backslash \; operatorname\; \{util\}\; (x,\; i)\; =\; I\_\; \{i\}\; (x)\; \{\backslash \; frac\; \{c\_\; \{i\}\; (x)\}\; \{1\; +\; p\_\; \{i\}\}\}.\}$

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

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

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

$г\; (Икс)\; знак\; равно\; е\; (Икс)\; +\; \lambda \; a\; \sum \; 1\; \le \; я\; \le \; м\; I\; я\; (Икс)\; пи\; \{\backslash \; Displaystyle\; г\; (х)\; =\; е\; (х)\; +\; \backslash \; лямбда\; а\; \backslash \; сумма\; \_\; \{1\; \backslash \; Leq\; i\; \backslash \; leq\; m\}\; I\_\; \{i\}\; (x)\; p\_\; \{i\}\}$

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

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

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

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

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

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

Tabu search - это класс методов поиска, которые могут быть созданы для определенных методов. 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]
• Lau, TL Цанг, EPK, Решение проблемы конфигурации процессора с помощью генетического алгоритма на основе мутаций, Международный журнал по инструментам искусственного интеллекта (IJAIT), World Scientific, Том 6, № 4, декабрь 1997 г., 567- 585
• Лау, TL И Цанг, E.P.K., Управляемый генетический алгоритм и его применение к задачам присвоения частот радиоканала, Ограничения, Том 6, № 4, 2001, 373-398 [3]
• Лау, Т.Л. Цанг, EPK, Управляемый генетический алгоритм и его применение к общим задачам назначения, 10-я Международная конференция IEEE по инструментам с искусственным интеллектом (ICTAI'98), Тайвань, ноябрь 1998 г.
• Mills, П. и Цанг, EPK, Управляемый локальный поиск для решения задач SAT и взвешенных задач MAX-SAT, Journal of Automated Reasoning, Special Issue on Satisfiability Problems, Kluwer, Vol.24, 2000, 205-223 [4]
• Миллс П. и Цанг ЕПК И Форд, Дж., Применение расширенного управляемого локального поиска к задаче квадратичного назначения, Annals of Operations Research, Kluwer Academic Publishers, Vol.118, 2003, 121-135 [5]
• Минтон, С., Джонстон, М., Филипс, AB И Лэрд П., Минимизация конфликтов: эвристический метод исправления для удовлетворения ограничений и задач планирования, Искусственный интеллект (специальный том по рассуждению на основе ограничений), Том 58, №№ 1-3 1992, 161-205
• Цанг, ЕПК И Вудурис, К., Быстрый локальный поиск и управляемый локальный поиск и их применение к проблеме планирования рабочей силы British Telecom, Письма об исследованиях операций, издательство Elsevier Science Publishers, Амстердам, Том 20, № 3, март 1997 г., 119–127 [6]
• Вудурис, К. Управляемый локальный поиск для задач комбинаторной оптимизации, докторская диссертация, факультет компьютерных наук, Университет Эссекса, Колчестер, Великобритания, июль 1997 г. [7]
• Вудурис, К., Guided Local Search - наглядный пример оптимизации функций, BT Technology Journal, Том 16, № 3, июль 1998 г., 46-50 [8]
• Вудурис, К. и Цанг, EPK, Guided Local Поиск и его применение к проблеме коммивояжера, European Journal of Operational Research, Anbar Publishing, Vol.113, Issue 2, March 1999, 469-499 [9]
• Voudouris, C. Tsang, EPK, Управляемый локальный поиск присоединяется к элите дискретной оптимизации, серия DIMACS по дискретной математике и теоретической информатике, том 57, 2001, 29-39 [10]
• Воуду ris, C. Tsang, E.P.K., Управляемый локальный поиск, в F. Glover (ed.), Handbook of metaheuristics, Kluwer, 2003, 185-218 [11]
• Voudouris, C., Tsang, E.P.K. И Алшедди, А., Управляемый локальный поиск, Глава 11, в М. Гендро и Дж. Я. Потвин (ред.), Справочник по метаэвристике, Springer, 2010, 321-361

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