АссистентНовый вопросИсторияОбласти знаний
Партнёрские проектыСпецпроектыСтать автором
Сменить язык
О РУВИКИ

Метаоптимизация

Метаоптимизация — в прикладной численной оптимизации — это применение одного метода оптимизации для настройки другого метода оптимизации. Первые упоминания о её применении относятся к 1970 году (Мерсер и Сэмпсон) для поиска оптимальных конфигураций параметров в генетических алгоритмах. В литературе метаоптимизация также известна под названиями: метаэволюция, сверхоптимизация, автоматическая калибровка параметров и др.[1]

В общем случае задача состоит в поиске набора значений (допустимой конфигурации) параметров некоторого алгоритма A, чтобы при применении A к экземпляру задачи P был достигнут наилучший результат. Это также называют выбором конфигураций, настройкой параметров или оптимизацией конфигураций. Эффективность работы алгоритма может измеряться потреблёнными вычислительными ресурсами (время выполнения, объём используемой оперативной памяти) либо качеством полученного решения — в любом случае критерий эффективности должен задан исследователем при автоматизации процесса настройки.

Мотивация

undefined

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

Параметры алгоритма оптимизации могут иметь различную природу, а эффективность процесса можно рассматривать топологически. Такой подход выполним при малом числе параметров и несложных задачах, но с увеличением числа параметров требуется всё больше времени для построения «ландшафта» производительности — проблема известна как проклятие размерности для пространства поиска, сформированного параметрами оптимизатора. Поэтому требуется эффективный метод для изучения такого пространства.

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

Методы

undefined

Простейший способ подобрать параметры алгоритма оптимизации — использовать над ним другой алгоритм оптимизации, называемый метаоптимизатором (от префикса мета-). Конкретная реализация зависит от типа параметров (например, вещественные или дискретные) и выбранного критерия эффективности.

Экспериментальный дизайн

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

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

Схожий подход реализован Аденсо-Диасом и Лагуной в системе CALIBRA, где каждая конфигурация оценивается с помощью полного факторного дизайна из двух уровней (по два значения на параметр), после чего итеративно исследуется пространство параметров. Используется фракционный факторный дизайн, основанный на ортогональных матрицах Тагути: анализируется 9 конфигураций вокруг лучшей текущей, при достижении локального минимума сужается область поиска и процесс повторяется. Ограничения: необходимо дискретизировать непрерывные параметры и можно настраивать максимум 5 параметров.

F-Race

Метод F-Race, предложенный Бирартарии, Штюцле, Пакете и Варрентраппом, реализует процедуру отбора конфигураций на основе гоночных алгоритмов. Метод вдохновлён идеями машинного обучения: изначально заданный набор конфигураций тестируется, и худшие исключаются по мере накопления статистических данных против них.

Имея алгоритм A, конечное начальное множество конфигураций и распределение экземпляров задачи I, проводится итеративный процесс — своего рода «гонка», в ходе которой худшие конфигурации «выбывают», а наиболее перспективные получают больше запусков и, соответственно, лучшую оценку эффективности. На каждом этапе выбирается одна задача из I, на которой тестируются все конфигурации, далее проводится тест Фридмана на наличие значимых различий между ними. Эта процедура выполняет роль «арбитра», устраняя конфигурации, неспособные обеспечить хороший результат. Если нулевая гипотеза отвергается, проводят попарные сравнения всех конфигураций с лучшей и исключают те, которые статистически хуже. Процесс продолжается, пока не останется одна конфигурация или не истечёт выделенное время.

Поскольку все конфигурации на первом этапе должны быть протестированы, применение F-Race ограничено задачами, где можно перечислить все возможные варианты параметров. Используемый полный факторный дизайн пространства параметров ограничивает масштабируемость: число вариантов растёт экспоненциально с их количеством. В более поздней работе Бирартари и соавт. предложили альтернативу — случайную выборку параметров по равномерному распределению для формирования начального множества, что оказалось эффективнее полного перебора. Такой случайный подход, особенно для числовых параметров, устраняет необходимость заранее задавать уровни параметров и позволяет равномерно исследовать пространство конфигураций при любом числе кандидатов. Для фокусировки поиска на лучших предложен вариант Iterated F-Race: на каждом этапе новые кандидаты выбираются вокруг лучших конфигураций предыдущего этапа.

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

ParamILS

Ф. Хуттер, Х. Хус и К. Лейтон-Браун разработали систему для решения общей задачи выбора конфигураций — ParamILS. Этот фреймворк оптимизирует производительность заданного (детерминированного или стохастического) алгоритма на определённом подмножестве задач путём вариации ряда порядковых и/или категориальных параметров. В основе лежит итерационный локальный поиск, инициализируемый выбранными заранее или случайными конфигурациями; основной алгоритм использует стратегию локального поиска «первый лучший» и случайные возмущения для обхода локальных минимумов. Любая конфигурация, улучшающая или не ухудшающая текущий результат, принимается, поиск при необходимости переинициализируется случайной конфигурацией. На каждом шаге изменяется по одному параметру.

Ключевая особенность ParamILS — определить при сравнении двух конфигураций, какая из них лучше. В простейшем варианте BasicILS статистическая мера эффективности каждой конфигурации сравнивается заданное число раз N. Такой подход даёт хорошие результаты на больших или гетерогенных выборках, так как даже небольшого («представительного») подмножества задач зачастую достаточно для поиска хорошей конфигурации при приемлемых вычислительных затратах, но выбор N — непростая задача: слишком малое значение ухудшит обобщаемость, слишком большое увеличит время поиска. В FocusedILS (вариант ParamILS) значение N определяется динамически для каждой конфигурации; применяется понятие доминирования, что обеспечивает дополнительное тестирование лучших решений.

В первой публикации о ParamILS приводятся эксперименты с: алгоритмом SAPS для SAT, алгоритмом локального поиска GLS+ для задачи поиска наиболее вероятного объяснения в байесовских сетях, а также SAT4J. Сравнивались стандартные конфигурации, настройки через CALIBRA и найденные ParamILS; в большинстве экспериментов FocusedILS показал преимущество над CALIBRA, а ParamILS — значительное улучшение относительно стандартных параметров.

ParamILS также успешно использовался для настройки параметров в системе оптимизации CPLEX для различных задач, включая целочисленное квадратичное программирование и оценку параметров в цепях РНК. Оба варианта ParamILS находили конфигурации, существенно превосходящие стандартные, иногда на несколько порядков. Метод встроен во фреймворк SATenstein для автоматической настройки параметров локальных стохастических поисковых алгоритмов для SAT-задач; в частности, FocusedILS позволял подобрать параметры лучше 11 известных алгоритмов в шести категориях SAT-задач.

SACO

Методы автоматического выбора конфигураций, разработанные для F-Race и ParamILS, положены в основу инструмента SACO, предложенного О. Вера в 2011 году. SACO решает задачу подбора параметров для как точных, так и стохастических алгоритмов на базе адаптивной метаэвристики Harmony Search. Отличие подхода — раздельная работа с непрерывными и дискретными параметрами: вещественные параметры не дискретизируются, что является преимуществом по сравнению с F-Race и ParamILS.

В SACO используется конечное и репрезентативное множество задач для инициализации популяции конфигураций Harmony Search, затем новые найденные во время работы решения также тестируются на этой выборке. В каждой итерации строится новая конфигурация, параметр за параметром, на основе текущей информации («импровизация» по аналогии с Harmony Search); каждый параметр либо выбирается из памяти, либо из заранее определённого диапазона. Если параметр берётся из памяти, его случайно изменяют. В каждой итерации найденная конфигурация может вытеснить худшую среди сохранённых, если она по определённому критерию доминирует над ней. Алгоритм заканчивает работу после заданного числа итераций, возвращая лучшую найденную конфигурацию.

SACO был успешно применён для настройки параметров алгоритмов компьютерного зрения, например в задачах сегментации изображений по текстурным областям и слежения за положением руки на видеопоследовательностях.

Другие методы

Метаоптимизация параметров генетических алгоритмов исследовалась Грефенштетте и Кином, а также в ряде экспериментов Бэка, где оптимизировались и параметры, и генетические операторы. Крус и Андерссон реализовали метаоптимизацию для алгоритма COMPLEX-RF и предложили индекс производительности, основанный на теории информации. Метаоптимизация для оптимизации роя частиц (PSO) была осуществлена Мейснером и др., а также Педерсеном и Чипперфилдом (также их работа связана с метаоптимизацией дифференциальной эволюции). В ряде исследований применялись статистические модели для изучения связи между выбором параметров и эффективностью оптимизации, например Франсуа и Лаверн, Наннен и Айбен. Смит и Айбен провели сравнительный анализ разных методов метаоптимизации.

Примечания

  1. ↑ R.E. MERCER, J.R. SAMPSON. ADAPTIVE SEARCH USING A REPRODUCTIVE META‐PLAN (англ.) // Kybernetes. — 1978-03-01. — Vol. 7, iss. 3. — P. 215–228. — ISSN 0368-492X. — doi:10.1108/eb005486.

Литература

  • Mercer R.E., Sampson J.R. Adaptive search using a reproductive metaplan // Kybernetes (The International Journal of Systems and Cybernetics). 1978. Vol. 7, № 3. С. 215—228. DOI: 10.1108/eb005486.
  • Coy S., Golden B. L., Runger G. C., Wasil E. A. Using Experimental Design to Find Effective Parameter Settings for Heuristics // Journal of Heuristics. 2000. № 7. С. 77-97.
  • Vera O. L. Una propuesta para la selección automática de configuraciones. 2011. С. 6.
  • Birattari M., Yuan Z., Balaprakash P., Stützle T. F-Race and iterated F-Race: An overview // Iridia — Technical Report Series. 2009. № 18.
  • Hutter F., Hoos H., Leyton-Brown K. ParamILS: An automatic algorithm configuration framework // Journal of Artificial Intelligence Research. 2009. № 36. С. 267—306.
  • KhudaBukhsh A., Xu L., Hoos H. H., Leyton-Brown K. SATenstein: Automatically building local search sat solvers from components // Proceedings of the Twenty-first International Joint Conference on Artificial Intelligence (IJCAI’09). 2009. С. 517—524.
  • Hutter F., Hoos H. H., Stützle T. Automatic algorithm configuration based on local search // Proceedings of the Twenty-second National Conference on Artificial Intelligence (AAAI’07). 2007. С. 1152—1157.
  • Grefenstette J.J. Optimization of control parameters for genetic algorithms // IEEE Transactions Systems, Man, and Cybernetics. 1986. Vol. 16, № 1. С. 122—128. DOI: 10.1109/TSMC.1986.289288.
  • Keane A.J. Genetic algorithm optimization in multi-peak problems: studies in convergence and robustness // Artificial Intelligence in Engineering. 1995. Vol. 9, № 2. С. 75-83. DOI: 10.1016/0954-1810(95)95751-Q.
  • Meissner M., Schmuker M., Schneider G. Optimized Particle Swarm Optimization (OPSO) and its application to artificial neural network training // BMC Bioinformatics. 2006. Vol. 7.
  • Pedersen M.E.H., Chipperfield A.J. Simplifying particle swarm optimization // Applied Soft Computing. 2010. Vol. 10, № 2. С. 618—628. DOI: 10.1016/j.asoc.2009.08.029. Дата обращения: 10 декабря 2012. Архивировано 24 января 2014 года.
  • Francois O., Lavergne C. Design of evolutionary algorithms — a statistical perspective // IEEE Transactions on Evolutionary Computation. 2001. Vol. 5, № 2. С. 129—148. DOI: 10.1109/4235.918434.
  • Birattari M., Stützle T., Paquete L., Varrentrapp K. A racing algorithm for configuring metaheuristics // Proceedings of the Genetic and Evolutionary Computation Conference (GECCO). 2002. С. 11-18.
  • Krus P.K., Andersson J. Optimizing optimization for design optimization // Proceedings of DETC’03 2003 ASME Design Engineering Technical Conferences and Computers and Information in Engineering Conference Chicago, Illinois, USA. 2003.
  • Smit S.K., Eiben A.E. Comparing parameter tuning methods for evolutionary algorithms // Proceedings of the IEEE Congress on Evolutionary Computation (CEC). 2009. С. 399—406.
  • Bäck T. Parallel optimization of evolutionary algorithms // Proceedings of the International Conference on Evolutionary Computation. 1994. С. 418—427.
  • Adenso-Díaz B., Laguna M. Fine-Tuning of Algorithms Using Fractional Experimental Designs and Local Search // Operations research. 2006. Vol. 54, № 1. С. 99-114.
  • Nannen V., Eiben A.E. A method for parameter calibration and relevance estimation in evolutionary algorithms // Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation (GECCO). 2006. С. 183—190.

Категории