Гиперэвристика
Гиперэвристика метод поиска, целью которого является автоматизация, часто за — это эвристический счет использования методов машинного обучения , процесса выбора, комбинирования, генерации или адаптации нескольких более простых эвристик (или компонентов таких эвристик) для эффективного решения задач вычислительного поиска. Одной из причин изучения гиперэвристики является создание систем, способных решать классы задач, а не только одну проблему. [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 проблема с рюкзаком
- проблема с максимальным разрезом
- квадратичная задача о назначениях
- план ветровой электростанции
Связанные области
[ редактировать ]Гиперэвристика — не единственный подход, изучаемый в поисках более общих и применимых методологий поиска. Многие исследователи в области информатики, искусственного интеллекта и операционных исследований уже признали необходимость разработки автоматизированных систем, которые заменят роль человека-эксперта в процессе настройки и адаптации методологий поиска. В следующем списке представлены некоторые смежные области исследований:
- адаптация и самоадаптация параметров алгоритма
- адаптивный меметический алгоритм
- адаптивный поиск больших окрестностей
- конфигурация алгоритма
- алгоритм управления
- портфолио алгоритмов
- автономный поиск
- генетическое программирование
- косвенное кодирование в эволюционных алгоритмах
- переменный поиск окрестностей
- реактивный поиск
Существующие фреймворки
[ редактировать ]В настоящее время доступно несколько фреймворков на разных языках программирования. К ним относятся, помимо прочего:
См. также
[ редактировать ]- Конструктивная эвристика
- Метаоптимизация тесно связана с гиперэвристикой.
- генетические алгоритмы
- генетическое программирование
- эволюционные алгоритмы
- локальный поиск (оптимизация)
- машинное обучение
- меметические алгоритмы
- метаэвристика
- нет бесплатного обеда в поиске и оптимизации
- оптимизация роя частиц
- реактивный поиск
Ссылки и примечания
[ редактировать ]- ^ EK Берк, Э. Харт, Г. Кендалл , Дж. Ньюолл, П. Росс и С. Шуленбург, Гиперэвристика: новое направление в современной поисковой технологии , Справочник по метаэвристике (Ф. Гловер и Г. Кохенбергер, ред. .), Клювер, 2003, стр. 457–474.
- ^ Jump up to: а б П. Росс, Гиперэвристика, Методологии поиска: Вводные уроки по методам оптимизации и поддержки принятия решений (ЭК Берк и Г. Кендалл , ред.), Springer, 2005, стр. 529–556.
- ^ Э. Озджан, Б. Билгин, Э. Э. Коркмаз, Комплексный анализ гиперэвристики [ мертвая ссылка ] , Интеллектуальный анализ данных, 12:1, стр. 3–23, 2008 г.
- ^ Э. Озджан, Б. Билгин, Э. Е. Коркмаз, Альпинисты и мутационная эвристика в гиперэвристике, Конспекты лекций по информатике, Springer-Verlag, 9-я Международная конференция по параллельному решению проблем из природы, 2006, стр. 202-211.
- ^ Амайя, И., Ортис-Бейлисс, Д.К., Розалес-Перес, А., Гутьеррес-Родригес, А.Е., Конант-Паблос, С.Е., Терашима-Марин, Х. и Коэльо, CAC, 2018. Улучшение гиперэвристики выбора с помощью Преобразования функций. Журнал IEEE Computational Intelligence, 13(2), стр.30–41. https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=8335843
- ^ Амайя, И., Ортис-Бейлисс, Дж.К., Гутьеррес-Родригес, А.Е., Терашима-Марин, Х. и Коэльо, CAC, 2017, июнь. Улучшение гиперэвристической производительности за счет преобразования функций. Конгресс IEEE по эволюционным вычислениям (CEC) 2017 г. (стр. 2614–2621). IEEE. https://ieeeexplore.ieee.org/stamp/stamp.jsp?arnumber=7969623
- ^ Берк Э.К., Ланда Сильва Дж.Д., Собейга Э.: Многоцелевые гиперэвристические подходы к распределению пространства и составлению расписаний , В «Метаэвристике: прогресс как реальные решения проблем», Избранные статьи с 5-й Международной конференции по метаэвристике (MIC 2003), стр. 129-158, 2005.
- ^ К. Сегура, Г. Миранда и К. Леон: Параллельная гиперэвристика для задачи назначения частотСпециальный выпуск о вдохновленных природой совместных стратегиях оптимизации, In Memetic Computing, Специальный выпуск о вдохновленных природой совместных стратегиях оптимизации, ( doi : 10.1007/s12293-010-0044-5 [1] ), 2010.
- ^ Jump up to: а б Коулинг П. и Собейга Э. Структуры соседства для планирования персонала: проблема планирования встреч на высшем уровне (аннотация), в материалах 3-й Международной конференции по практике и теории автоматизированного составления расписаний, Берк Э.К. и Эрбен В. (редакторы), 16- 18 августа 2000 г., Констанц, Германия.
- ^ Jump up to: а б Коулинг П., Кендалл Г. и Собейга Э., Гиперэвристический подход к планированию саммита по продажам, 2001 г., Конспекты лекций по информатике, 2079 г., Springer-Verlag, стр. 176–190, 2001 г., ISBN 3540424210 , ( два : 10.1007/3-540-44629-X
- ^ Берк Э.К., Кендалл Г. и Собейга Э. (2003) Гиперэвристика табу-поиска для составления расписания и составления реестров. Журнал эвристики, 9 (6): 451-470. ( doi : 10.1023/B:HEUR.0000012446.94732.b6 [2] )
- ^ Jump up to: а б Х. Фишер и Г. Л. Томпсон, Вероятностные комбинации обучения правил планирования местных цехов, Конференция по планированию предприятий (Технологический институт Карнеги), 1961.
- ^ Jump up to: а б * Х. Фишер и Г.Л. Томпсон, Вероятностные обучающие комбинации правил планирования местного цеха, Промышленное планирование (Нью-Джерси) (Дж. Ф. Мут и Г. Л. Томпсон, ред.), Prentice-Hall, Inc, 1963, стр. 225–251.
- ^ Р. Х. Сторер, С. Д. Ву и Р. Ваккари, Новые пространства поиска для решения проблем последовательности с применением к планированию цеха , Management Science, 38 (10), 1992, 1495–1509.
- ^ HL Fang, П. Росс и Д. Корн, Многообещающий подход с использованием генетических алгоритмов к решению задач планирования, перепланирования и планирования открытых цехов , Пятая международная конференция по генетическим алгоритмам (Сан-Матео) (С. Форрест, изд.) , Морган Кауфманн, 1993, стр. 375–382.
- ^ У. Дорндорф и Э. Пеш, Обучение, основанное на эволюции, в среде планирования рабочего места , Computers and Operations Research, 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] )
Внешние ссылки
[ редактировать ]Гиперэвристические библиографии
[ редактировать ]Исследовательские группы
[ редактировать ]- Лаборатория искусственного интеллекта (ART+I). Архивировано 7 июня 2008 г. в Wayback Machine , Университет Йедитепе , Турция.
- Исследовательская группа по автоматизированному планированию, оптимизации и планированию (ASAP) , Ноттингемский университет , Великобритания
- Исследовательская группа по комбинаторной оптимизации и поддержке принятия решений (CODeS) , KU Leuven. Архивировано 5 марта 2011 г. в Wayback Machine , Бельгия.
- Исследовательская группа вычислительной эвристики, исследования операций и поддержки принятия решений (CHORDS) , Университет Стерлинга , Великобритания
- Группа исследований в области эволюционных вычислений , Университет Виктории, Веллингтон , Новая Зеландия
- Лаборатория интеллектуальных систем , Университет Хериот-Ватт , Великобритания
- Исследовательская группа по передовому искусственному интеллекту (ранее: Исследовательская группа интеллектуальных систем ), Tecnologico de Monterrey , Мексика .
- Лаборатория машинного обучения и исследования операций (MEMORY) , Нанкинский университет аэронавтики и космонавтики , КНР
- Исследовательская группа моделирования, оптимизации планирования и интеллектуального управления (MOSAIC) , Университет Брэдфорда , Великобритания
- Группа операционных исследований (OR) , Лондонский университет Королевы Марии , Великобритания
- Оптимизация программного обеспечения посредством вычислений, результаты исследовательской группы искусственного интеллекта (OSCAR) , Даляньский технологический университет , КНР
Недавняя деятельность
[ редактировать ]- Трансляция о гиперэвристике на ЕВРО-2019
- Приглашенная сессия по разработке автоматизированных алгоритмов для задач многокритериальной оптимизации @ MCDM 2019
- 8-й семинар по эволюционным вычислениям для автоматизированного проектирования алгоритмов (ECADA) @ GECCO 2018
- Трансляция о гиперэвристике на ЕВРО-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). Архивировано 30 сентября 2011 г. на Wayback Machine.
- Специальная сессия «Системы для построения систем» @ MISTA 2011
- Учебное пособие по автоматизированному эвристическому проектированию @ GECCO 2011
- Специальная сессия по гибридным эволюционным алгоритмам, гиперэвристике и меметическим вычислениям @ IEEE CEC2010 (WCCI 2010). Архивировано 19 сентября 2011 г. на Wayback Machine.
- Семинар по самонастройке, самонастройке и самогенерации поисковых эвристик (Self* 2010) @ PPSN 2010
- Семинар по гиперэвристике @ PPSN 2008