Онлайн-оптимизация

Не путать онлайн и офлайн .

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

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

Проблемы онлайн

Задача, иллюстрирующая концепции онлайн-алгоритмов, — это задача канадского путешественника . Цель этой проблемы — минимизировать стоимость достижения цели во взвешенном графе, где некоторые ребра ненадежны и могут быть удалены из графа. Однако то, что ребро было удалено ( не удалось становится известно только ), путешественнику тогда, когда он достигает одной из конечных точек ребра. Худший случай этой проблемы состоит в том, что все ненадежные ребра выходят из строя, и проблема сводится к обычной задаче о кратчайшем пути . Альтернативный анализ проблемы можно провести с помощью конкурентного анализа. В этом методе анализа автономный алгоритм заранее знает, какие ребра потерпят неудачу, и цель состоит в том, чтобы минимизировать соотношение между производительностью онлайн- и оффлайн-алгоритмов. Эта задача является PSPACE-полной .

которых предлагает более одного онлайн-алгоритма Существует множество формальных задач, решение :

• с k -сервером проблема
• Проблема с расписанием работы магазина
• Проблема с обновлением списка
• Бандитская проблема
• Проблема с секретарем
• Поиск игр
• Проблема с прокатом лыж.
• Задача линейного поиска
• Проблема выбора портфеля
• Онлайн сопоставление

См. также

• Онлайн-алгоритм
• Онлайн зеркальный спуск