Математические проблемы, которые остановят мир.

[evgeniyum]

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



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

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

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

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

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

Давайте сначала рассмотрим упрощенный пример, чтобы увидеть, что такое проблема с динамическим распределением ресурсов и почему ее так трудно решить.
Представьте, что вы готовите ужин для своей семьи из четырех человек. Вы выбираете говядину со специями, зная, что это является любимым блюдом семьи. Но как только вы начинаете готовить, ваша дочь объявляет, что она вегетарианка, ваш партнер сообщает, что он опаздывает, а ваш сын говорит, что он пригласил «несколько» друзей на ужин. Затем ваша собака убегает с кусочком говядины в то время, когда вы отчаянно пытаетесь понять - как вы собираетесь удовлетворить потребности всех этих очень требовательных и (весьма откровенно) недисциплинированных людей.

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

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

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

«Все примеры [динамического распределения ресурсов] должны иметь дело с изменяющимися входными данными и средами, которые очень динамичны. Их трудно оценить и предсказать, поскольку будущая нагрузка статистически не зависит от текущей нагрузки», - говорит Эйко Йонеки, ведущий исследователь группы систем, ориентированных на данные, в компьютерной лаборатории Кембриджского университета. «Одно изменение вызывает другое изменение и, если вы хотите контролировать систему с помощью точных решений, необходимо учитывать будущий статус системы».

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

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

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

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

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

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

Фирмы по доставке тоже решают проблемы динамического распределения ресурсов, чтобы ускорить поставки. Например, UPS разработала свою систему интегрированной оптимизации и навигации на дороге (Orion) для оптимизации маршрутов доставки с использованием передовых алгоритмов. Компания утверждает, что это решение позволило сэкономить 100 миллионов миль в год, но в других отчетах говорится о проблемах системы в сложных городских условиях.

Цепочки поставок - еще одна «проблема, которая никогда не исчезнет», говорит Пауэлл, из-за сложной природы современных продуктов. Например, если вы хотите изготовить стандартный смартфон, вам нужно скоординировать поставку сотни компонентов со всего мира, каждый из которых собран в определенном порядке на заводской площадке. «Сбои в цепочках поставок являются серьезной проблемой при попытке удовлетворить потребности общества», - добавляет он.

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

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

Это важный момент. Разнообразие проблем с динамическим распределением ресурсов означает, что необходима общеотраслевая стандартизация различных вычислительных методов, используемых для их решения. Пауэлл - один из тех, кто пытается объединить разрозненные сообщества, работающие над проблемами динамического распределения ресурсов. «Наш подход не заменяет никакой предыдущей работы», - говорит он. «Скорее, он объединяет всю эту работу и помогает определить возможности для взаимного обмена знаниями».

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

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

Благодаря глубокому обучению в последнее время программа AlphaGo от Google DeepMind победила чемпиона мира по го. Система начинала с того, что ничего не знала об игре в Го, а затем играла против себя, чтобы тренировать и оптимизировать свою производительность. Хотя игры являются важным доказательством концепции методов глубокого обучения, обучение игре в игры не является конечной целью таких методов.

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

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

Команда исследователей из стартапа по искусственному интеллекту Prowler.io, базирующегося в Кембридже в Великобритании, также использует свой собственный подход к машинному обучению для решения проблем динамического распределения ресурсов. Его алгоритмы стимулируют определенное поведение в системе. В реальных условиях это может быть эквивалентно введению «умных» пошлин для стимулирования водителей к использованию конкретных дорог, минимизации пробок и загрязнения.
Но в области машинного обучения предстоит еще много работы - говорит Йонеки.

«Использование обучения с подкреплением продвинет вперед проблемы динамического распределения ресурсов, но для построения модели обучения с подкреплением требуется много данных, и оно все еще находится на экспериментальной стадии, особенно в компьютерных системах, где приходится иметь дело с более сложными параметрами, чем с простыми игровые случаи», - говорит она. «Исследования по этой теме быстро продвигаются».

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

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

Оригинал