Гиперэвристический - Hyper-heuristic

А гиперэвристический это эвристический поисковый метод, который стремится автоматизировать, часто за счет включения машинное обучение методы, процесс выбора, комбинирования, генерации или адаптации нескольких более простых эвристик (или компонентов таких эвристик) для эффективного решения задач вычислительного поиска. Одним из мотивов изучения гиперэвристики является создание систем, которые могут обрабатывать классы проблем, а не решать только одну проблему.[1][2][3]

Может быть несколько эвристик, из которых можно выбирать для решения проблемы, и каждая эвристика имеет свои сильные и слабые стороны. Идея состоит в том, чтобы автоматически разрабатывать алгоритмы, сочетая сильные стороны и компенсируя недостатки известных эвристик.[4] В типичной гиперэвристической структуре есть методология высокого уровня и набор эвристик низкого уровня (конструктивная или пертурбативная эвристика). Учитывая экземпляр проблемы, метод высокого уровня выбирает, какая эвристика низкого уровня должна применяться в любой момент времени, в зависимости от текущего состояния проблемы (или стадии поиска), определяемого функциями.[2][5][6]

Гиперэвристика против метаэвристики

Принципиальная разница между метаэвристика и гиперэвристика - это то, что большинство реализаций метаэвристического поиска в пространство поиска решений проблем, тогда как гиперэвристики всегда ищут в поисковом пространстве эвристик. Таким образом, используя гиперэвристику, мы пытаемся найти правильный метод или последовательность эвристик в данной ситуации, а не пытаемся решить проблему напрямую. Более того, мы ищем общедоступную методологию, а не решаем единичный пример проблемы.

Гиперэвристику можно рассматривать как «нестандартные» методы в противоположность метаэвристике «по индивидуальному заказу». Они стремятся быть универсальными методами, которые должны давать решения приемлемого качества на основе набора простых для реализации эвристик низкого уровня.

Мотивация

Несмотря на значительный прогресс в создании методологий поиска для самых разных областей применения, такие подходы по-прежнему требуют, чтобы специалисты интегрировали свои знания в данной проблемной области. Многие исследователи из Информатика, искусственный интеллект и исследование операций уже признали необходимость разработки автоматизированных систем, которые заменят роль человека-эксперта в таких ситуациях. Одна из основных идей автоматизации проектирования эвристик требует включения машинное обучение механизмы в алгоритмы для адаптивного управления поиском. Процессы обучения и адаптации могут быть реализованы в интерактивном или автономном режиме и основаны на конструктивной или пертурбативной эвристике.

Гиперэвристика обычно направлена ​​на уменьшение количества базовые знания в методологии поиска. Результирующий подход должен быть дешевым и быстрым для реализации, требующим меньших знаний ни в проблемной области, ни в эвристических методах, и (в идеале) он должен быть достаточно надежным, чтобы эффективно обрабатывать ряд экземпляров проблемы из множества областей. Цель состоит в том, чтобы повысить уровень универсальности методологии поддержки принятия решений, возможно, за счет снижения - но все же приемлемого - качества решения по сравнению с индивидуализированными метаэвристическими подходами.[7] Чтобы уменьшить разрыв между индивидуализированными схемами и стратегиями, основанными на гиперэвристике, были предложены параллельные гиперэвристики.[8]

Происхождение

Термин «гиперэвристика» впервые был введен в 2000 г. в публикации Коулинга и Субейги, которые использовали его для описания идеи «эвристики для выбора эвристики».[9] Они использовали подход машинного обучения с «функцией выбора», который сводит на нет использование и исследование при выборе следующей эвристики для использования.[10] Впоследствии Каулинг, Субейга, Кендалл, Хан, Росс и другие авторы исследовали и расширили эту идею в таких областях, как эволюционные алгоритмы и патологическая эвристика низкого уровня. Первая журнальная статья, в которой использовался этот термин, появилась в 2003 году.[11] Происхождение идеи (хотя и не самого термина) восходит к началу 1960-х годов.[12][13] и был независимо повторно открыт и расширен несколько раз в течение 1990-х годов.[14][15][16] В области планирования рабочих мест - новаторская работа Фишера и Томпсона,[12][13] выдвинул гипотезу и экспериментально доказал, используя вероятностное обучение, что объединение правил планирования (также известных как правила приоритета или диспетчеризации) превосходит любое из правил, взятых по отдельности. Хотя этот термин тогда еще не использовался, это была первая «гиперэвристическая» статья. Еще один корень, лежащий в основе концепции гиперэвристики, происходит из области искусственный интеллект. В частности, это результат работы над автоматизированное планирование системы, и его конечная направленность на проблему обучения контролю знаний. Так называемая система COMPOSER, разработанная Gratch et al.,[17][18] использовался для управления расписаниями спутниковой связи с участием ряда спутников на околоземной орбите и трех наземных станций. Систему можно охарактеризовать как скалолазание поиск в пространстве возможных стратегий управления.

Классификация подходов

Пока что гиперэвристические подходы можно разделить на две основные категории. В первом классе запечатлен фразой эвристика для выбора эвристики,[9][10] Гиперэвристический фреймворк снабжен набором уже существующих, широко известных эвристик для решения целевой проблемы. Задача состоит в том, чтобы найти хорошую последовательность применений этой эвристики (также известной как эвристика низкого уровня в области гиперэвристики) для эффективного решения проблемы. На каждом этапе принятия решения эвристика выбирается с помощью компонента, называемого механизмом выбора, и применяется к действующему решению. Новое решение, полученное в результате применения выбранной эвристики, принимается / отклоняется на основе другого компонента, называемого критерием приемлемости. Отклонение решения означает, что оно просто отбрасывается, в то время как принятие ведет к замене действующего решения. Во втором классе эвристика для генерации эвристики, ключевая идея - «разработать новую эвристику, используя компоненты известной эвристики».[19] Процесс требует, как и в первом классе гиперэвристик, выбора подходящего набора эвристик, которые, как известно, могут быть полезны при решении целевой проблемы. Однако вместо того, чтобы передавать их непосредственно в структуру, эвристика сначала разбивается на их основные компоненты.

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

Методики выбора эвристики

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

  • На основе конструктивной эвристики
  • На основе пертурбативной эвристики

Методики создания эвристики

Создавайте новые эвристические методы, используя базовые компоненты ранее существовавших эвристических методов.

  • На основе базовых компонентов конструктивной эвристики
  • На основе основных компонентов пертурбативной эвристики

Гиперэвристика онлайн-обучения

Обучение происходит, когда алгоритм решает экземпляр проблемы, поэтому зависящие от задачи локальные свойства могут использоваться стратегией высокого уровня для определения соответствующей эвристики низкого уровня для применения. Примерами подходов к онлайн-обучению в рамках гиперэвристики являются: использование обучение с подкреплением для эвристического отбора и, как правило, использования метаэвристика как стратегии поиска высокого уровня в пространстве эвристики.

Гиперэвристика автономного обучения

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


Расширенная классификация отбор гиперэвристика была предоставлена ​​в 2019 году,[20] обеспечить более полную категоризацию современных гиперэвристических методов отбора.

Приложения

Гиперэвристика применялась для решения множества различных задач. Действительно, одна из мотиваций гиперэвристики - способность работать с разными типами задач. Следующий список представляет собой неполный список некоторых проблем и областей, в которых изучалась гиперэвристика:

Связанные области

Гиперэвристика - не единственный подход, который исследуется в поисках более общих и применимых методологий поиска. Многие исследователи из области информатики, искусственный интеллект и исследование операций уже признали необходимость разработки автоматизированных систем, которые заменят роль человека-эксперта в процессе настройки и адаптации методологий поиска. В следующем списке перечислены некоторые смежные области исследований:

Смотрите также

