Гипер-эвристический является эвристическим методом поиска , который стремится автоматизировать, часто путем включения машинного обучения методов, процесс выбора, совмещающие, генерирующие или адаптирующие несколько простых эвристик (или компоненты такой эвристики) для эффективного решения вычислительных задач поиска. Одним из мотивов изучения гиперэвристики является создание систем, которые могут обрабатывать классы проблем, а не решать только одну проблему. [1] [2] [3]
Может быть несколько эвристик, из которых можно выбрать решение проблемы, и каждая эвристика имеет свои сильные и слабые стороны. Идея состоит в том, чтобы автоматически разрабатывать алгоритмы, сочетая сильные стороны и компенсируя недостатки известных эвристик. [4] В типичной гиперэвристической структуре есть высокоуровневая методология и набор низкоуровневых эвристик (конструктивных или пертурбативных эвристик). Учитывая экземпляр проблемы, метод высокого уровня выбирает, какая эвристика низкого уровня должна применяться в любой момент времени, в зависимости от текущего состояния проблемы (или стадии поиска), определяемого функциями. [2] [5] [6]
Гиперэвристика против метаэвристики
Фундаментальное различие между метаэвристикой и гиперэвристикой заключается в том, что большинство реализаций метаэвристики выполняет поиск в пространстве поиска решений проблемы, тогда как гиперэвристика всегда выполняет поиск в пространстве поиска эвристики. Таким образом, используя гиперэвристику, мы пытаемся найти правильный метод или последовательность эвристик в данной ситуации, а не пытаемся решить проблему напрямую. Более того, мы ищем общедоступную методологию, а не решаем единичный пример проблемы.
Гиперэвристику можно рассматривать как «нестандартные» методы в противоположность метаэвристике «по индивидуальному заказу». Они стремятся быть универсальными методами, которые должны давать решения приемлемого качества на основе набора простых в реализации эвристик низкого уровня.
Мотивация
Несмотря на значительный прогресс в создании методологий поиска для самых разных областей применения, такие подходы по-прежнему требуют от специалистов интеграции их опыта в данной проблемной области. Многие исследователи из области информатики , искусственного интеллекта и операционных исследований уже признали необходимость разработки автоматизированных систем, которые заменят роль человека-эксперта в таких ситуациях. Одна из основных идей автоматизации проектирования эвристик требует включения механизмов машинного обучения в алгоритмы для адаптивного управления поиском. Процессы обучения и адаптации могут быть реализованы в интерактивном или автономном режиме и основаны на конструктивных или пертурбативных эвристиках.
Гиперэвристика обычно направлена на сокращение объема знаний предметной области в методологии поиска. Результирующий подход должен быть дешевым и быстрым для реализации, требующим меньших знаний ни в проблемной области, ни в эвристических методах, и (в идеале) он должен быть достаточно надежным, чтобы эффективно обрабатывать ряд экземпляров проблемы из множества областей. Цель состоит в том, чтобы повысить уровень универсальности методологии поддержки принятия решений, возможно, за счет снижения - но все же приемлемого - качества решения по сравнению с индивидуализированными метаэвристическими подходами. [7] Чтобы сократить разрыв между индивидуализированными схемами и стратегиями, основанными на гиперэвристике, были предложены параллельные гиперэвристики. [8]
Происхождение
Термин «гиперэвристика» впервые был введен в 2000 г. в публикации Коулинга и Субейги, которые использовали его для описания идеи «эвристики для выбора эвристики». [9] Они использовали подход машинного обучения с «функцией выбора», который сводит на нет использование и исследование при выборе следующей эвристики для использования. [10] Впоследствии Каулинг, Субейга, Кендалл, Хан, Росс и другие авторы исследовали и расширили эту идею в таких областях, как эволюционные алгоритмы и патологические низкоуровневые эвристики. Первая журнальная статья, в которой использовался этот термин, появилась в 2003 году. [11] Происхождение идеи (хотя и не самого термина) можно проследить до начала 1960-х годов [12] [13], и она была независимо повторно открыта и расширена несколько раз. в течение 1990-х гг. [14] [15] [16] В области планирования работы в цехах новаторская работа Фишера и Томпсона [12] [13] выдвинула гипотезу и экспериментально доказала, используя вероятностное обучение, что комбинирующие правила планирования (также известные как приоритет или правила отправки) превосходит любое из правил по отдельности. Хотя этот термин тогда еще не использовался, это была первая «гиперэвристическая» статья. Еще один корень, вдохновляющий концепцию гиперэвристики, происходит из области искусственного интеллекта . В частности, это связано с работой над автоматизированными системами планирования и ее конечной направленностью на проблему обучения контрольным знаниям. Так называемая система COMPOSER, разработанная Грэтчем и др. [17] [18], использовалась для управления расписаниями спутниковой связи с участием ряда спутников на околоземной орбите и трех наземных станций. Систему можно охарактеризовать как восходящий поиск в пространстве возможных стратегий управления.
Классификация подходов
Пока что гиперэвристические подходы можно разделить на две основные категории. В первом классе, захваченный фраза эвристика для выбора эвристики , [9] [10] гипер-эвристической база снабжен набором уже существующего, как правило , широко известных эвристик для решения целевой задачи. Задача состоит в том, чтобы найти хорошую последовательность применений этой эвристики (также известной как эвристика низкого уровня в области гиперэвристики) для эффективного решения проблемы. На каждом этапе принятия решения эвристика выбирается с помощью компонента, называемого механизмом выбора, и применяется к действующему решению. Новое решение, полученное в результате применения выбранной эвристики, принимается / отклоняется на основе другого компонента, называемого критерием приемлемости. Отклонение решения означает, что оно просто отбрасывается, в то время как принятие приводит к замене действующего решения. Во втором классе, эвристиках для генерации эвристик , ключевая идея состоит в том, чтобы «разработать новую эвристику, используя компоненты известной эвристики». [19] Процесс требует, как и в первом классе гиперэвристик, выбора подходящего набора эвристик, которые, как известно, могут быть полезны при решении целевой проблемы. Однако вместо того, чтобы передавать их непосредственно в структуру, эвристики сначала разбиваются на их основные компоненты.
Эти два основных типа можно разделить на категории в зависимости от того, основаны ли они на конструктивном или пертурбативном поиске. Дополнительная ортогональная классификация гиперэвристики рассматривает источник, обеспечивающий обратную связь в процессе обучения, который может быть либо одним экземпляром ( онлайн-обучение ), либо множеством экземпляров основной изучаемой проблемы ( автономное обучение ).
Методики выбора эвристики
Откройте для себя хорошие комбинации фиксированных, разработанных людьми, хорошо известных эвристик низкого уровня.
- На основе конструктивной эвристики
- На основе пертурбативной эвристики
Методики создания эвристики
Создавайте новые эвристические методы, используя базовые компоненты ранее существовавших эвристических методов.
- На основе базовых компонентов конструктивной эвристики
- На основе основных компонентов пертурбативной эвристики
Гиперэвристика онлайн-обучения
Обучение происходит, когда алгоритм решает экземпляр проблемы, поэтому зависящие от задачи локальные свойства могут использоваться стратегией высокого уровня для определения соответствующей эвристики низкого уровня для применения. Примерами подходов к онлайн-обучению в рамках гиперэвристики являются: использование обучения с подкреплением для эвристического выбора и, как правило, использование метаэвристики в качестве высокоуровневых стратегий поиска в пространстве эвристики поиска.
Гиперэвристика автономного обучения
Идея состоит в том, чтобы собрать знания в форме правил или программ из набора обучающих примеров, которые, мы надеемся, можно было бы обобщить для процесса решения невидимых примеров. Примерами автономных подходов к обучению в рамках гиперэвристики являются: обучающие системы классификаторов , рассуждения на основе случаев и генетическое программирование .
Расширенная классификация гиперэвристических методов отбора была предоставлена в 2020 году [20], чтобы обеспечить более полную категоризацию современных гиперэвристических методов отбора.
Приложения
Гиперэвристика применялась для решения множества различных задач. Действительно, одна из мотиваций гиперэвристики - способность работать с разными типами задач. Следующий список представляет собой неполный список некоторых проблем и областей, в которых изучалась гиперэвристика:
- проблема с упаковкой бункера
- проблема логической выполнимости
- учебное расписание
- планирование работы цеха
- многоцелевое решение проблем и распределение пространства
- список медсестер
- планирование персонала
- задача коммивояжера
- проблема с маршрутизацией автомобиля
- многомерная задача о рюкзаке
- 0-1 задача о ранце
- проблема максимальной резки
- квадратичная задача о назначениях
- план ветряной электростанции
Связанные области
Гиперэвристика - не единственный подход, который исследуется в поисках более общих и применимых методологий поиска. Многие исследователи из области информатики, искусственного интеллекта и операционных исследований уже признали необходимость разработки автоматизированных систем, которые заменят роль человека-эксперта в процессе настройки и адаптации методологий поиска. В следующем списке перечислены некоторые смежные области исследований:
- адаптация и самоадаптация параметров алгоритма
- адаптивный меметический алгоритм
- адаптивный поиск больших окрестностей
- конфигурация алгоритма
- алгоритм управления
- портфели алгоритмов
- автономный поиск
- генетическое программирование
- косвенные кодировки в эволюционных алгоритмах
- поиск переменных окрестностей
- реактивный поиск
Смотрите также
- Конструктивная эвристика
- Метаоптимизация тесно связана с гиперэвристикой.
- генетические алгоритмы
- генетическое программирование
- эволюционные алгоритмы
- локальный поиск (оптимизация)
- машинное обучение
- меметические алгоритмы
- метаэвристика
- нет бесплатного обеда в поиске и оптимизации
- оптимизация роя частиц
- реактивный поиск
Ссылки и примечания
- ^ Э. К. Берк, Э. Харт, Г. Кендалл , Дж. Ньюолл, П. Росс и С. Шуленбург, Гиперэвристика: новое направление в современной поисковой технологии , Справочник по метаэвристике (Ф. Гловер и Г. Кохенбергер, ред. .), Kluwer, 2003, стр. 457–474.
- ^ а б П. Росс, Гиперэвристика, методологии поиска: вводные учебные пособия по методам оптимизации и поддержки принятия решений (Э. К. Берк и Г. Кендалл , ред.), Springer, 2005, стр. 529-556.
- ^ Э. Озкан, Б. Билгин, Э. Коркмаз, Комплексный анализ гиперэвристики , Интеллектуальный анализ данных, 12: 1, стр. 3-23, 2008.
- ^ Э. Озкан, Б. Билгин, Э. Коркмаз, Альпинисты и мутационная эвристика в гиперэвристике, Лекционные заметки по информатике, Springer-Verlag, 9-я Международная конференция по параллельному решению проблем с помощью природы, 2006, стр. 202-211.
- ↑ Amaya, I., Ortiz-Bayliss, JC, Rosales-Perez, A., Gutierrez-Rodriguez, AE, Conant-Pablos, SE, Terashima-Marin, H. и Coello, CAC, 2018. Повышение гиперэвристики отбора с помощью Преобразования функций. Журнал IEEE Computational Intelligence Magazine, 13 (2), стр.30-41. https://ieeexplore.ieee.org/iel7/10207/8335819/08335843.pdf
- ^ Амайя, И., Ортис-Бейлисс, JC, Гутьеррес-Родригес, AE, Терашима-Марин, Х. и Коэльо, CAC, 2017, июнь. Повышение гиперэвристической производительности за счет преобразования функций. В 2017 г. Конгресс IEEE по эволюционным вычислениям (CEC) (стр. 2614-2621). IEEE. https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7969623
- ^ Burke EK, Ланда Silva JD, Soubeiga E .: Многоцелевого Hyper-эвристические подходы к Распределению пространства и расписания , В метаэвристиках: Прогресскак реальная проблема вычислители, отдельные документы 5й Международной конференции метаэвристики (MIC 2003), стр 129-158, 2005.
- ^ С. Сегура, Г. Миранда и К. Леон: Параллельные гиперэвристики для задачи частотного присвоения Специальный выпуск о вдохновленных природой кооперативных стратегиях оптимизации, В меметических вычислениях, Специальный выпуск о вдохновленных природой совместных стратегиях для оптимизации, ( doi : 10.1007 / s12293 -010-0044-5 [1] ), 2010.
- ^ a b Каулинг П. и Субейга Э. Структуры соседства для планирования персонала: проблема планирования встреч на высшем уровне (аннотация), в материалах 3-й Международной конференции по практике и теории автоматизированного составления расписания, Берк Э. К. и Эрбен В. (ред.) , 16-18 августа 2000 г., Констанц, Германия
- ^ a b Каулинг П., Кендалл Г. и Субейга Э., Гиперэвристический подход к планированию саммита по продажам, 2001 г., Лекционные заметки по информатике 2079, Springer-Verlag, стр. 176–190, 2001 г., ISBN 3540424210 , ( doi : 10.1007 / 3-540-44629-X
- ^ Берк К., Kendall Г. и Soubeiga Е. (2003 г.) Табу-Search Hyper-Эвристический для расписаний и Rostering. Журнал эвристики, 9 (6): 451-470. ( DOI : 10,1023 / Б: HEUR.0000012446.94732.b6 [2] )
- ^ а б Х. Фишер и Г.Л. Томпсон, Вероятностные обучающие комбинации правил планирования местных рабочих мест, Конференция по планированию фабрик (Технологический институт Карнеги), 1961.
- ^ a b * Х. Фишер и Г.Л. Томпсон, Вероятностные обучающие комбинации правил планирования местных рабочих мест, Промышленное планирование (Нью-Джерси) (Дж. Ф. Мут и Г. Л. Томпсон, ред.), Prentice-Hall, Inc, 1963, стр. 225 –251.
- ^ RH Storer, SD Wu и R. Vaccari, Новые пространства поиска для задач последовательности с применением к планированию рабочих мест , Management Science, 38 (10), 1992, 1495–1509.
- ^ HL Фанг, П. Росс и Д. Корн, Многообещающий подход на основе генетических алгоритмов к планированию, изменению расписания и задачам планирования работы в цехах , Пятая международная конференция по генетическим алгоритмам (Сан-Матео) (С. Форрест, ред.) , Морган Кауфманн, 1993, стр. 375–382.
- ^ У. Дорндорф и Э. Пеш, Обучение на основе эволюции в среде планирования рабочего места , Компьютеры и исследования операций, 22 (1), 1995, 25-40.
- ^ Дж. Гратч, С. Чиен и Дж. ДеЙонг, Изучение знаний управления поиском для планирования сетей в дальнем космосе , Труды Десятой Международной конференции по машинному обучению (Амхерст, Массачусетс), 1993, стр. 135–142.
- ^ Дж. Грэтч и С. Чиен, Адаптивное решение задач для крупномасштабных задач планирования: тематическое исследование , Журнал исследований искусственного интеллекта, 4, 1996, 365–396.
- ^ М. Бадер-Эль-Ден и Р. Поли, Создание эвристики локального поиска спутников с использованием гиперэвристической структуры GP , Искусственная эволюция, 8-я международная конференция, Evolution Artificielle, EA 2007, Тур, Франция, 29–31 октября 2007 г. , Отредактированные избранные статьи. Конспект лекций по информатике 4926 Springer, 2008, стр. 37-49.
- ^ Дрейк Дж. Х., Хейри А., Озкан Э., Берк Е. К., (2020) Последние достижения в области гиперэвристики выбора. Европейский журнал операционных исследований, 285 (2), стр. 405-428. ( DOI : 10.1016 / j.ejor.2019.07.073 [3] )
Внешние ссылки
Гиперэвристические библиографии
- https://mustafamisir.github.io/hh.html
Исследовательские группы
- Лаборатория искусственного интеллекта (ART + I) , Университет Йедитепе , Турция
- Исследовательская группа по автоматизированному планированию, оптимизации и планированию (ASAP) , Ноттингемский университет , Великобритания
- Группа исследований комбинаторной оптимизации и поддержки принятия решений (CODeS) , KU Leuven , Бельгия
- Группа исследований вычислительной эвристики, исследования операций и поддержки принятия решений (CHORDS) , Университет Стерлинга , Великобритания
- Группа исследований эволюционных вычислений , Веллингтонский университет Виктории , Новая Зеландия
- Лаборатория интеллектуальных систем , Университет Хериот-Ватт , Великобритания
- Группа исследования интеллектуальных систем , Tecnologico de Monterrey , Мексика .
- Лаборатория машинного обучения и исследования операций (MEmORy) , Нанкинский университет аэронавтики и астронавтики , Китай
- Группа исследований по оптимизации планирования и интеллектуального управления (MOSAIC) , Университет Брэдфорда , Великобритания
- Группа операционных исследований , Лондонский университет королевы Марии , Великобритания
- Оптимизация программного обеспечения с помощью вычислений от исследовательской группы по искусственному интеллекту (ОСКАР) , Даляньский технологический университет , Китай
Последние действия
- Трансляция по гиперэвристике @ EURO 2019
- Приглашенная сессия по автоматизированному проектированию алгоритмов для многоцелевых задач оптимизации @ MCDM 2019
- 8-й семинар по эволюционным вычислениям для автоматизированного проектирования алгоритмов (ECADA) @ GECCO 2018
- Стрим по гиперэвристике @ EURO 2018
- Специальная сессия по автоматизированному проектированию алгоритмов как ансамблевым методам @ IEEE CIEL / SSCI 2017
- Учебное пособие по выбору алгоритма: автономные + онлайн-методы @ SEAL 2017
- 1-й симпозиум AISB по метаоптимизации: гиперэвристика и не только @ AISB Convention 2013
- Современная гиперэвристика для крупномасштабных задач оптимизации @ META2012
- Учебник по гиперэвристике и междоменной оптимизации @ GECCO 2012
- Самостоятельный поиск на сайте GECCO, 2012 г.
- Специальная сессия по эволюционной гиперэвристике и их приложениям @ IEEE CEC2012 (WCCI2012)
- Специальная сессия по междоменному эвристическому поиску (LION-CHESC) @ LION2012
- Задача междоменного эвристического поиска 2011 (CHeSC 2011)
- Специальная сессия «Системы для построения систем» @ MISTA 2011
- Учебное пособие по автоматизированному эвристическому проектированию @ GECCO 2011
- Специальная сессия по гибридным эволюционным алгоритмам, гиперэвристике и меметическим вычислениям @ IEEE CEC2010 (WCCI 2010)
- Семинар по самонастраивающейся, самонастраивающейся и самогенерирующейся эвристике поиска (Self * 2010) @ PPSN 2010
- Мастер-класс по гиперэвристике @ PPSN 2008
Другие
- Целевая группа по Hyper-эвристики в Техническом комитете интеллектуальных систем и приложений в области вычислительной разведки общества IEEE .