- 28,469
- 46
- 8 Ноя 2022
… и потребляет в миллиард раз меньше энергии.
<div class="articl-text-cover" style="position:relative;width:100%;max-width:800px;margin-left:auto;margin-right:auto;aspect-ratio:1200/676;margin-bottom:2rem;overflow:hidden">
<div itemprop="articleBody"> Исследователи разработали новый аналоговый вычислительный метод, который позволяет значительно быстрее находить решения для одного из самых сложных классов оптимизационных задач. По словам авторов, новый подход справляется с задачами, содержащими до 10 тысяч переменных, и при этом требует в миллиард раз меньше энергии по сравнению с существующими решениями.
Речь идёт о так называемых задачах квадратичной бинарной оптимизации без ограничений (Quadratic Unconstrained Binary Optimization, QUBO). Несмотря на сложное название, идея у них довольно простая. Нужно найти наилучшую комбинацию множества ответов «да» или «нет», чтобы минимизировать стоимость, потери энергии или другой показатель.
Подобные задачи встречаются гораздо чаще, чем кажется. Например, сервис заказа такси должен решить, какого водителя отправить к какому пассажиру, чтобы как можно больше людей добрались до места вовремя, а машины не простаивали без дела. При этом приходится учитывать тысячи факторов: расположение автомобилей, дорожную ситуацию, стоимость поездок, вероятность отмены заказа и многое другое.
Каждое такое решение можно представить в виде двоичной переменной. Если водитель получает конкретный заказ, соответствующая переменная принимает значение единицы, если нет — нуля. Затем все варианты объединяются в одно большое математическое выражение, а задача сводится к поиску комбинации, которая даёт минимальное значение функции.
Тот же принцип используется далеко за пределами транспортных сервисов. Задачи QUBO возникают при проектировании беспроводных сетей, финансовом моделировании, логистике, распределении ресурсов и поиске новых лекарств.
Одним из наиболее интересных направлений считается моделирование структуры белков. Белковая молекула должна свернуться в строго определённую трёхмерную форму, иначе она перестаёт выполнять свои функции. Каждое возможное изменение пространственной структуры можно представить как очередной выбор «да» или «нет», после чего задача снова превращается в QUBO.
Именно поэтому подобные методы активно используют в биоинформатике. Чем быстрее удаётся найти наиболее устойчивую структуру белка , тем проще исследовать механизмы заболеваний, связанных с неправильным сворачиванием белковых молекул, включая болезнь Альцгеймера.
Главная проблема заключается в количестве возможных комбинаций. Если вариантов выбора всего десять, число возможных решений уже превышает тысячу. При сотнях или тысячах переменных полный перебор становится практически невозможным даже для самых мощных суперкомпьютеров .
Поэтому вместо перебора исследователи используют специализированные методы оптимизации. Одним из самых известных считаются машины Изинга — вычислительные системы, вдохновлённые физикой магнитных материалов.
Они переводят математическую задачу на язык спинов электронов. Каждый двоичный выбор превращается в условный магнитный момент, который может находиться в одном из двух состояний. Затем система начинает искать конфигурацию с минимальной энергией , а найденное состояние соответствует решению исходной задачи.
Однако у такого подхода есть серьёзный недостаток. Машина может остановиться слишком рано, решив, что уже нашла лучший вариант, хотя на самом деле существует ещё более удачное решение.
Исследователи сравнивают это с путешественником, который ищет самую глубокую долину. Добравшись до первой достаточно глубокой впадины, он решает, что цель достигнута, ставит палатку и прекращает поиски. На самом деле где-то дальше находится гораздо более глубокая долина, но путешественник до неё уже не добирается.
В математике такая ситуация называется попаданием в локальный минимум. Решение получается рабочим, но не оптимальным. Например, сервис такси может успешно распределить пассажиров между водителями, однако существует другая схема, которая позволит обслужить больше клиентов, сократить время ожидания и увеличить доход водителей.
Чтобы избежать этой проблемы, команда профессора Кристиана Касселлы предложила новый метод, получивший название Analog Floquet Solver.
В его основе лежит теория Флоке, которая описывает поведение систем под действием периодических внешних воздействий. Вместо того чтобы позволить вычислительной системе постепенно успокоиться и остановиться в первом подходящем состоянии, исследователи постоянно добавляют небольшие периодические «толчки».
Эти воздействия не дают системе окончательно застрять в локальном минимуме. Она продолжает менять своё состояние, перескакивая через небольшие энергетические барьеры и исследуя новые варианты решения.
Возвращаясь к примеру с путешественником, можно представить, что кто-то время от времени слегка подталкивает его вперёд. Благодаря этому он выбирается из первой попавшейся долины и продолжает путь, пока не доберётся до самой глубокой.
Авторы сообщают, что такой подход позволил решить ряд задач, которые прежде оставались практически недоступными для аналоговых вычислительных систем. В испытаниях новый метод справился с задачами, в которых насчитывалось до 10 тысяч двоичных переменных.
Ещё более впечатляющим оказался расход энергии. По словам разработчиков, аналоговый решатель потреблял примерно на девять порядков меньше энергии, чем существующие цифровые методы, выполнявшие аналогичные вычисления.
Такой выигрыш объясняется самой природой аналоговых вычислений. Вместо выполнения огромного количества последовательных арифметических операций система использует физические процессы, которые естественным образом стремятся к наиболее устойчивому состоянию.
Исследователи считают, что новый подход может оказаться полезным в самых разных областях — от экономики и телекоммуникаций до разработки лекарств и инженерных расчётов. Многие подобные задачи сегодня приходится упрощать, поскольку поиск действительно оптимального решения занимает слишком много времени или требует слишком больших вычислительных ресурсов.
Разумеется, речь пока не идёт о готовой замене обычных компьютеров. Analog Floquet Solver представляет собой специализированный инструмент для решения задач конкретного типа. Однако именно такие задачи лежат в основе огромного количества современных инженерных, логистических и научных расчётов.
Если технология подтвердит свою эффективность за пределами лаборатории, она сможет заметно ускорить поиск решений там, где сегодня приходится выбирать между точностью результата и временем вычислений.
<div class="articl-text-cover" style="position:relative;width:100%;max-width:800px;margin-left:auto;margin-right:auto;aspect-ratio:1200/676;margin-bottom:2rem;overflow:hidden">
<div itemprop="articleBody"> Исследователи разработали новый аналоговый вычислительный метод, который позволяет значительно быстрее находить решения для одного из самых сложных классов оптимизационных задач. По словам авторов, новый подход справляется с задачами, содержащими до 10 тысяч переменных, и при этом требует в миллиард раз меньше энергии по сравнению с существующими решениями.
Речь идёт о так называемых задачах квадратичной бинарной оптимизации без ограничений (Quadratic Unconstrained Binary Optimization, QUBO). Несмотря на сложное название, идея у них довольно простая. Нужно найти наилучшую комбинацию множества ответов «да» или «нет», чтобы минимизировать стоимость, потери энергии или другой показатель.
Подобные задачи встречаются гораздо чаще, чем кажется. Например, сервис заказа такси должен решить, какого водителя отправить к какому пассажиру, чтобы как можно больше людей добрались до места вовремя, а машины не простаивали без дела. При этом приходится учитывать тысячи факторов: расположение автомобилей, дорожную ситуацию, стоимость поездок, вероятность отмены заказа и многое другое.
Каждое такое решение можно представить в виде двоичной переменной. Если водитель получает конкретный заказ, соответствующая переменная принимает значение единицы, если нет — нуля. Затем все варианты объединяются в одно большое математическое выражение, а задача сводится к поиску комбинации, которая даёт минимальное значение функции.
Тот же принцип используется далеко за пределами транспортных сервисов. Задачи QUBO возникают при проектировании беспроводных сетей, финансовом моделировании, логистике, распределении ресурсов и поиске новых лекарств.
Одним из наиболее интересных направлений считается моделирование структуры белков. Белковая молекула должна свернуться в строго определённую трёхмерную форму, иначе она перестаёт выполнять свои функции. Каждое возможное изменение пространственной структуры можно представить как очередной выбор «да» или «нет», после чего задача снова превращается в QUBO.
Именно поэтому подобные методы активно используют в биоинформатике. Чем быстрее удаётся найти наиболее устойчивую структуру белка , тем проще исследовать механизмы заболеваний, связанных с неправильным сворачиванием белковых молекул, включая болезнь Альцгеймера.
Главная проблема заключается в количестве возможных комбинаций. Если вариантов выбора всего десять, число возможных решений уже превышает тысячу. При сотнях или тысячах переменных полный перебор становится практически невозможным даже для самых мощных суперкомпьютеров .
Поэтому вместо перебора исследователи используют специализированные методы оптимизации. Одним из самых известных считаются машины Изинга — вычислительные системы, вдохновлённые физикой магнитных материалов.
Они переводят математическую задачу на язык спинов электронов. Каждый двоичный выбор превращается в условный магнитный момент, который может находиться в одном из двух состояний. Затем система начинает искать конфигурацию с минимальной энергией , а найденное состояние соответствует решению исходной задачи.
Однако у такого подхода есть серьёзный недостаток. Машина может остановиться слишком рано, решив, что уже нашла лучший вариант, хотя на самом деле существует ещё более удачное решение.
Исследователи сравнивают это с путешественником, который ищет самую глубокую долину. Добравшись до первой достаточно глубокой впадины, он решает, что цель достигнута, ставит палатку и прекращает поиски. На самом деле где-то дальше находится гораздо более глубокая долина, но путешественник до неё уже не добирается.
В математике такая ситуация называется попаданием в локальный минимум. Решение получается рабочим, но не оптимальным. Например, сервис такси может успешно распределить пассажиров между водителями, однако существует другая схема, которая позволит обслужить больше клиентов, сократить время ожидания и увеличить доход водителей.
Чтобы избежать этой проблемы, команда профессора Кристиана Касселлы предложила новый метод, получивший название Analog Floquet Solver.
В его основе лежит теория Флоке, которая описывает поведение систем под действием периодических внешних воздействий. Вместо того чтобы позволить вычислительной системе постепенно успокоиться и остановиться в первом подходящем состоянии, исследователи постоянно добавляют небольшие периодические «толчки».
Эти воздействия не дают системе окончательно застрять в локальном минимуме. Она продолжает менять своё состояние, перескакивая через небольшие энергетические барьеры и исследуя новые варианты решения.
Возвращаясь к примеру с путешественником, можно представить, что кто-то время от времени слегка подталкивает его вперёд. Благодаря этому он выбирается из первой попавшейся долины и продолжает путь, пока не доберётся до самой глубокой.
Авторы сообщают, что такой подход позволил решить ряд задач, которые прежде оставались практически недоступными для аналоговых вычислительных систем. В испытаниях новый метод справился с задачами, в которых насчитывалось до 10 тысяч двоичных переменных.
Ещё более впечатляющим оказался расход энергии. По словам разработчиков, аналоговый решатель потреблял примерно на девять порядков меньше энергии, чем существующие цифровые методы, выполнявшие аналогичные вычисления.
Такой выигрыш объясняется самой природой аналоговых вычислений. Вместо выполнения огромного количества последовательных арифметических операций система использует физические процессы, которые естественным образом стремятся к наиболее устойчивому состоянию.
Исследователи считают, что новый подход может оказаться полезным в самых разных областях — от экономики и телекоммуникаций до разработки лекарств и инженерных расчётов. Многие подобные задачи сегодня приходится упрощать, поскольку поиск действительно оптимального решения занимает слишком много времени или требует слишком больших вычислительных ресурсов.
Разумеется, речь пока не идёт о готовой замене обычных компьютеров. Analog Floquet Solver представляет собой специализированный инструмент для решения задач конкретного типа. Однако именно такие задачи лежат в основе огромного количества современных инженерных, логистических и научных расчётов.
Если технология подтвердит свою эффективность за пределами лаборатории, она сможет заметно ускорить поиск решений там, где сегодня приходится выбирать между точностью результата и временем вычислений.
- Источник новости
- www.securitylab.ru
