Хабрахабр

[Перевод] Чтобы разрешить труднейшие задачи по оптимизации, просто добавьте лазеры

Странное устройство, известное, как «оптическая машина Изинга», способно управлять воздушным трафиком и помогать NFL составлять график игр

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

И хотя инцидент с American Airlines произошёл не напрямую по вине алгоритма, итог мог бы быть схожим. К примеру, у всех крупных авиалиний работают сложные алгоритмы оптимизации графика, сопоставляющие пилотов и полёты. Большая часть современного мира не сможет нормально функционировать без этих алгоритмов: ежегодно 50 000 грузовых судов перевозят товары, вырабатывается 25 000 ТВт*ч электричества, а роутеры проводят через себя 1 Зеттабайт трафика. Такой отказ привёл бы к тому, что сотни тысяч людей оказались бы в затруднительном или очень неудобном положении, пока авиакомпания искала бы выход из ситуации.
Триумф алгоритмической науки и закона Мура состоит в том, что мы теперь можем подступиться ко множеству сложных задачи по оптимизации, включая такие области, как перевозки, логистика и составление расписаний. Однако организации часто работают с неоптимальными решениями из-за поджимающих сроков сдачи и недостатка доступных компьютерных ресурсов. Всё это работало бы куда как менее эффективно. Более того, ещё полно возможностей для улучшения используемых нами методов, помогающих решать большую часть задач оптимизации.

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

Группа учёных из Стэнфордского университета (куда входит и автор статьи) под руководством Йошихика Ямамото начала эти исследования семь лет назад. Один многообещающий подход – разработка оптических машин, предназначенных для оптимизации. Спустя годы работы появляется всё больше уверенности в том, что по меньшей мере одна из этих групп когда-нибудь сможет создать машину, которая могла бы помочь нам подступиться к некоторым из наиболее сложных задач оптимизации, решение которых требует современная промышленность. Теперь эту тему изучают несколько групп учёных, а также исследователи из лабораторий HP и NTT.

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

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

Её можно просчитать, просто рассмотрев все 12 путей. Для пяти городов задача решается просто. Однако если трудяга-продавец намеревается посетить 50 городов, тогда метод перебора, рассматривающий все возможные пути, окажется непосильным – этих путей будет больше, чем новемдесиллион, или 1060 — единичка и 60 нулей.

Но даже наилучшие из них могут заставить задуматься самый мощный компьютер. Возможные решения такой задачи могут дать нам алгоритмы, использующие различные пути обхода и разумные приближения. Для этого он использовал 310 мощных процессоров, работавших без остановки 9 месяцев. В недавнем примере Университет Ватерлоо из Канады пытался найти кратчайший путь между почти 50 000 городами США, попавшими в национальный реестр исторических мест, и доказать правильность своего решения.

Ещё одна сложная задача состоит в составлении расписания. Но к оптимизации относится гораздо больше задач, чем только задача коммивояжёра. Для решения этой задачи в 2017 году NFL воспользовалась кластером из 400 компьютеров. К примеру, Национальная футбольная лига в США должна ежегодно составлять расписание нескольких сотен игр, пытаясь при этом соответствовать тысячам правил, которые, например, запрещают командам играть больше трёх игр не на своём поле подряд.

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

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

В середине 1980-х Дэвид Тэнк, работавший тогда в лабораториях AT&T Bell, и Джон Хопфилд, работавший как в AT&T Bell, так и в Калтехе, предложили использовать аналоговые электронные схемы, представляющие нейросети, для решения таких задач оптимизации, как задача коммивояжёра. Исследователи много лет пытаются создать специальные машины для решения задач оптимизации. Затем в 1994 году Леонард Эдлман из Южнокалифорнийского университета, обнаружил, что в теории ДНК можно использовать для решения проблем подобного типа. Их работа породила десятилетия исследований этого направления. Однако эти попытки разработать радикально новые и эффективные подходы к решению задач оптимизации привели к практическим альтернативам обычных компьютеров и технологий, остающихся сегодня основными инструментами для решения таких задач. Его идея породила сходный шквал исследований.

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

Рассмотрим обычный магнитный брусок. Чтобы понять, как модель Изинга связана с оптимизацией, нужно начать с её использования в физике для понимания магнетизма. У электронов в атомах есть свойство под названием спин. Используя модель Изинга можно представить себе магнитный брусок, как трёхмерную решётку атомов, в которой каждый из атомов сам представляет собой магнитный брусок. Направление спинов определяет намагниченность материала. Спины валентных электронов – находящихся на внешних оболочках атома – направлены либо вверх, либо вниз. Если вниз, материал тоже намагничен – только с противоположной полярностью. Если все спины направлены вверх, материал намагничен. Если спины смешаны, материал не намагничен.

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

Параметры задачи были аппаратно заложены в установках в виде разветвляющихся отрезков оптического кабеля определённой длины. В наших экспериментах мы сначала сделали систему с четырьмя спинами, а затем – с 16 спинами. В 2016 году мы создали машину с обратной связью на основе ППВМ, способную решать задачи Изинга со 100 спинами. В этих экспериментах мы успешно обнаружили состояния минимальной энергии, и это дало нам мотивацию к развитию этого подхода. Сравнение скорости работы нашей установки со специализированными системами, включая аппарат "квантового отжига" из НАСА, дало нам уверенность в том, что ОПО-машины Изинга могут быть эффективными оптимизаторами.

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть