Как ИИ ускоряет решение проблем в сложных сценариях?

Статья является переводом статьи MIT

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

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

Это программное обеспечение, называемое смешанным целочисленным линейным программирование ((MILP) решатель)), разбивает массивную оптимизационную задачу на более мелкие части и использует общие алгоритмы для поиска наилучшего решения. Однако на поиск решения у решателя могут уйти часы, а то и дни.

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

Исследователи из Массачусетского технологического института (MIT) и Высшей технической школы Цюриха (ETH) использовали машинное обучение, чтобы ускорить процесс.

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

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

Новая методика позволила ускорить работу MILP-решателей на 30-70 % без снижения точности. С помощью этого метода можно быстрее получить оптимальное решение или, для особо сложных задач, лучшее решение за приемлемое время.

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

"Иногда в такой области, как оптимизация, очень распространено мнение, что решения могут быть либо чисто машинными, либо чисто классическими. Я твердо убеждена, что мы хотим получить лучшее из обоих миров, и это действительно сильное воплощение гибридного подхода", - говорит старший автор работы Кэти Ву, доцент кафедры гражданского и экологического строительства (CEE) имени Гилберта У. Уинслоу, член Лаборатории систем информации и принятия решений (LIDS) и Института данных, систем и общества (IDSS).

Ву написала работу вместе с соавторами Сируи Ли, аспирантом IDSS, и Вэньбином Оуяном, аспирантом CEE, а также Максом Паулюсом, аспирантом ETH. Исследование будет представлено на конференции по нейронным системам обработки информации.

Сложности в решениях

Задачи MILP имеют экспоненциальное число потенциальных решений. Например, продавец-путешественник хочет найти кратчайший путь, чтобы посетить несколько городов, а затем вернуться в свой город. Если городов, которые можно посетить в любом порядке, много, то количество потенциальных решений может быть больше, чем количество атомов во Вселенной.

"Такие задачи называются NP-трудными, что означает, что очень маловероятно, что существует эффективный алгоритм для их решения. Когда проблема достаточно велика, мы можем надеяться только на достижение некоторой субоптимальной производительности", - объясняет Ву.

Решатель MILP использует целый ряд методов и практических приемов, которые позволяют получить разумные решения за приемлемое время.

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

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

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

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

Сокращение пространства решений

Она и ее коллеги разработали механизм фильтрации, который сокращает пространство поиска разделителя с более чем 130 000 потенциальных комбинаций до примерно 20 вариантов. Этот механизм фильтрации опирается на принцип убывающей предельной отдачи, который гласит, что наибольшую пользу принесет небольшой набор алгоритмов, а добавление дополнительных алгоритмов не принесет значительного улучшения.

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

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

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

Этот подход, основанный на данных, ускорил работу решателей MILP на 30-70% без какого-либо снижения точности. Более того, ускорение было одинаковым, когда они применяли его к более простому решателю с открытым исходным кодом и более мощному коммерческому решателю.

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

Это исследование частично поддержано компанией Mathworks, Национальным научным фондом (NSF), MIT Amazon Science Hub и Комитетом по поддержке исследований MIT.