Предоставлено Институтом автоматизации Китайской академии наук.

Кубиты | Публичный аккаунт QbitAI

Решение задачи стохастического планирования занимает всего 15 секунд, что в 1440 раз быстрее, чем традиционные методы!

Новое исследование Института автоматизации Китайской академии наук использовало GCN для достижения новых прорывов в таких проблемах. Статья была выбрана для ICML 2024, ведущей конференции по искусственному интеллекту.

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

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

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

Среди них двухэтапное стохастическое программирование (2SP) является эффективным методом моделирования таких проблем принятия решений и широко используется.

Это достижение Института автоматизации Китайской академии наук, модель HGCN2SP (HGCN расшифровывается как Hierarchical Graph Convolution Network), представляет собой именно комбинацию метода 2SP икартинаВ сочетании со сверточными сетями модель можно использовать для более эффективного решения таких задач.

Первым автором статьи является докторант института У Ян, автором-переписчиком — научный сотрудник Чжан Ифань.

Что такое двухэтапное стохастическое программирование?

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

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

Двухэтапное стохастическое планирование, как следует из названия, делит процесс на два этапа.

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

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

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

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

Например, предположим, что мы хотим выбрать около 10 мест-кандидатов для строительства складов, отвечающих потребностям 20 прилегающих территорий.

На первом этапе необходимо решить, какое из этих 10 мест-кандидатов следует выбрать;

На втором этапе необходимо определить отношения распределения между складом и регионом. На этом этапе количество переменных решения достигает 200 (то есть, распределяет ли склад i в регион j).

△Изображение создано DALL·E

Математически задача 2SP обычно выражается так:

Среди них Q(x,ξ) представляет собой задачу оптимизации второго этапа с учетом решения x первого этапа и сценария ξ, и ее форма имеет вид:

В реальном решении обычно выбираются N сцен для расчета соответствующего значения Q, аппроксимирующего ожидание.

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

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

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

Фактически, когда N равно 500, даже при использовании самого совершенного коммерческого решателя Gurobi для принятия оптимального решения потребуется не менее 6 часов.

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

На основе этого выведена конструктивная идея модели HGCN2SP – при сокращении количества сцен выборки получить максимально приближенные точные результаты.

Использование сверточных сетей на графах для решения задачи 2SP

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

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

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

Декодер, основанный на механизме внимания, используется для выбора сцен по порядку. Он позволяет не только находить репрезентативные сцены для упрощения задачи, но и улучшать выбор исходной базы при решении задачи симплекс-методом за счет оптимизации порядка следования. сцены Значительно сокращает время решения.

△Структура модели HGCN2SP

Команда также объединила обучение с подкреплением (RL) для всестороннего изучения качества принятия решений и времени решения для оптимизации параметров модели, что значительно повысило эффективность и качество решения проблем.

В приведенной выше задаче о местоположении склада, хотя HGCN2SP выбрал только 10 сценариев, разница между результатами его решения и решением, принятым решателем Gurobi за 6 часов, составила всего 1,7%, а время решения составило всего 15 секунд, что эквивалентно скорости Улучшение составляет 1440 раз, что полностью отражает эффективность данного метода.

Кроме того, в эксперименте по задаче проектирования сети (NDP) HGCN2SP достиг аналогичного эффекта принятия решений менее чем в два раза быстрее, чем существующие методы.

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

Предложение HGCN2SP предоставляет новую идею и инструмент для решения сложных проблем 2SP и имеет широкие перспективы применения.

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

Бумажный адрес:
https://openreview.net/forum?id=8onaVSFTEj