Ссылки и примечания

  1. ^ Э. К. Берк, Э. Харт, Дж. Кендалл, Дж. Ньюолл, П. Росс и С. Шуленбург, Гиперэвристика: новое направление в современных поисковых технологиях, Справочник по метаэвристике (Ф. Гловер и Г. Кохенбергер, ред.), Kluwer, 2003, стр. 457–474.
  2. ^ а б Росс, Гиперэвристика, методологии поиска: вводные учебные пособия по методам оптимизации и поддержки принятия решений (Э. К. Берк и Дж. Кендалл, ред.), Springer, 2005, стр. 529-556.
  3. ^ Э. Озджан, Б. Билгин, Э. Э. Коркмаз, Комплексный анализ гиперэвристики, Интеллектуальный анализ данных, 12: 1, стр. 3-23, 2008.
  4. ^ Э. Озкан, Б. Билгин, Э. Э. Коркмаз, Альпинисты и мутационная эвристика в гиперэвристике, Конспект лекций по информатике, Springer-Verlag, 9-я Международная конференция по параллельному решению проблем с помощью природы, 2006, стр. 202-211.
  5. ^ Амая, И., Ортис-Бейлисс, Дж. К., Росалес-Перес, А., Гутьеррес-Родригес, А. Э., Конант-Паблос, С. Е., Терашима-Марин, Х. и Коэльо, САС, 2018. Повышение гиперэвристики отбора с помощью функции Преобразования. Журнал IEEE Computational Intelligence Magazine, 13 (2), стр.30-41. https://ieeexplore.ieee.org/iel7/10207/8335819/08335843.pdf
  6. ^ Амайя, И., Ортис-Бейлисс, Дж. К., Гутьеррес-Родригес, А. Э., Терасима-Марин, Х. и Коэльо, Калифорния, 2017 г., июнь. Повышение гиперэвристической производительности за счет преобразования функций. В 2017 г. Конгресс IEEE по эволюционным вычислениям (CEC) (стр. 2614-2621). IEEE. https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7969623
  7. ^ Берк Э.К., Ланда Сильва Д.Д., Субейга Э .: Многоцелевые гиперэвристические подходы к распределению пространства и расписанию, В метаэвристике: прогресс как реальное решение проблем, Избранные статьи 5-й Международной конференции по метаэвристике (MIC 2003), стр 129-158, 2005.
  8. ^ К. Сегура, Г. Миранда и К. Леон: Параллельные гиперэвристики для задачи частотного присвоения Специальный выпуск о вдохновленных природой кооперативных стратегиях оптимизации, В меметических вычислениях, Специальный выпуск о вдохновленных природой кооперативных стратегиях оптимизации, (Дои:10.1007 / s12293-010-0044-5 [1] ), 2010.
  9. ^ а б Каулинг П. и Субейга Э. Структуры соседства для планирования персонала: проблема планирования встреч на высшем уровне (аннотация), в материалах 3-й Международной конференции по практике и теории автоматизированного расписания, Берк Э.К. и Эрбен В. (ред.), 16-18 августа 2000 г., Констанц, Германия
  10. ^ а б Каулинг П., Кендалл Г. и Soubeiga E., Гиперэвристический подход к планированию саммита по продажам, 2001, Lecture Notes in Computer Science 2079, Springer-Verlag, pp. 176–190, 2001, ISBN  3540424210, (Дои:10.1007 / 3-540-44629-X
  11. ^ Берк Э. К., Кендалл Г., и Soubeiga E. (2003) Гиперэвристика табу-поиска для составления расписания и составления списков. Журнал эвристики, 9 (6): 451-470. (Дои:10.1023 / B: HEUR.0000012446.94732.b6 [2] )
  12. ^ а б Х. Фишер и Г. Л. Томпсон, Вероятностные обучающие комбинации местных правил планирования работы цеха, Конференция по планированию фабрик (Технологический институт Карнеги), 1961.
  13. ^ а б * Х. Фишер и Г. Л. Томпсон, Вероятностные обучающие комбинации правил планирования местных рабочих мест, Промышленное планирование (Нью-Джерси) (Дж. Ф. Мут и Г. Л. Томпсон, ред.), Prentice-Hall, Inc, 1963, стр. 225–251.
  14. ^ Р. Х. Сторер, С. Д. Ву и Р. Ваккари, Новые области поиска для определения последовательности проблем с приложением к планированию работы цеха, Management Science, 38 (10), 1992, 1495–1509.
  15. ^ Х. Л. Фанг, П. Росс и Д. Корн, Многообещающий подход на основе генетического алгоритма к задачам планирования, перепланирования и планирования работы в цехах, Пятая международная конференция по генетическим алгоритмам (Сан-Матео) (С. Форрест, ред.), Морган Кауфманн, 1993, стр. 375–382.
  16. ^ У. Дорндорф и Э. Пеш, Обучение на основе эволюции в среде планирования работы цеха, Компьютеры и исследования операций, 22 (1), 1995, 25–40.
  17. ^ Дж. Грэтч, С. Чиен, Дж. ДеЙонг, Изучение знаний об управлении поиском для планирования сети в дальнем космосе, Труды Десятой Международной конференции по машинному обучению (Амхерст, Массачусетс), 1993, стр. 135–142.
  18. ^ Дж. Грэтч и С. Чиен, Адаптивное решение задач для крупномасштабных задач планирования: пример из практики, Журнал исследований искусственного интеллекта, 4, 1996, 365–396.
  19. ^ М. Бадер-Эль-Ден и Р. Поли, Создание эвристики локального поиска спутников с использованием гиперэвристической структуры GP, Искусственная эволюция, 8-я Международная конференция, Evolution Artificielle, EA 2007, Тур, Франция, 29–31 октября 2007 г., Пересмотренные избранные статьи. Конспект лекций по информатике 4926 Springer, 2008, стр. 37-49.
  20. ^ Дрейк Дж. Х., Хейри А., Озкан Э., Берк Э. К., (2019) Последние достижения в области гиперэвристики выбора. Европейский журнал операционных исследований (принято к печати). (Дои:10.1016 / j.ejor.2019.07.073 [3] )

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

Гиперэвристические библиографии

Исследовательские группы

Последние действия

Другие