"Электронная амеба" находит приближенное решение задачи коммивояжера за линейное временя

Исследователи из Университета Хоккайдо и компании Amoeba Energy в Японии, вдохновленные эффективным кормовым поведением одноклеточной амебы, разработали аналоговый компьютер для поиска надежного и быстрого решения задачи коммивояжера-репрезентативной комбинаторной задачи оптимизации.

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

Этих препятствий можно избежать, используя недавно разработанную "электронную амебу", аналоговый компьютер, вдохновленный одноклеточным амебоидным организмом. Известно, что амеба максимально эффективно усваивает питательные вещества, деформируя свое тело. Показано, что для нахождения приближенного решения задачи коммивояжера (ТСП), т. е. при заданной карте определенного числа городов, задача состоит в том, чтобы найти кратчайший маршрут для посещения каждого города ровно один раз и возвращаемся в стартовый город. Это открытие вдохновило профессора Университета Хоккайдо сейю Касаи имитировать динамику амебы в электронном виде с помощью аналоговой схемы, как описано в журнале Scientific Reports. "Ядро амебы ищет решение в электронной среде, где значения сопротивления на пересечениях поперечин представляют собой ограничения и запросы TSP", - говорит Касаи. Используя поперечины, макет города можно легко изменить, обновив значения сопротивления без сложной предварительной обработки.

Принципиальная схема электронной амебы (слева: ядро амебы, справа: поперечина сопротивления). Кредит: Энергия Амебы

Кента Сайто, аспирант из лаборатории Касаи, собрал схему на макетной плате и сумел найти кратчайший маршрут для 4-го городского TSP. Он оценил производительность для задач большего размера, используя имитатор цепи. Тогда схема надежно нашла качественное решение со значительно меньшей длиной маршрута, чем средняя длина, полученная методом случайной выборки. Кроме того, требуется время, чтобы найти качественное юридическое решение росла только линейно по отношению к числу городов. Сравнивая время поиска с репрезентативным алгоритмом TSP "2-opt", электронная амеба становится все более выигрышной по мере увеличения числа городов. "Аналоговая схема хорошо воспроизводит уникальную и эффективную оптимизационную способность амебы, которую организм приобрел в результате естественного отбора", - говорит Касаи.

TSP solution-поисковая производительность электронной амебы в зависимости от количества городов, N. (слева) длина маршрута, полученная электронной амебой (красные точки), нормализовалась на среднюю длину, рассчитанную методом случайной выборки. (Справа) время поиска решения электронной амебы (красные точки) и 2-опт выполняется на обычном компьютере (белый круг), где вертикальная ось представляет собой приращение от результатов для 10-го города TSP. Кредит: Масаси Аоно

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

Источник: vk.com

Комментарии: